답안 #672264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672264	2022-12-15T09:20:38 Z	Dan4Life	Fireworks (APIO16_fireworks)	C++17	26 / 100	22 ms	1620 KB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int maxn = 5e3+10;
const int LINF = (int)1e18;
int p[maxn], c[maxn];
int n, m, ans;
vector<pair<int,int>> adj[maxn];
int dp[maxn][310];
bool ok[maxn][310];

void dfs(int s, int p){
	if(s>n){ dp[s][0]=0;ok[s][0]=1; return; }
	for(auto cur : adj[s]){
		int u = cur.fi, c = cur.se;
		if(u==p) continue; dfs(u,s);
		for(int i = 0; i <= 300; i++){
			int price = LINF;
			for(int j = 0; j <= i; j++)
				if(ok[u][j]) price = min(price, abs(c-(i-j))+dp[u][j]);
			if(price==LINF) ok[s][i]=false;
			else dp[s][i]+=price;
		}
	}
}

int32_t main() {
	cin >> n >> m; ans=LINF;
	for(int i = 2; i <= n+m; i++){
		cin >> p[i] >> c[i];
		adj[i].pb({p[i],c[i]});
		adj[p[i]].pb({i,c[i]});
	}
	if(n==1){ ans=0; vector<int> v;
		for(int i = n+1; i <= n+m; i++) v.pb(c[i]);
		sort(all(v));  int ans = 0;
		for(auto u : v) ans+=abs(u-v[sz(v)/2]);
		cout << ans; return 0;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 300; j++)
			ok[i][j]=1;
	dfs(1,1);
	for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
}

Compilation message

fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:22:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |   if(u==p) continue; dfs(u,s);
      |   ^~
fireworks.cpp:22:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |   if(u==p) continue; dfs(u,s);
      |                      ^~~
fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:50:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |  for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
      |  ^~~
fireworks.cpp:50:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |  for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
      |                                                                     ^~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	468 KB	Output is correct
3	Correct	3 ms	596 KB	Output is correct
4	Correct	5 ms	596 KB	Output is correct
5	Correct	9 ms	740 KB	Output is correct
6	Correct	6 ms	724 KB	Output is correct
7	Correct	7 ms	852 KB	Output is correct
8	Correct	7 ms	852 KB	Output is correct
9	Correct	8 ms	852 KB	Output is correct
10	Correct	9 ms	980 KB	Output is correct
11	Correct	10 ms	980 KB	Output is correct
12	Correct	11 ms	1108 KB	Output is correct
13	Correct	12 ms	1120 KB	Output is correct
14	Correct	15 ms	1268 KB	Output is correct
15	Correct	13 ms	1188 KB	Output is correct
16	Correct	13 ms	1236 KB	Output is correct
17	Correct	13 ms	1180 KB	Output is correct
18	Correct	13 ms	1240 KB	Output is correct
19	Correct	12 ms	1236 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	3 ms	596 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	9 ms	740 KB	Output is correct
16	Correct	6 ms	724 KB	Output is correct
17	Correct	7 ms	852 KB	Output is correct
18	Correct	7 ms	852 KB	Output is correct
19	Correct	8 ms	852 KB	Output is correct
20	Correct	9 ms	980 KB	Output is correct
21	Correct	10 ms	980 KB	Output is correct
22	Correct	11 ms	1108 KB	Output is correct
23	Correct	12 ms	1120 KB	Output is correct
24	Correct	15 ms	1268 KB	Output is correct
25	Correct	13 ms	1188 KB	Output is correct
26	Correct	13 ms	1236 KB	Output is correct
27	Correct	13 ms	1180 KB	Output is correct
28	Correct	13 ms	1240 KB	Output is correct
29	Correct	12 ms	1236 KB	Output is correct
30	Incorrect	22 ms	1620 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	3 ms	596 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	9 ms	740 KB	Output is correct
16	Correct	6 ms	724 KB	Output is correct
17	Correct	7 ms	852 KB	Output is correct
18	Correct	7 ms	852 KB	Output is correct
19	Correct	8 ms	852 KB	Output is correct
20	Correct	9 ms	980 KB	Output is correct
21	Correct	10 ms	980 KB	Output is correct
22	Correct	11 ms	1108 KB	Output is correct
23	Correct	12 ms	1120 KB	Output is correct
24	Correct	15 ms	1268 KB	Output is correct
25	Correct	13 ms	1188 KB	Output is correct
26	Correct	13 ms	1236 KB	Output is correct
27	Correct	13 ms	1180 KB	Output is correct
28	Correct	13 ms	1240 KB	Output is correct
29	Correct	12 ms	1236 KB	Output is correct
30	Incorrect	22 ms	1620 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #672264

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0