Submission #1225130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225130		cpdreamer	Wiring (IOI17_wiring)	C++20	17 / 100	1095 ms	10260 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
#define inf 1e17
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<ll> p;
vector<ll> a;
vector<bool> b;
ll n, m;
ll sum(ll l, ll r)
{
    ll sm=p[r];
    if(l > 0) sm-=p[l-1];
    return sm;
}
ll l3iba(ll l, ll r, ll x, ll y)
{
    ll sm=sum(x,y)-sum(l,r);
    ll sz1=(r-l+1);
    ll sz2=y-x+1;
    if(sz2 > sz1)
    {
        sm-=a[r]*(sz2-sz1);
    }
    else
    {
        sm+=a[x]*(sz1-sz2);
    }
    return sm;
}
long long min_total_length(std::vector<int> r, std::vector<int> bro)
{
    n=r.size();
    m=bro.size();
    vector<pair<ll,ll>>  merged;
    for (int i=0;i<n;i++)
    {
        merged.push_back({r[i],0});
    }
  
    for (int i=0;i<m;i++)
    {
        merged.push_back({bro[i],1});
    }
    sort(merged.begin(),merged.end());
    for (int i=0;i<n+m;i++)
    {
        a.push_back(merged[i].first);
        b.push_back(merged[i].second);
    }
    p.resize(n+m);
    for (int i=0;i<n+m;i++)
    {
        p[i]=a[i];
        if(i>0)p[i]+=p[i-1];
    }
    vector<ll> dp(n+m,inf);
    ll b1=-1;
    ll b2=-1;
    for (int i=0;i<m+n;i++)
    {
        if(i!=0 && b[i]!=b[i-1])
        {
            b1=i-1;
            b2=i;
        }
        if(b1==-1 || b2==-1)
        {
            dp[i]=inf;
        }
        else
        {
            for (int j=b1;j>=0 && b[j]!=b[i];j--)
            {
                ll x=0;
                if(j>0) x=min(dp[j-1],dp[j]);
                dp[i]=min(dp[i],l3iba(j,b1,b2,i)+x);
            }
        }
    }
    return dp.back();
    // return l3iba(0,n-1,n,m+n-1);
}

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