oj.uz

Submission #922576

# Submission time Handle Problem Language Result Execution time Memory
922576 2024-02-05T17:10:38 Z LucaLucaM Wiring (IOI17_wiring) C++17
0 / 100
 1 ms 348 KB 
#ifndef WIRING_CPP_INCLUDED
#define WIRING_CPP_INCLUDED

#include "wiring.h"
#include <algorithm>
#include <iostream>

typedef long long ll;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
  int n = (int) r.size();
  int m = (int) b.size();
  std::vector<std::pair<int, int>> A;
  for (const auto &x : r) {
    A.push_back({x, 0});
  }
  for (const auto &x : b) {
    A.push_back({x, 1});
  }
  A.push_back({-1, -1});
  std::sort(A.begin(), A.end());
  n = (int) A.size() - 1;
  ll dp[n + 1] = {};
  /**

  dp[i] =def= costul minim sa cuplez primele i
  1. c[i] == c[i - 1]
    dp[i] = dp[i - 1] + (last == 0? 0 : a[i] - last)
  2. c[i] != c[i - 1]
    dp[i] = min{dp[j - 1] + sum{a[i] - a[k] | k = j..i - 1} | j=1..i-1}

  **/
  std::vector<int> a;
  std::vector<int> c;
  for (const auto &[x, y] : A) {
    a.push_back(x);
    c.push_back(y);
  }
  int last = -1;
  int delta = 0;
  int nextDelta = 0;
  for (int i = 1; i <= n; i++) {
    if (c[i] == c[i - 1]) {
      if (delta <= 1) {
        dp[i] = dp[i - 1] + (last == -1? 0 : a[i] - last);
      } else {
        dp[i] = dp[i - 1] + 1;
        delta--;
      }
    } else {
      last = a[i - 1];
      dp[i] = 1e18;
      delta = 0;
      for (int j = 1; j < i; j++) {
        ll cost = dp[j - 1];
        for (int k = j; k < i; k++) {
          cost += a[i] - a[k];
        }
        if (cost < dp[i]) {
          dp[i] = cost;
          delta = i - j;
        }
      }
//      std::cout << " > " << delta << '\n';
    }
//    std::cout << i << ' ' << "dp = " << dp[i] << '\n';
  }
  return dp[n];
}


#endif // WIRING_CPP_INCLUDED

Compilation message

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:12:7: warning: unused variable 'm' [-Wunused-variable]
   12 |   int m = (int) b.size();
      |       ^
wiring.cpp:41:7: warning: unused variable 'nextDelta' [-Wunused-variable]
   41 |   int nextDelta = 0;
      |       ^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '25859', found: '25030'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '904', found: '637'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '316', found: '181'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '27', found: '25'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '25859', found: '25030'
2 Halted 0 ms 0 KB -