Submission #1121710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121710		E_rK	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	28 ms	10264 KiB

Main

#include <bits/stdc++.h>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define sp " "
#define endl "\n"
#define mod 1000000007
#define MAXN 200005
#define MAXM 1000005
#define INF 0x3f
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) for(auto& a: x) cout << a << " "
 
using namespace std;
typedef long long int lo;
const lo inf = 1000000000000000000;

lo arr[MAXN],dad[MAXN],sz[MAXN];
lo n,m,k;
vector<pair<lo,lo>> v[505];
string s;

void solve() {
    cin >> n;
    lo mx=0, mxind=0;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
        if(mx <= arr[i]){
            mxind = i;
            mx = arr[i];
        }
    }
    vector<lo> duz(n+1,0);
    vector<lo> preduz(n+1,0);

    vector<lo> ters(n+1,0);
    vector<lo> preters(n+1,0);
    for (int i = 1; i < n; ++i)
    {
        duz[i] = max(arr[i-1]-arr[i]+1,0ll)+duz[i-1];
        preduz[i] = max(preduz[i-1],duz[i]);
    }
    reverse(arr,arr+n);
    for (int i = 1; i < n; ++i)
    {
        ters[i] = max(arr[i-1]-arr[i]+1,0ll)+ters[i-1];
        preters[i] = max(preters[i-1],ters[i]);
    }
    // reverse(all(preters));
    // debug(preduz);
    // cout << endl;
    // debug(preters);
    // cout << endl;
    lo ans = inf;
    for (int i = 0; i < n; ++i)
    {
        // cout << preters[n-i-1] << sp;
        // cout << ans << endl;
        ans = min(ans,max(preters[n-i-1],preduz[i]));
    }

    cout << ans << endl;
    
}
int main()
{
    // cout << fixed << setprecision(12);
    // freopen("snowboots.in","r",stdin);
    // freopen("snowboots.out","w",stdout);
    fast;
    int t = 1;
 
    // cin >> t;
    while(t--)      
    {
        solve();
    }

    // cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:28:14: warning: variable 'mxind' set but not used [-Wunused-but-set-variable]
   28 |     lo mx=0, mxind=0;
      |              ^~~~~

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