Submission #638449

#	Time	Username	Problem	Language	Result	Execution time	Memory
638449		ankish2000nayak	Knapsack (NOI18_knapsack)	C++14	73 / 100	684 ms	262144 KiB

knapsack

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<climits>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
// #include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<bitset>
#include<iomanip>
#include<deque>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
// #include<thread>
// #include<chrono>
// #include "mingw.thread.h"
// #include<unordered_set>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
 
// down up right left
int dx[] = { 0, 1, -1, 0};
int dy[] = { 1, 0, 0, -1};
 
// all compases directions
int ax[] = { -1, -1, 0, 1, 1, 1, 0, -1};
int ay[] = {  0, 1, 1, 1, 0, -1, -1, -1};
 
int kx[] = { -2, -2, -1, 1, 2, 2, 1, -1};
int ky[] = { -1, 1, 2, 2, 1, -1, -2, -2};
 
#define   valid(x,y,row,col)     x>=0 && y>=0 && x<row && y<col
#define   pb                     push_back
#define   mp                     make_pair
#define   fs                     first
#define   se                     second
#define   pi                     2*acos(0)
#define   PI                     3.14159265358979323846264338
#define   modulo                 1000000007
#define   SMA                    300010
#define   MAX                    100000010
// #define   INT_MAX                2147483647
// #define   INT_MIN                -2147483648
#define   input                  freopen("input.txt", "r", stdin)
#define   output                 freopen("output.txt", "w", stdout)
#define   ms(a,b)                memset(a, b, sizeof(a))
#define   sc(n)                  scanf("%d",&n)
#define   loop(i,n)              for(int i = 0; i<n; i++)
#define   nloop(i,n)             for(int i = 1; i<=n; i++)
#define   prln(n)                printf("%d\n",n)
#define   prsp(n)                printf("%d ",n)
#define   pr(n)                  printf("%d",n)
#define   INF                    1100000000
#define   all(x)                 (x).begin(), (x).end()
 
using namespace std;
// using namespace std::chrono;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pint;
// // typedef vector<int> vint;
// // typedef vector<pint> vpint;
// // after input of int dont forget to take getchar() in uva
// // getline()  takes complete line.
// // Matrix 45* rotation formula of n*n (i,j) -> (n-1+i-j,i+j) zero based indexing
// // unique function is awesome
// // compiler might replace this with its function

struct item{
  int v, w, k;
};

int maxValue(vector<item> &items,int n,int s,vector<vector<int>> &Mem){
  if(n == 0){
    return 0;
  }
  if(Mem[n][s] != -1){
    return Mem[n][s];
  }
  int maxV = 0;
  for(int i = 0; i<=items[n-1].k; ++i){
    if(s-i*items[n-1].w >= 0)
      maxV = max( maxV, maxValue( items, n-1, s-i*items[n-1].w, Mem)+i*items[n-1].v);
    else
      return Mem[n][s] = maxV;
  }
  return Mem[n][s] = maxV;
}

int main(){
  int s, n;
  cin >> s >> n;
  vector<item> items(n);
  for(int i = 0; i<n; ++i){
    cin >> items[i].v >> items[i].w >> items[i].k;
  }
  vector<vector<int>> Mem(n+1,vector<int>(s+1,-1));
  cout << maxValue( items, n, s, Mem) << "\n";
  return 0;
}
 
// priority_queue customized
// struct ele{
//     ll value, i, j;
// };
  
// struct myComp{
//     constexpr operator()(struct ele const &e1,struct ele const &e2) const noexcept{
//         return e1.value > e2.value;
//     }
// };

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