Submission #358314

#	Time	Username	Problem	Language	Result	Execution time	Memory
358314		Vladth11	Watching (JOI13_watching)	C++14	100 / 100	258 ms	9384 KiB

watching

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 2001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 35;
 
int n, p, q, pp, qq;
int v[NMAX];
int next2w[NMAX];
int nextw[NMAX];
int dp[2001][2001];
 
bool OK(int w) {
    for(int i = 0; i <= p; i++) {
        for(int j = 0; j <= q; j++) {
            dp[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        int r = 0, pas = (1 << 11);
        while(pas) {
            if(r + pas <= n && v[r + pas] < v[i] + w) {
                r += pas;
            }
            pas /= 2;
        }
        nextw[i] = r;
        r = 0, pas = (1 << 11);
        while(pas) {
            if(r + pas <= n && v[r + pas] < v[i] + 2 * w) {
                r += pas;
            }
            pas /= 2;
        }
        next2w[i] = r;
    }
    for(int i = 0; i <= p; i++) {
        for(int j = 0; j <= q; j++) {
            if(i != 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                int unde = dp[i - 1][j];
                unde++;
                int r = nextw[unde];
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + (r - unde + 1));
            }
            if(j != 0) {
                int unde = dp[i][j - 1];
                dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                unde++;
                int r = next2w[unde];
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + (r - unde + 1));
            }
        }
    }
    return (dp[p][q] >= n);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> p >> q;
    pp = p;
    qq = q;
    v[0] = -2e9;
    for(i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    p = min(p, n);
    q = min(q, max(0, n - p));
    int r = 0, pas = (1 << 30);
    while(pas) {
        if(!OK(r + pas))
            r += pas;
        pas /= 2;
    }
    cout << r + 1;
    return 0;
}

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