제출 #1047985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047985		Trent	전선 연결 (IOI17_wiring)	C++17	17 / 100	1097 ms	12228 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const ll INF = 1e17;

struct grp{
	char ty;
	vi pos;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = r.size(), m = b.size();
	vector<grp> gps;
	int api=0, bpi=0;
	while(api < n || bpi < m) {
		if(api < n && (bpi == m || r[api] < b[bpi])) {
			gps.push_back({'r', {}});
			while(api < n && (bpi == m || r[api] < b[bpi])) {
				gps.back().pos.push_back(r[api]);
				++api;
			}
		} else {
			gps.push_back({'b', {}});
			while(bpi < m && (api == n || r[api] > b[bpi])) {
				gps.back().pos.push_back(b[bpi]);
				++bpi;
			}
		}
	}

	int l = gps.size();
	vi cnt(l);
	forR(i, l) cnt[i] = gps[i].pos.size();
	vvll dp(l);
	forR(i, l) dp[i].resize(cnt[i] + 1);
	forR(i, l) {
		if(i == 0) {
			forR(j, cnt[i]) dp[i][j] = INF;
			dp[i][cnt[i]] = 0;
		} else {
			forR(bck, cnt[i] + 1) {
				int fwd = cnt[i] - bck;
				if(bck == 0) dp[i][fwd] = dp[i-1][0];
				else {
					dp[i][fwd] = INF;
					forR(las, cnt[i-1] + 1) {
						ll cTot = dp[i-1][las];
						REP(j, cnt[i-1] - las, cnt[i-1]) cTot += gps[i-1].pos.back() - gps[i-1].pos[j];
						forR(j, bck) cTot += gps[i].pos[j] - gps[i].pos.front();
						cTot += (ll) max(las, bck) * (gps[i].pos.front() - gps[i-1].pos.back());
						dp[i][fwd] = min(dp[i][fwd], cTot);
					}
				}
			}
		}
	}
	// forR(i, l) {
	// 	forR(j, cnt[i] + 1) cout << dp[i][j] << ' ';
	// 	cout << '\n';
	// }
	return dp[l-1][0];
}

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