Submission #73697

#	Time	Username	Problem	Language	Result	Execution time	Memory
73697		MANcity	Wiring (IOI17_wiring)	C++14	100 / 100	94 ms	8388 KiB

wiring

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "wiring.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
pair<int,int> L[200002];
int q;
LL dp[200002];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    for0(i,r.size()-1)
    {
        q++;
        L[q].first=r[i];
        L[q].second=1;
    }
    for0(i,b.size()-1)
    {
        q++;
        L[q].first=b[i];
        L[q].second=2;
    }
    sort(L+1,L+q+1);
    dp[0]=0;
    dp[1]=(LL)100000000000000000;
    //cout<<dp[1]<<endl;
    LL qurDist=0;
    int qurPos=0;
    vector<LL> V;
    vector<LL> B_end;
    vector<LL> B_beg;
    LL Len=0;
    LL Dist=0;
    LL DIST=0;
    fo(i,2,q)
    {
        dp[i]=(LL)100000000000000000;
        /// big number
        if(L[i].second!=L[i-1].second)
        {
            V.clear();
            B_end.clear();
            B_beg.clear();
            qurDist=L[i].first-L[i-1].first;
            qurPos=i;
            Len=0;
            Dist=0;
            DIST=0;
            fr(j,i-1,1)
            {
                if(L[j].second==L[i].second)
                    break;
                Dist+=Len;
                Dist+=L[min(j+1,i-1)].first-L[j].first;
                Len+=L[min(j+1,i-1)].first-L[j].first;
                V.push_back(Dist+min(dp[j],dp[j-1]));
            }
            int vector_l=V.size();
            for(int j=vector_l-1;j>=0;j--)
            {
                if(j==vector_l-1)
                {
                    B_end.push_back((LL)V[j]+(LL)(j+1)*(LL)qurDist);
                }
                else
                {
                    B_end.push_back(min(B_end[vector_l-2-j],(LL)V[j]+(LL)(j+1)*(LL)qurDist));
                }
            }
            for0(j,vector_l-1)
            {
                if(j==0)
                    B_beg.push_back(V[j]);
                else
                    B_beg.push_back(min(B_beg[j-1],V[j]));
            }
            for0(j,B_end.size()-1)
                dp[i]=min(dp[i],B_end[j]);
            Len=0;
            Dist=0;
            //break;
        }
        if(L[i].second==L[i-1].second)
        {
            Len+=(L[i].first-L[i-1].first);
            Dist+=Len;
            int qd=i-qurPos;
            if(dp[i-1]<100000000000000000)
            {
                ///TLE-i momen;
                int lenBeg=B_beg.size()-1;
                dp[i]=min(dp[i],B_beg[min(qd,lenBeg)]+(qd+1)*qurDist+Dist);
                if(qd+1<B_end.size())
                {
                    int qqd=B_end.size()-qd-1;
                    dp[i]=min(dp[i],B_end[qqd-1]+Dist);
                }
            }
        }
    }
    //cout<<dp[9]<<endl;
	return dp[q];
}
/*
4 5
1 2 4 100
5 6 7 8 101
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:110:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(qd+1<B_end.size())
                    ~~~~^~~~~~~~~~~~~
wiring.cpp:51:8: warning: variable 'DIST' set but not used [-Wunused-but-set-variable]
     LL DIST=0;
        ^~~~

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