Submission #1233292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233292		MuhammadSaram	봉쇄 시간 (IOI23_closing)	C++20	35 / 100	1095 ms	22340 KiB

closing

#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+v[s].ss.ss);
		}
	
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17