oj.uz

Submission #71075

# Submission time Handle Problem Language Result Execution time Memory
71075 2018-08-24T05:43:32 Z funcsr Wiring (IOI17_wiring) C++17
7 / 100
 1000 ms 263168 KB 
#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[2][401][401];
long long dp[401][401];
long long costA[401];
long long costB[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] = sum;
  rep(i, A.size()+1) rep(j, B.size()+1) {
    if (i == A.size() && j == B.size()) continue;
    if (!(i == 0 && j == 0)) {
    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 ((i == a || j == b) && abs(A[i]-B[j]) > mincost) continue;
      chmin(dp[i+1][j+1], dp[i][j] + abs(A[i]-B[j])-costA[i]-costB[j]);
    }
  }
  return dp[A.size()][B.size()];
}

Compilation message

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()+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:62:22: note: in expansion of macro 'rep'
   rep(i, A.size()+1) rep(j, B.size()+1) {
                      ^~~
wiring.cpp:63:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == A.size() && j == B.size()) continue;
         ~~^~~~~~~~~~~
wiring.cpp:63:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i == A.size() && j == B.size()) continue;
                          ~~^~~~~~~~~~~
wiring.cpp:65: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:66: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:68:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i < A.size() && j < B.size()) {
         ~~^~~~~~~~~~
wiring.cpp:68: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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 8 ms 1952 KB Output is correct
9 Correct 9 ms 2120 KB Output is correct
10 Correct 9 ms 2120 KB Output is correct
11 Correct 8 ms 2120 KB Output is correct
12 Correct 10 ms 2120 KB Output is correct
13 Correct 8 ms 2120 KB Output is correct
14 Correct 8 ms 2120 KB Output is correct
15 Correct 8 ms 2120 KB Output is correct
16 Correct 8 ms 2120 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2120 KB Output is correct
2 Correct 6 ms 2120 KB Output is correct
3 Execution timed out 1020 ms 263168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 10 ms 1952 KB Output is correct
8 Correct 8 ms 1952 KB Output is correct
9 Correct 9 ms 2120 KB Output is correct
10 Correct 9 ms 2120 KB Output is correct
11 Correct 8 ms 2120 KB Output is correct
12 Correct 10 ms 2120 KB Output is correct
13 Correct 8 ms 2120 KB Output is correct
14 Correct 8 ms 2120 KB Output is correct
15 Correct 8 ms 2120 KB Output is correct
16 Correct 8 ms 2120 KB Output is correct
17 Correct 3 ms 2120 KB Output is correct
18 Correct 6 ms 2120 KB Output is correct
19 Execution timed out 1020 ms 263168 KB Time limit exceeded
20 Halted 0 ms 0 KB -