Submission #382634

#	Time	Username	Problem	Language	Result	Execution time	Memory
382634		jainbot27	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	0 / 100	219 ms	364 KiB

Main

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

using ll = long long;

#define F0R(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ROF(i, a, b) for(int i=b-1; i>=a; i--)
#define siz(x) (int) x.size()

const int mxN = 2e5+10;

int n;
ll a[mxN];
//ll p[mxN], s[mxN];
ll ans = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i, 1, n+1)
        cin >> a[i];
    //FOR(i, 2, n+1){
    //    p[i] = p[i-1]+max(a[i-1]-a[i]+1, 0LL);
    //}
    //ROF(i, 1, n){
    //    s[i] = s[i+1]+max(a[i+1]-a[i]+1, 0LL);
    //}
    // we have some costs on the prefixs and the suffixs 
    // what to do for the middle element:
    // we care about 
    //FOR(i, 1, n+1){
    //    // set costs
    //    ll cur = p[i-1]+s[i+1];

    //}
    FOR(i, 1, n+1){
        priority_queue<ll> sufs, prefs;
        //cout << "I: " << i << endl;
        FOR(j, 2, i+1){
            prefs.push(max(a[j-1]-a[j]+1, 0LL));
            //cout << a[j-1]-a[j]+1 << endl;
        }
        //cout << "---\n";
        FOR(j, i, n){
            sufs.push(max(a[j+1]-a[j]+1, 0LL));
            //cout << a[j+1]-a[j]+1 << endl;
        }
        ll cur = 0;
        while(siz(sufs)&&siz(prefs)){
            cur += max(sufs.top(), prefs.top());
            sufs.pop(); prefs.pop();
        }
        while(siz(sufs)) cur += sufs.top(), sufs.pop();
        while(siz(prefs)) cur += prefs.top(), prefs.pop();
        ans = min(ans, cur);
    }
    cout << ans << "\n";

}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 60