oj.uz

Submission #56837

# Submission time Handle Problem Language Result Execution time Memory
56837 2018-07-12T19:54:59 Z SpeedOfMagic Watching (JOI13_watching) C++17
100 / 100
 391 ms 30332 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here

void run() {
    int n, p, q;
    read(n, p, q);

    int a[n];
    rep(i, 0, n)
        get a[i];
    sort(a, a + n);

    if (p + q >= n) {
        put 1;
        return;
    }

    int l = 0, r = inf;
    while (l + 1 < r) {
        int w = (l + r) / 2;

        int dp[n][p + 1];

        int pointerForP = 0, pointerForQ = 0;
        rep(i, 0, n) {
            while (a[i] - a[pointerForP] >= w)
                pointerForP++;
            while (a[i] - a[pointerForQ] >= 2 * w)
                pointerForQ++;

            //debug(w, i, pointerForP, pointerForQ);

            rep(j, 0, p + 1)
                if (j) {
                    if (pointerForP == 0)
                        dp[i][j] = 0;
                    else if (pointerForQ == 0)
                        dp[i][j] = min(dp[pointerForP - 1][j - 1], 1ll);
                    else
                        dp[i][j] = min(dp[pointerForP - 1][j - 1], dp[pointerForQ - 1][j] + 1);
                } else {
                    if (pointerForQ == 0)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = dp[pointerForQ - 1][j] + 1;
                }
        }

        int mn = inf;
        rep(i, 0, p + 1)
            mn = min(mn, dp[n - 1][i]);

        if (mn > q)
            l = w;
        else
            r = w;
    }

    put r;
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 3 ms 536 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 4 ms 624 KB Output is correct
12 Correct 3 ms 624 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 704 KB Output is correct
2 Correct 3 ms 704 KB Output is correct
3 Correct 2 ms 704 KB Output is correct
4 Correct 3 ms 704 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 3 ms 704 KB Output is correct
7 Correct 7 ms 764 KB Output is correct
8 Correct 24 ms 2556 KB Output is correct
9 Correct 144 ms 12460 KB Output is correct
10 Correct 391 ms 30332 KB Output is correct
11 Correct 17 ms 30332 KB Output is correct
12 Correct 165 ms 30332 KB Output is correct
13 Correct 5 ms 30332 KB Output is correct
14 Correct 7 ms 30332 KB Output is correct
15 Correct 7 ms 30332 KB Output is correct