Submission #638453

#	Time	Username	Problem	Language	Result	Execution time	Memory
638453		ankish2000nayak	Knapsack (NOI18_knapsack)	C++14	100 / 100	152 ms	4880 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{
  ll v, w, k;
};

ll maxValue(vector<item> &items,int n,ll s,vector<vector<ll>> &Mem){
  if(n == 0){
    return 0;
  }
  if(Mem[n][s] != -1){
    return Mem[n][s];
  }
  ll 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(){
  ll s;
  int 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<ll>> Mem(n+1,vector<ll>(s+1,-1));
  vector<ll> dp(s+1,0);
  sort(items.begin(),items.end(),[](const item &i1,const item &i2){
    if(i1.w == i2.w){
      return i1.v > i2.v;
    }
    return i1.w < i2.w;
  }); 
  // elements in sorted in a way where they less weight more 
  map<int,int> mpp;
  vector<item> newItems;
  for(item item : items){
    if(mpp[item.w] * item.w > s){
      continue;
    }
    mpp[item.w] += item.k;
    newItems.push_back(item);
  }
  swap(newItems,items);
  n = items.size();
  // cout << maxValue( items, n, s, Mem) << "\n";
  // dp[i][j] : maxValue can achive using first i items with weight of j
  for(int i = 1; i<=n; ++i){
    for(int j = s; j>=0; --j){
      for(int t = 0; t<=items[i-1].k; ++t){
        if(j-t*items[i-1].w >= 0)
          dp[j] = max( dp[j], dp[j-t*items[i-1].w] + t*items[i-1].v);
        else{
          break;
        }
      }
    }
  } 
  ll ans = 0;
  for(int i = 0; i<=s; ++i){
    ans = max( ans, dp[i]);
    // cout << dp[i] << " ";
  }
  cout << "\n";
  cout << ans << "\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: 27 / 27