Submission #1233291

#TimeUsernameProblemLanguageResultExecution timeMemory
1233291MuhammadSaram봉쇄 시간 (IOI23_closing)C++20
0 / 100
1096 ms22340 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second int max_score(int n, int x, int y, ll k,vector<int> U, vector<int> V, vector<int> W) { ll pre[n]={}; for (int i=1;i<n;i++) pre[i]=pre[i-1]+W[i-1]; ll dis[n][2],mn[n]; dis[0][0]=abs(pre[x]-pre[0]),dis[0][1]=abs(pre[y]-pre[0]); mn[0]=min(dis[0][0],dis[0][1]); for (int i=1;i<n;i++) dis[i][0]=abs(pre[x]-pre[i])+dis[i-1][0], dis[i][1]=abs(pre[y]-pre[i])+dis[i-1][1], mn[i]=mn[i-1]+min(abs(pre[x]-pre[i]),abs(pre[y]-pre[i])); set<pair<ll,int>> se; for (int i=x-1;i>=0;i--) se.insert({abs(pre[x]-pre[i]),i}); for (int i=y+1;i<n;i++) se.insert({abs(pre[y]-pre[i]),i}); vector<pair<ll,pair<int,int>>> v; v.push_back({0,{0,0}}); while (!se.empty()) { auto p=*se.begin();se.erase(p); auto x=v.back(); if (p.second>y) v.push_back({x.ff+p.ff,{x.ss.ff,x.ss.ss+1}}); else v.push_back({x.ff+p.ff,{x.ss.ff+1,x.ss.ss}}); } int ans=0; for (int i=x;i<n;i++) for (int j=y;j>=0;j--) { ll val=dis[i][0]-dis[x][0]+dis[y][1]-(j?dis[j-1][1]:0); if (i>j) val-=mn[min(y,i)]-(j||x?mn[max(j,x)-1]:0); if (val>k) continue; int a=max(0,x-j),b=max(0,i-y); int s=0,e=v.size(); while (s+1<e) { int mid=(s+e)/2; ll q=v[mid].ff,w=min(a,v[mid].ss.ff),r=min(b,v[mid].ss.ss); q-=dis[x][0]-(w<x?dis[x-w-1][0]:0)+dis[y+r][1]-dis[y][1]; if (val+q<=k) s=mid; else e=mid; } ans=max(ans,y-j+1+i-x+1+v[s].ss.ff-a+v[s].ss.ss-b); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...