oj.uz

Submission #285274

# Submission time Handle Problem Language Result Execution time Memory
285274 2020-08-28T14:55:51 Z Fidisk Watching (JOI13_watching) C++14
100 / 100
 649 ms 8576 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-pos;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-pos;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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 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 1 ms 384 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #2
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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 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 123 ms 1152 KB Output is correct
9 Correct 131 ms 3908 KB Output is correct
10 Correct 44 ms 8576 KB Output is correct
11 Correct 77 ms 1024 KB Output is correct
12 Correct 649 ms 8184 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 512 KB Output is correct