Submission #363506

#	Time	Username	Problem	Language	Result	Execution time	Memory
363506		Fysty	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	492 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],cnt[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());
    dp[0]=0;
    ll last=0,d=1,sum=0;
    for(int i=1;i<v.size();i++)
    {
        if(v[i-1].S!=v[i].S)
        {
            dp[i]=INF;
            ll tmp=0,cur=i-1;
            while(v[cur].S==v[i-1].S)
            {
                tmp+=v[i].F-v[cur].F;
                //cout<<cur<<":"<<tmp<<"&"<<dp[cur]<<"&"<<dp[cur-1]<<" ";
                dp[i]=min({dp[i],dp[cur]+tmp,dp[cur-1]+tmp});
                cur--;
            }
            last=i-1,d=1,sum=v[i].F-v[i-1].F;
        }
        else
        {
            dp[i]=dp[i-1]+v[i].F-v[last].F;
            if(v[last].S==v[last-d].S)
            {
                sum+=v[i].F-v[last-d].F;
                dp[i]=min(dp[i],dp[last-d-1]+sum),d++;
            }
        }
        //cout<<dp[i]<<"\n";
    }
    return dp[v.size()-1];
}
/*
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;
    }
    cout<<min_total_length(a,b);
}
*/

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:25: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]
   25 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~

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