oj.uz

Submission #13361

# Submission time Handle Problem Language Result Execution time Memory
13361 2015-02-13T17:03:59 Z gs14004 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16876 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,p,q,a[2005];
int nxt[2005], nxt2[2005];

int dp[2005][2005];

int f(int y, int z){
    if(y == p && z == q) return 0;
    if(~dp[y][z]) return dp[y][z];
    int ret = 0;
    if(y != p) ret = max(ret,nxt[f(y+1,z)]);
    if(z != q) ret = max(ret,nxt2[f(y,z+1)]);
    return dp[y][z] = ret;
}

bool trial(int x){
    for (int i=0; i<n; i++) {
        nxt[i] = (int)(lower_bound(a,a+n,a[i]+x) - a);
        nxt2[i] = (int)(lower_bound(a,a+n,a[i]+2*x) - a);
    }
    nxt[n] = nxt2[n] = n;
    memset(dp,-1,sizeof(dp));
    return f(0,0) >= n;
}

int main(){
    scanf("%d %d %d",&n,&p,&q);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    p = min(p,n);
    q = min(q,n);
    sort(a,a+n);
    int s = 0, e = 5e8;
    while (s != e) {
        int m = (s+e)/2;
        if(trial(m)) e = m;
        else s = m+1;
    }
    printf("%d",s);
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16812 KB Output is correct
2 Correct 48 ms 16812 KB Output is correct
3 Correct 53 ms 16812 KB Output is correct
4 Correct 49 ms 16812 KB Output is correct
5 Correct 49 ms 16812 KB Output is correct
6 Correct 54 ms 16812 KB Output is correct
7 Correct 52 ms 16812 KB Output is correct
8 Correct 54 ms 16812 KB Output is correct
9 Correct 48 ms 16812 KB Output is correct
10 Correct 50 ms 16812 KB Output is correct
11 Correct 53 ms 16812 KB Output is correct
12 Correct 50 ms 16812 KB Output is correct
13 Correct 49 ms 16812 KB Output is correct
14 Correct 53 ms 16812 KB Output is correct
15 Correct 49 ms 16812 KB Output is correct

Subtask #2
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16812 KB Output is correct
2 Correct 53 ms 16812 KB Output is correct
3 Correct 900 ms 16828 KB Output is correct
4 Correct 121 ms 16812 KB Output is correct
5 Correct 114 ms 16812 KB Output is correct
6 Execution timed out 1000 ms 16876 KB Program timed out
7 Halted 0 ms 0 KB -