Submission #122909

#	Time	Username	Problem	Language	Result	Execution time	Memory
122909		baqargam	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	376 KiB

wiring

#include<bits/stdc++.h>
#include "wiring.h"

using namespace std;

long long n,m,bs[200005],bn[200005],sum[200005],dp[200005],j;
vector<pair<int,int> >w;
/**/
long long cnt(long long l,long long r) {
    long long m=bs[r];
    long long res=(long long)(w[m].first-w[m-1].first)*max(r-m+1,m-l);
    res+=w[m-1].first*(m-l);
    res-=(sum[m-1]-sum[l-1]);
    res+=sum[r]-sum[m-1];
    res-=w[m].first*(r-m+1);
    res+=dp[l-1];
	return res;
}
/**/

void preprnt(){
    for(int i=1;i<=n+m;i++)
        cout<<w[i].first<<" "; cout<<"  position"<<endl;
    for(int i=1;i<=n+m;i++)
        cout<<w[i].second<<" "; cout<<"  color"<<endl;
    for(int i=1;i<=n+m;i++)
        cout<<bn[i]<<" "; cout<<"  block number"<<endl;
    for(int i=1;i<=n+m;i++)
        cout<<bs[i]<<" "; cout<<"  block start"<<endl;
    for(int i=1;i<=n+m;i++)
        cout<<sum[i]<<" "; cout<<endl;
    cout<<"  ";
}
long long min_total_length(vector<int> r, vector<int> b) {
    n=r.size();
    m=b.size();
    for(int i=0;i<n;i++)
        w.push_back({r[i],0});
    for(int i=0;i<m;i++)
        w.push_back({b[i],1});
    w.push_back({-100000,-100000});
    sort(w.begin(),w.end());
    for(int i=1;i<=n+m;i++){
        sum[i]=w[i].first;
        bn[i]=bn[i-1];bs[i]=bs[i-1];
        sum[i]+=sum[i-1];
        if(w[i].second!=w[i-1].second || i==0)
        {
            bn[i]++;
            bs[i]=i;
        }
    }
    //preprnt();
    for(int i=1;i<=n+m;i++){
        if(bn[i]==1) continue;
        if(bn[i]!=bn[i-1])
            j=i-1;
        dp[i]=cnt(j,i);
        while(cnt(j-1,i)<dp[i] && bn[j]==bn[j-1]){
            j--;
            dp[i]=cnt(j,i);
        }
     //   cout<<dp[i]<<" ";
    }
//    cout<<endl;
    return dp[n+m];
}

Compilation message (stderr)

wiring.cpp: In function 'void preprnt()':
wiring.cpp:22:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n+m;i++)
     ^~~
wiring.cpp:23:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         cout<<w[i].first<<" "; cout<<"  position"<<endl;
                                ^~~~
wiring.cpp:24:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n+m;i++)
     ^~~
wiring.cpp:25:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         cout<<w[i].second<<" "; cout<<"  color"<<endl;
                                 ^~~~
wiring.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n+m;i++)
     ^~~
wiring.cpp:27:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         cout<<bn[i]<<" "; cout<<"  block number"<<endl;
                           ^~~~
wiring.cpp:28:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n+m;i++)
     ^~~
wiring.cpp:29:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         cout<<bs[i]<<" "; cout<<"  block start"<<endl;
                           ^~~~
wiring.cpp:30:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n+m;i++)
     ^~~
wiring.cpp:31:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         cout<<sum[i]<<" "; cout<<endl;
                            ^~~~

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