Submission #1097633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097633		kiethm07	Knapsack (NOI18_knapsack)	C++11	73 / 100	1095 ms	4344 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 = 2e9 + 5;
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];
deque<pii> dq[S];
int ptr[S];

void build(int i){
    bool pre = (i & 1) ^ 1;
    for (int j = 0; j < w[i]; j++){
        f[j].clear();
        dq[j].clear();
        ptr[j] = 0;
    }
    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 << " " << f[id][i].se << " " << j - f[id][i].se << " " << tmp << "\n";
//        res = max(res, f[id][i].fi);
//    }
    int &i = ptr[id];
    for (i; i < f[id].size(); i++){
        while((!dq[id].empty()) && (j - dq[id].front().se) / w[x] > k[x]) dq[id].pop_front();
        if (f[id][i].se > j) break;
        while((!dq[id].empty()) && dq[id].back().fi <= f[id][i].fi) dq[id].pop_back();
        dq[id].push_back(pii(f[id][i].fi,f[id][i].se));
    }
    if (!dq[id].empty()) res = max(res, dq[id].front().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:53:10: warning: statement has no effect [-Wunused-value]
   53 |     for (i; i < f[id].size(); i++){
      |          ^
knapsack.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (i; i < f[id].size(); i++){
      |             ~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:76:14: warning: unused variable 'pre' [-Wunused-variable]
   76 |         bool pre = cur ^ 1;
      |              ^~~
knapsack.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         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