Submission #697338

#	Time	Username	Problem	Language	Result	Execution time	Memory
697338		khanhtai	Knapsack (NOI18_knapsack)	C++14	100 / 100	118 ms	36356 KiB

knapsack

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "knapsack"
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 100009;
int s[MAXN],w[MAXN],k[MAXN],dp[2009][2009];
int n,S;
vector<int> value[2009];
struct data{
    int s,w,k;
};
data d[MAXN];
bool cmp(data a,data b){
    if (a.s!=b.s) return (a.s < b.s);
    else return (a.w < b.w);
}
main()
{
    fast;
 //   freopen(TASKNAME".inp","r",stdin);
//    freopen(TASKNAME".out","w",stdout);
    cin>>S>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i].s>>d[i].w>>d[i].k;
    }
    sort(d+1,d+1+n,cmp);
    for(int i=n;i>=1;i--){
        int w = d[i].w;
        if (value[w].size() < S/w){
            for(int t=1;t<=d[i].k;t++){
                value[w].pb(d[i].s);
                if (value[w].size() == S/w) break;
            }
        }
    }
    for(int i=1;i<=S;i++){
        for(int j=0;j<=S;j++){
            dp[i][j] = dp[i-1][j];
            int sum = 0,sz=value[i].size();
            for(int t=1;t <= sz; t++){
                sum += value[i][t-1];
                if (j>=t*i) dp[i][j] = max(dp[i][j], dp[i-1][j-t*i] + sum);
            }
        }
    }
    cout<<dp[S][S]<<endl;
}

Compilation message (stderr)

knapsack.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main()
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:43:29: 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 (value[w].size() < S/w){
      |             ~~~~~~~~~~~~~~~~^~~~~
knapsack.cpp:46:37: 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]
   46 |                 if (value[w].size() == S/w) break;
      |                     ~~~~~~~~~~~~~~~~^~~~~~

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