Submission #990406

#	Time	Username	Problem	Language	Result	Execution time	Memory
990406		StefanSebez	전선 연결 (IOI17_wiring)	C++14	13 / 100	16 ms	3932 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const ll inf=1e9;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n=r.size(),m=b.size();
	ll res=0;
	bool subtask2=false;if(r.back()<b[0]) subtask2=true;
	if(subtask2){
		for(int i=n-1,j=m-1;i>=0 || j>=0;){
			if(i==-1 && j>0){
				while(j>=0){
					res+=b[j]-r[n-1];
					j--;
				}
				break;
			}
			else if(i>0 && j==-1){
				while(i>=0){
					res+=b[0]-r[i];
					i--;
				}
				break;
			}
			else{
				res+=b[j]-r[i];
				j--;
				i--;
			}
		}
	}
	else{
		if(n>m){
			swap(n,m);
			swap(r,b);
		}
		int best[m+10];
		for(int i=0;i<m;i++){
			best[i]=inf;
			for(int j=0;j<n;j++){
				best[i]=min(best[i],abs(b[i]-r[j]));
			}
			//printf("%i\n",best[i]);
		}
		res=inf;
		for(int k=0;k<=n;k++){
			ll ans=0;
			vector<int>B;
			for(int i=0;i<=m-1;i++){
				if(i<k || i>=k+m-n) B.pb(b[i]);
			}
			/*printf("%i: ",k);
			for(auto i:B) printf("%i ",i);
			printf("\n");*/
			for(int i=n-1;i>=0;i--){
				ans+=abs(B[i]-r[i]);
			}
			for(int i=k;i<k+m-n;i++){
				ans+=best[i];
			}
			res=min(res,ans);
		}
		/*for(int i=n-1,j=m-1;i>=0 || j>=0;){
			if(i==-1){

				break;
			}
			else if(j==-1){
				break;
			}
			res+=abs(r[i]-b[j]);
		}*/
	}
	/*ll dp[n+1][m+1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(r[i-1]>b[j-1]){
				dp[]
			}
			else{

			}
		}
	}*/
	return res;
}

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