oj.uz

Submission #71009

# Submission time Handle Problem Language Result Execution time Memory
71009 2018-08-24T02:13:18 Z funcsr Wiring (IOI17_wiring) C++17
7 / 100
 217 ms 17192 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 cost[401];

long long min_total_length(vector<int> R, vector<int> B) {
  vector<P> all;
  for (int x : R) all.pb(P(x, 0));
  for (int x : B) all.pb(P(x, 1));
  sort(all(all));
  N = all.size();
  rep(i, N) {
    cost[i] = INF;
    if (all[i]._2 == 0) {
      auto it = lower_bound(all(B), all[i]._1);
      if (it != B.end()) chmin(cost[i], *it-all[i]._1);
      if (it != B.begin()) chmin(cost[i], all[i]._1-*(--it));
    }
    else {
      auto it = lower_bound(all(R), all[i]._1);
      if (it != R.end()) chmin(cost[i], *it-all[i]._1);
      if (it != R.begin()) chmin(cost[i], all[i]._1-*(--it));
    }
  }
  //rep(i,N)cout<<cost[i]<<",";cout<<"\n";

  rep(j, N+1) rep(k, N+1) dp[0][j][k] = INF;
  dp[0][0][0] = 0;
  rep(i, N) {
    rep(j, N+1) rep(k, N+1) dp[1][j][k] = INF;
    int pos = all[i]._1, color = all[i]._2;
    rep(j, N) {
      rep(k, N) {
        if (j > 0 && k > 0) continue;
        // [
        if (color == 0) chmin(dp[1][j+1][k], dp[0][j][k]-pos);
        if (color == 1) chmin(dp[1][j][k+1], dp[0][j][k]-pos);
        // ]
        if (color == 1 && j > 0) chmin(dp[1][j-1][k], dp[0][j][k]+pos);
        if (color == 0 && k > 0) chmin(dp[1][j][k-1], dp[0][j][k]+pos);
        // .
        chmin(dp[1][j][k], dp[0][j][k] + cost[i]);
      }
    }
    swap(dp[0], dp[1]);
  }
  return dp[0][0][0];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2808 KB Output is correct
2 Correct 14 ms 2808 KB Output is correct
3 Correct 13 ms 2832 KB Output is correct
4 Correct 14 ms 3008 KB Output is correct
5 Correct 14 ms 3100 KB Output is correct
6 Correct 10 ms 3140 KB Output is correct
7 Correct 174 ms 3212 KB Output is correct
8 Correct 177 ms 3220 KB Output is correct
9 Correct 193 ms 3220 KB Output is correct
10 Correct 189 ms 3352 KB Output is correct
11 Correct 217 ms 3404 KB Output is correct
12 Correct 177 ms 3404 KB Output is correct
13 Correct 191 ms 3420 KB Output is correct
14 Correct 204 ms 3420 KB Output is correct
15 Correct 212 ms 3420 KB Output is correct
16 Correct 174 ms 3420 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3420 KB Output is correct
2 Correct 107 ms 3420 KB Output is correct
3 Runtime error 86 ms 12436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12436 KB Output is correct
2 Correct 10 ms 12436 KB Output is correct
3 Runtime error 145 ms 15876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15876 KB Output is correct
2 Runtime error 113 ms 17192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2808 KB Output is correct
2 Correct 14 ms 2808 KB Output is correct
3 Correct 13 ms 2832 KB Output is correct
4 Correct 14 ms 3008 KB Output is correct
5 Correct 14 ms 3100 KB Output is correct
6 Correct 10 ms 3140 KB Output is correct
7 Correct 174 ms 3212 KB Output is correct
8 Correct 177 ms 3220 KB Output is correct
9 Correct 193 ms 3220 KB Output is correct
10 Correct 189 ms 3352 KB Output is correct
11 Correct 217 ms 3404 KB Output is correct
12 Correct 177 ms 3404 KB Output is correct
13 Correct 191 ms 3420 KB Output is correct
14 Correct 204 ms 3420 KB Output is correct
15 Correct 212 ms 3420 KB Output is correct
16 Correct 174 ms 3420 KB Output is correct
17 Correct 12 ms 3420 KB Output is correct
18 Correct 107 ms 3420 KB Output is correct
19 Runtime error 86 ms 12436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -