Submission #363519

#	Time	Username	Problem	Language	Result	Execution time	Memory
363519		Fysty	Wiring (IOI17_wiring)	C++17	100 / 100	63 ms	13528 KiB

wiring

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
//#define int ll
const int MOD=1e9+7;
const ll INF=1e16;
const int N=200005;
ll dp[N],sum[N],l[N],r[N];
ll min_total_length(vector<int> R,vector<int> b)
{
    vector<pll> v;
    v.pb({-INF,-1});
    for(int i=0;i<R.size();i++) v.pb({R[i],0});
    for(int i=0;i<b.size();i++) v.pb({b[i],1});
    sort(v.begin(),v.end());
    v.pb({INF,-1});
    dp[0]=0;
    ll last=0,d=0,prv=0;
    for(int i=1;i<v.size()-1;i++)
    {
        //cout<<i<<": ";
        if(v[i-1].S!=v[i].S)
        {
            //cout<<"HI";
            for(int j=i;v[j].S==v[i].S;j++) sum[i]+=v[j].F;
            for(int j=i-1;j>=last;j--)
            {
                r[j]=v[i-1].F*(i-j)-sum[j]+min(dp[j],dp[j-1]);
                if(j!=i-1) r[j]=min(r[j],r[j+1]);
            }
            for(int j=last;j<=i-1;j++)
            {
                l[j]=v[i].F*(i-j)-sum[j]+min(dp[j],dp[j-1]);
                if(j!=last) l[j]=min(l[j],l[j-1]);
            }
            last=i,prv=d,d=1;
        }
        else d++,sum[i]=sum[i-1]-v[i-1].F;
        if(last==1)
        {
            dp[i]=INF;
            continue;
        }
        ll cur=sum[last]-sum[i]+v[i].F;
        if(prv<=d) dp[i]=r[last-prv]-d*v[last-1].F+cur;
        else dp[i]=min(r[last-d]-d*v[last-1].F+cur,l[last-d-1]-d*v[last].F+cur);
        //cout<<dp[i]<<"\n";
    }
    return dp[v.size()-2];
}
/*
int main()
{
    ll n,m;
    cin>>n>>m;
    //n=200,m=200;
    vector<int> a(n),b(m);
    rep(i,n)
    {
        cin>>a[i];
        //a[i]=1e9-i;
    }
    rep(i,m)
    {
        cin>>b[i];
        //b[i]=1e9-(n-1)-i;
    }
    ll k=min_total_length(a,b);
    cout<<k;
    return 0;
}
*/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<R.size();i++) v.pb({R[i],0});
      |                 ~^~~~~~~~~
wiring.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<b.size();i++) v.pb({b[i],1});
      |                 ~^~~~~~~~~
wiring.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=1;i<v.size()-1;i++)
      |                 ~^~~~~~~~~~~

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