Submission #593815

#TimeUsernameProblemLanguageResultExecution timeMemory
593815Valaki2Shortcut (IOI16_shortcut)C++14
31 / 100
2077 ms2260 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define n N #define c C #define int long long const int inf = 1e16 + 42; int n, c; vector<int> v, nxt_dst; vector<vector<int> > dist; int ans; int solve_for(int a, int b) { int res = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { res = max(res, v[i] + v[j] + min({dist[i][j], dist[i][a] + c + dist[b][j], dist[i][b] + c + dist[a][j]})); } } // aa // // ab // // ac // // bb // // bc // // cc // //cout << a << " " << b << ": " << res << "\n"; return res; } int solve() { dist.assign(1 + n + 1, vector<int> (1 + n + 1, 0)); for(int i = 1; i <= n; i++) { int sum = 0; for(int j = i; j <= n; j++) { dist[i][j] = dist[j][i] = sum; sum += nxt_dst[j]; } } // ans = inf; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { ans = min(ans, solve_for(i, j)); } } return ans; } #undef n #undef c int find_shortcut(signed n, vector<signed> l, vector<signed> d, signed c) { N = n; C = c; v.assign(1 + N + 1, 0); nxt_dst.assign(1 + N + 1, 0); for(int i = 0; i < N; i++) { v[i + 1] = d[i]; if(i != N - 1) { nxt_dst[i + 1] = l[i]; } } return solve(); }
#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...