oj.uz

Submission #167365

# Submission time Handle Problem Language Result Execution time Memory
167365 2019-12-07T16:46:54 Z Hideo Watching (JOI13_watching) C++14
100 / 100
 246 ms 16248 KB 
// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 2007;
const int INF = 1e9 + 7;

int a[N], dp[N][N];
int n, p, q;

bool check (int w){
    memset(dp, 0, sizeof(dp));
    dp[0][0] = q;
    int l1 = 1, l2 = 1;
    for (int i = 1; i <= n; i++){
        while (a[i] - a[l1] + 1 > w)
            l1++;
        while (a[i] - a[l2] + 1 > 2 * w)
            l2++;
        for (int j = 0; j <= p; j++){
            dp[i][j] = dp[l2 - 1][j] - 1;
            if (j)
                dp[i][j] = max(dp[i][j], dp[l1 - 1][j - 1]);
        }
    }
    if (dp[n][p] >= 0)
        return true;
    return false;
}

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    if (p + q >= n){
        puts("1");
        return 0;
    }
    sort(a + 1, a + n + 1);
    int l = 0, r = INF;
    while (l + 1 < r){
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%d", r);
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message

watching.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
watching.cpp: In function 'int main()':
watching.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16120 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 43 ms 16120 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 42 ms 16124 KB Output is correct
8 Correct 44 ms 16120 KB Output is correct
9 Correct 44 ms 16120 KB Output is correct
10 Correct 41 ms 16092 KB Output is correct
11 Correct 43 ms 16120 KB Output is correct
12 Correct 44 ms 16120 KB Output is correct
13 Correct 48 ms 16128 KB Output is correct
14 Correct 43 ms 16120 KB Output is correct
15 Correct 46 ms 16120 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16128 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 51 ms 16120 KB Output is correct
8 Correct 59 ms 16144 KB Output is correct
9 Correct 137 ms 16120 KB Output is correct
10 Correct 246 ms 16244 KB Output is correct
11 Correct 64 ms 16120 KB Output is correct
12 Correct 171 ms 16248 KB Output is correct
13 Correct 50 ms 16120 KB Output is correct
14 Correct 52 ms 16120 KB Output is correct
15 Correct 52 ms 16124 KB Output is correct