oj.uz

답안 #283526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283526 2020-08-25T22:56:32 Z zecookiez 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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