Submission #602241

#TimeUsernameProblemLanguageResultExecution timeMemory
602241SamAndGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const int N = 200005; const ll INF = 1000000009000000009; int n; int a[N]; ll pl[N], pr[N]; ll ppl[N], spr[N]; ll hp[N], hs[N]; void solv() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) { if (a[i - 1] + pl[i - 1] < a[i]) { pl[i] = 0; } else { pl[i] = (a[i - 1] + pl[i - 1] + 1 - a[i]); } } for (int i = n; i >= 1; --i) { if (a[i + 1] + pr[i + 1] < a[i]) { pr[i] = 0; } else { pr[i] = (a[i + 1] + pr[i + 1] + 1 - a[i]); } } for (int i = 1; i <= n; ++i) { ppl[i] = ppl[i - 1] + pl[i]; } for (int i = n; i >= 1; --i) { spr[i] = spr[i + 1] + pr[i]; } for (int i = 1; i <= n; ++i) { hp[i] = hp[i - 1] + min(pl[i], pl[i - 1]); } for (int i = n; i >= 1; --i) { hs[i] = hs[i + 1] + min(pr[i], pr[i + 1]); } ll ans = INF; for (int i = 1; i <= n; ++i) { ll yans = ppl[i - 1] + spr[i + 1]; yans -= hp[i - 1]; yans -= hs[i + 1]; ll pp; if (a[i] > max(a[i - 1] + pl[i - 1], a[i + 1] + pr[i + 1])) pp = 0; else pp = max(a[i - 1] + pl[i - 1], a[i + 1] + pr[i + 1]) + 1 - a[i]; yans += pp; yans -= min(pl[i - 1], pp); yans -= min(pr[i + 1], pp); ans = min(ans, yans); } cout << ans << "\n"; } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solv(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...