Submission #1022952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022952		hirayuu_oj	Wiring (IOI17_wiring)	C++17	20 / 100	18 ms	2004 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll=long long;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	if(r.size()<=1000&&b.size()<=1000){
		if(r.size()<b.size())swap(r,b);
		int n=r.size();
		int m=b.size();
		vector<ll> dp(m,1LL<<60);
		dp[0]=abs(r[0]-b[0]);
		for(int k=1; k<m; k++)dp[k]=dp[k-1]+abs(r[0]-b[k]);
		for(int i=1; i<n; i++){
			vector<ll> ndp(m,1LL<<60);
			rep(j,m){
				rep(k,j+1)ndp[j]=min(ndp[j],dp[j]+abs(r[i]-b[k]));
				ll cbl=0;
				for(int k=j+1; k<m; k++){
					cbl+=abs(r[i]-b[k]);
					ndp[k]=min(ndp[k],dp[j]+cbl);
				}
			}
			swap(dp,ndp);
		}
		return dp[m-1];
	}
	else{
		ll ans=0;
		rep(i,max(b.size(),r.size())){
			ans+=abs(r[min((int)r.size()-1,i)]-b[max(0,(int)b.size()-1-i)]);
		}
		return ans;
	}
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
wiring.cpp:31:3: note: in expansion of macro 'rep'
   31 |   rep(i,max(b.size(),r.size())){
      |   ^~~

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