Submission #310075

#	Time	Username	Problem	Language	Result	Execution time	Memory
310075		vipghn2003	Wiring (IOI17_wiring)	C++14	100 / 100	98 ms	25192 KiB

wiring

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;

const int N=1e5+5;
vector<int>seg[N];
vector<long long>last[N],first[N],dp[N];

long long min_total_length(vector<int>r,vector<int>b)
{
    vector<pii>coor;
    for(auto&x:r) coor.push_back(mp(x,0));
    for(auto&x:b) coor.push_back(mp(x,1));
    sort(coor.begin(),coor.end());
    int cnt=0;
    int color=-1;
    seg[0].push_back(-1);
    for(auto&x:coor)
    {
        if(color==x.se) seg[cnt].push_back(x.fi);
        else
        {
            cnt++;
            color=x.se;
            seg[cnt].push_back(-1);
            seg[cnt].push_back(x.fi);
        }
    }
    for(int i=0;i<=cnt;i++)
    {
        int sz=seg[i].size();
        first[i].resize(sz);
        last[i].resize(sz);
        sz--;
        for(int j=1;j<=sz;j++)
        {
            first[i][j]=first[i][j-1]+seg[i][j];
			last[i][j]=last[i][j-1]+seg[i][sz-j+1];
        }
    }
    for(int i=0;i<=cnt;i++)
    {
        int sz=seg[i].size();
        dp[i].resize(sz);
        for(int j=0;j<sz;j++) dp[i][j]=1e15;
    }
    dp[0][0]=0;
    for(int i=0;i<cnt;i++)
    {
        int sz_prev=seg[i].size()-1;
        int sz_cur=seg[i+1].size()-1;
        for(int j=sz_prev;j>0;j--)
        {
			dp[i][j-1]=min(dp[i][j-1],dp[i][j]+abs(seg[i][sz_prev-j+1]-seg[i+1][1]));
		}
		for(int j=0;j<=min(sz_cur,sz_prev);j++)
        {
			dp[i+1][sz_cur-j]=min(dp[i+1][sz_cur-j],dp[i][j]+abs(last[i][j]-first[i+1][j]));
		}
		for(int j=sz_cur;j>0;j--)
        {
			if(i==0) break;
			dp[i+1][j-1]=min(dp[i+1][j-1],dp[i+1][j]+abs(seg[i+1][sz_cur-j+1]-seg[i].back()));
		}
    }
    return dp[cnt][0];
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>r(n),b(m);
    for(int i=0;i<n;i++) cin>>r[i];
    for(int i=0;i<m;i++) cin>>b[i];
    cout<<min_total_length(r,b);
}*/
/*
4 5
1 2 3 7
0 4 5 9 10
*/

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