oj.uz

Submission #358300

# Submission time Handle Problem Language Result Execution time Memory
358300 2021-01-25T09:55:50 Z Vladth11 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16208 KB 
#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 dp[2001][2001];

bool OK(int w) {
    for(int i = 0; i < NMAX; i++) {
        for(int j = 0; j < NMAX; j++) {
            dp[i][j] = 0;
        }
    }
    for(int i = 0; i <= min(p, n); i++) {
        for(int j = 0; j <= min(q, n); j++) {
            if(i != 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                int unde = dp[i - 1][j];
                unde++;
                int r = 0, pas = (1 << 11);
                while(pas) {
                    if(r + pas <= n && v[r + pas] < v[unde] + w) {
                        r += pas;
                    }
                    pas /= 2;
                }
                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 = 0, pas = (1 << 11);
                while(pas) {
                    if(r + pas <= n && v[r + pas] < v[unde] + 2 * w) {
                        r += pas;
                    }
                    pas /= 2;
                }
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + (r - unde + 1));
            }
        }
    }
    return (dp[min(p,n)][min(q,n)] >= 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);
    int r = 0, pas = (1 << 30);
    while(pas) {
        if(!OK(r + pas))
            r += pas;
        pas /= 2;
    }
    cout << r + 1;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 15980 KB Output is correct
2 Correct 144 ms 15980 KB Output is correct
3 Correct 147 ms 16108 KB Output is correct
4 Correct 151 ms 16108 KB Output is correct
5 Correct 147 ms 16108 KB Output is correct
6 Correct 167 ms 16108 KB Output is correct
7 Correct 167 ms 15980 KB Output is correct
8 Correct 150 ms 15980 KB Output is correct
9 Correct 149 ms 15980 KB Output is correct
10 Correct 154 ms 16068 KB Output is correct
11 Correct 159 ms 16108 KB Output is correct
12 Correct 165 ms 15980 KB Output is correct
13 Correct 146 ms 16108 KB Output is correct
14 Correct 168 ms 16108 KB Output is correct
15 Correct 145 ms 15980 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 16208 KB Output is correct
2 Correct 165 ms 16108 KB Output is correct
3 Execution timed out 1087 ms 15980 KB Time limit exceeded
4 Halted 0 ms 0 KB -