oj.uz

Submission #170668

# Submission time Handle Problem Language Result Execution time Memory
170668 2019-12-26T02:52:31 Z mdn2002 Watching (JOI13_watching) C++14
100 / 100
 938 ms 33656 KB 
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,a,b,sum,c[2003],dp[2050][2050];
long long f(int x,int y,long long z)
{
    if(y>a)return 1e6;
    if(x==n)return 0;
    if(dp[x][y]!=-1)return dp[x][y];
    long long mx=1e6,go1=x,go2=x;
    for(int i=x;i<n;i++)
    {
        if(c[i]-c[x]+1>z)break;
        go1=i;
    }
    for(int i=x;i<n;i++)
    {
        if(c[i]-c[x]+1>z*2)break;
        go2=i;
    }
    mx=min(mx,f(go1+1,y+1,z));
    mx=min(mx,f(go2+1,y,z)+1);
    return dp[x][y]=mx;
}
bool ck(long long x)
{
    memset(dp,-1,sizeof dp);
    if(f(0,0,x)<=b)return 1;
    else return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>a>>b;
    for(int i=0;i<n;i++)cin>>c[i];
    long long l=1,r=1e9+1,mid;
    sort(c,c+n);
    while(l<r)
    {
        mid=(l+r)/2;
        if(ck(mid))r=mid;
        else l=mid+1;
    }
    cout<<r;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 33272 KB Output is correct
2 Correct 175 ms 33276 KB Output is correct
3 Correct 166 ms 33280 KB Output is correct
4 Correct 170 ms 33400 KB Output is correct
5 Correct 181 ms 33320 KB Output is correct
6 Correct 175 ms 33288 KB Output is correct
7 Correct 166 ms 33400 KB Output is correct
8 Correct 149 ms 33288 KB Output is correct
9 Correct 175 ms 33272 KB Output is correct
10 Correct 280 ms 33164 KB Output is correct
11 Correct 145 ms 33272 KB Output is correct
12 Correct 284 ms 33392 KB Output is correct
13 Correct 273 ms 33272 KB Output is correct
14 Correct 206 ms 33400 KB Output is correct
15 Correct 160 ms 33400 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 33352 KB Output is correct
2 Correct 176 ms 33280 KB Output is correct
3 Correct 887 ms 33540 KB Output is correct
4 Correct 899 ms 33528 KB Output is correct
5 Correct 259 ms 33540 KB Output is correct
6 Correct 938 ms 33444 KB Output is correct
7 Correct 188 ms 33272 KB Output is correct
8 Correct 245 ms 33272 KB Output is correct
9 Correct 452 ms 33380 KB Output is correct
10 Correct 931 ms 33528 KB Output is correct
11 Correct 262 ms 33400 KB Output is correct
12 Correct 789 ms 33656 KB Output is correct
13 Correct 276 ms 33400 KB Output is correct
14 Correct 142 ms 33528 KB Output is correct
15 Correct 218 ms 33272 KB Output is correct