Submission #00222

ソースコード

?
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
class DisjointSet {
public:
vector<int> rank, p;
DisjointSet() {}
DisjointSet(int size) {
rank.resize(size, 0);
p.resize(size, 0);
for(int i=0;i<size;i++)makeSet(i);
}
void makeSet(int x) {
p[x] = x;
rank[x] = 0;
}
bool same(int x, int y){
return findSet(x) == findSet(y);
}
void unite(int x, int y){
link(findSet(x), findSet(y));
}
void link(int x, int y) {
if(rank[x] > rank[y]){
p[y] = x;
} else {
p[x] = y;
if(rank[x] == rank[y]){
rank[y]++;
}
}
}
int findSet(int x){
if(x != p[x]){
p[x] = findSet(p[x]);
}
return p[x];
}
};
int n, m, l;
int cost[111], happy[111];
DisjointSet ds = DisjointSet(111);
int dp[111][11111];
int slv(int now, int num);
int main(){
ios_base::sync_with_stdio(false);
for(int i=0;i<111;i++){
for(int j=0;j<11111;j++){
dp[i][j] = -1;
}
}
cin >> n >> m >> l;
for(int i=1;i<=n;i++){
cin >> cost[i] >> happy[i];
}
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
ds.unite(a, b);
}
cout << slv(1, 0) << endl;
return 0;
}
int slv(int now, int num){
if(now > n){
return 0;
}
if(dp[now][num] != -1){
return dp[now][num];
}
if(ds.same(1, now)){
if(num + cost[now] > l){
return dp[now][num] = (slv(now + 1, num));
}
return dp[now][num] = (max(slv(now, num+cost[now]) + happy[now], max(slv(now+1, num+cost[now]) + happy[now], slv(now+1, num))));
}
return dp[now][num] = (slv(now + 1, num));
}

ステータス

項目 データ
問題 0008 - 試食
ユーザー名 Xyca.
投稿日時 2018-11-24 15:36:29
言語 C++14
状態 Accepted
得点 400
ソースコード長 1923 Byte
最大実行時間 40 ms
最大メモリ使用量 7196 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.in AC 24 ms 5980 KB
1
input02.in AC 24 ms 5848 KB
1
input03.in AC 22 ms 5840 KB
1
input04.in AC 30 ms 5884 KB
1
input05.in AC 23 ms 5420 KB
1
input06.in AC 32 ms 6748 KB
1
input07.in AC 25 ms 5512 KB
1
input08.in AC 25 ms 5884 KB
1
input09.in AC 31 ms 6412 KB
1
input10.in AC 32 ms 6308 KB
1
input11.in AC 34 ms 5976 KB
1
input12.in AC 32 ms 5404 KB
1
input13.in AC 35 ms 5896 KB
1
input14.in AC 40 ms 7124 KB
1
input15.in AC 26 ms 5620 KB
1
input16.in AC 30 ms 6172 KB
1
input17.in AC 28 ms 5556 KB
1
input18.in AC 32 ms 6208 KB
1
input19.in AC 30 ms 6192 KB
1
input20.in AC 39 ms 7196 KB
1
sample.in AC 23 ms 5484 KB
1