Submission #510920

#	Time	Username	Problem	Language	Result	Execution time	Memory
510920		KoD	Akcija (COCI21_akcija)	C++17	30 / 110	36 ms	31684 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

constexpr i64 inf = std::numeric_limits<i64>::max() / 2;

void setmin(i64& x, const i64 y) {
    if (x > y) {
        x = y;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K;
    std::cin >> N >> K;
    vector<pair<int, int>> prod(N);
    for (auto& [d, w] : prod) {
        std::cin >> w >> d;
    }    
    std::sort(prod.begin(), prod.end());
    if (K == 1) {
        vector dp(N + 1, vector<i64>(N + 1, inf));
        setmin(dp[0][0], 0);
        for (int i = 0; i < N; ++i) {
            const auto& [d, w] = prod[i];
            for (int j = 0; j <= N; ++j) {
                if (dp[i][j] == inf) continue;
                if (d > j) {
                    setmin(dp[i + 1][j + 1], dp[i][j] + w);
                }
                setmin(dp[i + 1][j], dp[i][j]);
            }
        }
        int j = N;
        while (dp[N][j] == inf) {
            j -= 1;
        }
        std::cout << j << ' ' << dp[N][j] << '\n';
    }
    return 0;
}

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