oj.uz

Submission #831472

# Submission time Handle Problem Language Result Execution time Memory
831472 2023-08-20T09:33:04 Z WLZ Wiring (IOI17_wiring) C++17
7 / 100
 1000 ms 8084 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll LINF = (ll) 1e18;

long long min_total_length(std::vector<int> a, std::vector<int> b) {
  int n = (int) a.size(), m = (int) b.size();
  vector< pair<int, int> > v;
  for (int i = 0; i < n; i++) v.emplace_back(a[i], 0);
  for (int i = 0; i < m; i++) v.emplace_back(b[i], 1);
  sort(v.begin(), v.end());
  v.insert(v.begin(), {0, -1});
  vector<int> seg(n + m + 1); seg[1] = 0; seg[0] = -5;
  vector<int> sz;
  int len = 1;
  for (int i = 2; i <= n + m; i++) {
    seg[i] = seg[i - 1];
    len++;
    if (v[i].second != v[i - 1].second) {
      sz.push_back(len - 1);
      seg[i]++, len = 1;
    }
  }
  sz.push_back(len);
  vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
  for (int i = 1; i <= n + m; i++) {
    if (seg[i] == 0) continue;
    int cnt_l = 0, cnt_r = 0;
    ll sum_l = 0, sum_r = 0;
    int last_l = 0, last_r = -1;
    for (int j = i - 1; j >= 0; j--) {
      if (seg[j + 1] == seg[i]) {
        cnt_l++; sum_l += v[j + 1].first;
        last_l = v[j + 1].first;
      }
      if (seg[j + 1] == seg[i] - 1) {
        cnt_r++; sum_r += v[j + 1].first;
        if (last_r == -1) last_r = v[j + 1].first;
      }
      if (cnt_r > 0) {
        ll add = sum_l - sum_r;
        if (cnt_l > cnt_r) add -= last_r * (cnt_l - cnt_r);
        else add += last_l * (cnt_r - cnt_l);
        dp[i] = min(dp[i], dp[j + 1] + add);
        dp[i] = min(dp[i], dp[j] + add);
      } 
      if (seg[j] < seg[i] - 1) break;
    }
  }
	return dp[n + m];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 300 KB Output is correct
15 Correct 0 ms 300 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 1084 ms 5820 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 38 ms 8084 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '-54063581813318'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1079 ms 7000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 300 KB Output is correct
15 Correct 0 ms 300 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Execution timed out 1084 ms 5820 KB Time limit exceeded
20 Halted 0 ms 0 KB -