oj.uz

Submission #793288

# Submission time Handle Problem Language Result Execution time Memory
793288 2023-07-25T17:22:38 Z ToniB Fireworks (APIO16_fireworks) C++17
19 / 100
 87 ms 1484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 505;

int n, m, L[MAXN], R[MAXN];
vector<pair<int, int> > adj[MAXN];
ll walk[MAXN], dp[MAXN][MAXN];

void precalc(int node){
	for(pair<int, int> x : adj[node]){
		walk[x.first] = walk[node] + x.second;
		precalc(x.first);
	}
}

void dfs(int node){
	if(node >= n){
		for(int i = 0; i < MAXN; ++i) dp[node][i] = 1e9;
		dp[node][walk[node]] = 0;
	}
	for(pair<int, int> x : adj[node]){
		dfs(x.first);
		for(int i = 0; i < MAXN; ++i){
			ll mini = 1e9;
			for(int j = 0; j < MAXN; ++j){
				if(x.second + i - j >= 0) mini = min(mini, dp[x.first][j] + abs(i - j));
			}
			dp[node][i] += mini;
		}
	}
}

int main(){
	cin >> n >> m;
	for(int i = 1; i < n + m; ++i){
		int p, c;
		cin >> p >> c, --p;
		adj[p].push_back({i, c});
	}
	precalc(0);

	dfs(0);
	ll ans = 1e9;
	for(int i = 0; i < MAXN; ++i) ans = min(ans, dp[0][i]);
	bool found = 0;
	for(int i = n; i < n + m; ++i){
		if(dp[0][walk[i]] == ans) found = 1;
	}
	assert(found);
	cout << ans;
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 15 ms 492 KB Output is correct
4 Correct 27 ms 632 KB Output is correct
5 Correct 29 ms 680 KB Output is correct
6 Correct 37 ms 756 KB Output is correct
7 Correct 39 ms 864 KB Output is correct
8 Correct 64 ms 984 KB Output is correct
9 Correct 46 ms 1048 KB Output is correct
10 Correct 50 ms 1156 KB Output is correct
11 Correct 57 ms 1188 KB Output is correct
12 Correct 61 ms 1316 KB Output is correct
13 Correct 64 ms 1256 KB Output is correct
14 Correct 75 ms 1376 KB Output is correct
15 Correct 87 ms 1484 KB Output is correct
16 Correct 72 ms 1448 KB Output is correct
17 Correct 72 ms 1400 KB Output is correct
18 Correct 71 ms 1408 KB Output is correct
19 Correct 71 ms 1460 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -