#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long int
#define umap unordered_map
#define mod 998244353ll
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MN(a,b,c) min(a,min(b,c))
#define MX(a,b,c) max(a,max(b,c))
#define pr1 pair<ll,ll>
#define F first
#define S second
#define mP make_pair
#define f(i,n) for(ll i=0;i<n;i++)
#define f1(i,x,y) for(ll i=x;i<=y;i++)
#define f2(i,x,y) for(ll i=x;i>=y;i--)
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define modsum(a,b) ((a%mod)+(b%mod))%mod
#define modpro(a,b) ((a%mod)*(b%mod))%mod
#define moddif(a,b) ((a%mod)-(b%mod)+mod)%mod
#define modsumt(a,b,c) modsum(a,modsum(b,c))
// Remove macro of endl in interactive task
// in case of no errors check macros and functions again
//__builtin_popcount(x)
//__builtin_parity(x) =(number of set bits)%2
//__builtin_clz(x) to count the number of leading zeroes
//__builtin_ctz(x) to count the number of trailing zeroes
//__gcd(a,b)
// Binary Search
// TO AVOID GETTING INFINITE LOOP
// mid = (l+r)/2 l=mid+1 r=mid
// mid = (l+r+1)/2 l=mid r=mid-1
//std::cout << std::fixed; std::cout << std::setprecision(12); std::cout << z ;
using namespace std;
bool cmp(pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b)
{
if(a.F == b.F)
{
return a.S.F > b.S.F;
}
else return a.F<b.F;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll s,n;cin>>s>>n;
vector <pair<ll,pair<ll,ll>>> v(n);
f(i,n)
{
ll val,wei,freq;
cin>>val>>wei>>freq;
v[i]={wei,{val,freq}};
}
vector <ll> dp(s+1,-1);
dp[0]=0;
sort(all(v),cmp);
ll c=0;
f(i,n)
{
ll wei=v[i].F;
ll val=v[i].S.F;
ll freq=v[i].S.S;
ll lim = s/wei;
if(i>0 && v[i].F==v[i-1].F)
{
freq=min(freq,lim-c);
c+=freq;
}
else
{
c=freq;
freq=min(freq,lim);
}
if(freq>0)
{
for(ll j=s;j>=0;j--)
{
ll c=1,VAL=val,WEI=wei;
while(c<=freq && WEI<=j)
{
if(dp[j-WEI]!=-1) dp[j]=max(dp[j],dp[j-WEI]+VAL);
VAL+=val;
WEI+=wei;
c++;
}
}
}
}
ll ans=0;
f(i,s+1) ans=max(ans,dp[i]);
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
2 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
316 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
320 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
316 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
320 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
320 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
316 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
3 ms |
320 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
27 ms |
3656 KB |
Output is correct |
36 |
Correct |
31 ms |
3948 KB |
Output is correct |
37 |
Correct |
31 ms |
3744 KB |
Output is correct |
38 |
Correct |
28 ms |
3936 KB |
Output is correct |
39 |
Correct |
32 ms |
4684 KB |
Output is correct |
40 |
Correct |
50 ms |
4704 KB |
Output is correct |
41 |
Correct |
52 ms |
3944 KB |
Output is correct |
42 |
Correct |
52 ms |
3924 KB |
Output is correct |
43 |
Correct |
57 ms |
3924 KB |
Output is correct |
44 |
Correct |
53 ms |
3924 KB |
Output is correct |
45 |
Correct |
35 ms |
4712 KB |
Output is correct |
46 |
Correct |
25 ms |
4600 KB |
Output is correct |
47 |
Correct |
36 ms |
4704 KB |
Output is correct |
48 |
Correct |
41 ms |
4724 KB |
Output is correct |
49 |
Correct |
26 ms |
4416 KB |
Output is correct |
50 |
Correct |
41 ms |
4588 KB |
Output is correct |