Submission #521052

#	Time	Username	Problem	Language	Result	Execution time	Memory
521052		krit3379	Wiring (IOI17_wiring)	C++17	100 / 100	112 ms	16144 KiB

wiring

#include<bits/stdc++.h>
using namespace std;
#define N 200005
 
int last[2],cnt;
long long dp[N],dis[N],sum[N];
vector<pair<long long,int>> v;
map<int,int> mp;
 
long long min_total_length(vector<int> r, vector<int> b){
    int n,m,i;
    n=r.size()+b.size();
    v.push_back({0,0});
    for(auto x:r)v.push_back({x,0});
    for(auto x:b)v.push_back({x,1});
    sort(v.begin(),v.end());
    last[0]=last[1]=0;
    for(i=1;i<=n;i++){
        dp[i]=dis[i]=1e18;
        if(last[!v[i].second])dis[i]=min(dis[i],abs(v[i].first-v[last[!v[i].second]].first));
        last[v[i].second]=i;
    }
    last[0]=last[1]=0;
    for(i=n;i>0;i--){
        if(last[!v[i].second])dis[i]=min(dis[i],abs(v[i].first-v[last[!v[i].second]].first));
        last[v[i].second]=i;
    }
    cnt=0;
    mp[0]=0;
    for(i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if(v[i].second)sum[i]+=v[i].first,cnt++;
        else sum[i]-=v[i].first,cnt--;
        dp[i]=dp[i-1]+dis[i];
        if(mp.count(cnt))dp[i]=min(dp[i],dp[mp[cnt]]+abs(sum[i]-sum[mp[cnt]]));
        mp[cnt]=i;
    }
    return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:11:11: warning: unused variable 'm' [-Wunused-variable]
   11 |     int n,m,i;
      |           ^

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