Submission #559677

#	Time	Username	Problem	Language	Result	Execution time	Memory
559677		jamezzz	전선 연결 (IOI17_wiring)	C++17	100 / 100	38 ms	10900 KiB

wiring

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

#define fi first
#define se second
#define pf printf
#define LINF 1023456789123456789
#define mnto(x,y) x=min(x,(__typeof__(x))y)
typedef long long ll;
typedef pair<int,int> ii;
#define maxn 100005

ll min_total_length(vector<int> r,vector<int> b){
	int n=r.size(),m=b.size();
	vector<ii> v;
	int pr=0,pb=0;
	while(pr!=n||pb!=m){
		if(pr==n||(pb!=m&&b[pb]<r[pr]))v.push_back({b[pb++],1});
		else v.push_back({r[pr++],0});
	}
	vector<int> a;
	for(ii pr:v)a.push_back(pr.fi);
	int pv=0;
	vector<int> gl,gr,gs;
	vector<vector<ll>> dp;
	for(int i=0;i<v.size();++i){
		if(i==v.size()-1||v[i+1].se!=v[pv].se){
			gl.push_back(pv);
			gr.push_back(i);
			gs.push_back(i-pv+1);
			pv=i+1;
		}
	}
	dp.resize(gs.size());
	for(int i=0;i<gs.size();++i){
		dp[i].resize(gs[i]+1,LINF);
	}
	dp[0][gs[0]]=0;
	for(int i=1;i<gs.size();++i){
		for(int j=gs[i-1]-1;j>=0;--j){
			mnto(dp[i-1][j],dp[i-1][j+1]+a[gl[i]]-a[gr[i-1]-j]);
		}
		ll pfx=0;
		for(int j=0;j<=min(gs[i],gs[i-1]);++j){
			mnto(dp[i][gs[i]-j],dp[i-1][j]+pfx);
			if(j!=min(gs[i],gs[i-1])){
				pfx+=a[gl[i]+j]-a[gr[i-1]-j];
			}
		}
		for(int j=gs[i]-1;j>=0;--j){
			mnto(dp[i][j],dp[i][j+1]+a[gr[i]-j]-a[gr[i-1]]);
		}
	}
	/*
	for(int i=0;i<gs.size();++i){
		for(int j=0;j<=gs[i];++j){
			if(dp[i][j]==LINF)pf("-1 ");
			else pf("%lld ",dp[i][j]);
		}
		pf("\n");
	}
	*/
	return dp[gs.size()-1][0];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<v.size();++i){
      |              ~^~~~~~~~~
wiring.cpp:28:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if(i==v.size()-1||v[i+1].se!=v[pv].se){
      |      ~^~~~~~~~~~~~
wiring.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<gs.size();++i){
      |              ~^~~~~~~~~~
wiring.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=1;i<gs.size();++i){
      |              ~^~~~~~~~~~

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