# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
821769 |
2023-08-11T16:01:15 Z |
Zobio |
Knapsack (NOI18_knapsack) |
C++14 |
|
52 ms |
36288 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef long double ld;
typedef vector<double> vd;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef set<int> si;
typedef set<ll> sl;
#define all(c) (c).begin(),(c).end()
#define srt(c) sort(all(c))
#define srtrev(c) sort(all(c)); reverse(all(c))
#define fr(i,a,n) for( int i=a;i<n;i++)
#define frev(i,a,n) for( int i=a;i>=n;i--)
#define inp(ve) for(int i=0;i<ve.size();i++) cin>>ve[i];
#define PB push_back
#define F first
#define S second
#define cont continue
#define br break
#define MP make_pair
#define nl cout<<"\n"
#define M 1000000007
const ll INF = 1e17;
const ll NINF = -1e17;
const int N = 1e6+1;
int lindieq (int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = lindieq(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
ll gcd (ll c, ll d) {
ll a = max(c,d);
ll b = min(c,d);
while (b) {
a %= b;
ll temp = a;
a=b;
b=temp;
}
return a;
}
ll bexp(ll a,ll b){
ll res = 1;
while(b>0){
if(b%2) res = res*a;
a*=a;
b/=2;
}
return res;
}
vb isprime(int n){
vector<bool> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
return is_prime;
}
ll bexpm(ll a,ll b){
ll res = 1;
while(b>0){
if(b%2) res = (res*a)%M;
a = (a*a)%M;
b/=2;
}
return res;
}
// int par[N];
// int r[N];
// int find(int a){
// if(par[a]==a) return a;
// else return par[a] = find(par[a]);
// }
// bool isSame(int a, int b){
// return find(a)==find(b);
// }
// void unite(int a, int b){
// a = find(a);
// b = find(b);
// if(r[a]>=r[b]){
// par[b] = a;
// r[a]+=r[b];
// }else{
// par[a] = b;
// r[b]+=r[a];
// }
// }
map<int,vpl> mp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
int s,n;
cin>>s>>n;
vector<vpl> w(s+1);
fr(i,0,n){
int cost,weig,feq;
cin>>cost>>weig>>feq;
w[weig].push_back({cost,feq});
}
fr(i,1,s+1){
srt(w[i]);
reverse(all(w[i]));
}
vvl dp(s+1,vl(s+1,0));
fr(i,1,s+1){
dp[i] = dp[i-1];
ll cs = 0;
ll we = 0;
int ma = s/i;
for(auto it : w[i]){
while(it.second && ma){
cs+=it.first;
we+=i;
ma--;
it.second--;
for(int j = we;j<=s;j++){
dp[i][j] = max(dp[i][j],dp[i-1][j-we]+cs);
}
}
if(ma==0) break;
}
}
ll ans = 0;
fr(i,1,s+1){
ans = max(dp[s][i],ans);
}
cout<<ans;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12220 KB |
Output is correct |
2 |
Correct |
5 ms |
12348 KB |
Output is correct |
3 |
Correct |
5 ms |
12244 KB |
Output is correct |
4 |
Correct |
5 ms |
12212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
15 ms |
31744 KB |
Output is correct |
3 |
Correct |
15 ms |
31680 KB |
Output is correct |
4 |
Correct |
16 ms |
31572 KB |
Output is correct |
5 |
Correct |
14 ms |
31572 KB |
Output is correct |
6 |
Correct |
13 ms |
31784 KB |
Output is correct |
7 |
Correct |
14 ms |
31700 KB |
Output is correct |
8 |
Correct |
17 ms |
31680 KB |
Output is correct |
9 |
Correct |
14 ms |
31616 KB |
Output is correct |
10 |
Correct |
13 ms |
31728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
15 ms |
31744 KB |
Output is correct |
3 |
Correct |
15 ms |
31680 KB |
Output is correct |
4 |
Correct |
16 ms |
31572 KB |
Output is correct |
5 |
Correct |
14 ms |
31572 KB |
Output is correct |
6 |
Correct |
13 ms |
31784 KB |
Output is correct |
7 |
Correct |
14 ms |
31700 KB |
Output is correct |
8 |
Correct |
17 ms |
31680 KB |
Output is correct |
9 |
Correct |
14 ms |
31616 KB |
Output is correct |
10 |
Correct |
13 ms |
31728 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
15 ms |
31776 KB |
Output is correct |
13 |
Correct |
13 ms |
31700 KB |
Output is correct |
14 |
Correct |
14 ms |
31740 KB |
Output is correct |
15 |
Correct |
13 ms |
31640 KB |
Output is correct |
16 |
Correct |
16 ms |
31684 KB |
Output is correct |
17 |
Correct |
14 ms |
31616 KB |
Output is correct |
18 |
Correct |
14 ms |
31700 KB |
Output is correct |
19 |
Correct |
13 ms |
31772 KB |
Output is correct |
20 |
Correct |
16 ms |
31700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12220 KB |
Output is correct |
2 |
Correct |
5 ms |
12348 KB |
Output is correct |
3 |
Correct |
5 ms |
12244 KB |
Output is correct |
4 |
Correct |
5 ms |
12212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
15 ms |
31744 KB |
Output is correct |
7 |
Correct |
15 ms |
31680 KB |
Output is correct |
8 |
Correct |
16 ms |
31572 KB |
Output is correct |
9 |
Correct |
14 ms |
31572 KB |
Output is correct |
10 |
Correct |
13 ms |
31784 KB |
Output is correct |
11 |
Correct |
14 ms |
31700 KB |
Output is correct |
12 |
Correct |
17 ms |
31680 KB |
Output is correct |
13 |
Correct |
14 ms |
31616 KB |
Output is correct |
14 |
Correct |
13 ms |
31728 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
15 ms |
31776 KB |
Output is correct |
17 |
Correct |
13 ms |
31700 KB |
Output is correct |
18 |
Correct |
14 ms |
31740 KB |
Output is correct |
19 |
Correct |
13 ms |
31640 KB |
Output is correct |
20 |
Correct |
16 ms |
31684 KB |
Output is correct |
21 |
Correct |
14 ms |
31616 KB |
Output is correct |
22 |
Correct |
14 ms |
31700 KB |
Output is correct |
23 |
Correct |
13 ms |
31772 KB |
Output is correct |
24 |
Correct |
16 ms |
31700 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
15 ms |
31700 KB |
Output is correct |
27 |
Correct |
13 ms |
31700 KB |
Output is correct |
28 |
Correct |
13 ms |
31700 KB |
Output is correct |
29 |
Correct |
13 ms |
31664 KB |
Output is correct |
30 |
Correct |
14 ms |
31664 KB |
Output is correct |
31 |
Correct |
14 ms |
31700 KB |
Output is correct |
32 |
Correct |
13 ms |
31680 KB |
Output is correct |
33 |
Correct |
13 ms |
31572 KB |
Output is correct |
34 |
Correct |
14 ms |
31700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12220 KB |
Output is correct |
2 |
Correct |
5 ms |
12348 KB |
Output is correct |
3 |
Correct |
5 ms |
12244 KB |
Output is correct |
4 |
Correct |
5 ms |
12212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
15 ms |
31744 KB |
Output is correct |
7 |
Correct |
15 ms |
31680 KB |
Output is correct |
8 |
Correct |
16 ms |
31572 KB |
Output is correct |
9 |
Correct |
14 ms |
31572 KB |
Output is correct |
10 |
Correct |
13 ms |
31784 KB |
Output is correct |
11 |
Correct |
14 ms |
31700 KB |
Output is correct |
12 |
Correct |
17 ms |
31680 KB |
Output is correct |
13 |
Correct |
14 ms |
31616 KB |
Output is correct |
14 |
Correct |
13 ms |
31728 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
15 ms |
31776 KB |
Output is correct |
17 |
Correct |
13 ms |
31700 KB |
Output is correct |
18 |
Correct |
14 ms |
31740 KB |
Output is correct |
19 |
Correct |
13 ms |
31640 KB |
Output is correct |
20 |
Correct |
16 ms |
31684 KB |
Output is correct |
21 |
Correct |
14 ms |
31616 KB |
Output is correct |
22 |
Correct |
14 ms |
31700 KB |
Output is correct |
23 |
Correct |
13 ms |
31772 KB |
Output is correct |
24 |
Correct |
16 ms |
31700 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
15 ms |
31700 KB |
Output is correct |
27 |
Correct |
13 ms |
31700 KB |
Output is correct |
28 |
Correct |
13 ms |
31700 KB |
Output is correct |
29 |
Correct |
13 ms |
31664 KB |
Output is correct |
30 |
Correct |
14 ms |
31664 KB |
Output is correct |
31 |
Correct |
14 ms |
31700 KB |
Output is correct |
32 |
Correct |
13 ms |
31680 KB |
Output is correct |
33 |
Correct |
13 ms |
31572 KB |
Output is correct |
34 |
Correct |
14 ms |
31700 KB |
Output is correct |
35 |
Correct |
22 ms |
3368 KB |
Output is correct |
36 |
Correct |
37 ms |
34632 KB |
Output is correct |
37 |
Correct |
37 ms |
34348 KB |
Output is correct |
38 |
Correct |
35 ms |
34728 KB |
Output is correct |
39 |
Correct |
39 ms |
35320 KB |
Output is correct |
40 |
Correct |
52 ms |
36120 KB |
Output is correct |
41 |
Correct |
40 ms |
35276 KB |
Output is correct |
42 |
Correct |
41 ms |
35336 KB |
Output is correct |
43 |
Correct |
45 ms |
35304 KB |
Output is correct |
44 |
Correct |
44 ms |
35176 KB |
Output is correct |
45 |
Correct |
41 ms |
36160 KB |
Output is correct |
46 |
Correct |
41 ms |
35272 KB |
Output is correct |
47 |
Correct |
39 ms |
36288 KB |
Output is correct |
48 |
Correct |
42 ms |
36028 KB |
Output is correct |
49 |
Correct |
37 ms |
35640 KB |
Output is correct |
50 |
Correct |
43 ms |
35312 KB |
Output is correct |