제출 #1233282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233282		MuhammadSaram	Closing Time (IOI23_closing)	C++20	0 / 100	1097 ms	14148 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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<=0;i++)
		se.insert({abs(pre[y]-pre[i]),i});
	vector<vector<ll>> 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[0]+p.first,x[1],x[2]+1});
		else
			v.push_back({x[0]+p.first,x[1]+1,x[2]});	
	}
	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;
			ll 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][0],w=min(a,v[mid][1]),e=min(b,v[mid][2]);
				q-=dis[x][0]-(w<x?dis[x-w-1][0]:0)+dis[y+e][1]-dis[y][1];
				if (val+q<=k)
					s=mid;
				else
					e=mid;
			}
			ans=max((ll)ans,y-j+1+i-x+1+v[s][1]-a+v[s][2]-b);
		}
	
    return ans;
}

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