Submission #684864

#	Time	Username	Problem	Language	Result	Execution time	Memory
684864		Farhan_HY	Knapsack (NOI18_knapsack)	C++14	73 / 100	1047 ms	68428 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 2005;
const int M = 1e3 + 3;
const int mod = 1e9 + 7;
int n, s, dp[N][N];
vector<pair<int, int>> vec[N];
vector<int> weights[N];

int Rec(int i, int j) {
    if (i > s) return 0;
    int &ret = dp[i][j];
    if (ret != -1) return ret;
    ret = Rec(i + 1, j);
    int value = 0;
    for(int k = 0; k < weights[i].size(); k++) {
        value += weights[i][k];
        if (j + (k + 1) * i <= s)
            ret = max(ret, Rec(i + 1, j + (k + 1) * i) + value);
    }
    return ret;
}

main() {
    IOS
    cin >> s >> n;
    for(int i = 1; i <= n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        vec[w].push_back({v, k});
    }
    for(int i = 1; i <= s; i++) {
        sort(begin(vec[i]), end(vec[i]), greater<pair<int, int>>());
        for(auto x: vec[i]) {
            if (weights[i].size() == s) break;
            for(int j = 1; j <= x.S; j++) {
                if (weights[i].size() == s) break;
                weights[i].push_back(x.F);
            }
        }
    }
    memset(dp, -1, sizeof dp);
    cout << Rec(1, 0);
}

Compilation message (stderr)

knapsack.cpp: In function 'long long int Rec(long long int, long long int)':
knapsack.cpp:22:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int k = 0; k < weights[i].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
knapsack.cpp: At global scope:
knapsack.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main() {
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:41:35: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   41 |             if (weights[i].size() == s) break;
      |                 ~~~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:43:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |                 if (weights[i].size() == s) break;
      |                     ~~~~~~~~~~~~~~~~~~^~~~

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