oj.uz

Submission #40883

# Submission time Handle Problem Language Result Execution time Memory
40883 2018-02-09T16:29:39 Z IvanC Fireworks (APIO16_fireworks) C++14
26 / 100
 63 ms 2304 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 1 ms 656 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1240 KB Output is correct
2 Correct 8 ms 1240 KB Output is correct
3 Correct 13 ms 1248 KB Output is correct
4 Correct 14 ms 1380 KB Output is correct
5 Correct 20 ms 1384 KB Output is correct
6 Correct 22 ms 1384 KB Output is correct
7 Correct 25 ms 1396 KB Output is correct
8 Correct 29 ms 1404 KB Output is correct
9 Correct 32 ms 1408 KB Output is correct
10 Correct 37 ms 1408 KB Output is correct
11 Correct 37 ms 1408 KB Output is correct
12 Correct 43 ms 1408 KB Output is correct
13 Correct 63 ms 1408 KB Output is correct
14 Correct 40 ms 1408 KB Output is correct
15 Correct 48 ms 1408 KB Output is correct
16 Correct 61 ms 1408 KB Output is correct
17 Correct 48 ms 1532 KB Output is correct
18 Correct 48 ms 1532 KB Output is correct
19 Correct 50 ms 1532 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 1 ms 656 KB Output is correct
11 Correct 4 ms 1240 KB Output is correct
12 Correct 8 ms 1240 KB Output is correct
13 Correct 13 ms 1248 KB Output is correct
14 Correct 14 ms 1380 KB Output is correct
15 Correct 20 ms 1384 KB Output is correct
16 Correct 22 ms 1384 KB Output is correct
17 Correct 25 ms 1396 KB Output is correct
18 Correct 29 ms 1404 KB Output is correct
19 Correct 32 ms 1408 KB Output is correct
20 Correct 37 ms 1408 KB Output is correct
21 Correct 37 ms 1408 KB Output is correct
22 Correct 43 ms 1408 KB Output is correct
23 Correct 63 ms 1408 KB Output is correct
24 Correct 40 ms 1408 KB Output is correct
25 Correct 48 ms 1408 KB Output is correct
26 Correct 61 ms 1408 KB Output is correct
27 Correct 48 ms 1532 KB Output is correct
28 Correct 48 ms 1532 KB Output is correct
29 Correct 50 ms 1532 KB Output is correct
30 Runtime error 4 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 1 ms 656 KB Output is correct
10 Correct 1 ms 656 KB Output is correct
11 Correct 4 ms 1240 KB Output is correct
12 Correct 8 ms 1240 KB Output is correct
13 Correct 13 ms 1248 KB Output is correct
14 Correct 14 ms 1380 KB Output is correct
15 Correct 20 ms 1384 KB Output is correct
16 Correct 22 ms 1384 KB Output is correct
17 Correct 25 ms 1396 KB Output is correct
18 Correct 29 ms 1404 KB Output is correct
19 Correct 32 ms 1408 KB Output is correct
20 Correct 37 ms 1408 KB Output is correct
21 Correct 37 ms 1408 KB Output is correct
22 Correct 43 ms 1408 KB Output is correct
23 Correct 63 ms 1408 KB Output is correct
24 Correct 40 ms 1408 KB Output is correct
25 Correct 48 ms 1408 KB Output is correct
26 Correct 61 ms 1408 KB Output is correct
27 Correct 48 ms 1532 KB Output is correct
28 Correct 48 ms 1532 KB Output is correct
29 Correct 50 ms 1532 KB Output is correct
30 Runtime error 4 ms 2304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -