oj.uz

Submission #167364

# Submission time Handle Problem Language Result Execution time Memory
167364 2019-12-07T16:44:11 Z Hideo Watching (JOI13_watching) C++14
50 / 100
 542 ms 32504 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]);
    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 45 ms 16120 KB Output is correct
3 Correct 43 ms 16120 KB Output is correct
4 Correct 542 ms 16116 KB Output is correct
5 Correct 43 ms 16120 KB Output is correct
6 Correct 539 ms 16248 KB Output is correct
7 Correct 43 ms 16120 KB Output is correct
8 Correct 43 ms 16248 KB Output is correct
9 Correct 42 ms 16120 KB Output is correct
10 Correct 44 ms 16120 KB Output is correct
11 Correct 43 ms 16120 KB Output is correct
12 Correct 49 ms 16120 KB Output is correct
13 Correct 44 ms 16236 KB Output is correct
14 Correct 44 ms 16120 KB Output is correct
15 Correct 43 ms 16120 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16120 KB Output is correct
2 Correct 43 ms 16120 KB Output is correct
3 Correct 187 ms 16180 KB Output is correct
4 Runtime error 331 ms 32504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -