Submission #65093

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<bool> vbl;
int inf=(1LL<<31)-1;
int MOD=1000000007;
#define fi(a,b) for(int i=a;i<b;i++)
#define fj(a,b) for(int j=a;j<b;j++)
#define f_i(a,b) for(int i=a;i<=b;i++)
#define f_j(a,b) for(int j=a;j<=b;j++)
#define vvii(c,a,b) vector<vector<ii>> c(a,vector<ii>(b,0))
#define vvll(c,a,b) vector<vector<ll>> c(a,vector<ll>(b,0))
#define vvstr(c,a,b) vector<vector<string> c(a,vector<string>(b,0))
#define vvbol(c,a,b) vector<vector<bool>> c(a,vector<bool>(b,true))
#define bgen(c) c.begin(),c.end()
signed main()
{
// flfkdllfkdldkflldkslldksllskdllskdlskdllskdllskkdlskkdlskkdlskkdlskkdldksldkksldkksldk
///////高速化///////
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
///////////////////
vector<ll> w(10100,0);
vector<ll> v(10100,0);
vector<vector<ll>> dp(1100,vector<ll>(10100,0));
int n,h;
cin >> n >> h;
for(int i=0;i<n;i++)
{
cin >> v.at(i) >> w.at(i);
}
for(int i=0;i<h;i++)
{
dp.at(0).at(i)=0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=h;j++)
{
if(j>=w.at(i))
{
dp.at(i+1).at(j)=max(dp.at(i).at(j-w.at(i))+v.at(i),dp.at(i).at(j));
}
else
{
dp.at(i+1).at(j)=dp.at(i).at(j);
}
}
}
cout << dp.at(n).at(h) << endl;
return(0);
}

ステータス

項目 データ
問題 0238 - ナップザック問題(Easy)
ユーザー名 <span style="color:#000000;font-weight:bold;">ei2031</span>
投稿日時 2020-12-22 15:49:37
言語 C++17
状態 Accepted
得点 3
ソースコード長 1607 Byte
最大実行時間 104 ms
最大メモリ使用量 87916 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 85 ms 87640 KB
1
DPL_1_B_in2.txt AC 67 ms 87528 KB
1
DPL_1_B_in3.txt AC 67 ms 87808 KB
1
DPL_1_B_in4.txt AC 91 ms 87908 KB
1
DPL_1_B_in5.txt AC 69 ms 87824 KB
1
DPL_1_B_in6.txt AC 104 ms 87872 KB
1
DPL_1_B_in7.txt AC 66 ms 87916 KB
1
DPL_1_B_in8.txt AC 62 ms 87840 KB
1
DPL_1_B_in9.txt AC 61 ms 87884 KB
1
DPL_1_B_in10.txt AC 69 ms 87432 KB
1
DPL_1_B_in11.txt AC 66 ms 87476 KB
1
DPL_1_B_in12.txt AC 68 ms 87524 KB
1
DPL_1_B_in13.txt AC 75 ms 87576 KB
1
DPL_1_B_in14.txt AC 69 ms 87624 KB
1
DPL_1_B_in15.txt AC 70 ms 87672 KB
1
DPL_1_B_in16.txt AC 63 ms 87724 KB
1
DPL_1_B_in17.txt AC 67 ms 87772 KB
1
DPL_1_B_in18.txt AC 58 ms 87692 KB
1
DPL_1_B_in19.txt AC 62 ms 87736 KB
1
DPL_1_B_in20.txt AC 80 ms 87576 KB
1
DPL_1_B_in21.txt AC 69 ms 87752 KB
1
DPL_1_B_in22.txt AC 66 ms 87804 KB
1
DPL_1_B_in23.txt AC 66 ms 87724 KB
1
DPL_1_B_in24.txt AC 68 ms 87772 KB
1
DPL_1_B_in25.txt AC 69 ms 87692 KB
1
DPL_1_B_in26.txt AC 75 ms 87736 KB
1
DPL_1_B_in27.txt AC 72 ms 87788 KB
1
DPL_1_B_in28.txt AC 75 ms 87708 KB
1
DPL_1_B_in29.txt AC 69 ms 87884 KB
1
DPL_1_B_in30.txt AC 61 ms 87860 KB
1
DPL_1_B_in31.txt AC 63 ms 87776 KB
1
DPL_1_B_in32.txt AC 67 ms 87816 KB
1
DPL_1_B_in33.txt AC 62 ms 87728 KB
1
DPL_1_B_in34.txt AC 65 ms 87772 KB
1
DPL_1_B_in35.txt AC 64 ms 87816 KB
1
DPL_1_B_in36.txt AC 69 ms 87736 KB
1