Submission #1022263

#TimeUsernameProblemLanguageResultExecution timeMemory
1022263AmirAli_H1Shortcut (IOI16_shortcut)C++17
23 / 100
2040 ms600 KiB
// In the name of Allah #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #include "shortcut.h" using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 300 + 4; const ll oo = 1e18 + 4; int n; ll w; ll l[maxn], d[maxn]; ll D[maxn], ans; ll get_dis(int i, int j) { if (i > j) swap(i, j); return D[j] - D[i]; } ll getD(int u, int v) { ll x = 0; if (get_dis(u, v) <= w) return oo; for (int i = 0; i < n; i++) { x = max(x, d[i]); for (int j = i + 1; j < n; j++) { x = max(x, min({get_dis(i, j), get_dis(i, u) + w + get_dis(v, j), get_dis(i, v) + w + get_dis(u, j)}) + d[i] + d[j]); } } return x; } ll find_shortcut(int nx, vector<int> lx, vector<int> dx, int wx) { n = nx; w = wx; for (int i = 0; i < n - 1; i++) l[i] = lx[i]; for (int i = 0; i < n; i++) d[i] = dx[i]; D[0] = 0; for (int i = 1; i < n; i++) D[i] = D[i - 1] + l[i - 1]; ll mx = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { mx = max(mx, get_dis(i, j) + d[i] + d[j]); } } ll ans = mx; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) ans = min(ans, getD(i, j)); } 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...