Submission #584436

#	Time	Username	Problem	Language	Result	Execution time	Memory
584436		quagmire	Knapsack (NOI18_knapsack)	C++17	49 / 100	1091 ms	79800 KiB

knapsack

/*
ANIKET ASH
*/
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
const int mod= 1e9+7;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define mset(a , b) memset(a , b , sizeof(a))
#define mp make_pair
#define ff            first
#define ss            second
#define nline '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#ifdef quagmire
#define  dbg(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define dbg(x)
#endif
typedef set <int> si;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef multiset <int> msi;
typedef vector <string> vs;
typedef pair <int , int> pii;
typedef vector <char> vch;
typedef vector <pair <int, int>> vpi;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key//for multiset less_equal<int>


void _print(int t) {cerr << t;}
void _print(bool t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(deque <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(deque <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
const int inf =1e18;
const double PI=2*acosl(0);
/*----------------------------- # --- MATH ALGORITHMS --- # -----------------------------*/
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
template <class T> T gcd(T a , T b){ while(a != 0){T temp = a; a = b % a; b = temp;}return b;}
template <class T> T egcd(T a , T b , T &x , T &y){T gcd , xt , yt;if(a == 0){gcd = b;x = 0 , y = 1;}else {gcd = egcd(b % a , a , xt , yt);x = yt - (b/a)*xt; y = xt;}return gcd;}
template <class T> T expo(T base , T exp , T m){T res = 1;base = base % m;while (exp > 0){if (exp & 1)res = (res*base) % m;exp = exp>>1;base = (base*base) % m;}return res;}
template <class T> T modinv(T a ){T x , y; egcd<T>(a , mod , x , y);while(x < 0) x += mod; while(x >= mod) x -= mod; return x;}
template <class T> bool rev(T a , T b){return a > b;}
template <class T> int maxpower(T a , T b){int ans = 0;while(a >0 && a % b == 0){ans++;a /= b;}return ans;}
template <class T> T mceil(T a, T b){if(a % b == 0) return a/b; else return a/b + 1;}
template <class T> T lcm(T a, T b){return (a*b)/gcd<T>(a, b);}
int modinv_prime(int a, int b) {return expo(a, b - 2,mod);}//modinvfermat
 int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, modinv_prime(b, m), m) + m) % m;}  //only for prime m
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?), slow multiset operations
	* do something instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
	*try to check like n is even or odd or ith index even or odd
	*try thinking in REVERSE
	* try to observe by using brute force for first few cases if not getting idea
*/

// vvi dp;
	int s, n;
	vi v,w,k;
	map<array<int,3> ,int> dp;
int helper(int ind , int k_used , int s_rem )
{ 
	//base
	if(ind==n) 
	{ 
		return 0 ;
	}
	array<int,3> dp_t = {ind,k_used,s_rem};
	auto it = dp.find(dp_t);
	if(it!=dp.end())
	{ 
		return it->ss;
	}
	int take = 0 ;
	if(k_used<k[ind])
	{ 
		if(s_rem>=w[ind])
		take =v[ind]+ helper(ind,k_used+1,s_rem-w[ind]);
	}
	int dont_take = helper(ind+1,0,s_rem);
	return dp[dp_t]= max(take,dont_take);
}
void solve()
{
	cin>>s>>n;
	v.resize(n);
	w.resize(n);
	k.resize(n);
	rep(i,0,n) 
	{ 
		cin>>v[i]>>w[i]>>k[i];
	}
	int ans = helper(0,0,s);
	cout<<ans<<nline;
}
int32_t main()
{
 	// freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);
#ifdef quagmire
   freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  freopen("error.txt", "w", stderr);
#endif
ios
int test_case=1;
// cin>>test_case;
for(int _=1;_<=test_case;_++)
{
	// cout << "Case #" << _ << ": ";
  auto start1 = high_resolution_clock::now();
	solve();
	auto stop1 = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stop1 - start1);
  #ifdef quagmire
	cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}

return 0;
}

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