oj.uz

Submission #510915

# Submission time Handle Problem Language Result Execution time Memory
510915 2022-01-15T03:46:21 Z KoD Akcija (COCI21_akcija) C++17
10 / 110
 30 ms 31732 KB 
#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);
                } else {
                    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29260 KB Output is correct
2 Correct 23 ms 31732 KB Output is correct
3 Correct 27 ms 26784 KB Output is correct
4 Correct 24 ms 26172 KB Output is correct
5 Correct 29 ms 31092 KB Output is correct
6 Correct 24 ms 26096 KB Output is correct
7 Correct 30 ms 31460 KB Output is correct
8 Correct 25 ms 27012 KB Output is correct
9 Correct 23 ms 25864 KB Output is correct
10 Correct 24 ms 27860 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29260 KB Output is correct
2 Correct 23 ms 31732 KB Output is correct
3 Correct 27 ms 26784 KB Output is correct
4 Correct 24 ms 26172 KB Output is correct
5 Correct 29 ms 31092 KB Output is correct
6 Correct 24 ms 26096 KB Output is correct
7 Correct 30 ms 31460 KB Output is correct
8 Correct 25 ms 27012 KB Output is correct
9 Correct 23 ms 25864 KB Output is correct
10 Correct 24 ms 27860 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 29 ms 29284 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 29260 KB Output is correct
2 Correct 23 ms 31732 KB Output is correct
3 Correct 27 ms 26784 KB Output is correct
4 Correct 24 ms 26172 KB Output is correct
5 Correct 29 ms 31092 KB Output is correct
6 Correct 24 ms 26096 KB Output is correct
7 Correct 30 ms 31460 KB Output is correct
8 Correct 25 ms 27012 KB Output is correct
9 Correct 23 ms 25864 KB Output is correct
10 Correct 24 ms 27860 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 29 ms 29284 KB Output isn't correct
15 Halted 0 ms 0 KB -