Submission #1022510

#TimeUsernameProblemLanguageResultExecution timeMemory
1022510RaresFelixShortcut (IOI16_shortcut)C++17
0 / 100
1 ms348 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vll = vector<ll>; const ll INF = 1e18; bool posib(int n, vll alpha, vll beta, vll s, ll l, ll c) { vll gamma(n, 0); for(int i = 0; i < n; ++i) gamma[i] = l - alpha[i]; vector<vll> DP1(n, vll(n, 0)); vector<vll> DP2(n, vll(n, 0)); vector<vll> DP3(n, vll(n, 0)); vector<vll> DP4(n, vll(n, 0)); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) { if(beta[j] > gamma[i]) { DP1[i][j] = alpha[i] + alpha[j]; DP2[i][j] = beta[j] + alpha[i]; DP3[i][j] = beta[i] + alpha[j]; DP4[i][j] = beta[i] + beta[j]; } } auto propag = [&](int i, int len) { int j = i + len; if(j >= n) return; if(j) { DP1[i][j] = max(DP1[i][j], DP1[i][j - 1]); DP3[i][j] = max(DP3[i][j], DP3[i][j - 1]); } if(i) { DP1[i][j] = max(DP1[i][j], DP1[i - 1][j]); DP2[i][j] = max(DP2[i][j], DP2[i - 1][j]); } if(i + 1 < n) { DP3[i][j] = max(DP3[i + 1][j], DP3[i][j]); DP4[i][j] = max(DP4[i + 1][j], DP4[i][j]); } if(j + 1 < n) { DP2[i][j] = max(DP2[i][j], DP2[i][j + 1]); DP4[i][j] = max(DP4[i][j], DP4[i][j + 1]); } }; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) propag(i, j); for(int i = 0; i < n; ++i) for(int j = n - 1; j >= 0; --j) propag(i, j); for(int i = n - 1; i >= 0; --i) for(int j = 0; j < n; ++j) propag(i, j); for(int i = n - 1; i >= 0; --i) for(int j = n - 1; j >= 0; --j) propag(i, j); for(int a = 0; a < n; ++a) for(int b = a; b < n; ++b) { bool ok = true; ok &= DP1[a][b] + s[a] + s[b] + c <= l; ok &= DP2[a][b] + s[a] - s[b] + c <= l; ok &= DP3[a][b] - s[a] + s[b] + c <= l; ok &= DP4[a][b] - s[a] - s[b] + c <= l; if(ok) return true; } return false; } ll find_shortcut(int n, vi l, vi d, int c) { vll s(n, 0), alpha(n, 0), beta(n, 0); for(int i = 1; i < n; ++i) { s[i] = s[i - 1] + l[i - 1]; } for(int i = 0; i < n; ++i) { alpha[i] = d[i] - s[i]; beta[i] = d[i] + s[i]; } ll st = 0, dr = INF, mij; while(st < dr) { mij = (st + dr) / 2; if(posib(n, alpha, beta, s, mij, c)) dr = mij; else st = mij + 1; } return st; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...