Submission #50275

#	Time	Username	Problem	Language	Result	Execution time	Memory
50275		tmwilliamlin168	Wiring (IOI17_wiring)	C++14	100 / 100	74 ms	7676 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5;
const ll INF=1e18;
ll p[2*mxN], ps[2*mxN+1], dp[2*mxN+1], mn1[mxN+1]={INF};

ll min_total_length(vector<int> r, vector<int> b) {
	int n=r.size()+b.size();
	vector<pii> cls;
	for(int i=0, ri=0, bi=0, lc=-1, cc; i<n; ++i, lc=cc) {
		if(ri>=r.size()||bi<b.size()&&b[bi]<r[ri]) {
			p[i]=b[bi++];
			cc=0;
		} else {
			p[i]=r[ri++];
			cc=1;
		}
		ps[i+1]=p[i]+ps[i];
		if(cc!=lc)
			cls.push_back({i, i});
		else
			++cls.back().se;
	}
	for(int i=cls[0].fi; i<=cls[0].se; ++i)
		dp[i+1]=INF;
	for(int bi=0; bi<cls.size()-1; ++bi) {
		for(int i=0; i<=cls[bi].se-cls[bi].fi; ++i)
			mn1[i+1]=min(min(dp[i+cls[bi].fi], dp[cls[bi+1].fi])+(cls[bi].se-cls[bi].fi+1-i)*p[cls[bi+1].fi]+ps[cls[bi].fi+i], mn1[i]);
		ll mn2=INF;
		for(int i=0; i<=cls[bi+1].se-cls[bi+1].fi; ++i) {
			dp[i+cls[bi+1].fi+1]=mn2-(i+1)*p[cls[bi].se];
			if(i<=cls[bi].se-cls[bi].fi) {
				dp[i+cls[bi+1].fi+1]=min(mn1[cls[bi].se-cls[bi].fi+1-i]-(i+1)*p[cls[bi+1].fi], dp[i+cls[bi+1].fi+1]);
				mn2=min(min(dp[cls[bi].se-i], dp[cls[bi+1].fi])+(i+1)*p[cls[bi].se]+ps[cls[bi].se-i], mn2);
			}
			dp[i+cls[bi+1].fi+1]+=ps[cls[bi+1].fi+i+1]-2*ps[cls[bi+1].fi];
		}
	}
	return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ri>=r.size()||bi<b.size()&&b[bi]<r[ri]) {
      ~~^~~~~~~~~~
wiring.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ri>=r.size()||bi<b.size()&&b[bi]<r[ri]) {
                    ~~^~~~~~~~~
wiring.cpp:18:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(ri>=r.size()||bi<b.size()&&b[bi]<r[ri]) {
wiring.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int bi=0; bi<cls.size()-1; ++bi) {
                ~~^~~~~~~~~~~~~

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