제출 #1112826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112826		vjudge1	Knapsack (NOI18_knapsack)	C++14	73 / 100	15 ms	4112 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define LL pair<ll, ll>
#define ii pair<int, int>
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define pqueue priority_queue
#define all(v) v.begin(), v.end()
#define szi(v) (int)(v.size())
#define szl(v) (ll)(v.size())
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//Time: cerr << "Time elapsed: " << TIME << " s.\n";

const ll mod = 1e9 + 7;
const int nmax = 1e5;
const ll inf = 1e18;

ll Pow(ll a, ll b){ if (!b || a == 1) return 1; if (!a) return 0; ll ans = 1; while (b){if (b & 1) ans *= a, ans %= mod; a *= a; a %= mod; b >>= 1;} return ans;}
ll Gcd(ll a, ll b){return (b ? Gcd(b, a % b) : a);}
bool minimize(int &a, int b){if (a > b){a = b; return 1;} return 0;}
bool maximize(ll &a, ll b){if (a < b){a = b; return 1;} return 0;}
void add(int &a, int b){a += b; if (a >= mod) a -= mod;}
void sub(int &a, int b){a -= b; if (a < 0) a += mod;}

int n, s;
//int w[2002], v[2002], c[2002];

int m = 0;
LL a[100002];

ll dp[2][100002];

int main(){
	faster
//	freopen("MARKET.INP", "r", stdin);
//	freopen("MARKET.OUT", "w", stdout);
	cin >> s >> n;
	for (int i = 1; i <= n; i++){
		int c = 1;
		ll p, h;
		int k;
		cin >> h >> p >> k;
		while (k > c){
			k -= c;
			a[++m].fi = c * p;
			a[m].se = c * h;
			c <<= 1;
		}
		if (k){
			a[++m].fi = k * p;
			a[m].se = k * h;
		}
	}
	
	for (int i = 1; i <= m; i++){
		int cur = i & 1, last = cur ^ 1;
		for (int j = 0; j <= s; j++){
			dp[cur][j] = dp[last][j];
			if (j >= a[i].fi) maximize(dp[cur][j], dp[last][j - a[i].fi] + a[i].se);
		} 
	}
	
	cout << dp[m & 1][s];
}

/*

            !#########       #
           !########!          ##!
        !########!               ###
     !##########                  ####
   ######### #####                ######
    !###!      !####!              ######
      !           #####            ######!
                    !####!         #######
                       #####       #######
                         !####!   #######!
                            ####!########
         ##                   ##########
       ,######!          !#############
     ,#### ########################!####!
   ,####'     ##################!'    #####
 ,####'            #######              !####!
####'                                      #####
~##                                          ##~

LONG LIVE THE GLORIOUS COMMUNIST PARTY OF VIET NAM
LONG LIVE THE SOCIALIST REPUBLIC OF VIET NAM
LONG LIVE GENERAL SECRETARY NGUYEN PHU TRONG

*/

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