Submission #586320

#	Time	Username	Problem	Language	Result	Execution time	Memory
586320		Mazaalai	Knapsack (NOI18_knapsack)	C++17	100 / 100	44 ms	676 KiB

knapsack

#include <bits/stdc++.h>
// #pragma GCC optimize("O3, unroll-loops")
// #pragma GCC target("avx2")
// #define int long long
using namespace std;
 
#define _upgrade                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORB(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a) for (int i = 0; i < a; i++)
#define REP1(i, a) for (int i = 1; i < a; i++)
#define REPB(i, a) for (int i = a - 1; i >= 0; i--)
#define TRAV(a,x) for (auto& a: x)
#define LINE "---------------------\n"
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define Q queue
#define ff first
#define ss second
#define ts to_string
#define pb push_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound 
#define sz(x) (int)x.size()
 
using ll = long long;
using db = double;
using ld = long double;
using uint = unsigned;
// PQ going up <int, VI, greater<int> >
using VI = vector<int>;
using VS = vector<string>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VD = vector<db>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void eraseDups(VI& a) {
    a.erase(unique(a.begin(), a.end()), a.end());
}
int strToInt(string&a) {
    stringstream x(a);
    int b;
    x >> b;
    return b;
}
int bitCnt(int a) {
    bitset <64> b(a);
    return b.count();
}
int bitCnt(string a) {
    bitset <64> b(a);
    return b.count();
}
 
int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}
 
void print(VI& a) {
    for (auto el : a) {
        cout << el << ' ';
    }
    cout << '\n';
}
void print(VPI& a) {
    for (auto el : a) {
        cout << el.ff << ',' << el.ss << ' ';
    }
    cout << '\n';
}
 
void print(VI& a, int n) {
    int cnt = 0;
    for (auto el : a) {
        if (cnt++ == n) break;
        cout << el << ' ';
    }
    cout << '\n';
}
void print(VVI& a) {
    for (auto el : a) {
        print(el);
    }
}
 
/*
 
|                    _                                                     
|  __   _           | |                                                    
| |   \| | ___  ___ | |_                                                   
| | |\ | |/ _ \/ __/| __|                                                  
| | | \  |  __/\__ \| |_                                                   
| |_|  \_|\___ /___/ \__|                                                  
|                                                      _         _   _     
|                                                     (_)       | | | |    
|  _ __  _ __ ___   __ _ _ __ __ _ _ __ ___  _ __ ___  _ ___ ___| |_| |_   
| | '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|  
| | |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_   
| | .__/|_|  \___/ \__, |_|  \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|  
| | |               __/ |                                                  
| |_|              |___/                   _                               
|                                  _      (_)                              
|  _ __ ___   __ _ ____ __ _  __ _| | __ _ _                               
| | '_ ` _ \ / _` |_   / _` |/ _` | |/ _` | |                              
| | | | | | | (_|  /  / (_| | (_| | | (_| | |                              
| |_| |_| |_|\__,_|____\__,_|\__,_|_|\__,_|_|                              
*/
 
const db PI = acos(-1.0); //M_PI;
const ll INFF = 4e18;
const int INF = 1.07e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353; //7*19*2^23 +1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
 
 
 
 
const int N = 2e3 + 5;
const int M = 2e3 + 5;
 
 
int n, m;
string s;
int dp[N];
// multiset <int> val[N];
priority_queue <int, vector<int>, greater<int> > val[N];
VI vals[N];
void go () {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int v, w, q; cin >> v >> w >> q;
        for (int j = 0; j < q; j++) {
            if ((val[w].size()+1) * w <= m) {
                val[w].push(v);
            } else {
                if (val[w].top() < v) {
                    val[w].pop();
                    val[w].push(v);
                } else {
                    break;
                }
            }
        }
    }
    for (int w = 1; w <= m; w++) {
        vals[w].reserve(val[w].size()+1);
        while (!val[w].empty()) {
            vals[w].pb(val[w].top());
            val[w].pop();
        }
        vals[w].pb(0);
        reverse(ALL(vals[w]));
        for (int i = 1; i < vals[w].size(); i++) vals[w][i] += vals[w][i-1];
    }
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int w = m; w > 0; w--) // 2e3
    for (int j = m-w; j >= 0; j--)  // 2e3
    for (int k = 1; k < vals[w].size() && j + w*k <= m && dp[j] >= 0; k++) // (m-j)/w ~~ 2e1.5
        dp[j + w*k] = max(dp[j + w*k], dp[j] + vals[w][k]);
    
    for (int i = 1; i <= m; i++) dp[i] = max(dp[i], dp[i-1]);
    cout << dp[m] << '\n';
    
}
 
 
 
signed main () {
 
#ifndef ONLINE_JUDGE
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
#endif
    _upgrade
    int T = 1;
    while(T--) go();
    return (0-0); //<3
}
 
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    
*/
 
 
 
 
 
 
 
 

Compilation message (stderr)

knapsack.cpp: In function 'void go()':
knapsack.cpp:150:39: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if ((val[w].size()+1) * w <= m) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:170:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for (int i = 1; i < vals[w].size(); i++) vals[w][i] += vals[w][i-1];
      |                         ~~^~~~~~~~~~~~~~~~
knapsack.cpp:176:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for (int k = 1; k < vals[w].size() && j + w*k <= m && dp[j] >= 0; k++) // (m-j)/w ~~ 2e1.5
      |                     ~~^~~~~~~~~~~~~~~~

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