#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |