oj.uz

답안 #51459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51459 2018-06-18T03:16:00 Z vivukhue 구경하기 (JOI13_watching) C++14
100 / 100
 126 ms 16380 KB 
#include <bits/stdc++.h>
#define fw(i,l,r) for (int i=l;i<r;i++)

using namespace std;
int n,p,q;
int a[2001];
int fars[2001];
int farl[2001];
int dp[2001][2001];

bool check(int w)
{
    for(int i=0;i<n;i++)
    {
        fars[i] = upper_bound(a,a+n,a[i]+w-1) - a;
        farl[i] = upper_bound(a,a+n,a[i]+2*w-1) - a;
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    for(int i=0;i<=p;i++)
    {
        for(int j=0;j<=q;j++)
        {
            if(dp[i][j]!=-1)
            {
                if(dp[i][j]==n)
                    return true;
                dp[i+1][j] = max(dp[i+1][j],fars[dp[i][j]]);
                dp[i][j+1] = max(dp[i][j+1],farl[dp[i][j]]);
            }
        }
    }

    return false;
}

signed main()
{
    cin>>n>>p>>q;
    for(int i=0;i<n;i++)
        cin>>a[i];

    if(p+q>=n)
    {
        cout<<1;
        return 0;
    }

    sort(a,a+n);
    //for(int i=0;i<n;i++)
        //cout<<a[i]<<" ";

    int L=1,R=1e9;
    while(L!=R)
    {
        int mid = (L+R)/2;
        if(check(mid))
            R = mid;
        else
            L = mid+1;
    }

    cout<<L;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 15992 KB Output is correct
2 Correct 3 ms 15992 KB Output is correct
3 Correct 51 ms 16216 KB Output is correct
4 Correct 2 ms 16216 KB Output is correct
5 Correct 2 ms 16216 KB Output is correct
6 Correct 2 ms 16216 KB Output is correct
7 Correct 46 ms 16216 KB Output is correct
8 Correct 43 ms 16216 KB Output is correct
9 Correct 40 ms 16244 KB Output is correct
10 Correct 50 ms 16244 KB Output is correct
11 Correct 54 ms 16244 KB Output is correct
12 Correct 42 ms 16244 KB Output is correct
13 Correct 82 ms 16256 KB Output is correct
14 Correct 54 ms 16256 KB Output is correct
15 Correct 47 ms 16256 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 16256 KB Output is correct
2 Correct 2 ms 16256 KB Output is correct
3 Correct 3 ms 16256 KB Output is correct
4 Correct 3 ms 16256 KB Output is correct
5 Correct 3 ms 16256 KB Output is correct
6 Correct 4 ms 16256 KB Output is correct
7 Correct 48 ms 16256 KB Output is correct
8 Correct 76 ms 16380 KB Output is correct
9 Correct 63 ms 16380 KB Output is correct
10 Correct 115 ms 16380 KB Output is correct
11 Correct 53 ms 16380 KB Output is correct
12 Correct 126 ms 16380 KB Output is correct
13 Correct 48 ms 16380 KB Output is correct
14 Correct 50 ms 16380 KB Output is correct
15 Correct 52 ms 16380 KB Output is correct