Submission #987330

#	Time	Username	Problem	Language	Result	Execution time	Memory
987330		nikaa123	Watching (JOI13_watching)	C++14	100 / 100	175 ms	31836 KiB

watching

// #pragma GCC diagnostic warnign "-std=c++11"
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << "-" << x  << endl
 
typedef char chr;
typedef string str;
typedef long long ll;
typedef vector <int> vii;
typedef pair <int,int> pii;
 
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const double PI = 2 * acos(0.0);

const int N = 2e3 + 5;

int n,p,q,arr[N],ans;
int dp[N][N];

bool check(int w) {
    vector <int> s;
    s.push_back(-INF);
    for (int i = 1; i <= n; i++) {
        s.pb(arr[i]);
        int l1 = (lower_bound(all(s),arr[i]-w+1))-s.begin();
        int l2 = (lower_bound(all(s),arr[i]-2*w+1)-s.begin());
        for (int j = 0; j <= q; j++) {
            
            
            dp[i][j] = dp[l1-1][j]+1;
            
            
            if (j) dp[i][j] = min(dp[i][j],dp[l2-1][j-1]);
        }
    }
    for (int i = 0; i <= q; i++) {
        if (dp[n][i] <= p) return true;
    }
    return false;
}

inline void test_case () {     

    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sort(arr+1,arr+1+n);
    if (p+q >= n) {
        cout << 1 << endl;
        return;
    }
    int l = 1; int r = 2*1e9;
    while (l <= r) {
        int mid = (l+r)/2;
        dp[0][0] = 0;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;

}
 
signed main () {
 
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T = 1;
    // cin >> T;
    while(T--) {
        test_case();
    }
    
    return 0;
 
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50