Submission #291009

#	Time	Username	Problem	Language	Result	Execution time	Memory
291009		shayan_p	Wiring (IOI17_wiring)	C++17	7 / 100	66 ms	8936 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 = 1e5 + 10, inf = 1e9 + 10, mod = 1e9 + 7;

ll dl[maxn];
ll dp[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 j = 0; j < n; j++){
	dp[j] = dl[j] + (j == 0 ? 0 : dp[j-1]);
	priority_queue<ll> pq[2];
	ll SM = 0, num = 0; 
	for(int i = j; i >= 0 ;i--){
	    if(pq[!vec[i].S].empty()){
		num+= vec[i].F;
		pq[vec[i].S].push(dl[i] - vec[i].F);
		SM+= dl[i] - vec[i].F;
	    }
	    else{
		SM-= pq[!vec[i].S].top();
		pq[!vec[i].S].pop();
		num+= -vec[i].F;
	    }
	    dp[j] = min(dp[j], num + SM + (i == 0 ? 0 : dp[i-1]));
	    if(pq[0].empty() && pq[1].empty())
		break;
	}
    }
    return dp[n-1];
}

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