Submission #1104354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104354		Daniel_1997	Knapsack (NOI18_knapsack)	C++17	12 / 100	11 ms	12540 KiB

knapsack

#include<bits/stdc++.h>
//#pragma GCC optimizate("Ofast")
using namespace std;
 
///Error types :
#define rte std::vector<int>rtt(oo);
#define wa std::cout<<"d";
#define tle while(1){;}
#define ir exit(1);
 
 
///STL
#define pb push_back
#define pp pop
#define fr first
#define sc second
#define vec vector<int>
 
 
///General
#define ios ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0)
#define int long long
#define endl "\n"
#define oo 1e18
const int mod = 998244353;

int32_t main(){
     ios;
     int m,n;
     cin >> m >> n;
     vector <pair < int,pair<int,int> > > v(n);
     for(int i = 0;i < v.size();i++){
          cin >> v[i].fr >> v[i].sc.fr >> v[i].sc.sc;
     }

     int dp[m+1] = {};
     int dp2[m+1][m+1] = {};
     for(int i = 0;i <= m;i++){
          for(int j = 0;j <= m;j++){
               dp2[i][j] = oo;
          }
     }

     for(int i = 0;i < v.size();i++){
          if(v[i].sc.sc > m)v[i].sc.sc = m;
          if(v[i].fr > dp2[v[i].sc.fr][v[i].sc.sc])continue;
          dp2[v[i].sc.fr][v[i].sc.sc] = v[i].fr;
          for(int j = 0;j < v[i].sc.sc;j++){
               for(int k = m;k >= v[i].sc.fr;k--){
                    dp[k] = max(dp[k],dp[k - v[i].sc.fr] + v[i].fr);
               }
          }
     }

     int maxx = 0;
     for(int i = 0;i <= m;i++){
          maxx = max(maxx,dp[i]);
     }
     cout << maxx << endl;
    
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:32:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      for(int i = 0;i < v.size();i++){
      |                    ~~^~~~~~~~~~
knapsack.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |      for(int i = 0;i < v.size();i++){
      |                    ~~^~~~~~~~~~

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