| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 840799 | 2023-08-31T17:18:05 Z | Lib | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KB |
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
long long pos[200003];
long long cost1[200003];
long long cost2[200003];
long long pfx1[200003];
long long pfx2[200003];
long long maxroll[200003]; //maxroll[i]=a <==> de "tra no" 1 khoang toi da =a, can rollback it nhat i vi tri tu loai 1 xuong loai 0
long long minupd[200003]; //minupt[i]=k <==> voi 1 budget<=i; upgrade duoc toi da k vi tri tu loai 1 len loai 2
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
int n=N;
int x=X;
int y=Y;
long long k=K;
for(int i=0;i<=n;i++){
adj.push_back(temp);
}
for(int i=0;i<n-1;i++){
cin>>U[i]>>V[i]>>W[i];
pos[i+1]=pos[i]+W[i];
}
for(int i=0;i<n;i++){
cost1[i]=min(abs(pos[i]-pos[x]),abs(pos[i]-pos[y]));
cost2[i]=max(abs(pos[i]-pos[x]),abs(pos[i]-pos[y]))-cost1[i];
pfx1[i+1]=pfx1[i]+cost1[i];
}
int initpos;
long long curmax=0;
for(int i=0;i<n;i++){
pfx2[i+1]=pfx2[i]+cost2[i];
cout<<pfx2[i+1]<<" ";
}
cout<<"\n";
for(int i=x+1;i<=y-1;i++){
if(cost1[i]>curmax){
curmax=cost1[i];
initpos=i;
}
}
maxroll[1]=curmax;
for(int i=2;i<y-x;i++){
for(int l=0;l<i;l++){
maxroll[i]=max(maxroll[i],pfx1[initpos+l+1]-pfx1[initpos-(i-l-1)]);
}
}
long long curmin=1000000000000000000;
for(int i=0;i<n;i++){
if(cost2[i]<curmin){
curmin=cost2[i];
initpos=i;
}
}
minupd[1]=curmin;
for(int i=2;i<=n;i++){
minupd[i]=1000000000000000000;
for(int l=0;l<i;l++){
if((l+initpos<n)&&((initpos-(i-l-1))>=0)){
minupd[i]=min(minupd[i],pfx2[initpos+l+1]-pfx2[initpos-(i-l-1)]);
//cout<<i<<" "<<initpos+l+1<<" "<<initpos-(i-l-1)+1<<" "<<pfx2[initpos+l+1]-pfx2[initpos-(i-l)+1]<<"\n";
}
}
}
long long tcost,rcost;
int ans;
int tans=2;
for(int i=0;i<=x;i++){
for(int l=y;l<n;l++){
tcost=pfx1[l+1]-pfx1[i];
rcost=abs(tcost-K);
ans=l-i+1;
// cout<<i<<" "<<l<<" "<<tcost<<"\n";
if(tcost>K){
for(int a=1;a<=y-x;a++){
if(rcost<=maxroll[a]){
ans-=a;
tans=max(tans,ans);
break;
}
}
}else if(tcost<K){
for(int a=n;a>=0;a--){
if(rcost>=minupd[a]){
ans+=a;
tans=max(tans,ans);
break;
}
}
}else{
tans=max(tans,ans);
}
}
}
return tans;
}