Submission #1097623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097623		kiethm07	Knapsack (NOI18_knapsack)	C++11	73 / 100	1069 ms	2900 KiB

knapsack

#include <bits/stdc++.h>

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);
const int N = 1e5 + 5;
const int S = 2e3 + 5;

int n,s;
int dp[2][S];
int v[N], w[N], k[N];
vector<pii> f[S];

void build(int i){
    bool pre = (i & 1) ^ 1;
    for (int j = 0; j < w[i]; j++) f[j].clear();
    for (int j = 0; j <= s; j++){
        int id = j % w[i];
        f[id].push_back(pii(dp[pre][j] - v[i] * (j / w[i]),j));
    }
}

int query(int x,int j){
    int res = -inf;
    int id = j % w[x];
    for (int i = 0; i < f[id].size(); i++){
        int tmp = (j - f[id][i].se) / w[x];
        if (tmp > k[x] || tmp < 0) continue;
        cout << "Q: " << x << " " << j << " " << id << " " << tmp << "\n";
        res = max(res, f[id][i].fi);
    }
    return res;
}

int main(){
    #define TEXT "knapsack"
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> s >> n;
    for (int i = 1; i <= n; i++){
        cin >> v[i] >> w[i] >> k[i];
    }
    for (int i = 1; i <= n; i++){
        bool cur = i & 1;
        bool pre = cur ^ 1;
        build(i);
        for (int j = 0; j <= s; j++){
            //dp[cur][j] = v[i] * (j / w[i]) + query(i,j);
            for (int x = 0; x <= k[i]; x++){
                int t = w[i] * x;
                if (t > j) break;
                dp[cur][j] = max(dp[cur][j], dp[pre][j - t] + v[i] * x);
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= s; j++){
        res = max(res, dp[n & 1][j]);
    }
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int query(int, int)':
knapsack.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < f[id].size(); i++){
      |                     ~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27