# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
90317 | 2018-12-21T08:37:32 Z | YottaByte | Mountain Trek Route (IZhO12_route) | C++14 | 2000 ms | 1516 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mk make_pair #define fr first #define sc second #define ok puts("OK") #define int long long const int N = 1e6 + 2; int n, k, a[N]; void fil(int l, int gap) { int cnt = 1; for(int i = l; cnt <= gap; i++, cnt++) { bool c = (i > n); a[i % (n + 1) + c]++; } } void check(int gap) { for(int i = 1; i <= n; i++) { bool f = true; int toi; for(int j = 0; j < gap; j++) { toi = (i + j); if(i + j > n) toi = toi % (n + 1) + 1; if(a[i] != a[toi]) { f = false; break; } } int ttoi = (toi + 1) % (n + 1) + ((toi + 1) > n); while(f && k >= gap && a[i - 1] > a[i] && a[toi] < a[ttoi]) { k -= gap; fil(i, gap); } } } main() { cin >> n >> k; for(int i = 1; i <= n; i++) { scanf("%I64d", &a[i]); } int diff = 0; a[0] = a[n]; a[n + 1] = a[1]; a[n + 2] = a[2]; for(int i = 1; i <= n; i++) { diff += abs(a[i] - a[i + 1]); } //cout << diff << endl; if(!diff) { cout << 0 << endl; return 0; } for(int i = 1; i <= n && i <= k; i++) { check(i); //puts("OK"); } //for(int i = 1; i <= n; i++) //cout << a[i] << " "; //puts(""); int diff1 = 0; for(int i = 1; i <= n; i++) { int toi = (i + 1) % (n + 1) + ((i + 1) > n); diff1 += abs(a[i] - a[toi]); } cout << diff - diff1 << endl; } /* 3 2 1 2 1 7 1000 4 3 3 2 3 2 1 4 5 4 3 2 1 5 4 1 2 4 4 5 5 4 5 4 4 2 1 5 1 1 3 2 3 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 508 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 1 ms | 560 KB | Output is correct |
7 | Correct | 18 ms | 560 KB | Output is correct |
8 | Correct | 155 ms | 592 KB | Output is correct |
9 | Correct | 1102 ms | 616 KB | Output is correct |
10 | Correct | 1276 ms | 1516 KB | Output is correct |
11 | Execution timed out | 2060 ms | 1516 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |