Submission #711545

#TimeUsernameProblemLanguageResultExecution timeMemory
711545shoryu386Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define int long long main(){ int n; cin >> n; int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x]; int ans = INT_MAX; for (int k = 0; k < n; k++){ //try every point as the breaking point (max value) int left = k, right = k; int leftval = arr[k], rightval = arr[k]; int inc = 0; while (left != 0 || right != n-1){ if (left != 0 && arr[left-1] - leftval < arr[right+1] - rightval){ if (arr[left-1] < leftval){ leftval = arr[left-1]; left--; } else{ inc += arr[left-1] - leftval + 1; rightval += arr[left-1] - leftval + 1; leftval += arr[left-1] - leftval + 1; leftval -= 1; left--; } } else{ if (arr[right+1] < rightval){ rightval = arr[right+1]; right++; } else{ inc += arr[right+1] - rightval + 1; leftval += arr[right+1] - rightval + 1; rightval += arr[right+1] - rightval + 1; rightval -= 1; right++; } } } //cout << inc << ' '; ans = min(inc, ans); /* int increase[n]; memset(increase, 0, sizeof(increase)); int runningmax = -1; for (int x = 0; x <= k; x++){ if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1; if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x]; } int initkInc = increase[k]; runningmax = -1; for (int x = n-1; x >= k; x--){ if (arr[x] <= runningmax+1) increase[x] = runningmax - arr[x] + 1; if (arr[x]+increase[x] > runningmax) runningmax = arr[x]+increase[x]; } increase[k] = max(increase[k], initkInc); if (k != 0) increase[k] = max(increase[k-1], increase[k]); if (k != n-1) increase[k] = max(increase[k+1], increase[k]); int runsum = 0; int curHeight = 0; for (int x = 0; x < n; x++){ if (curHeight > increase[x]){ curHeight = increase[x]; } else if (curHeight < increase[x]){ runsum += increase[x] - curHeight, curHeight = increase[x]; } } cout << k << '\n'; for (int x = 0; x < n; x++) cout << arr[x] + increase[x] << ' '; cout << '\n'; cout << runsum << "\n\n"; ans = min(ans, runsum); * */ } cout << ans; //theory: can we always set max point as the k? no lol?? }

Compilation message (stderr)

Main.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...