Submission #576177

#	Time	Username	Problem	Language	Result	Execution time	Memory
576177		ogibogi2004	Wiring (IOI17_wiring)	C++14	100 / 100	74 ms	15884 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e18;
struct bucket
{
    bool col;
    vector<ll> pos;
    vector<ll> dp;
};
vector<bucket>v;
struct segment_tree
{
    vector<ll>t;
    int n;
    void init(int sz)
    {
        n=sz;
        t.resize(4*sz);
        for(int i=0;i<4*sz;i++)t[i]=INF;
    }
    void update(int l,int r,int idx,int q,ll val)
    {
        if(l>q)return;
        if(r<q)return;
        if(l==r)
        {
            t[idx]=val;
            return;
        }
        int mid=(l+r)/2;
        update(l,mid,idx*2,q,val);
        update(mid+1,r,idx*2+1,q,val);
        t[idx]=min(t[idx*2],t[idx*2+1]);
    }
    void update(int idx,int val)
    {
        update(0,n,1,idx,val);
    }
    ll query(int l,int r,int idx,int ql,int qr)
    {
        if(l>qr)return INF;
        if(r<ql)return INF;
        if(l>=ql&&r<=qr)return t[idx];
        int mid=(l+r)/2;
        return min(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
    }
    ll query(int l,int r)
    {
        return query(0,n,1,l,r);
    }
};
long long min_total_length(vector<int> r, vector<int> b) {
    vector<pair<ll,bool> >all;
    for(ll i=0;i<r.size();i++)
    {
        all.push_back({r[i],0});
    }
    for(ll i=0;i<b.size();i++)
    {
        all.push_back({b[i],1});
    }
    sort(all.begin(),all.end());
    bucket last;
    last.col=all[0].second;
    last.pos={all[0].first};
    for(ll i=1;i<all.size();i++)
    {
        if(all[i].second==all[i-1].second)
        {
            last.pos.push_back(all[i].first);
        }
        else
        {
            v.push_back(last);
            last.col=all[i].second;
            last.pos={all[i].first};
        }
    }
    v.push_back(last);
    v[0].dp.push_back(0);
    for(ll i=0;i<v[0].pos.size();i++)v[0].dp.push_back(INF);
    /*for(int j=0;j<v[0].dp.size();j++)cout<<v[0].dp[j]<<" ";
    cout<<endl;*/
    for(ll i=1;i<v.size();i++)
    {
        vector<ll>prefmin(v[i-1].pos.size()+3,INF),sufmin(v[i-1].pos.size()+3,INF);
        ll sufsum=0;
        for(ll j=v[i-1].pos.size();j>=0;j--)
        {
            if(j!=v[i-1].pos.size())sufsum+=v[i-1].pos[j];
            sufmin[j]=min((ll)sufmin[j+1],(ll)(v[i-1].dp[j]-sufsum+(v[i-1].pos.size()-j)*v[i-1].pos.back()));
        }
        ll prefsum=sufsum;
        prefmin[0]=v[i-1].dp[0]-prefsum+v[i-1].pos.size()*v[i].pos[0];
        for(ll j=1;j<=v[i-1].pos.size();j++)
        {
            prefsum-=v[i-1].pos[j-1];
            prefmin[j]=min((ll)prefmin[j-1],(ll)(v[i-1].dp[j]-prefsum+(v[i-1].pos.size()-j)*v[i].pos[0]));
        }
        /*cout<<"prefmin : ";
        for(int j=0;j<prefmin.size();j++)cout<<prefmin[j]<<" ";
        cout<<endl;
        cout<<"sufmin : ";
        for(int j=0;j<sufmin.size();j++)cout<<sufmin[j]<<" ";
        cout<<endl;*/
        for(ll j=0;j<=v[i].pos.size();j++)v[i].dp.push_back(INF);
        prefsum=0;
        for(ll j=0;j<=v[i].pos.size();j++)
        {
            if(j!=0)prefsum+=v[i].pos[j-1];
            // we will chose first j from this bucket
            // connect them with last k from prev bucket
            // first case : k <= j
            // k=0,1,...j
            // v[i].dp[j]=min(v[i].dp[j],sufmin[v[i-1].pos.size()-j]+prefsum+(j-k)*v[i].pos[0]);
            //cout<<"^^ "<<j<<" "<<sufmin[max(0,(int)v[i-1].pos.size()-j)]+prefsum-j*v[i-1].pos.back()<<endl;
            v[i].dp[j]=min(v[i].dp[j],sufmin[max(0ll,(ll)v[i-1].pos.size()-j)]+prefsum-j*v[i-1].pos.back());
            //second case : k > j
            // k = j+1,....,v[i-1].pos.size()
            // v[i].dp[j]=min(v[i].dp[j],prefmin[v[i].pos-j-1]+prefsum-j*v[i-1].pos.back());
            if((ll)(v[i-1].pos.size()-j-1)>=0)
            {
                v[i].dp[j]=min((ll)v[i].dp[j],(ll)(prefmin[v[i-1].pos.size()-j-1]+prefsum-j*v[i].pos[0]));
                //cout<<"^^^ "<<j<<" "<<prefmin[v[i-1].pos.size()-j-1]+prefsum-j*v[i].pos[0]<<" "<<prefmin[v[i-1].pos.size()-j-1]<<" "<<prefsum<<" "<<j*v[i].pos[0]<<" "<<v[i-1].pos.size()-j-1<<endl;
            }
        }
        //for(int j=0;j<v[i].dp.size();j++)cout<<v[i].dp[j]<<" ";
        //cout<<endl;
    }
    //cout<<v.back().dp.back()<<endl;
	return v.back().dp.back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(ll i=0;i<r.size();i++)
      |                ~^~~~~~~~~
wiring.cpp:60:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(ll i=0;i<b.size();i++)
      |                ~^~~~~~~~~
wiring.cpp:68:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(ll i=1;i<all.size();i++)
      |                ~^~~~~~~~~~~
wiring.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(ll i=0;i<v[0].pos.size();i++)v[0].dp.push_back(INF);
      |                ~^~~~~~~~~~~~~~~~
wiring.cpp:86:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(ll i=1;i<v.size();i++)
      |                ~^~~~~~~~~
wiring.cpp:92:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if(j!=v[i-1].pos.size())sufsum+=v[i-1].pos[j];
      |                ~^~~~~~~~~~~~~~~~~~~
wiring.cpp:97:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(ll j=1;j<=v[i-1].pos.size();j++)
      |                    ~^~~~~~~~~~~~~~~~~~~
wiring.cpp:108:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(ll j=0;j<=v[i].pos.size();j++)v[i].dp.push_back(INF);
      |                    ~^~~~~~~~~~~~~~~~~
wiring.cpp:110:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(ll j=0;j<=v[i].pos.size();j++)
      |                    ~^~~~~~~~~~~~~~~~~

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