oj.uz

답안 #35031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35031 2017-11-17T12:44:25 Z dqhungdl 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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