oj.uz

Submission #82315

# Submission time Handle Problem Language Result Execution time Memory
82315 2018-10-29T21:10:40 Z patcasrares Wiring (IOI17_wiring) C++14
0 / 100
 893 ms 8456 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Incorrect 243 ms 6432 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '1000000000000000000'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6432 KB Output is correct
2 Correct 2 ms 6432 KB Output is correct
3 Incorrect 47 ms 8404 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8404 KB Output is correct
2 Incorrect 893 ms 8456 KB 3rd lines differ - on the 1st token, expected: '373710605', found: '1000000000000000000'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -