Submission #1081898

#TimeUsernameProblemLanguageResultExecution timeMemory
1081898BoasClosing Time (IOI23_closing)C++17
9 / 100
1074 ms32188 KiB
#include "closing.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <typename T1, typename T2> using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define pb push_back #define loop(x, i) for (int i = 0; i < x; i++) #define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--) #define ALL(x) begin(x), end(x) typedef pair<int, int> ii; typedef signed i32; typedef vector<ii> vii; typedef vector<int> vi; typedef vector<i32> vi32; typedef vector<bool> vb; typedef vector<vi> vvi; typedef vector<vii> vvii; int sum(vi &pSum, int a, int b) { int l = min(a, b), r = max(a, b); return pSum[r + 1] - pSum[l]; } i32 max_score(i32 N, i32 X, i32 Y, int K, vi32 U, vi32 V, vi32 W) { vvii adj(N); loop(N - 1, i) { adj[U[i]].pb({V[i], W[i]}); adj[V[i]].pb({U[i], W[i]}); } vi xTime(N), yTime(N); auto dfs = [&](auto &&self, int i, int prev, vi &time) -> void { for (auto [j, w] : adj[i]) { if (j == prev) continue; time[j] = time[i] + w; self(self, j, i, time); } }; dfs(dfs, X, X, xTime); dfs(dfs, Y, Y, yTime); vi maxTime(N); loop(N, i) maxTime[i] = max(xTime[i], yTime[i]); vi pSumX = {0}, pSumY = {0}, pSumMax = {0}; loop(N, i) { pSumX.pb(pSumX.back() + xTime[i]); pSumY.pb(pSumY.back() + yTime[i]); pSumMax.pb(pSumMax.back() + maxTime[i]); } int res = 0; for (int lx = X; lx >= 0; lx--) { for (int rx = X; rx < N; rx++) { for (int ly = Y; ly >= 0; ly--) { for (int ry = Y; ry < N; ry++) { int sumX = 0, sumY = 0, sumBoth = 0; if (rx >= ly) { if (lx < ly) { sumX += sum(pSumX, lx, ly - 1); } if (rx < ry) { sumY += sum(pSumY, rx + 1, ry); } sumBoth += sum(pSumMax, ly, rx); } else { sumX += sum(pSumX, lx, rx); sumX += sum(pSumY, ly, ry); } int dis = sumX + sumY + sumBoth; if (dis <= K) { int cnt = (rx - lx + 1) + (ry - ly + 1); res = max(res, cnt); } } } } } /*for (int both = 0; both < N; both++) { int best = 0, bestDis = INT_MAX; for (int i = X; i <= Y; i++) { int dis = sumDis(X, i) + sumDis(i, Y); if (dis < bestDis) { best = i; bestDis = dis; } } }*/ return res; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...