Submission #203368

#	Time	Username	Problem	Language	Result	Execution time	Memory
203368		anonymous	Wiring (IOI17_wiring)	C++14	100 / 100	74 ms	15072 KiB

wiring

#include "wiring.h"
#include<vector>
#include<utility>
#include<iostream>
#define MAXN 200005
#define LL long long
#define fi first
#define se second
#define INF (1LL<<50)
using namespace std;
vector<pair<LL,bool> > P;
LL dp[MAXN], pref[MAXN], suf[MAXN], Cost[MAXN], dp_min[MAXN];

LL get(int i) {
    if (i>=0) {return(dp_min[i]);}
    return(0);
}
LL min_total_length(std::vector<int> r, std::vector<int> b) {
	int ptR=0, ptB=0, N=r.size(), M=b.size();
	while (ptR<r.size() || ptB<b.size()) {
        if (ptR == r.size() || (ptB<b.size() && r[ptR] >= b[ptB])) {
            P.push_back({b[ptB], true});
            ptB++;
        } else {
            P.push_back({r[ptR], false});
            ptR++;
        }
	}

	int s2=0,s1=0; //indices of second and first prior swaps (if i != i+1 then s1 = i+1)
	LL cur_cost=0;
	for (int i=0; i<N+M; i++) {
        if (i && P[i].se != P[i-1].se) {
            dp_min[i]=suf[i]=INF;
            for (int j=i-1; j>=s1; j--) { //initialise costs
                Cost[j]=Cost[j+1]+P[i-1].fi-P[j].fi;
                dp_min[j]=min(dp_min[j+1], dp[j]);
            }
            if (s1) {
                pref[s1-1]=INF;
                dp_min[s1-1]=min(dp_min[s1], dp[s1-1]);
            }
            for (int j=i-1; j>=s1; j--) { //initialise suffix querys
                suf[j]=min(suf[j+1], Cost[j] + get(j-1)); //add gap cost and cur cost later
            }
            for (int j=s1; j<i; j++) {
                LL dif = i-j; //put j to i-1 to current
                pref[j]=min(j ? pref[j-1] : INF, Cost[j]+ get(j-1) + dif*(P[i].fi-P[i-1].fi)); //add cur cost later
            }
            s2 = s1;
            s1 = i;
            cur_cost=0;
        }
        cur_cost += P[i].fi - P[s1].fi;
        if (s1 == 0) {
            dp[i]=INF;
        } else {
            LL num = i-s1+1;
            dp[i]=min(suf[max(s2,i-2*(i-s1)-1)]+num*(P[s1].fi-P[s1-1].fi),
                  (i-2*(i-s1)-1)>=s2 ? pref[i-2*(i-s1)-1] : INF) + cur_cost;
        }
	}
	return(dp[N+M-1]);
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptR<r.size() || ptB<b.size()) {
         ~~~^~~~~~~~~
wiring.cpp:20:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptR<r.size() || ptB<b.size()) {
                         ~~~^~~~~~~~~
wiring.cpp:21:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ptR == r.size() || (ptB<b.size() && r[ptR] >= b[ptB])) {
             ~~~~^~~~~~~~~~~
wiring.cpp:21:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ptR == r.size() || (ptB<b.size() && r[ptR] >= b[ptB])) {
                                 ~~~^~~~~~~~~

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