Submission #558698

#	Time	Username	Problem	Language	Result	Execution time	Memory
558698		kwongweng	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	34 ms	6996 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
ll MOD1 = 998244353;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

ld pi = 3.141592653589793238;

void solve(){
    int n; cin >> n;
    vector<ll> a(n); FOR(i,0,n) cin >> a[i];
    vector<ll> pre(n), suf(n);
    ll mx = a[0];
    FOR(i,1,n){
        pre[i] = pre[i-1] + max((ll)0,mx+1-(a[i]+pre[i-1]));
        mx=max(mx+1,a[i]+pre[i]);
    }
    mx = a[n-1];
    ROF(i,n-2,0){
        suf[i] = suf[i+1] + max((ll)0, mx+1-(a[i]+suf[i+1]));
        mx=max(mx+1,a[i]+suf[i]);
    }
    //FOR(i,0,n){cout << pre[i] << " " << suf[i] << '\n';}
    ll mn = max(pre[0],suf[0]);
    FOR(i,1,n) mn=min(mn,max(pre[i],suf[i]));
    cout << mn << '\n';
    return;
}
 
int main() {
    cout << fixed << setprecision(8);
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message (stderr)

Main.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("Ofast")
      | 
Main.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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