Submission #291185

#	Time	Username	Problem	Language	Result	Execution time	Memory
291185		shayan_p	Wiring (IOI17_wiring)	C++17	100 / 100	75 ms	11240 KiB

wiring

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 2e5 + 10, inf = 1e9 + 10, mod = 1e9 + 7;

ll dl[maxn];
ll dp[maxn];
int blk[maxn];
ll sm[maxn];

ll min_total_length(vector<int> A, vector<int> B){
    vector<pii> vec;
    for(int x : A)
	vec.PB({x, 0});
    for(int x : B)
	vec.PB({x, 1});
    sort(vec.begin(), vec.end());
    int n = sz(vec);
    for(int i = 0; i < n; i++){
	if(vec[i].S){
	    int id = lower_bound(A.begin(), A.end(), vec[i].F) - A.begin();
	    dl[i] = min( id == sz(A) ? inf : (A[id] - vec[i].F), id == 0 ? inf : (vec[i].F - A[id-1]) );
	}
	else{
	    int id = lower_bound(B.begin(), B.end(), vec[i].F) - B.begin();
	    dl[i] = min( id == sz(B) ? inf : (B[id] - vec[i].F), id == 0 ? inf : (vec[i].F - B[id-1]) );
	}
    }
    for(int i = 0; i < n; i++){
	sm[i+1] = sm[i] + vec[i].F;
    }
    
    blk[0] = 1;
    for(int i = 1; i < n; i++){
	if(vec[i].S == vec[i-1].S)
	    blk[i] = blk[i-1] + 1;
	else
	    blk[i] = 1;
    }
    auto Sum = [](int pos, int cnt){ // 1 base
		   return sm[pos] - sm[pos - cnt];
	       };
    for(int i = 0; i < n; i++){
	dp[i+1] = dp[i] + dl[i];
	int cnt = blk[i];
	if(cnt + cnt <= i+1 && blk[i-cnt] >= cnt){
	    dp[i+1] = min(dp[i+1], dp[i+1-cnt-cnt] + Sum(i+1, cnt) - Sum(i+1-cnt, cnt));
	}
    }
    return dp[n];
}

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