oj.uz

Submission #498975

# Submission time Handle Problem Language Result Execution time Memory
498975 2021-12-26T21:09:18 Z Karabasan Watching (JOI13_watching) C++17
100 / 100
 546 ms 31908 KB 
#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")

int n,m,ar[2005],p,q;
int dp[2005][2005];
bool check(int w)
{
	int lp=0,lq=0;
	memset(dp,0,sizeof(dp));
	for(ll i=1;i<=n;i++)
	{
		while(lp<n&&ar[lp+1]<=ar[i]-w)
			lp++;
		while(lq<n&&ar[lq+1]<=ar[i]-2*w)
			lq++;
		for(int j=0;j<=min(i,p);j++)
		{
			if(j==0)
			{
				dp[i][j]=dp[lq][0]+1;
				continue;
			}
			int t1=dp[lp][j-1];
			int t2=dp[lq][j]+1;

			dp[i][j]=min(t1,t2);
		}
	}
	for(int i=0;i<=min(n,p);i++)
    {
        if(dp[n][i]<=q)
            return true;
    }
    return false;
}
signed main()
{
	fast1;
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++)
		cin>>ar[i];
	sort(ar+1,ar+n+1);
	int bas=1;
	int son=1e14;
	while(bas<son)
    {
        int orta=(bas+son)/2;
        if(check(orta))
            son=orta;
        else bas=orta+1;
    }
    cout<<bas;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 31768 KB Output is correct
2 Correct 163 ms 31692 KB Output is correct
3 Correct 171 ms 31672 KB Output is correct
4 Correct 156 ms 31772 KB Output is correct
5 Correct 169 ms 31764 KB Output is correct
6 Correct 164 ms 31696 KB Output is correct
7 Correct 152 ms 31768 KB Output is correct
8 Correct 159 ms 31776 KB Output is correct
9 Correct 176 ms 31780 KB Output is correct
10 Correct 157 ms 31772 KB Output is correct
11 Correct 158 ms 31776 KB Output is correct
12 Correct 165 ms 31696 KB Output is correct
13 Correct 160 ms 31772 KB Output is correct
14 Correct 154 ms 31696 KB Output is correct
15 Correct 167 ms 31772 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 31904 KB Output is correct
2 Correct 155 ms 31764 KB Output is correct
3 Correct 477 ms 31800 KB Output is correct
4 Correct 483 ms 31908 KB Output is correct
5 Correct 190 ms 31824 KB Output is correct
6 Correct 546 ms 31800 KB Output is correct
7 Correct 166 ms 31800 KB Output is correct
8 Correct 211 ms 31800 KB Output is correct
9 Correct 368 ms 31800 KB Output is correct
10 Correct 489 ms 31820 KB Output is correct
11 Correct 198 ms 31720 KB Output is correct
12 Correct 465 ms 31696 KB Output is correct
13 Correct 165 ms 31824 KB Output is correct
14 Correct 180 ms 31792 KB Output is correct
15 Correct 180 ms 31824 KB Output is correct