oj.uz

Submission #552753

# Submission time Handle Problem Language Result Execution time Memory
552753 2022-04-23T20:12:40 Z nhuang685 Knapsack (NOI18_knapsack) C++17
12 / 100
 31 ms 63052 KB 
#include <bits/stdc++.h>

#ifdef VSLOCAL
#include "debug/d.h"
#endif
#ifdef LOCAL
#include "../../debug/d.h"
#endif

using namespace std;

using ll = long long;
using ld = long double;

#if defined(LOCAL) || defined(VSLOCAL)
#define dbg(...) line_info(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 0
void nline() {}
#endif

struct item {
    int W; ll V, K;
    bool operator< (const item that) const {
        return (W == that.W) ? V > that.V : W < that.W;
    }
};

ostream& operator<< (ostream& out, item i) {
    out << "{" << i.V << ", " << i.W << ", " << i.K << "}";
    return out;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("log.txt", "w", stderr);
    #endif

    int S, N;
    cin >> S >> N;

    vector<item> items (N);
    for (int i = 0; i < N; ++i) {
        cin >> items[i].V >> items[i].W >> items[i].K;
    }

    sort(items.begin(), items.end());
    dbg(items);

    vector<vector<ll>> value (S + 1, vector<ll> (S + 1));
    vector<vector<ll>> dp (S + 1, vector<ll> (S + 1)); // maximum value

    int index = 0;
    for (int i = 1; i <= S; ++i) {
        int count = 0;
        dp[i] = dp[i - 1];
        for (int j = i; j <= S; j += i) {
            count++;
            if (count > items[index].K) {
                count = 1;
                index++;
            }
            if (items[index].W != i) break;
            value[i][j] = value[i][j - i] + items[index].V;

            for (int k = j; k <= S; ++k) {
                // dp[i][k] = max(dp[i][k], dp[i - 1][k]);
                dp[i][k] = max(dp[i][k], dp[i - 1][k - j] + value[i][j]);
            }
        }
    }
    dbg(dp);
    cout << dp[S][S] << '\n';
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
knapsack.cpp:52:5: note: in expansion of macro 'dbg'
   52 |     dbg(items);
      |     ^~~
knapsack.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
knapsack.cpp:76:5: note: in expansion of macro 'dbg'
   76 |     dbg(dp);
      |     ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24276 KB Output is correct
2 Correct 12 ms 24252 KB Output is correct
3 Correct 12 ms 24248 KB Output is correct
4 Correct 12 ms 24276 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 63036 KB Output is correct
3 Correct 28 ms 63052 KB Output is correct
4 Incorrect 30 ms 62872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 31 ms 63036 KB Output is correct
3 Correct 28 ms 63052 KB Output is correct
4 Incorrect 30 ms 62872 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24276 KB Output is correct
2 Correct 12 ms 24252 KB Output is correct
3 Correct 12 ms 24248 KB Output is correct
4 Correct 12 ms 24276 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 31 ms 63036 KB Output is correct
7 Correct 28 ms 63052 KB Output is correct
8 Incorrect 30 ms 62872 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24276 KB Output is correct
2 Correct 12 ms 24252 KB Output is correct
3 Correct 12 ms 24248 KB Output is correct
4 Correct 12 ms 24276 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 31 ms 63036 KB Output is correct
7 Correct 28 ms 63052 KB Output is correct
8 Incorrect 30 ms 62872 KB Output isn't correct
9 Halted 0 ms 0 KB -