Submission #45145

#	Time	Username	Problem	Language	Result	Execution time	Memory
45145		erdemkiraz	Fireworks (APIO16_fireworks)	C++14	0 / 100	2061 ms	1784 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;

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

const int N = 600 + 5;

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

int f(int x, int k) {
	if(k < 0)
		return 1e9;
	if(x > n) {
		return k ? 1e9 : 0;
	}
	int &r = dp[x][k];
	if(r != -1) return r;
	r = 0;
	for(auto u : v[x]) {
		int res = 1e9;
		for(int i = -u.second; i <= 600 - (k - u.second); i++) {
			res = min(res, f(u.first, k + i - u.second) + abs(i));
		}
		r = min((int)1e9, r + res);
	}
	return r;
}

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});
	}

	memset(dp, -1, sizeof(dp));

	int res = 1e9;

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

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

    return 0;

}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:35: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:39: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
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45