oj.uz

Submission #49598

# Submission time Handle Problem Language Result Execution time Memory
49598 2018-06-01T00:48:04 Z mra2322001 Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16712 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i<(n); i++)
#define f1(i, n) for(int i(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 2002;
typedef pair <int, int> pii;

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

ostream& operator << (ostream &os, pii yu){
    cout << yu.first << " " << yu.second;
}

istream& operator >> (istream &is, pii &yu){
    cin >> yu.first >> yu.second;
}

int f[N][N];
bool check(int mid){
    memset(f, -1, sizeof(f));
    f0(j, q + 1) f[0][j] = p;
    f1(i, n){
        f0(j, q + 1){
            if(j == 0){
                int k = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a; --k;
                /// k + 1 -> i
                if(f[k][j] > 0){
                    f[i][j] = f[k][j] - 1;
                }
            }
            else{
                int k = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a; --k;
                /// k + 1 -> i
                if(f[k][j] > 0){
                    f[i][j] = f[k][j] - 1;
                }
                k = lower_bound(a + 1, a + n + 1, a[i] - 2*mid + 1) - a; --k;
                f[i][j] = max(f[i][j], f[k][j - 1]);
            }
        }
    }
    return (f[n][q] >= 0);
}

int main(){
    ios_base::sync_with_stdio(0);
 
    cin >> n >> p >> q;
    f1(i, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    if(p + q >= n){
        cout << 1; return 0;
    }
    int l = 1, r = 1e9 + 2, ans = -1;
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
}

Compilation message

watching.cpp: In function 'std::ostream& operator<<(std::ostream&, pii)':
watching.cpp:14:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
watching.cpp: In function 'std::istream& operator>>(std::istream&, pii&)':
watching.cpp:18:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16120 KB Output is correct
2 Correct 2 ms 16120 KB Output is correct
3 Correct 54 ms 16220 KB Output is correct
4 Correct 2 ms 16220 KB Output is correct
5 Correct 2 ms 16220 KB Output is correct
6 Correct 2 ms 16220 KB Output is correct
7 Correct 59 ms 16476 KB Output is correct
8 Correct 112 ms 16540 KB Output is correct
9 Correct 83 ms 16548 KB Output is correct
10 Correct 66 ms 16548 KB Output is correct
11 Correct 53 ms 16628 KB Output is correct
12 Correct 47 ms 16628 KB Output is correct
13 Correct 54 ms 16628 KB Output is correct
14 Correct 45 ms 16628 KB Output is correct
15 Correct 42 ms 16628 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16668 KB Output is correct
2 Correct 2 ms 16668 KB Output is correct
3 Correct 3 ms 16668 KB Output is correct
4 Correct 3 ms 16668 KB Output is correct
5 Correct 2 ms 16668 KB Output is correct
6 Correct 3 ms 16668 KB Output is correct
7 Correct 107 ms 16692 KB Output is correct
8 Execution timed out 1076 ms 16712 KB Time limit exceeded
9 Halted 0 ms 0 KB -