Submission #429072

#	Time	Username	Problem	Language	Result	Execution time	Memory
429072		REALITYNB	Wiring (IOI17_wiring)	C++14	13 / 100	67 ms	10652 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define ll  long long
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
const ll inf = 1e18 ;
ll min_total_length(vector<int> r,vector<int> bb){
    vector<ll> a ;
    for(int&x:r) ++x ;
    for(int&x: bb) ++x;
    for(ll x:r) a.pb(x) ;
    for(ll x:bb) a.pb(-x) ;
    sort(all(a),[&](ll x,ll y){return abs(x) <abs(y) ; });
    ll n = a.size() ;
    vector<vector<ll>> b ;
    for(ll i=0;i<n;i++){
        ll sz = 0 ;
        vector<ll> hey  ;
        for(ll j=i;j<n;j++){
            if(a[i]*a[j]<0) break ;
            hey.pb(j);
            i=j ;
        }
        b.pb(hey);
    }
    for(ll&x:a)if(x<0) x*=-1 ;
    for(ll&x:a) --x;
    /*cout << b.size() << endl ;
    for(auto x :b){
        for(ll y:x) cout << y << " ";
        cout << endl ;
    }*/
    vector<ll> dp(n,inf) ;
    ll sumi = 0 ;
    for(ll x:b[0]) sumi+=a[x] ;
    ll loli = a[b[1][0]]*(b[0].size()) ;
    for(ll i=0;i<b[1].size();i++){
            loli+=a[b[1][i]];
        if(i+1>b[0].size()){
            sumi+=a[b[0].back()];
        }
        else loli-=a[b[1][0]];
//            cout << loli << " " << sumi << " "<< a[b[1][0]] << endl ;

        dp[b[1][i]]=loli-sumi ;
    }
    dp[b[0].back()]=dp[b[1][0]];
    for(ll i=2;i<b.size();i++){
        ll prev = dp[b[i-1].back()] ;
        ll lol = b[i-1].back();
        ll sum = 0 ;
        for(ll j=0;j<b[i].size();j++){
            prev+=a[b[i][j]];
            prev-=a[b[i-1].back()] ;
            if(lol-j>=b[i-1][0]){
                sum+=a[b[i][j]];
                sum-=a[lol-j];
                prev=min(prev,dp[lol-j-1]+sum) ;
            }
            dp[b[i][j]]=min(dp[b[i][j]],prev) ;
        }
        ll mn = min(b[i].size(),b[i-1].size()) ;
        prev=inf;
         sum = 0;
        for(ll j=0;j<mn;j++) sum+=a[b[i][j]];
        for(ll j=b[i-1].size()-1;j>b[i-1].size()-1-mn;j--) sum-=a[b[i-1][j]];
        ll nigg =sum ;
        for(ll j=b[i-1].size()-1-mn;j>=0;j--){
            nigg-=a[b[i-1][j]];
            nigg+=a[b[i][0]];
            prev=min(prev,dp[b[i-1][j]-1]+nigg);
        }
        for(ll j=mn-1;j>-1;j--){
            prev=min(prev,sum+dp[lol-j-1]) ;
            dp[b[i][j]]=min(dp[b[i][j]],prev) ;
            prev-=a[b[i][j]];
            prev+=a[b[i][0]];
            sum-=a[b[i][j]] ;
            sum+=a[lol-j-1];
        }

    }
 //  for(ll x: dp) cout << x << " " ;
    return dp.back() ;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:12: warning: unused variable 'sz' [-Wunused-variable]
   18 |         ll sz = 0 ;
      |            ^~
wiring.cpp:38: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]
   38 |     for(ll i=0;i<b[1].size();i++){
      |                ~^~~~~~~~~~~~
wiring.cpp:40:15: 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]
   40 |         if(i+1>b[0].size()){
      |            ~~~^~~~~~~~~~~~
wiring.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(ll i=2;i<b.size();i++){
      |                ~^~~~~~~~~
wiring.cpp:53: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]
   53 |         for(ll j=0;j<b[i].size();j++){
      |                    ~^~~~~~~~~~~~
wiring.cpp:67:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   67 |         for(ll j=b[i-1].size()-1;j>b[i-1].size()-1-mn;j--) sum-=a[b[i-1][j]];
      |                                  ~^~~~~~~~~~~~~~~~~~~

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