Submission #773546

#TimeUsernameProblemLanguageResultExecution timeMemory
773546JomnoiShortcut (IOI16_shortcut)C++17
38 / 100
2063 ms1492 KiB
#include <bits/stdc++.h> #include "shortcut.h" using namespace std; const int MAX_N = 3005; const long long INF = 1e18 + 7; int n; multiset <pair <int, int>> graph[MAX_N]; long long qsl[MAX_N]; long long preLeft[MAX_N], preRight[MAX_N]; long long dp1[MAX_N][MAX_N]; long long table1[MAX_N][20], table2[MAX_N][20]; long long get1(int l, int r) { if (l > r) return -INF; int j = log2(r - l + 1); return max(table1[l][j], table1[r - (1<<j) + 1][j]); } long long get2(int l, int r) { if (l > r) return -INF; int j = log2(r - l + 1); return max(table2[l][j], table2[r - (1<<j) + 1][j]); } long long find_shortcut(int n, vector <int> l, vector <int> d, int c) { ::n = n; for (int i = 1; i < n; i++) qsl[i] = qsl[i - 1] + l[i - 1]; for (int i = 0; i < n; i++) { table1[i][0] = -qsl[i] + d[i]; table2[i][0] = qsl[i] + d[i]; } for (int j = 1; j < 20; j++) { for (int i = 0; i < n; i++) { if (i + (1<<j) - 1 >= n) break; table1[i][j] = max(table1[i][j - 1], table1[i + (1<<(j - 1))][j - 1]); table2[i][j] = max(table2[i][j - 1], table2[i + (1<<(j - 1))][j - 1]); } } for (int i = 1; i < n; i++) preLeft[i] = max(preLeft[i - 1], get1(0, i - 1) + qsl[i] + d[i]); for (int i = n - 2; i >= 0; i--) preRight[i] = max(preRight[i + 1], get2(i + 1, n - 1) - qsl[i] + d[i]); // for (int i = 0; i <= n - 2; i++) { // for (int j = i + 1; j <= n - 1; j++) { // dp1[i][j] = qsl[j] - qsl[i] + d[i] + d[j]; // } // } // for (int s = 2; s < n; s++) { // for (int i = 0, j = s; j < n; i++, j++) { // dp1[i][j] = max({dp1[i][j], dp1[i + 1][j], dp1[i][j - 1]}); // } // } long long ans = INF; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long long maxleft = 0, maxright = 0; for (int k = i; k >= 0; k--) maxleft = max(maxleft, qsl[i] - qsl[k] + d[k]); for (int k = j; k < n; k++) maxright = max(maxright, qsl[k] - qsl[j] + d[k]); long long max_dist = maxleft + maxright + min(qsl[j] - qsl[i], 1ll * c); for (int k = i + 1; k <= j - 1; k++) { max_dist = max(max_dist, maxleft + min(qsl[k] - qsl[i], qsl[j] - qsl[k] + c) + d[k]); max_dist = max(max_dist, maxright + min(qsl[j] - qsl[k], qsl[k] - qsl[i] + c) + d[k]); } for (int k = i + 1, l = i + 1; k <= j - 1; k++) { while (l < j - 1 and qsl[l + 1] - qsl[k] <= qsl[k] - qsl[l + 1] + qsl[j] - qsl[i] + c) l++; // cout << i << ' ' << j << " : " << k << ' ' << l << endl; max_dist = max(max_dist, -qsl[k] + d[k] + get2(k + 1, l)); max_dist = max(max_dist, qsl[j] - qsl[i] + c + get1(l + 1, j - 1) + qsl[k] + d[k]); } // for (int k = i + 1; k <= j - 1; k++) { // for (int l = k + 1; l <= j - 1; l++) { // max_dist = max(max_dist, d[k] + d[l] + min(qsl[l] - qsl[k], // qsl[k] - qsl[i] + qsl[j] - qsl[l] + c)); // } // } // for (int k = 0; k <= i - 1; k++) { // for (int l = k + 1; l <= i; l++) max_dist = max(max_dist, qsl[l] - qsl[k] + d[k] + d[l]); // } // for (int k = j; k <= n - 2; k++) { // for (int l = k + 1; l <= n - 1; l++) max_dist = max(max_dist, qsl[l] - qsl[k] + d[k] + d[l]); // } // max_dist = max(max_dist, min(dp1[i + 1][j - 1], dp2[i + 1][j - 1] + qsl[j] - qsl[i])); max_dist = max(max_dist, max(preLeft[i], preRight[j])); // cout << i << ' ' << j << ' ' << max_dist << endl; ans = min(ans, max_dist); } } return ans; }
#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...