oj.uz

Submission #636833

# Submission time Handle Problem Language Result Execution time Memory
636833 2022-08-30T09:50:50 Z lovrot Fireworks (APIO16_fireworks) C++11
0 / 100
 2000 ms 1088 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<ll> v;
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]);
		if(i > n) v.pb(calc[i]);
	}

	sort(v.begin(), v.end());

	if(v.size() == 1){ 
		printf("0\n");
	} else {
		dist = v[v.size() / 2];
		// printf("%d %d +\n", v[v.size() / 2], v[(v.size() - 1)/ 2]);
		memset(dp, -1, sizeof(dp));
		ll ans = DP(1, 0);;
		dist = v[(v.size() - 1)/ 2];
		memset(dp, -1, sizeof(dp));
		ans = min(ans, DP(1, 0));
		printf("%d", ans);
	}
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:49:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   49 |   scanf("%d%d", &p[i], &c[i]);
      |          ~^     ~~~~~
      |           |     |
      |           int*  long long int*
      |          %lld
fireworks.cpp:49:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   49 |   scanf("%d%d", &p[i], &c[i]);
      |            ~^          ~~~~~
      |             |          |
      |             int*       long long int*
      |            %lld
fireworks.cpp:68:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   68 |   printf("%d", ans);
      |           ~^   ~~~
      |            |   |
      |            int long long int
      |           %lld
fireworks.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &p[i], &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 2078 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Incorrect 15 ms 1088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 2078 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 2078 ms 980 KB Time limit exceeded
3 Halted 0 ms 0 KB -