Submission

Score: 100

User: porpeang

Problemset: ปริมาตรน้ำท่วม

Language: cpp

Time: 0.002 second

Submitted On: 2026-10-06 20:23:49

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    vector<int>vec(n);
    int mx=-1;
    int mx_idx=-1;
    for(int i=0;i<n;++i){
        cin>>vec[i];
        if(vec[i]>mx){
            mx=vec[i];
            mx_idx=i;
        }
    }
    int out=0;
    // left
    int sec,sec_idx;
    while(mx_idx!=0){
        sec=-1;
        sec_idx=-1;
        for(int i=mx_idx-1;i>=0;--i){
            if(vec[i]>sec){
                sec=vec[i];
                sec_idx=i;
            }
        }
        out+=(mx_idx-sec_idx-1)*vec[sec_idx];
        for(int i=mx_idx-1;i>sec_idx;--i){
            out-=vec[i];
        }
        mx=sec;
        mx_idx=sec_idx;
    }

    //right
    mx=-1;
    mx_idx=-1;
    for(int i=0;i<n;++i){
        if(vec[i]>mx){
            mx=vec[i];
            mx_idx=i;
        }
    }
    while(mx_idx!=n-1){
        sec=-1;
        sec_idx=-1;
        for(int i=mx_idx+1;i<n;++i){
            if(vec[i]>sec){
                sec=vec[i];
                sec_idx=i;
            }
        }
        out+=(sec_idx-mx_idx-1)*vec[sec_idx];
        for(int i=mx_idx+1;i<sec_idx;++i){
            out-=vec[i];
        }
        mx=sec;
        mx_idx=sec_idx;
    }

    cout<<out;
}