답안 #401646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401646	2021-05-10T15:49:33 Z	BERNARB01	Fireworks (APIO16_fireworks)	C++17	컴파일 오류	0 ms	0 KB

fireworks

#include <bits/stdc++.h>

using namespace std;

const int N = 5001;
const long long inf = (long long) 4e18L;

int n, m;
vector<pair<int, long long>> g[N];
long long dp[N][302];

long long sol(int u, int left) {
	if (g[u].size() == 0) {
		assert(left == 0);
		return 0;
	}
	long long& ret = dp[u][left];
	if (ret != -1) {
		return ret;
	}
	ret = 0;
	for (pair<int, long long> _p : g[u]) {
		long long sub = inf;
		int v = _p.first;
		long long w = _p.second;
		if (g[v].size() == 0) {
			sub = abs(w - left);
			ret += sub;
			continue;
		}
		for (int j = 0; j <= left; j++) {
			sub = min(sub, abs(w - j) + sol(v, left - j));
		}
		ret += sub;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	if (n == 1) {
		vector<long long> cs;
		for (int i = 1; i < n + m; i++) {
			int p;
			long long c;
			cin >> p >> c;
			cs.emplace_back(c);
		}
		sort(cs.begin(), cs.end());
		long long loc = cs[cs.size() / 2];
		long long ans = 0;
		for (int i = 0; i < (int) cs.size(); i++) {
			ans += abs(loc - cs[i]);
		}
		cout << ans << '\n';
		return 0;
	}
	long long res = 0;
	for (int i = 1; i < n + m; i++) {
		int p;
		long long c;
		cin >> p >> c;
		g[p - 1].emplace_back(i, c);
		res += c;
	}
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < 301; i++) {
		res = min(res, sol(0, i));
	}
	cout << res << '\n';
	return 0;
}
#include <bits/stdc++.h>

using namespace std;

const int N = 5001;
const long long inf = (long long) 4e18L;

int n, m;
vector<pair<int, long long>> g[N];
long long dp[N][302];

long long sol(int u, int left) {
	if (g[u].size() == 0) {
		assert(left == 0);
		return 0;
	}
	long long& ret = dp[u][left];
	if (ret != -1) {
		return ret;
	}
	ret = 0;
	for (pair<int, long long> _p : g[u]) {
		long long sub = inf;
		int v = _p.first;
		long long w = _p.second;
		if (g[v].size() == 0) {
			sub = abs(w - left);
			ret += sub;
			continue;
		}
		for (int j = 0; j <= left; j++) {
			sub = min(sub, abs(w - j) + sol(v, left - j));
		}
		ret += sub;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	if (n == 1) {
		vector<long long> cs;
		for (int i = 1; i < n + m; i++) {
			int p;
			long long c;
			cin >> p >> c;
			cs.emplace_back(c);
		}
		sort(cs.begin(), cs.end());
		long long loc = cs[cs.size() / 2];
		long long ans = 0;
		for (int i = 0; i < (int) cs.size(); i++) {
			ans += abs(loc - cs[i]);
		}
		cout << ans << '\n';
		return 0;
	}
	long long res = 0;
	for (int i = 1; i < n + m; i++) {
		int p;
		long long c;
		cin >> p >> c;
		g[p - 1].emplace_back(i, c);
		res += c;
	}
	memset(dp, -1, sizeof dp);
	for (int i = 0; i < 301; i++) {
		res = min(res, sol(0, i));
	}
	cout << res << '\n';
	return 0;
}

Compilation message

fireworks.cpp:79:11: error: redefinition of 'const int N'
   79 | const int N = 5001;
      |           ^
fireworks.cpp:5:11: note: 'const int N' previously defined here
    5 | const int N = 5001;
      |           ^
fireworks.cpp:80:17: error: redefinition of 'const long long int inf'
   80 | const long long inf = (long long) 4e18L;
      |                 ^~~
fireworks.cpp:6:17: note: 'const long long int inf' previously defined here
    6 | const long long inf = (long long) 4e18L;
      |                 ^~~
fireworks.cpp:82:5: error: redefinition of 'int n'
   82 | int n, m;
      |     ^
fireworks.cpp:8:5: note: 'int n' previously declared here
    8 | int n, m;
      |     ^
fireworks.cpp:82:8: error: redefinition of 'int m'
   82 | int n, m;
      |        ^
fireworks.cpp:8:8: note: 'int m' previously declared here
    8 | int n, m;
      |        ^
fireworks.cpp:83:30: error: redefinition of 'std::vector<std::pair<int, long long int> > g [5001]'
   83 | vector<pair<int, long long>> g[N];
      |                              ^
fireworks.cpp:9:30: note: 'std::vector<std::pair<int, long long int> > g [5001]' previously declared here
    9 | vector<pair<int, long long>> g[N];
      |                              ^
fireworks.cpp:84:11: error: redefinition of 'long long int dp [5001][302]'
   84 | long long dp[N][302];
      |           ^~
fireworks.cpp:10:11: note: 'long long int dp [5001][302]' previously declared here
   10 | long long dp[N][302];
      |           ^~
fireworks.cpp:86:11: error: redefinition of 'long long int sol(int, int)'
   86 | long long sol(int u, int left) {
      |           ^~~
fireworks.cpp:12:11: note: 'long long int sol(int, int)' previously defined here
   12 | long long sol(int u, int left) {
      |           ^~~
fireworks.cpp:113:5: error: redefinition of 'int main()'
  113 | int main() {
      |     ^~~~
fireworks.cpp:39:5: note: 'int main()' previously defined here
   39 | int main() {
      |     ^~~~