oj.uz

Submission #261949

# Submission time Handle Problem Language Result Execution time Memory
261949 2020-08-12T08:23:27 Z Saboon Fireworks (APIO16_fireworks) C++14
0 / 100
 2000 ms 5996 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5000 + 10;
const ll inf = 1e18;

vector<pair<int,int>> t[maxn];
ll dp[maxn][maxn];
int lo[maxn], r[maxn];

void dfs(int v){
	if (t[v].empty()){
		dp[v][0] = 0;
		for (int j = 1; j < maxn; j++)
			dp[v][j] = inf;
		return;
	}
	for (auto [u,c] : t[v]){
		dfs(u);
		for (int i = 0; i < maxn; i++){
			ll now = inf;
			for (int j = 0; j <= i; j++)
				now = min(now, dp[u][j] + abs(i-j-c));
			dp[v][i] += now;
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 2; i <= n+m; i++){
		int v, c;
		cin >> v >> c;
		t[v].push_back({i,c});
	}
	dfs(1);
	ll answer = inf;
	for (int i = 0; i < maxn; i++)
		answer = min(answer, dp[1][i]);
	cout << answer << endl;
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:18:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [u,c] : t[v]){
            ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 940 KB Output is correct
2 Correct 542 ms 2040 KB Output is correct
3 Correct 906 ms 2936 KB Output is correct
4 Correct 1444 ms 4308 KB Output is correct
5 Correct 1806 ms 4996 KB Output is correct
6 Execution timed out 2029 ms 5996 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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