Submission #61235

#	Time	Username	Problem	Language	Result	Execution time	Memory
61235		dukati8	Fireworks (APIO16_fireworks)	C++14	26 / 100	39 ms	1660 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<int(b); i++)

int main() {
  int n,m;
  cin >> n >> m;
  vector<int>p(n+m);
  vector<long long>c(n+m);
  p[0]=-1;
  c[0]=-1;
  rep (i,1,n+m) {
    cin >> p[i] >> c[i];
    p[i]--; //0-indexed
  }
  if (n==1 && m<=100) {
    rep (i,1,m+1) {
      assert(p[i]==0);
    }
    sort(c.begin(),c.end());
    long long goal=c[m/2+1];
    long long ans=0;
    rep (i,1,m+1) {
      ans+=abs(goal-c[i]);
    }
    cout << ans << endl;
  }
  else {
    //assume N+M <=300 and longest path <=300;
    long long cost[n+m][301]; //This will be, for every node, cost[t] is cost to make that node a certain time t
    vector<vector<int> > children (n);
    rep (i,1,n+m) {
      children[p[i]].push_back(i);
    }
    queue<int> ready;
    int done[n]; //Says how many of intersection i's children are done
    rep (i,0,n) done[i]=0;
    rep (i,n,n+m) {
      //Loop over all leafs, set costs
      cost[i][0]=0; //All leafs are 0
      rep (j,1,301) {
        cost[i][j]=999999999;
      }
      done[p[i]]++;
      if (done[p[i]]==children[p[i]].size()) {
        ready.push(p[i]);
      }
    }
    while (true) {
      int curr =ready.front();
      ready.pop();
      rep (i,0,301) {
        cost[curr][i]=0;
        //calculate sum for all children
        for (auto child:children[curr]) {
          long long best=999999999;
          rep (j,0,i+1) {
            best=min(best,cost[child][j]+abs(i-j-c[child]));
          }
          cost[curr][i]+=best;
        }
      }
      if (curr==0) break;
      done[p[curr]]++;
      if (done[p[curr]]==children[p[curr]].size()) ready.push(p[curr]);
    }
    long long best=999999999;
    rep (i,0,301) {
      best=min(best,cost[0][i]);
    }
    cout << best << endl;

  }
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (done[p[i]]==children[p[i]].size()) {
           ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (done[p[curr]]==children[p[curr]].size()) ready.push(p[curr]);
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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