Submission #545433

#	Time	Username	Problem	Language	Result	Execution time	Memory
545433		AA_Surely	Knapsack (NOI18_knapsack)	C++17	100 / 100	98 ms	19412 KiB

knapsack

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 2000 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int s, n;
int dp[MAXN][MAXN];
VPII group[MAXN];

inline int get(int x, int y) {
    int ret = max(dp[x - 1][y], dp[x][y - 1]);
    if (group[x].empty()) return ret;

    int ptr = 0, cap = y, val = 0;
    int keep = 0;
    
    while(1) {
        if (ptr < group[x].size() && !group[x][ptr].S) {
            group[x][ptr].S = keep;
            keep = 0;
            ptr++;
        }
        
        //if (x == 15 && y == 15) cout << ptr << endl;
        if (ptr >= group[x].size()) break;
        cap -= x; group[x][ptr].S--; val += group[x][ptr].F;
        keep++;

        if (cap < 0) break;
        //if (x == 15 && y == 15) cout << "ret is max(ret, " << dp[x - 1][cap] + val << ") " << endl;
        ret = max(ret, dp[x - 1][cap] + val);
    }
    if (ptr < group[x].size()) group[x][ptr].S += keep;

    return ret;
}

int main() {
    IOS;
    
    cin >> s >> n;
    int v, w, k;
    F0R(i, n) {
        cin >> v >> w >> k;
        group[w].pb({v, k});
    }

    FOR(i, 1, s + 1) sort(RALL(group[i]));
    FOR(i, 1, s + 1) FOR(j, 1, s + 1) 
        dp[i][j] = get(i, j);
    
    //cout << dp[15][15] << endl;
    cout << dp[s][s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int get(int, int)':
knapsack.cpp:47:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (ptr < group[x].size() && !group[x][ptr].S) {
      |             ~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (ptr >= group[x].size()) break;
      |             ~~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp:62:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (ptr < group[x].size()) group[x][ptr].S += keep;
      |         ~~~~^~~~~~~~~~~~~~~~~

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