oj.uz

Submission #283526

# Submission time Handle Problem Language Result Execution time Memory
283526 2020-08-25T22:56:32 Z zecookiez Watching (JOI13_watching) C++14
100 / 100
 797 ms 31992 KB 
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int len(const C&c){return int(c.size());}
const int MAXN = 2003;
int N, P, Q;
long long W, arr[MAXN], dp[MAXN][MAXN];
int helper(int pos, int left, long long loc){
    if(pos == N) return 0;
    //cout << pos << " " << left << " " << loc << endl;
    if(loc > arr[pos]) return helper(pos + 1, left, loc);
    if(dp[pos][left] != -1) return dp[pos][left];
    int ans = helper(pos + 1, left, arr[pos] + W + W) + 1;
    if(left > 0) ans = min(ans, helper(pos + 1, left - 1, arr[pos] + W));
    return dp[pos][left] = ans;
}
bool check(long long w){
    memset(dp, -1, sizeof(dp)); W = w;
    return helper(0, P, 0) <= Q;
}
int main(){
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("haybales.in", "r", stdin);
    //freopen("haybales.out", "w", stdout);
    // Bsearch on answer
    // Check:
    //     DP[i][j] = Minimum large cameras for first i and j small cameras
    cin >> N >> P >> Q;
    if(P + Q >= N){ // thanks JOI
        cout << "1\n"; return 0;
    }
    for(int i = 0; i < N; ++i) cin >> arr[i];
    sort(arr, arr + N);
    long long mid, left = -1, right = 1e9 + 1;
    while(right - left > 1){
        mid = left + (right - left) / 2LL;
        if(check(mid)) right = mid;
        else left = mid;
    }
    cout << right << '\n';
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 31744 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 134 ms 31792 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 130 ms 31796 KB Output is correct
8 Correct 131 ms 31744 KB Output is correct
9 Correct 138 ms 31800 KB Output is correct
10 Correct 137 ms 31736 KB Output is correct
11 Correct 131 ms 31792 KB Output is correct
12 Correct 137 ms 31744 KB Output is correct
13 Correct 135 ms 31744 KB Output is correct
14 Correct 135 ms 31744 KB Output is correct
15 Correct 136 ms 31868 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 31744 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 144 ms 31864 KB Output is correct
8 Correct 200 ms 31992 KB Output is correct
9 Correct 388 ms 31864 KB Output is correct
10 Correct 797 ms 31864 KB Output is correct
11 Correct 212 ms 31924 KB Output is correct
12 Correct 540 ms 31972 KB Output is correct
13 Correct 134 ms 31744 KB Output is correct
14 Correct 138 ms 31868 KB Output is correct
15 Correct 138 ms 31744 KB Output is correct