Submission #1060318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060318		phong	Watching (JOI13_watching)	C++17	100 / 100	233 ms	16220 KiB

watching

#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 (stderr)

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 / 50
• Subtask 2: 50 / 50