#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll maxn=200005;
ll n,m;
ll v[2001];
ll w[2001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
ll sum=0;
ll pos=1;
if (m==1) {
int x,y,z;
cin >> x >> y >> z;
int cur=n/y;
cur=min(cur,z);
cout << x*cur;
return 0;
}
for (ll i=1; i<=m; i++)
{
ll k;
cin >> v[pos] >> w[pos] >> k;
sum+=k;
for (ll j=pos+1; j<pos+k; j++)
{
v[j]=v[pos];
w[j]=w[pos];
}
pos=pos+k;
}
ll dp[sum+4][n+4];
memset(dp,0,sizeof(dp));
for (ll j=1; j<=n; j++)
{
for (ll i=1; i<=sum; i++)
{
dp[i][j]=dp[i-1][j];
if (j-w[i]>=0)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
ll ans=0;
for (ll i=1; i<=n; i++)
{
ans=max(ans,dp[sum][i]);
}
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
2 ms |
1856 KB |
Output is correct |
3 |
Correct |
2 ms |
1840 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
2 ms |
1940 KB |
Output is correct |
8 |
Correct |
2 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
1860 KB |
Output is correct |
10 |
Correct |
2 ms |
1856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
2 ms |
1856 KB |
Output is correct |
3 |
Correct |
2 ms |
1840 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
2 ms |
1940 KB |
Output is correct |
8 |
Correct |
2 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
1860 KB |
Output is correct |
10 |
Correct |
2 ms |
1856 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
16 ms |
15712 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
1 ms |
1876 KB |
Output is correct |
15 |
Correct |
6 ms |
8916 KB |
Output is correct |
16 |
Correct |
7 ms |
8704 KB |
Output is correct |
17 |
Correct |
1 ms |
1864 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
3 ms |
3540 KB |
Output is correct |
20 |
Correct |
4 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
2 ms |
1856 KB |
Output is correct |
7 |
Correct |
2 ms |
1840 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1940 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1860 KB |
Output is correct |
14 |
Correct |
2 ms |
1856 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
16 ms |
15712 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1876 KB |
Output is correct |
19 |
Correct |
6 ms |
8916 KB |
Output is correct |
20 |
Correct |
7 ms |
8704 KB |
Output is correct |
21 |
Correct |
1 ms |
1864 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
3 ms |
3540 KB |
Output is correct |
24 |
Correct |
4 ms |
3412 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
2 ms |
1856 KB |
Output is correct |
7 |
Correct |
2 ms |
1840 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
2 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1940 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1860 KB |
Output is correct |
14 |
Correct |
2 ms |
1856 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
16 ms |
15712 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
1 ms |
1876 KB |
Output is correct |
19 |
Correct |
6 ms |
8916 KB |
Output is correct |
20 |
Correct |
7 ms |
8704 KB |
Output is correct |
21 |
Correct |
1 ms |
1864 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
3 ms |
3540 KB |
Output is correct |
24 |
Correct |
4 ms |
3412 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
27 |
Halted |
0 ms |
0 KB |
- |