Submission #388167

#	Time	Username	Problem	Language	Result	Execution time	Memory
388167		BartolM	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	33 ms	8492 KiB

Main

#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;

int n;
ll p[N], pref[N], suff[N];
ll br[N];

void solve() {
    br[0]=p[0]; pref[0]=0;
    for (int i=1; i<n; ++i) {
        br[i]=max(p[i]+pref[i-1], br[i-1]+1);
        pref[i]=max(pref[i-1], br[i]-p[i]);
    }
    br[n-1]=p[n-1]; suff[n-1]=0;
    for (int i=n-2; i>=0; --i) {
        br[i]=max(p[i]+suff[i+1], br[i+1]+1);
        suff[i]=max(suff[i+1], br[i]-p[i]);
    }
    ll sol=(ll)INF*INF;
    for (int i=0; i<n; ++i) sol=min(sol, max(pref[i], suff[i]));
    printf("%lld\n", sol);
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i) scanf("%lld", p+i);
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void load()':
Main.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:41:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     for (int i=0; i<n; ++i) scanf("%lld", p+i);
      |                             ~~~~~^~~~~~~~~~~~~

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