Submission #947965

#	Time	Username	Problem	Language	Result	Execution time	Memory
947965		_callmelucian	Watching (JOI13_watching)	C++14	100 / 100	161 ms	16220 KiB

watching

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int a[2024], dp[2024][2024], prS[2024], prL[2024];
int n, S, L;

bool ok (int w) {
    int pS = 0, pL = 0;
    for (int i = 1; i <= n; i++) {
        while (pS + 1 <= n && a[i] - a[pS + 1] >= w) pS++;
        while (pL + 1 <= n && a[i] - a[pL + 1] >= 2 * w) pL++;
        prS[i] = pS, prL[i] = pL;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= L; j++) {
            dp[i][j] = dp[prS[i]][j] + 1;
            if (j) dp[i][j] = min(dp[i][j], dp[prL[i]][j - 1]);
        }
    }
    return dp[n][L] <= S;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> S >> L;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);

    if (n <= S + L) {
        cout << 1;
        return 0;
    }

    int ans = 0;
    for (int i = 29; i >= 0; i--) {
        int mask = ans | (1 << i);
        if (!ok(mask)) ans = mask;
    }
    cout << ans + 1;

    return 0;
}

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