Submission #895525

#	Time	Username	Problem	Language	Result	Execution time	Memory
895525		nbphong	Watching (JOI13_watching)	C++14	50 / 100	1048 ms	4188 KiB

watching

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a), _b =(b); i <= _b; i++)
#define FORD(i, a, b) for(int i = (a), _b =(b); i >= _b; i--)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> i) & 1)
#define popc(i) __builtin_popcountll(i)
#define fi first
#define se second
#define ALL(v) (v).begin(),(v).end()
#define pii pair<int, int>
using ll = long long;
using namespace std;
const int maxn = 2e3 + 10;
int n,p,q;
vector<vector<int>> dp;
long long a[maxn];
long long res(1);
bool check(long long w){
    FOR(i,0,p)
        FOR(j,0,q)
            dp[i][j] = 0;
    dp[0][0] = 1;
    FOR(i,0,p)
        FOR(j,0,q)
            if(dp[i][j] > 0){
                int pos = dp[i][j];
                if(i < p){
                    int tmp = upper_bound(&a[1],&a[n + 1],a[pos] + w - 1) - &a[0];
                    dp[i + 1][j] = max(dp[i + 1][j],tmp);
                }
                if(j < q){
                    int tmp = upper_bound(&a[1],&a[n + 1],a[pos] + 2LL*w - 1) - &a[0];
                    dp[i][j + 1] = max(dp[i][j + 1],tmp);
                }
            }
    FOR(i,0,p)
        FOR(j,0,q)
            if(dp[i][j] > n)
                return true;
    return false;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);
    #define task "events"
    //if(fopen(task".inp","r")){
    //    freopen(task".inp","r",stdin);
    //    freopen(task".out","w",stdout);
   // }
    cin >> n >> p >> q;
    FOR(i,1,n)
        cin >> a[i];
    if(n <= p + q)
        return cout << 1,0;
    dp.resize(p + 1,vector<int>(q + 1,0));
    sort(&a[1],&a[n + 1]);
    long long l = 1,r = a[n];
    while(l <= r){
        long long mid =(l + r) >> 1;
        if(check(mid)){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << res;
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50