oj.uz

Submission #285273

# Submission time Handle Problem Language Result Execution time Memory
285273 2020-08-28T14:54:12 Z Fidisk Watching (JOI13_watching) C++14
50 / 100
 1000 ms 8704 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;

const ld pi=acos(-1);

int res,n,q,p,i,a[5009],f[2009][2009];

bool ok(int x) {
    for (int ii=0;ii<=p;ii++) {
        for (int ij=0;ij<=q;ij++) {
            f[ii][ij]=0;
        }
    }
    for (int ii=0;ii<=p;ii++) {
        for (int ij=0;ij<=q;ij++) {
            if (ii>0) {
                int tmp=f[ii-1][ij];
                int pos=tmp+1;
                for (int jj=n;jj>0;jj/=2) {
                    while ((pos+jj<=n)&&(a[pos+jj]<=a[tmp+1]+x-1)) {
                        pos+=jj;
                    }
                }
                f[ii][ij]=max(f[ii][ij],pos);
            }
            if (ij>0) {
                int tmp=f[ii][ij-1];
                int pos=tmp+1;
                for (int jj=n;jj>0;jj/=2) {
                    while ((pos+jj<=n)&&(a[pos+jj]<=a[tmp+1]+2*x-1)) {
                        pos+=jj;
                    }
                }
                f[ii][ij]=max(f[ii][ij],pos);
            }
        }
    }
    if (f[p][q]>=n) {
        return true;
    }
    else {
        return false;
    }
}

int main() {
    IO;
    cin>>n>>p>>q;
    for (i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    if (p+q>n) {
        cout<<1;
        return 0;
    }
    else {
        res=1e9;
        for (int i=1e9;i>0;i/=2) {
            while ((res-i>0)&&(ok(res-i))) {
                res-=i;
            }
        }
        cout<<res<<'\n';
    }
}

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 159 ms 1400 KB Output is correct
9 Correct 161 ms 3712 KB Output is correct
10 Correct 107 ms 8704 KB Output is correct
11 Correct 157 ms 1024 KB Output is correct
12 Execution timed out 1093 ms 8064 KB Time limit exceeded
13 Halted 0 ms 0 KB -