Submission #47326

#	Time	Username	Problem	Language	Result	Execution time	Memory
47326		Talant	Fireworks (APIO16_fireworks)	C++17	26 / 100	37 ms	10160 KiB

fireworks

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e18 + 7;
const int N = (int)2e5 + 7;

int n,m;
int x,w;
int dp[302][302];
int ans = inf;
int sum,sm;

vector <int> vec;
vector <pair<int,int> > g[N];

void dfs (int v) {
      for (auto to : g[v]) {
            dfs(to.fr);
            int u = to.fr;
            int w = to.sc;
            for (int i = 0; i <= 300; i ++) {
                  int mn = inf;
                  for (int j = 0; j <= i; j ++) {
                        mn = min(mn,dp[u][j] + abs(i - j - w));
                  }

                  dp[v][i] += mn;
            }
      }
}
main () {
      cin >> n >> m;

      for (int i = 2; i <= n + m; i ++) {
            cin >> x >> w;
            g[x].pb(mk(i,w));
            if (n == 1) {
                  vec.pb(w);
            }
      }
      if (n == 1) {
            for (int j = 0; j < vec.size(); j ++) {
                  sm = 0;
                  for (int i = 0; i < vec.size(); i ++) {
                        sm += abs(vec[i] - vec[j]);
                  }
                  ans = min(ans,sm);
            }
            cout << ans << endl;
            return 0;
      }
      for (int i = n + 1; i <= n + m; i ++)
            for (int j = 1; j <= 300; j ++)
                  dp[i][j] = inf;

      dfs(1);

      for (int i = 0; i <= 300; i ++) {
            ans = min(ans,dp[1][i]);
      }

      cout << ans << endl;
}

Compilation message (stderr)

fireworks.cpp:40:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:51:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < vec.size(); j ++) {
                             ~~^~~~~~~~~~~~
fireworks.cpp:53:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for (int i = 0; i < vec.size(); i ++) {
                                   ~~^~~~~~~~~~~~

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