Submission #644876

#	Time	Username	Problem	Language	Result	Execution time	Memory
644876		alextodoran	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	17 ms	1360 KiB

prison

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500;

int N, K, T;
int start[N_MAX + 2];

int spread[N_MAX + 2];
vector <int> endSpread[N_MAX + 2];
int maxTrigger[N_MAX + 2];

//ll segMin[N_MAX * 4 + 2];
//int segMinID[N_MAX * 4 + 2];
//ll segLazy[N_MAX * 4 + 2];
//
//void build (int node, int l, int r) {
//    segMin[node] = 0;
//    segMinID[node] = l;
//    segLazy[node] = 0;
//    if (l == r) {
//        return;
//    }
//    int mid = (l + r) / 2;
//    int left = node * 2, right = node * 2 + 1;
//    build(left, l, mid);
//    build(right, mid + 1, r);
//}
//void build () {
//    build(1, 0, N);
//}
//void update (int node, int l, int r, int ul, int ur, ll uval) {
//    if (ul <= l && r <= ur) {
//        segMin[node] += uval;
//        segLazy[node] += uval;
//        return;
//    }
//    int mid = (l + r) / 2;
//    int left = node * 2, right = node * 2 + 1;
//    segMin[left] += segLazy[node]; segLazy[left] += segLazy[node];
//    segMin[right] += segLazy[node]; segLazy[right] += segLazy[node];
//    segLazy[node] = 0;
//    if (ul <= mid) {
//        update(left, l, mid, ul, ur, uval);
//    }
//    if (mid + 1 <= ur) {
//        update(right, mid + 1, r, ul, ur, uval);
//    }
//    segMin[node] = min(segMin[left], segMin[right]);
//    segMinID[node] = (segMin[node] == segMin[left] ? segMinID[left] : segMinID[right]);
//}
//void update (int ul, int ur, ll uval) {
//    update(1, 0, N, ul, ur, uval);
//}
//pair <ll, int> query (int node, int l, int r, int ql, int qr) {
//    if (ql <= l && r <= qr) {
//        return make_pair(segMin[node], segMinID[node]);
//    }
//    int mid = (l + r) / 2;
//    int left = node * 2, right = node * 2 + 1;
//    segMin[left] += segLazy[node]; segLazy[left] += segLazy[node];
//    segMin[right] += segLazy[node]; segLazy[right] += segLazy[node];
//    segLazy[node] = 0;
//    ll queryMin = INT_MAX; int queryMinID = 0;
//    if (ql <= mid) {
//        tie(queryMin, queryMinID) = query(left, l, mid, ql, qr);
//    }
//    if (mid + 1 <= qr) {
//        int rightMin, rightMinID;
//        tie(rightMin, rightMinID) = query(right, mid + 1, r, ql, qr);
//        if (rightMin < queryMin) {
//            queryMin = rightMin;
//            queryMinID = rightMinID;
//        }
//    }
//    return make_pair(queryMin, queryMinID);
//}
//pair <ll, int> query (int ql, int qr) {
//    return query(1, 0, N, ql, qr);
//}
//
//ll cutCost;
//ll minPref[N_MAX + 2];
//int cutsPref[N_MAX + 2];
//
//void solve () {
//    build();
//    ll cnt = 0;
//    for (int i = 1; i <= N; i++) {
//        if (maxTrigger[i] > 0) {
//            cnt += N;
//            update(0, maxTrigger[i] - 1, +N);
//        }
//        ll prefMin; int prefMinID;
//        tie(prefMin, prefMinID) = query(0, i - 1);
//        minPref[i] = prefMin + cutCost;
//        cutsPref[i] = cutsPref[prefMinID] + 1;
//        if (cnt < minPref[i]) {
//            minPref[i] = cnt;
//            cutsPref[i] = 0;
//        }
//        update(i, i, minPref[i]);
//    }
//}

int minPref[N_MAX + 2][N_MAX + 2];
int cnt[N_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(2);

    cin >> N >> K >> T;
    for (int i = 1; i <= N; i++) {
        cin >> start[i];
        spread[i] = max(i - 1, min(N, i + (T - start[i])));
        if (spread[i] < N) {
            endSpread[spread[i]].push_back(i);
        }
    }
    set <int> triggers;
    for (int i = 1; i <= N; i++) {
        if (start[i] <= T) {
            triggers.insert(i);
        }
        maxTrigger[i] = (triggers.empty() == false ? *triggers.rbegin() : 0);
        for (int j : endSpread[i]) {
            triggers.erase(j);
        }
    }

    for (int i = 1; i <= N; i++) {
        cnt[maxTrigger[i] - 1]++;
        int sum = 0;
        fill(minPref[i], minPref[i] + K + 1, INT_MAX);
        for (int j = i - 1; j >= 0; j--) {
            sum += cnt[j];
            for (int k = 1; k <= K; k++) {
                minPref[i][k] = min(minPref[i][k], minPref[j][k - 1] + sum);
            }
        }
        minPref[i][0] = sum;
    }
    cout << minPref[N][K] << "\n";

//    ll l = 0, r = (ll) N * N + 1;
//    while (l < r) {
//        cutCost = (l + r) / 2;
//        solve();
//        if (cutsPref[N] > K) {
//            l = cutCost + 1;
//        } else {
//            r = cutCost;
//        }
//    }
//    cutCost = l;
//    solve();
//    cout << (ll) (minPref[N] - cutsPref[N] * cutCost) / N << "\n";

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20