oj.uz

답안 #824588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
824588 2023-08-14T08:02:56 Z pickle_juice2023 Knapsack (NOI18_knapsack) C++17
29 / 100
 21 ms 31700 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

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

typedef long long ll;
const int MAX = 2002;
vector<pair<ll, ll>> a[MAX];
ll f[MAX][MAX], s, n, u, v, w, k, total;

void solve() {
    cin >> s >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w >> k;
        a[w].push_back({v, k});
    }
    for (int i = 1; i <= 2000; i++) sort(a[i].begin(), a[i].end(), greater<pair<ll, ll>>());
    for (int i = 1; i <= s; i++) {
        for (int j = 1; j <= s; j++) {
            total = 0;
            ll temp = 0;
            f[i][j] = f[i - 1][j];
            for (auto u : a[i]) {
                if (total + u.second * i <= j) {
                    total += u.second * i;
                    temp += u.second * u.first;
                    f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
                } else {
                    temp += (j - total) / i * u.first;
                    total += (j - total) / i * i;
                    f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
                    break;
                }
            }
            f[i][j] = max(f[i][j], temp + f[i - 1][j - total]);
            //if (i > 19) cout << f[i][j] << " ";
        }
        //if (i > 19) cout << "\n";
    }
    cout << f[s][s];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17156 KB Output is correct
2 Correct 9 ms 17128 KB Output is correct
3 Correct 9 ms 17228 KB Output is correct
4 Correct 9 ms 17236 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 19 ms 31604 KB Output is correct
3 Correct 19 ms 31564 KB Output is correct
4 Correct 18 ms 31588 KB Output is correct
5 Correct 18 ms 31544 KB Output is correct
6 Correct 19 ms 31700 KB Output is correct
7 Correct 19 ms 31680 KB Output is correct
8 Correct 20 ms 31560 KB Output is correct
9 Correct 18 ms 31596 KB Output is correct
10 Correct 18 ms 31684 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 19 ms 31604 KB Output is correct
3 Correct 19 ms 31564 KB Output is correct
4 Correct 18 ms 31588 KB Output is correct
5 Correct 18 ms 31544 KB Output is correct
6 Correct 19 ms 31700 KB Output is correct
7 Correct 19 ms 31680 KB Output is correct
8 Correct 20 ms 31560 KB Output is correct
9 Correct 18 ms 31596 KB Output is correct
10 Correct 18 ms 31684 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 19 ms 31620 KB Output is correct
13 Correct 19 ms 31572 KB Output is correct
14 Correct 18 ms 31700 KB Output is correct
15 Correct 21 ms 31572 KB Output is correct
16 Incorrect 19 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17156 KB Output is correct
2 Correct 9 ms 17128 KB Output is correct
3 Correct 9 ms 17228 KB Output is correct
4 Correct 9 ms 17236 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 19 ms 31604 KB Output is correct
7 Correct 19 ms 31564 KB Output is correct
8 Correct 18 ms 31588 KB Output is correct
9 Correct 18 ms 31544 KB Output is correct
10 Correct 19 ms 31700 KB Output is correct
11 Correct 19 ms 31680 KB Output is correct
12 Correct 20 ms 31560 KB Output is correct
13 Correct 18 ms 31596 KB Output is correct
14 Correct 18 ms 31684 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 19 ms 31620 KB Output is correct
17 Correct 19 ms 31572 KB Output is correct
18 Correct 18 ms 31700 KB Output is correct
19 Correct 21 ms 31572 KB Output is correct
20 Incorrect 19 ms 31608 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 17156 KB Output is correct
2 Correct 9 ms 17128 KB Output is correct
3 Correct 9 ms 17228 KB Output is correct
4 Correct 9 ms 17236 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 19 ms 31604 KB Output is correct
7 Correct 19 ms 31564 KB Output is correct
8 Correct 18 ms 31588 KB Output is correct
9 Correct 18 ms 31544 KB Output is correct
10 Correct 19 ms 31700 KB Output is correct
11 Correct 19 ms 31680 KB Output is correct
12 Correct 20 ms 31560 KB Output is correct
13 Correct 18 ms 31596 KB Output is correct
14 Correct 18 ms 31684 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 19 ms 31620 KB Output is correct
17 Correct 19 ms 31572 KB Output is correct
18 Correct 18 ms 31700 KB Output is correct
19 Correct 21 ms 31572 KB Output is correct
20 Incorrect 19 ms 31608 KB Output isn't correct
21 Halted 0 ms 0 KB -