oj.uz

답안 #1060318

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060318 2024-08-15T12:57:00 Z phong 구경하기 (JOI13_watching) C++17
100 / 100
 233 ms 16220 KB 
#include<bits/stdc++.h>

#define ll long long
const int nmax =  2e3+ 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, p, q;
int a[nmax];
int dp[nmax][nmax];
void ckmax(int &a, int b){
    a = max(a, b);
}
bool check(int mid){
    memset(dp, -1,sizeof dp);
    dp[0][0] = 0;
    for(int i = 0; i <= p; ++i){
        for(int j = 0; j <= q; ++j){
            if(dp[i][j] == n) return 1;
            if(dp[i][j] != -1 ){
                int x = dp[i][j] + 1;
                int it = upper_bound(a + x + 1, a + 1 + n, a[x] + mid - 1) - a - 1;
                ckmax(dp[i + 1][j], it);
                it = upper_bound(a + x + 1, a + 1 + n, a[x] + 2 * mid - 1) - a - 1;
                ckmax(dp[i][j + 1], it);
            }
        }
    }
    return 0;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> p >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    if(p + q >= n) cout << 1, exit(0);
    int l =1, r = 1e9, kq =-1;
    while(l <= r){
        int mid = r + l >> 1;
        if(check(mid)){
            kq = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << kq;
}
/*
a[mid] - a[x] > w


*/

Compilation message

watching.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~
watching.cpp: In function 'int main()':
watching.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = r + l >> 1;
      |                   ~~^~~

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15960 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 11 ms 16192 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 12 ms 16200 KB Output is correct
8 Correct 12 ms 16012 KB Output is correct
9 Correct 11 ms 15976 KB Output is correct
10 Correct 11 ms 15964 KB Output is correct
11 Correct 11 ms 15964 KB Output is correct
12 Correct 12 ms 15964 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 10 ms 15960 KB Output is correct
15 Correct 11 ms 15960 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16220 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 16220 KB Output is correct
8 Correct 43 ms 16196 KB Output is correct
9 Correct 48 ms 16216 KB Output is correct
10 Correct 63 ms 16192 KB Output is correct
11 Correct 29 ms 16216 KB Output is correct
12 Correct 233 ms 16220 KB Output is correct
13 Correct 13 ms 16216 KB Output is correct
14 Correct 12 ms 16220 KB Output is correct
15 Correct 13 ms 16216 KB Output is correct