Submission #425947

#	Time	Username	Problem	Language	Result	Execution time	Memory
425947		MOUF_MAHMALAT	전선 연결 (IOI17_wiring)	C++14	0 / 100	2 ms	1868 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define S second
#define F first
using namespace std;
typedef long long ll;
deque<pair<ll,ll> >v;
vector<int>a,b;
ll dp[200009],id[200009][2];
ll best(ll d)
{
    if(d==v.size())
        return 0;
    ll &r=dp[d];
    if(r!=-1)
        return r;
    r=1e16;
    if(v[d].S==0)
    {
        ll x=upper_bound(all(b),v[d].F)-b.begin(),sum;
        if(x>0)
        {
            x--;
            sum=abs(b[x]-v[d].F);
            if(b[x]>=v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
            else
                r=min(r,best(d+1)+sum);
            x++;
        }
        if(x<v.size())
        {
            sum=abs(b[x]-v[d].F);
            if(b[x]>=v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][1])+best(id[x][1]+1));
            else
                r=min(r,best(d+1)+sum);
        }
    }
    else
    {
        ll x=upper_bound(all(a),v[d].F)-a.begin(),sum;
        if(x>0)
        {
            x--;
            sum=abs(a[x]-v[d].F);
            if(a[x]>v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
            else
                r=min(r,best(d+1)+sum);
            x++;
        }
        if(x<v.size())
        {
            sum=abs(a[x]-v[d].F);
            if(a[x]>v[d].F)
                r=min(r,best(d+1)+sum-best(id[x][0])+best(id[x][0]+1));
            else
                r=min(r,best(d+1)+sum);
        }
    }
    return r;
}
long long min_total_length(vector<int> o1, vector<int>o2 )
{
    sort(all(o1));
    sort(all(o2));
    a=o1,b=o2;
    ll i=0,j=0;
    while(i<o1.size()&&j<o2.size())
    {
        if(o1[i]<=o2[j])
        {
            id[i][0]=v.size();
            v.push_back({o1[i++],0});
        }
        else
        {
            id[j][1]=v.size();
            v.push_back({o2[j++],1});
        }
    }
    while(i<o1.size())
    {
        id[i][0]=v.size();
        v.push_back({o1[i++],0});
    }
    while(j<o2.size())
    {
        id[j][1]=v.size();
        v.push_back({o2[j++],1});
    }
    memset(dp,-1,sizeof dp);
    return best(0);
}

Compilation message (stderr)

wiring.cpp: In function 'll best(ll)':
wiring.cpp:13:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(d==v.size())
      |        ~^~~~~~~~~~
wiring.cpp:32:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(x<v.size())
      |            ~^~~~~~~~~
wiring.cpp:54:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(x<v.size())
      |            ~^~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:71:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     while(i<o1.size()&&j<o2.size())
      |           ~^~~~~~~~~~
wiring.cpp:71:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     while(i<o1.size()&&j<o2.size())
      |                        ~^~~~~~~~~~
wiring.cpp:84:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while(i<o1.size())
      |           ~^~~~~~~~~~
wiring.cpp:89:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     while(j<o2.size())
      |           ~^~~~~~~~~~

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