제출 #40883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40883		IvanC	Fireworks (APIO16_fireworks)	C++14	26 / 100	63 ms	2304 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 310;
const ll INF = 1e9;
ll N,M,cost;
vector<ll> ordenado,grafo[MAXN],pesos[MAXN];
ll dp[MAXN][MAXN];
ll tenta(ll custo){
	ll tot = 0;
	for(ll val : ordenado) tot += abs(val - custo);
	return tot;
}
ll solve(ll v,ll dist){
	if(dp[v][dist] != -1) return dp[v][dist];
	if(v >= N + 1 && dist != 0) return INF;
	ll tot = 0;
	for(ll i = 0;i<grafo[v].size();i++){
		ll u = grafo[v][i],percorre = pesos[v][i];
		ll best = INF;
		for(ll novo = 0;novo<=dist;novo++){
			best = min(best, abs(percorre - novo) + solve(u,dist - novo) );
		}
		tot += best;
	}
	return dp[v][dist] = tot;
}
int main(){
	cin >> N >> M;
	if(N == 1){
		for(ll i = 2;i<=N+M;i++){
			ll p,c;
			cin >> p >> c;
			if(p == 1){
				ordenado.push_back(c);
			}
			else{
				cost += c;
			}
		}
		ll best = tenta(ordenado[0]);
		for(ll i = 1;i<=ordenado.size();i++) best = min(best, tenta(ordenado[i]) );
		cout << cost + best << endl;
		return 0;
	}
	for(ll i = 2;i<=N+M;i++){
		ll p,c;
		cin >> p >> c;
		grafo[p].push_back(i);
		pesos[p].push_back(c);
	}
	memset(dp,-1,sizeof(dp));
	ll best = solve(1,0);
	for(ll dist = 1;dist<=300;dist++) best = min(best, solve(1,dist) );
	cout << best << endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In function 'll solve(ll, ll)':
fireworks.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0;i<grafo[v].size();i++){
                ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i = 1;i<=ordenado.size();i++) best = min(best, tenta(ordenado[i]) );
                 ^

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45