oj.uz

Submission #49599

# Submission time Handle Problem Language Result Execution time Memory
49599 2018-06-01T00:51:13 Z mra2322001 Watching (JOI13_watching) C++14
100 / 100
 367 ms 16560 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], d1[N], d2[N];
bool check(int mid){
    memset(f, -1, sizeof(f));
    memset(d1, 0, sizeof(d1));
    memset(d2, 0, sizeof(d2));
    f1(i, n){
        int k = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a; --k;
        d1[i] = k;
        k = lower_bound(a + 1, a + n + 1, a[i] - 2*mid + 1) - a; --k;
        d2[i] = k;
    }
    f0(j, q + 1) f[0][j] = p;
    f1(i, n){
        f0(j, q + 1){
            if(j == 0){
                int k = d1[i];
                /// k + 1 -> i
                if(f[k][j] > 0){
                    f[i][j] = f[k][j] - 1;
                }
            }
            else{
                int k = d1[i];
                /// k + 1 -> i
                if(f[k][j] > 0){
                    f[i][j] = f[k][j] - 1;
                }
                k = d2[i];
                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 46 ms 15992 KB Output is correct
2 Correct 2 ms 15992 KB Output is correct
3 Correct 43 ms 16212 KB Output is correct
4 Correct 2 ms 16212 KB Output is correct
5 Correct 2 ms 16212 KB Output is correct
6 Correct 2 ms 16212 KB Output is correct
7 Correct 42 ms 16272 KB Output is correct
8 Correct 42 ms 16316 KB Output is correct
9 Correct 44 ms 16316 KB Output is correct
10 Correct 44 ms 16316 KB Output is correct
11 Correct 53 ms 16316 KB Output is correct
12 Correct 43 ms 16316 KB Output is correct
13 Correct 51 ms 16380 KB Output is correct
14 Correct 45 ms 16380 KB Output is correct
15 Correct 42 ms 16380 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16380 KB Output is correct
2 Correct 2 ms 16380 KB Output is correct
3 Correct 3 ms 16380 KB Output is correct
4 Correct 2 ms 16380 KB Output is correct
5 Correct 3 ms 16380 KB Output is correct
6 Correct 2 ms 16380 KB Output is correct
7 Correct 87 ms 16380 KB Output is correct
8 Correct 221 ms 16380 KB Output is correct
9 Correct 81 ms 16504 KB Output is correct
10 Correct 76 ms 16560 KB Output is correct
11 Correct 367 ms 16560 KB Output is correct
12 Correct 245 ms 16560 KB Output is correct
13 Correct 69 ms 16560 KB Output is correct
14 Correct 69 ms 16560 KB Output is correct
15 Correct 68 ms 16560 KB Output is correct