oj.uz

Submission #1006141

# Submission time Handle Problem Language Result Execution time Memory
1006141 2024-06-23T13:26:18 Z thangdz2k7 Wiring (IOI17_wiring) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int inf = 1e9;

int n;
long long dp[N], pre[N];
pair <int, int> p[N];

long long min_total_length(vector <int> r, vector <int> b){

    for (auto &i : r) p[++ n] = {i, 0};
    for (auto &i : b) p[++ n] = {i, 1};
    sort(p + 1, p + n + 1);
    p[0] = {-inf, 1 - p[1].second};

    for (int i = 1; i <= n; ++ i) pre[i] += p[i].first;

    for (int last = 1, i = 1; i <= n; ++ i){
        int j = i;
        while (j < n && p[j].second == p[j + 1].second) ++ j;
        for (int k = last; k < i; ++ k) dp[k] = min(dp[k], dp[k - 1] + p[i].first - p[k].first);

        long long Min = dp[i - 1], sum = 0;
        for (int k = i; k <= j; ++ k){
            sum += p[k].first - p[i - 1].first;
            int vc = i * i - k - 1;
            if (vc >= last){
                Min = min(Min, dp[vc - 1] + 1ll * p[i - 1].first * (i - vc) - pre[i - 1] + pre[vc - 1]);
            }

            dp[k] = Min + sum;
        }

        last = i;
        i = j;
    }

    return dp[n];
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

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