Submission #1161720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161720		Tyx2019	Real Mountains (CCO23_day1problem2)	C++20	0 / 25	0 ms	328 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define debug(x) if(1) cout << #x << " = " << x << endl;
using namespace std;
const int maxN = 5005;
const int INF = 1e18;
int A[maxN];
main(){
    int N;
    cin >> N;
    for(int i=0;i<N;i++) cin >> A[i];
    int mx = 0;
    for(int i=0;i<N;i++) mx = max(mx, A[i]);
    int s = INT_MAX;
    int e = 0;
    for(int i=0;i<N;i++){
        if(A[i] == mx){
            s = min(s, i);
            e = max(e, i);
        }
    }
    int B[N];
    for(int i=s;i<=e;i++) B[i] = mx;
    int cur = 0;
    for(int i=0;i<s;i++){
        cur = max(cur, A[i]);
        B[i] = cur;
    }
    cur = 0;
    
    for(int i=N-1;i>e;i--){
        cur = max(cur, A[i]);
        B[i] = cur;
    }
    //for(int i=0;i<N;i++) cout << B[i] << " ";
    //cout << '\n';
    int mxgg = 105;
    vector<int> guys[mxgg];
    for(int i=0;i<N;i++){
        for(int j=A[i];j<B[i];j++) guys[j].push_back(i);
    }
    int ans = 0;
    //debug("hi");
    for(int i=1;i<mxgg;i++){
        sort(guys[i].begin(), guys[i].end());
        int a = INF;
        int b = INF;
        int c = guys[i].size();
        if(c == 0) continue;
        for(int j=0;j<guys[i][0];j++) if(A[j] > i) a = min(a, A[j]);
        for(int j=guys[i][c-1];j<N;j++) if(A[j] > i) b = min(b, A[j]);
        ans += c * i;
        if(c == 1){
            ans += a + b;
        }
        else if(c >= 2){
            ans += a + b + min(a, b) + i;
            ans += 2 * i * (c - 2);
        }
    }
    cout << ans;
}

Compilation message (stderr)

Main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main(){
      | ^~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4