Submission #1201339

#TimeUsernameProblemLanguageResultExecution timeMemory
1201339PagodePaiva봉쇄 시간 (IOI23_closing)C++20
0 / 100
32 ms5188 KiB
#include "closing.h" #include<bits/stdc++.h> using namespace std; const long long N = 3010; vector <pair <long long, long long>> g[N]; long long v[N]; long long custo[N]; long long pref[N], pref2[N]; int max_score(int n, int X, int Y, long long k, std::vector<int> U, std::vector<int> V, std::vector<int> W){ for(int i = 0;i < n;i++){ g[i].clear(); v[i] = 0; custo[i] = 0; pref[i] = pref2[i] = 0; } for(long long i = 0;i < n-1;i++){ g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); v[i] = W[i]; } for(int i = X-1;i >= 0;i--){ pref[i] = pref[i+1] + v[i]; } for(int i = X+1;i < N;i++){ pref[i] = pref[i-1] + v[i-1]; } for(int i = Y-1;i >= 0;i--){ pref2[i] = pref2[i+1] + v[i]; } for(int i = Y+1;i < N;i++){ pref2[i] = pref2[i-1] + v[i-1]; } int res = 0; for(int l = 0;l <= X;l++){ for(int r = X;r < n;r++){ //cout << l << ' ' << r << '\n'; long long gasto = 0; for(int j = l;j <= r;j++){ gasto += pref[j]; } if(gasto > k){ //cout << "1: "; //cout << gasto << '\n'; continue; } int ans = r-l+1; for(int i = 0;i < l-1;i++) custo[i] = pref2[i]; for(int i = l;i <= r;i++){ custo[i] = max(pref[i], pref2[i]) - pref[i]; } for(int i = r+1;i < n;i++){ custo[i] = pref2[i]; } int pl = Y; while(gasto <= k){ if(pl < 0) break; if(gasto+custo[pl] <= k){ gasto += custo[pl]; pl--; } else break; } pl++; res = max(res, ans + Y-pl+1); for(int i = Y+1;i < n;i++){ //cout << "2: " << pl << ' ' << i-1 << '\n'; res = max(res, ans + i-pl); gasto += custo[i]; while(gasto > k){ if(pl > Y) break; gasto -= custo[pl]; pl++; } if(pl > Y) break; } } } 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...