oj.uz

Submission #723731

# Submission time Handle Problem Language Result Execution time Memory
723731 2023-04-14T08:35:25 Z fdnfksd Watching (JOI13_watching) C++14
100 / 100
 231 ms 31788 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,q,dp[2002][2002],a[maxN],p;
ll check(ll mid)
{
    ll k=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=q;j++) dp[i][j]=inf;
    }
    dp[0][0]=0;
    ll e=1;
    for(int i=1;i<=n;i++)
    {
        while(k<=n&&a[i]-a[k]+1>2*mid) k++;
        while(e<=n&&a[i]-a[e]+1>mid) e++;
        for(int j=0;j<=min(1ll*i,q);j++)
        {
            dp[i][j]=dp[e-1][j]+1;
            if(j>0)
            {
                dp[i][j]=min(dp[i][j],dp[k-1][j-1]);
            }
        }
    }
    for(int i=0;i<=q;i++)
    {
        if(dp[n][i]<=p) return true;
    }
    return false;
}
void solve()
{
    cin >> n >> p >> q;
    q=min(q,n);
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1,a+n+1);
    ll low=1,high=1e9;
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(check(mid)) high=mid-1;
        else low=mid+1;
    }
    cout << low;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

watching.cpp: In function 'void solve()':
watching.cpp:51:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         ll mid=low+high>>1;
      |                ~~~^~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 1 ms 712 KB Output is correct
6 Correct 1 ms 708 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8404 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 203 ms 31700 KB Output is correct
4 Correct 18 ms 9556 KB Output is correct
5 Correct 231 ms 31700 KB Output is correct
6 Correct 208 ms 31788 KB Output is correct
7 Correct 7 ms 8532 KB Output is correct
8 Correct 117 ms 20160 KB Output is correct
9 Correct 21 ms 10340 KB Output is correct
10 Correct 18 ms 9696 KB Output is correct
11 Correct 220 ms 31700 KB Output is correct
12 Correct 151 ms 23720 KB Output is correct
13 Correct 7 ms 8660 KB Output is correct
14 Correct 7 ms 8608 KB Output is correct
15 Correct 8 ms 8660 KB Output is correct