Submission #1190332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190332		boclobanchat	Watching (JOI13_watching)	C++20	100 / 100	482 ms	16328 KiB

watching

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2024;
long long pos[MAXN];
int dp[MAXN][MAXN],nex[MAXN][2];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,p,q;
    cin>>n>>p>>q;
    p=min(p,n),q=min(q,n);
    for(int i=1;i<=n;i++) cin>>pos[i];
    sort(pos+1,pos+n+1);
    long long l=1,r=1e9,ans=0;
    while(l<=r)
    {
    	long long mid=(l+r)/2;
    	for(int i=1;i<=n;i++)
    	{
    		nex[i][0]=upper_bound(pos+1,pos+n+1,pos[i]+mid-1)-pos-1;
    		nex[i][1]=upper_bound(pos+1,pos+n+1,pos[i]+mid*2-1)-pos-1;
		}
		nex[n+1][0]=nex[n+1][1]=n;
    	for(int i=0;i<=p;i++) for(int j=0;j<=q;j++) if(i==0&&j==0) dp[i][j]=0;
    	else
    	{
    		dp[i][j]=0;
    		if(i>0) dp[i][j]=max(dp[i][j],nex[dp[i-1][j]+1][0]);
    		if(j>0) dp[i][j]=max(dp[i][j],nex[dp[i][j-1]+1][1]);
		}
		if(dp[p][q]==n) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50