oj.uz

Submission #45145

# Submission time Handle Problem Language Result Execution time Memory
45145 2018-04-11T14:03:36 Z erdemkiraz Fireworks (APIO16_fireworks) C++14
0 / 100
 2000 ms 1784 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -