Submission #82315

#	Time	Username	Problem	Language	Result	Execution time	Memory
82315		patcasrares	Wiring (IOI17_wiring)	C++14	0 / 100	893 ms	8456 KiB

wiring

#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("t.in");
ofstream fout("t.out");
const int DN=2e5+5;
unsigned long long n,m,ml[2][DN],poz1,poz2,nr,poz,l,f,urm,pr[DN],dp[DN];
unsigned long long s[DN],st,dr,mij1,mij2,val1,val2,val;
pair<int,int>r[DN];
vector<int>a,b;
unsigned long long ve(int st,int l,int dr)
{
    unsigned long long val=dp[st-1],f=min(l-st+1,dr-l);
    val+=1LL*r[l+1].x*f;
    val-=s[st+f-1]-s[st-1];

    val+=s[l+f]-s[l];
    val-=1LL*r[l+1].x*f;

    val+=1LL*(l-st+1-f)*r[l+1].x;
    val-=s[l]-s[st+f-1];

    val+=s[dr]-s[l+f];
    val-=1LL*(dr-l-f)*r[l].x;
    return val;
}
long long min_total_length(vector<int>a,vector<int>b)
{
    n=a.size();
    m=b.size();
    poz1=poz2=0;
    nr=n+m;
    poz=-1;
    f=0;
    for(int i=0;i<=n+m;i++)
        dp[i]=1e18;
    while(nr--)
    {
        f++;
        urm=1e18;
        if(poz1==n)
        {
            r[f]={b[poz2],1};
            poz2++;
        }
        else
            if(poz2==m)
            {
                r[f]={a[poz1],0};
                poz1++;
            }
            else
                if(a[poz1]<b[poz2])
                {
                    r[f]={a[poz1],0};
                    poz1++;
                    urm=b[poz2];
                }
                else
                {
                    r[f]={b[poz2],1};
                    poz2++;
                    urm=a[poz1];
                }
        if(f==0)
            continue;
        if(r[f].y==r[f-1].y)
            pr[f]=pr[f-1];
        else
            pr[f]=f-1;
    }
    for(int i=1;i<=f;i++)
        s[i]=s[i-1]+r[i].x;
    dp[0]=0;
    for(int i=1;i<=f;i++)
    {
        if(pr[i]==0)
            continue;
        dr=pr[i];
        st=pr[pr[i]]+1;
        l=dr;
        while(dr-st>1e3)
        {
            mij1=st+(dr-st)/3;
            mij2=dr-(dr-st)/3;
            val1=ve(mij1,l,i);
            val2=ve(mij2,l,i);
            if(val1<val2)
                dr=mij2;
            else
                st=mij1;
        }
        val=1e18;
        for(int j=st;j<=dr;j++)
            val=min(val,ve(j,l,i));
        dp[i]=val;
    }
    return dp[f];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=n+m;i++)
                 ~^~~~~
wiring.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=f;i++)
                 ~^~~
wiring.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=f;i++)
                 ~^~~
wiring.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=st;j<=dr;j++)
                      ~^~~~

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