oj.uz

Submission #980254

# Submission time Handle Problem Language Result Execution time Memory
980254 2024-05-12T01:51:32 Z 12345678 Wiring (IOI17_wiring) C++17
0 / 100
 1 ms 348 KB 
#include "wiring.h"
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int nx=2e5+5;

ll n, ans, lst=1, dp[nx];
vector<pair<ll, ll>> v;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	v.push_back({-1e12, -1});
    for (auto x:r) v.push_back({x, 1});
    for (auto x:b) v.push_back({x, 2});
    sort(v.begin(), v.end());
    n=((int)v.size())-1;
    for (int i=1; i<=n; i++) dp[i]=1e18;
    for (int i=1; i<=n; i++)
    {
        //cout<<"debug "<<i<<' '<<v[i].first<<' '<<v[i].second<<'\n';
        if (v[i].second!=v[i-1].second)
        {
            //for (int j=lst; j<i; j++) cout<<"here "<<j<<' '<<i<<'\n', dp[j]=min(dp[j], dp[j-1]+v[i].first-v[j].first);
            ll l=i-1, r=i, sm=0;
            while (l>=1&&r<=n&&v[l].second==v[i-1].second&&v[r].second==v[i].second)
            {
                sm+=v[r].first-v[l].first;
                dp[r]=min(dp[r], dp[l-1]+sm);
                l--, r++;
            }
            for (int j=i+1; j<=n&&v[j].second==v[i].second; j++) dp[j]=min(dp[j], dp[j-1]+v[j].first-v[i-1].first); 
            lst=i;
        }
    }
    //for (int i=1; i<=n; i++) cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    return dp[n];
}

/*
4 5
1 3 4 5
8 9 10 12 14

3 4
0 2 4
7 10 12 15

5 1
5 6 7 10 11
1
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 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: '1000000000000000000'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '17703', found: '19052'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -