제출 #584407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584407		perchuts	전선 연결 (IOI17_wiring)	C++17	100 / 100	53 ms	14904 KiB

wiring

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
// #include "wiring.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ll custo[maxn], pr[maxn], prmn[maxn], sufmn[maxn], dp[maxn];

ll min_total_length(vector<int>a,vector<int>b){
    vector<pair<ll,bool>>v;
    v.pb({-1,0});

    for(auto x:a)v.pb({ll(x),0});
    for(auto x:b)v.pb({ll(x),1});

    sort(all(v));

    int n = sz(a) + sz(b), l = 0, r = 0;

    for(int i=1;i<=n;++i)pr[i] = pr[i-1] + v[i].first;

    for(int i=1;i<=n;++i){
        if(i!=1&&v[i].second!=v[i-1].second){
            //calcula o intervalo anterior
            l = r+1, r = i-1;
            for(int j=r;j>=l;--j){
                custo[j] = v[r].first*ll(r-j+1) - (pr[r] - pr[j-1]);
            }
            for(int j=l;j<=r;++j){
                if(j==l)prmn[j] = custo[j] + min(dp[j-1],dp[j]) + (v[r+1].first-v[r].first)*ll(r-l+1);
                else prmn[j] = min(prmn[j-1],
                custo[j]+min(dp[j-1],dp[j])+ll(r-j+1)*(v[r+1].first-v[r].first));
            }   
            for(int j=r;j>=l;--j){
                if(j==r)sufmn[j] = custo[j] + min(dp[j-1],dp[j]);
                else sufmn[j] = min(sufmn[j+1],
                custo[j]+min(dp[j-1],dp[j]));
            }
        }
        if(!l){
            dp[i] = 1e15;
            continue;
        }
        //agora, posso fazer o intervalo anterior vir ate mim,
        //ou eu ir ate o intervalo anterior
        int idx = max(l,2*r-i+1);//r - (i-r)
        ll volta = pr[i] - pr[r] - ll(i-r)*v[r+1].first;
        // eu ir ate o intervalo anterior
        dp[i] = volta + sufmn[idx] + ll(i-r)*(v[r+1].first-v[r].first);
        // intervalo anterior vir ate mim
        if(2*r-i+1>=l)ckmin(dp[i],volta+prmn[idx]);
        // cout<<volta+prmn[idx]<<endl;
    }
    return dp[n];
}

// int main(){
//     int n,m;cin>>n>>m;
//     vector<int>a(n), b(m);
//     for(auto& x:a)cin>>x;
//     for(auto& x:b)cin>>x;
//     cout<<min_total_length(a,b)<<endl;
// }

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45