Submission #1288962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288962		Phongnv	Knapsack (NOI18_knapsack)	C++20	49 / 100	3 ms	584 KiB

knapsack

/// PhongDang Cs4_uet

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define pii pair<int, int>
#define mx(x, y) max(x, y)
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define pob pop_back
#define all(x) x.begin(),x.end()
#define vii vector<int>
#define int long long
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) (1 << j) ^ i
#define onbit(i, j) (1 << j)  i
#define built(mask) __builtin_popcountll(mask)
#define len(s) (int)((s).size())
#define iii pair<int,pair<int, int> >
#define fillcharval(a) memset(a, -0x3f, sizeof(a));
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return 1;} return 0;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
const int N = 1e6 + 6;
const int mod = 1e9 + 7;
const int base = 31;
const int inf = 1e9;
void add(ll &x, const ll y){
    x+= y;
    if(x>=mod) x-= mod;
}
int S, n;
struct task{
	int val, wei, cnt;
}a[N];
namespace sub1{
	bool checksub(void){
		return (n == 1);
	}
	void sol(){
		int can = S/a[1].wei;
		can = min(can, a[1].cnt);
		cout <<  can*a[1].val;
	}
}
namespace sub23{
	bool checksub(void){
		fo(i, 1, n) if(a[i].cnt > 10) return 0;
		return (n <= 100);
	}
	int dp[2002];
	void sol(){
		fo(i, 1, n){
			foi(j, S, a[i].wei){
				for(int k = 1; k*a[i].wei <= j && k <= a[i].cnt; k++){
					maximize(dp[j], dp[j - k*a[i].wei] + k*a[i].val);
				}
			}
		}
		cout << dp[S];
	}
}
signed main()
{  
    faster  
    // in("task.inp");
    // out("task.out");
    // out("task.ans");
    cin >> S >> n;
    fo(i, 1, n) cin >> a[i].val >> a[i].wei >> a[i].cnt;
    if(sub1::checksub()) return sub1::sol(), 0;
    if(sub23::checksub()) return sub23::sol(), 0;
     
     
     
    
    return 0;

}

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