Submission #585676

#	Time	Username	Problem	Language	Result	Execution time	Memory
585676		quagmire	Knapsack (NOI18_knapsack)	C++17	100 / 100	840 ms	37544 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
*/
	int n;
	int W;
vector<pii> weight[2010];
vvi dp(2005,vi (2005,-1));
int helper(int ind , int wt)
{ 
	//base 
	if(wt<0) return - inf;
	if(ind ==W+1)return 0 ;
	if(dp[ind][wt]!=-1)return dp [ind][wt];
	int ans = 0 ;
	int dont_take = helper(ind+1,wt);
	int curval = 0 , curwt = 0 ;
	for(int i = 0 ;i<weight[ind].size();i++) 
	{ 
		int count = weight[ind][i].ss;//no of times it can be repeated
		bool flag = 1;
		while(count>0) 
		{ 
			curval+=weight[ind][i].ff;//value hoga 
			curwt+=ind;
			if(curwt>wt) 
			{ 
				break;
				flag = false;

			}
			count--;
			ans = max(ans, curval+helper(ind+1,wt-curwt));
		}
		if(!flag)break;
	}
	return dp [ind][wt] = max(ans ,dont_take);
}
void solve()
{
	cin>>W>>n;
	vi a(n);
	rep(i,0,n)
	{ 
		// cin>>a[i];
		int v, w, k;
		cin>>v>>w>>k;
		weight[w].pb(mp(v,k));
	}
	for(int i = 0 ;i<=W;i++)
	{ 
		sort(all(weight[i]));
		reverse(all(weight[i]));
	}
	cout<<helper(1,W)<<nline;
}
int32_t main()
{
 
#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;
}

Compilation message (stderr)

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

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