oj.uz

Submission #1112825

# Submission time Handle Problem Language Result Execution time Memory
1112825 2024-11-15T02:24:47 Z vjudge1 Knapsack (NOI18_knapsack) C++14
37 / 100
 2 ms 600 KB 
#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, p, h, 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 440 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 2 ms 600 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -