Submission #285273

#	Time	Username	Problem	Language	Result	Execution time	Memory
285273		Fidisk	Watching (JOI13_watching)	C++14	50 / 100	1093 ms	8704 KiB

watching

#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 / 50
• Subtask 2: 0 / 50