oj.uz

답안 #831508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831508 2023-08-20T09:58:42 Z WLZ 전선 연결 (IOI17_wiring) C++17
13 / 100
 50 ms 9276 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;
  vector<int> first(n + m + 1), last(n + m + 1);
  first[0] = v[1].first; last[0] = v[1].first;
  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;
      first[seg[i]] = v[i].first;
    }
    last[seg[i]] = v[i].first;
  }
  sz.push_back(len);
  vector<ll> dp(n + m + 1, LINF); dp[0] = 0;
  vector<int> cnt = {0, 0};
  vector<ll> sum = {0, 0};
  int j = 0;
  for (int i = 1; i <= n + m; i++) {
    cnt[v[i].second]++;
    sum[v[i].second] += v[i].first;
    if (seg[i] == 0) continue;
    while (seg[j] < seg[i] - 1) {
      if (j > 0) {
        cnt[v[j].second]--;
        sum[v[j].second] -= v[j].first; 
      }
      j++;
    }
    ll cur_cost = sum[v[i].second] - sum[!v[i].second];
    if (cnt[v[i].second] > cnt[!v[i].second]) cur_cost -= (ll) (cnt[v[i].second] - cnt[!v[i].second]) * last[seg[i] - 1];
    else cur_cost += (ll) (cnt[!v[i].second] - cnt[v[i].second]) * first[seg[i]];
    while (j < i) {
      dp[i] = min(dp[i], dp[j - 1] + cur_cost);
      dp[i] = min(dp[i], dp[j] + cur_cost);
      auto tmp_cnt = cnt; auto tmp_sum = sum;
      tmp_cnt[v[j].second]--; tmp_sum[v[j].second] -= v[j].first;
      ll new_cost = tmp_sum[v[i].second] - tmp_sum[!v[i].second];
      if (tmp_cnt[v[i].second] > tmp_cnt[!v[i].second]) new_cost -= (ll) (tmp_cnt[v[i].second] - tmp_cnt[!v[i].second]) * last[seg[i] - 1];
      else new_cost += (ll) (tmp_cnt[!v[i].second] - tmp_cnt[v[i].second]) * first[seg[i]];
      if (tmp_cnt[0] > 1 && tmp_cnt[1] > 1 && dp[j] + new_cost < dp[j - 1] + cur_cost) {
        cnt = tmp_cnt;
        sum = tmp_sum;
        cur_cost = new_cost;
        j++;
      } else break;
    }
    dp[i] = min(dp[i], dp[j - 1] + cur_cost);
    dp[i] = min(dp[i], dp[j] + cur_cost);
  }
  return dp[n + m];
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14910'
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 20 ms 6876 KB Output is correct
4 Correct 20 ms 6980 KB Output is correct
5 Correct 21 ms 6980 KB Output is correct
6 Correct 30 ms 9248 KB Output is correct
7 Correct 27 ms 9256 KB Output is correct
8 Correct 28 ms 9244 KB Output is correct
9 Correct 28 ms 9276 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 50 ms 9152 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1553019275'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '27', found: '40'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14910'
3 Halted 0 ms 0 KB -