oj.uz

Submission #35031

# Submission time Handle Problem Language Result Execution time Memory
35031 2017-11-17T12:44:25 Z dqhungdl Watching (JOI13_watching) C++14
100 / 100
 519 ms 17724 KB 
#include <bits/stdc++.h>
using namespace std;

int n,P,Q,a[2005],f[2005][2005];

bool Check(int w)
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=P;j++)
            f[i][j]=1e9;
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int id1,id2;
        for(int j=1;j<=i;j++)
            if(a[i]-a[j]+1<=w)
            {
                id1=j;
                break;
            }
        for(int j=1;j<=i;j++)
            if(a[i]-a[j]+1<=2*w)
            {
                id2=j;
                break;
            }
        for(int j=1;j<=P;j++)
            f[i][j]=min(f[i][j],f[id1-1][j-1]);
        for(int j=0;j<=P;j++)
            f[i][j]=min(f[i][j],f[id2-1][j]+1);
    }
    for(int j=0;j<=P;j++)
        if(f[n][j]<=Q)
            return true;
    return false;
}

int main()
{
    cin>>n>>P>>Q;
    P=min(P,n);
    Q=min(Q,n);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int res,l=1,r=1e9;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(Check(mid)==true)
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<res;
}

Compilation message

watching.cpp: In function 'bool Check(int)':
watching.cpp:14:17: warning: 'id2' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int id1,id2;
                 ^
watching.cpp:14:13: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int id1,id2;
             ^
watching.cpp: In function 'int main()':
watching.cpp:58:14: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<res;
              ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17724 KB Output is correct
2 Correct 0 ms 17724 KB Output is correct
3 Correct 433 ms 17724 KB Output is correct
4 Correct 499 ms 17724 KB Output is correct
5 Correct 129 ms 17724 KB Output is correct
6 Correct 519 ms 17724 KB Output is correct
7 Correct 86 ms 17724 KB Output is correct
8 Correct 136 ms 17724 KB Output is correct
9 Correct 283 ms 17724 KB Output is correct
10 Correct 519 ms 17724 KB Output is correct
11 Correct 133 ms 17724 KB Output is correct
12 Correct 329 ms 17724 KB Output is correct
13 Correct 79 ms 17724 KB Output is correct
14 Correct 96 ms 17724 KB Output is correct
15 Correct 103 ms 17724 KB Output is correct