Submission #59227

#	Time	Username	Problem	Language	Result	Execution time	Memory
59227		Bodo171	Wiring (IOI17_wiring)	C++14	100 / 100	89 ms	52860 KiB

wiring

#include "wiring.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
const long long lim=1LL*1e15;
vector<int> v[nmax];
int curr,i1,i2,i,j,nr,catenxt;
long long cate,sum,dif,cap,tot,inc,ans;
long long mic[nmax],mare[nmax],dp[nmax];
long long min_total_length(vector<int> r, vector<int> b) {
    i1=i2=0;curr=-1;
    for(i=0;i<r.size()+b.size();i++)
    {
        if(i1!=r.size()&&(i2==b.size()||r[i1]<b[i2]))
        {
            if(curr==0) v[nr].push_back(r[i1]);
            else nr++,v[nr].push_back(r[i1]);
            curr=0;i1++;
        }
        else
        {
            if(curr==1) v[nr].push_back(b[i2]);
            else nr++,v[nr].push_back(b[i2]);
            curr=1;i2++;
        }
    }
    cate=v[1].size();dif=v[2][0]-v[1].back();cap=v[1].back();
    for(j=0;j<v[1].size();j++)
        sum+=v[1][j];
    for(j=0;j<=v[2].size();j++)
        mic[j]=mare[j]=lim;
    for(j=1;j<=v[1].size();j++)
        mare[j]=dif*cate+cate*cap-sum;
    for(j=v[1].size();j<=v[2].size();j++)
        mic[j]=cate*cap-sum;
    for(i=2;i<nr;i++)
    {
        dif=v[i][0]-v[i-1].back();
        cap=v[i].back();inc=v[i][0];
        sum=0;tot=0;cate=v[i].size();
        for(j=0;j<cate;j++)
            tot+=v[i][j];
        for(j=0;j<=cate;j++)
        {
            dp[j]=1LL*min(mic[j]+j*dif,mare[j])+sum-j*inc+(cate-j)*cap-(tot-sum);
            if(j<cate)sum+=v[i][j];
        }
        catenxt=v[i+1].size();
        for(j=0;j<=catenxt;j++)
            mic[j]=mare[j]=lim;
        mic[0]=dp[cate];
        for(j=1;j<=cate;j++)
             mic[j]=min(mic[j-1],dp[cate-j]);
        for(j=cate+1;j<=catenxt;j++)
            mic[j]=mic[j-1];
        dif=v[i+1][0]-v[i].back();
        mare[cate+1]=lim;
        for(j=cate;j>=0;j--)
           mare[j]=min(mare[j+1],dp[cate-j]+dif*j);
    }
    sum=0;
    cate=v[nr].size();dif=v[nr][0]-v[nr-1].back();inc=v[nr][0];
    for(j=0;j<v[nr].size();j++)
        sum+=v[nr][j];
    ans=1LL*sum-cate*inc+min(mare[cate],mic[cate]+cate*dif);
	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:13:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<r.size()+b.size();i++)
             ~^~~~~~~~~~~~~~~~~~
wiring.cpp:15:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i1!=r.size()&&(i2==b.size()||r[i1]<b[i2]))
            ~~^~~~~~~~~~
wiring.cpp:15:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i1!=r.size()&&(i2==b.size()||r[i1]<b[i2]))
                           ~~^~~~~~~~~~
wiring.cpp:29:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<v[1].size();j++)
             ~^~~~~~~~~~~~
wiring.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<=v[2].size();j++)
             ~^~~~~~~~~~~~~
wiring.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=1;j<=v[1].size();j++)
             ~^~~~~~~~~~~~~
wiring.cpp:35:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=v[1].size();j<=v[2].size();j++)
                       ~^~~~~~~~~~~~~
wiring.cpp:64:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<v[nr].size();j++)
             ~^~~~~~~~~~~~~

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