Submission #1277170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277170		trungcan	Watching (JOI13_watching)	C++17	100 / 100	144 ms	16144 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, INF = 1e9 + 7;
int n, X, Y, r, a[N], dp[N][N], ans;
bool check(int w){
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= X; ++j) dp[i][j] = INF;
    dp[0][0] = 0;
    int u = 1, v = 1;
    for (int i = 1; i <= n; ++i){
        while (a[i] - a[u] + 1 > w)
            ++u;
        while (a[i] - a[v] + 1 > (w << 1))
            ++v;
        for (int j = 0; j <= X; ++j){
            //cerr << j << "\n";
            if (j)
                dp[i][j] = min(dp[i][j], dp[u - 1][j - 1]);
            dp[i][j] = min(dp[i][j], dp[v - 1][j] + 1);
//            if (w == 3){
//                cout << "\t" << i << " " << j << "\t" << u - 1 << " " << j - 1 << " " << dp[u - 1][j - 1] << "\t" << v - 1 << " " << j << " " << dp[v - 1][j] + 1 << "\n";
//            }
        }
    }
//    if (w == 3)
//        for (int i = 0; i <= X; ++i) cout << i << "\t" << dp[n][i] << "\n";
    for (int i = 0; i <= X; ++i)
        if (dp[n][i] <= Y) return 1;
    return 0;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> X >> Y;
    X = min(X, n);
    for (int i = 1; i <= n; ++i) cin >> a[i], r = max(r, a[i]);
    sort(a + 1, a + n + 1);
    int l = 1;
    while (l <= r){
        int mid = l + ((r - l) >> 1);
        //cerr << l << " " << r << "\n";
        if (check(mid)){
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans;
}

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