Submission #1097616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097616		kiethm07	Knapsack (NOI18_knapsack)	C++11	12 / 100	3 ms	348 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 it = 0; it < f[id].size(); it++){
        int tmp = (j - f[id][it].se) / w[x];
        if (tmp > k[x] || tmp <= 0) continue;
        //cout << "Q: " << x << " " << j << " " << id << " " << tmp << "\n";
        res = max(res, f[id][it].fi);
    }
    if (res == -inf) res = 0;
    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);
        }
    }
    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:25: 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 it = 0; it < f[id].size(); it++){
      |                      ~~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:63:14: warning: unused variable 'pre' [-Wunused-variable]
   63 |         bool pre = cur ^ 1;
      |              ^~~
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".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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