Submission #1238794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238794		modwwe	Akcija (COCI21_akcija)	C++20	110 / 110	76 ms	31812 KiB

Main

#include <cstdio>
#include <algorithm>
using namespace std;
int read() {
    char c = getchar();
    int x = 0;

    while (c < 48 || c > 57)
        c = getchar();

    do
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();

    while (c >= 48 && c <= 57);

    return x;
}
typedef long long ll;
const int N = 2003;
const ll INF = 0x3f3f3f3fll * N;
int n, k;
struct goods {
    int w, d;
    friend bool operator<(const goods x, const goods y) {
        return x.d < y.d;
    }
} s[N];
ll g[N][N];
struct path {
    int a, b;
    ll val;
    path() {}
    path(int A, int B, ll V): a(A), b(B), val(V) {}
    friend bool operator<(const path x, const path y) {
        return x.val + g[x.a][x.b] < y.val + g[y.a][y.b];
    }
} arr[N], stk[N << 1];
int rk, tp;
int main() {
    n = read();
    k = read();

    for (int i = 1; i <= n; ++i)
        s[i].w = read(), s[i].d = read();

    sort(s + 1, s + n + 1);

    for (int i = 0; i <= n; ++i)
        g[n + 1][i] = -i * INF;

    for (int i = n; i; --i)
        for (int j = 0; j <= n; ++j) {
            g[i][j] = g[i + 1][j];

            if (s[i].d > j) {
                ll val = g[i + 1][j + 1] + s[i].w;

                if (val < g[i][j])
                    g[i][j] = val;
            }
        }

    arr[rk = 1] = path(1, 0, 0);

    for (int i = 1; i <= n; ++i) {
        tp = 0;

        for (int t = 1; t <= rk; ++t) {
            int a = arr[t].a, b = arr[t].b;
            ll val = arr[t].val;
            stk[++tp] = path(a + 1, b, val);

            if (s[i].d > b)
                stk[++tp] = path(a + 1, b + 1, val + s[i].w);
        }

        if (tp <= k) {
            for (int t = 1; t <= tp; ++t)
                arr[t] = stk[t];

            rk = tp;
        } else {
            nth_element(stk + 1, stk + k, stk + tp + 1);

            for (int t = 1; t <= k; ++t)
                arr[t] = stk[t];

            rk = k;
        }
    }

    sort(arr + 1, arr + k + 1);

    for (int i = 1; i <= k; ++i)
        printf("%d %lld\n", arr[i].b, arr[i].val);

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 20 / 20