oj.uz

Submission #636781

# Submission time Handle Problem Language Result Execution time Memory
636781 2022-08-30T07:38:52 Z lovrot Fireworks (APIO16_fireworks) C++11
0 / 100
 2000 ms 1084 KB 
#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define pii pair<int, int> 
#define pb push_back 

using namespace std; 

const int N = 310;
const ll INF = 1e9;

ll abs2(ll x){ 
	return x < 0 ? -x : x;
}

int n, m;
ll dp[N][N], c[N], p[N], calc[N];
ll maxi, dist;

vector<int> g[N];

ll DP(int u, ll d){ 
	if(d < 0 || d > maxi) return INF;
	if(g[u].size() == 0){
		if(d > dist) return INF;
		return abs2(dist - (d + c[u]));
	}
	if(dp[u][d] != -1) return dp[u][d];
	dp[u][d] = INF;
	for(ll dx = 0; dx + d <= dist; dx++){ 
		ll res = abs2(c[u] - dx);
		for(int v : g[u]){ 
			res += DP(v, d + dx);		
		}
		dp[u][d] = min(dp[u][d], res);
	}
	return dp[u][d];
}

int main(){
	ios_base::sync_with_stdio(false);

	scanf("%d%d", &n, &m);

	for(int i = 2; i <= n + m; i++){ 
		scanf("%d%d", &p[i], &c[i]);
		g[p[i]].pb(i);
		calc[i] = calc[p[i]] + c[i];
		maxi = max(maxi, calc[i]);
	}
	ll ans = INF;
	for(dist; dist <= maxi; dist++){ 
		memset(dp, -1, sizeof(dp));
		DP(1, 0);
		ans = min(ans, dp[1][0]);
	}
	printf("%d", ans);
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:48:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |          ~^     ~~~~~
      |           |     |
      |           int*  long long int*
      |          %lld
fireworks.cpp:48:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |            ~^          ~~~~~
      |             |          |
      |             int*       long long int*
      |            %lld
fireworks.cpp:54:6: warning: statement has no effect [-Wunused-value]
   54 |  for(dist; dist <= maxi; dist++){
      |      ^~~~
fireworks.cpp:59:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   59 |  printf("%d", ans);
      |          ~^   ~~~
      |           |   |
      |           int long long int
      |          %lld
fireworks.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 1072 KB Output is correct
2 Correct 763 ms 1084 KB Output is correct
3 Correct 1333 ms 1084 KB Output is correct
4 Correct 346 ms 1084 KB Output is correct
5 Execution timed out 2071 ms 980 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 980 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 2086 ms 980 KB Time limit exceeded
2 Halted 0 ms 0 KB -