Submission #71090

#	Time	Username	Problem	Language	Result	Execution time	Memory
71090		funcsr	Wiring (IOI17_wiring)	C++17	0 / 100	1041 ms	263168 KiB

wiring

#include "wiring.h"
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
inline void chmin(long long &x, long long v) { if(x>v)x=v; }

int N;
long long dp[401][401];
long long costA[401];
long long costB[401];
long long best[401];

long long solveAB(vector<int> A, vector<int> B) {
  if (A[0] > B[0]) swap(A, B);
  long long sum = 0;
  rep(i, A.size()-1) sum += 1LL*(i+1)*(A[i+1]-A[i]);
  sum += 1LL*(max(A.size(), B.size()))*(B[0]-A[A.size()-1]);
  rep(i, B.size()-1) sum += 1LL*(B.size()-1-i)*(B[i+1]-B[i]);
  return sum;
}

long long min_total_length(vector<int> A, vector<int> B) {
  rep(i, A.size()) {
    costA[i] = INF;
    auto it = lower_bound(all(B), A[i]);
    if (it != B.end()) chmin(costA[i], *it-A[i]);
    if (it != B.begin()) chmin(costA[i], A[i]-*(--it));
  }
  rep(i, B.size()) {
    costB[i] = INF;
    auto it = lower_bound(all(A), B[i]);
    if (it != A.end()) chmin(costB[i], *it-B[i]);
    if (it != A.begin()) chmin(costB[i], B[i]-*(--it));
  }
  vector<pair<long long, P> > vs;
  rep(i, A.size()) rep(j, B.size()) vs.pb(make_pair(abs(A[i]-B[j]), P(i, j)));
  sort(all(vs));
  int a = vs[0]._2._1, b = vs[0]._2._2;
  //vs.resize(N-2*min(A.size(),B.size()));
  //cout<<"ok:";rep(i, vs.size()) cout<<vs[i]._2<<",";cout<<"\n";
  //rep(i, N) cost[i] = INF;
  //for (P p : vs) cost[p._2] = p._1;
  //rep(i,N)cout<<cost[i]<<",";cout<<"\n";

  long long mincost = INF, sum = 0;
  rep(i, A.size()) chmin(mincost, costA[i]), sum += costA[i];
  rep(i, B.size()) chmin(mincost, costB[i]), sum += costB[i];
  //cout<<a<<"<->"<<b<<": "<<abs(A[a]-B[b])<<" = "<<mincost<<"\n";

  rep(i, A.size()+1) rep(j, B.size()+1) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i, A.size()) {
    rep(j, B.size()) {
      long long e = abs(A[i]-B[j])-costA[i]-costB[j];
      //if (e < 0) cout<<i<<"<->"<<j<<":"<<e<<"\n";
      best[i] = min(best[i], e);
    }
    //cout<<"\n";
  }
  rep(i, A.size()+1) rep(j, B.size()+1) {
    if (i < A.size()) chmin(dp[i+1][j], dp[i][j]);
    if (j < B.size()) chmin(dp[i][j+1], dp[i][j]);
    if (i < A.size() && j < B.size()) {
      //if (costA[i] != costB[j]) continue;
      //if ((i == a || j == b) && abs(A[i]-B[j]) > mincost) continue;
      long long e = abs(A[i]-B[j])-costA[i]-costB[j];
      if (e != best[i]) continue;
      chmin(dp[i+1][j+1], dp[i][j] + e);
    }
  }
  //cout<< dp[A.size()][B.size()]<<"\n";
  return sum + dp[A.size()][B.size()];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int solveAB(std::vector<int>, std::vector<int>)':
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:26:3: note: in expansion of macro 'rep'
   rep(i, A.size()-1) sum += 1LL*(i+1)*(A[i+1]-A[i]);
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:28:3: note: in expansion of macro 'rep'
   rep(i, B.size()-1) sum += 1LL*(B.size()-1-i)*(B[i+1]-B[i]);
   ^~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:33:3: note: in expansion of macro 'rep'
   rep(i, A.size()) {
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:39:3: note: in expansion of macro 'rep'
   rep(i, B.size()) {
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:46:3: note: in expansion of macro 'rep'
   rep(i, A.size()) rep(j, B.size()) vs.pb(make_pair(abs(A[i]-B[j]), P(i, j)));
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:46:20: note: in expansion of macro 'rep'
   rep(i, A.size()) rep(j, B.size()) vs.pb(make_pair(abs(A[i]-B[j]), P(i, j)));
                    ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:56:3: note: in expansion of macro 'rep'
   rep(i, A.size()) chmin(mincost, costA[i]), sum += costA[i];
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:57:3: note: in expansion of macro 'rep'
   rep(i, B.size()) chmin(mincost, costB[i]), sum += costB[i];
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:60:3: note: in expansion of macro 'rep'
   rep(i, A.size()+1) rep(j, B.size()+1) dp[i][j] = INF;
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:60:22: note: in expansion of macro 'rep'
   rep(i, A.size()+1) rep(j, B.size()+1) dp[i][j] = INF;
                      ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:62:3: note: in expansion of macro 'rep'
   rep(i, A.size()) {
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:63:5: note: in expansion of macro 'rep'
     rep(j, B.size()) {
     ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:70:3: note: in expansion of macro 'rep'
   rep(i, A.size()+1) rep(j, B.size()+1) {
   ^~~
wiring.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
wiring.cpp:70:22: note: in expansion of macro 'rep'
   rep(i, A.size()+1) rep(j, B.size()+1) {
                      ^~~
wiring.cpp:71:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < A.size()) chmin(dp[i+1][j], dp[i][j]);
         ~~^~~~~~~~~~
wiring.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j < B.size()) chmin(dp[i][j+1], dp[i][j]);
         ~~^~~~~~~~~~
wiring.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < A.size() && j < B.size()) {
         ~~^~~~~~~~~~
wiring.cpp:73:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < A.size() && j < B.size()) {
                         ~~^~~~~~~~~~
wiring.cpp:48:7: warning: unused variable 'a' [-Wunused-variable]
   int a = vs[0]._2._1, b = vs[0]._2._2;
       ^
wiring.cpp:48:24: warning: unused variable 'b' [-Wunused-variable]
   int a = vs[0]._2._1, b = vs[0]._2._2;
                        ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45