제출 #445016

#제출 시각아이디문제언어결과실행 시간메모리
445016wind_reaperGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms204 KiB
#include <bits/stdc++.h> /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> */ using namespace std; // using namespace __gnu_pbds; using namespace chrono; // mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); /* template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; */ //***************** CONSTANTS ***************** //***************** GLOBAL VARIABLES ***************** //***************** AUXILIARY STRUCTS ***************** //***************** MAIN BODY ***************** void solve(){ int N; cin >> N; int A[N + 2]; for(int i = 1; i <= N; i++) cin >> A[i]; A[0] = A[N + 1] = 0; int64_t pref[N + 2], suf[N + 2]; // pref[i] -> min number required to fill till ith index from the 1st index // suf[i] -> min number required to fill till ith index from the nth index pref[0] = 0; for(int i = 1; i <= N; i++) pref[i] = pref[i - 1] + max(0, A[i] - A[i - 1] + 1); suf[N + 1] = 0; for(int i = N; i >= 1; --i) suf[i] = suf[i + 1] + max(0, A[i + 1] - A[i] + 1); int64_t ans = 1'000'000'000'000'000'000; for(int i = 0; i <= N; i++) ans = min(ans, max(pref[i], suf[i + 1])); cout << ans << '\n'; } //***************** ***************** int32_t main(){ ios_base::sync_with_stdio(NULL); cin.tie(NULL); #ifdef LOCAL auto begin = high_resolution_clock::now(); #endif int tc = 1; // cin >> tc; for (int t = 0; t < tc; t++) solve(); #ifdef LOCAL auto end = high_resolution_clock::now(); cout << fixed << setprecision(4); cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl; #endif return 0; } /* If code gives a WA, check for the following : 1. I/O format 2. Are you clearing all global variables in between tests if multitests are a thing 3. Can you definitively prove the logic */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...