oj.uz

Submission #45147

# Submission time Handle Problem Language Result Execution time Memory
45147 2018-04-11T14:21:20 Z erdemkiraz Fireworks (APIO16_fireworks) C++11
0 / 100
 5 ms 456 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 300 + 5;

int n, m;
vector < ii > v[N];
int dp[N][N], dp2[N];

void dfs(int x) {
	for(auto u : v[x])
		dfs(u.first);
	if(x > n) {
		for(int i = 1; i < N; i++)
			dp[x][i] = 1e9;
		return;
	}
	for(auto u : v[x]) {
		for(int i = 0; i < N; i++)
			dp2[i] = 1e9;
		for(int i = 0; i < N; i++)
			for(int j = -N; j < N; j++)
				if(u.second + j >= 0 and i + j + u.second < N)
					dp2[i + j + u.second] = min(dp2[i + j + u.second], dp[u.first][i] + abs(j));
		for(int i = 0; i < N; i++)
			dp[x][i] += dp2[i];
	}
}

int main() {

	scanf("%d %d", &n, &m);

	for(int i = 2; i <= n + m; i++) {
		int x, c;
		scanf("%d %d", &x, &c);
		v[x].push_back({i, c});
	}

	dfs(1);

	int res = 1e9;

	for(int i = 0; i <= 600; i++) {
		res = min(res, dp[1][i]);
	}

	printf("%d\n", res);

    return 0;

}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &c);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -