제출 #513739

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

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
const ll INF=1e9+7;
vector<ll>V[LIM], dp[LIM], midp[LIM];
vector<pair<int,int>>T;
int n;
long long min_total_length(vector<int>R, vector<int>B) {
	for(auto i : R) T.pb({i, 0});
	for(auto i : B) T.pb({i, 1});
	sort(all(T));
	V[0].pb(T[0].st);
	for(int i=1; i<T.size(); ++i) {
		if(T[i].nd!=T[i-1].nd) ++n;
		V[n].pb(T[i].st);
	}
	++n;
	V[n].pb(2*INF);
	ll sum=0;
	for(auto i : V[0]) sum+=V[1][0]-i;
	rep(i, V[0].size()+1) {
		dp[0].pb(sum);
		midp[0].pb(sum);
	}
	for(int i=1; i<n; ++i) {
		sum=0;
		for(auto j : V[i]) sum+=V[i+1][0]-j;
		ll akt=dp[i-1][dp[i-1].size()-1];
		dp[i].pb(sum+midp[i-1].back());
		rep(j, V[i].size()) {
			sum-=V[i+1][0]-V[i][j];
			sum+=V[i][j]-V[i][0];
			if(j<dp[i-1].size()) akt=min(akt, dp[i-1][dp[i-1].size()-j-1]);
			akt+=V[i][0]-V[i-1][V[i-1].size()-1];
			dp[i].pb(sum+akt);
			if(j<=midp[i-1].size()-2) {
				dp[i][dp[i].size()-1]=min(dp[i][dp[i].size()-1], sum+midp[i-1][midp[i-1].size()-j-2]);
			}
		}
		midp[i].pb(dp[i][0]);
		for(int j=1; j<dp[i].size(); ++j) midp[i].pb(min(midp[i][midp[i].size()-1], dp[i][j]));
	}
	return dp[n-1].back();
}

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=1; i<T.size(); ++i) {
      |               ~^~~~~~~~~
wiring.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
wiring.cpp:29:2: note: in expansion of macro 'rep'
   29 |  rep(i, V[0].size()+1) {
      |  ^~~
wiring.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
wiring.cpp:38:3: note: in expansion of macro 'rep'
   38 |   rep(j, V[i].size()) {
      |   ^~~
wiring.cpp:41:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    if(j<dp[i-1].size()) akt=min(akt, dp[i-1][dp[i-1].size()-j-1]);
      |       ~^~~~~~~~~~~~~~~
wiring.cpp:44:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if(j<=midp[i-1].size()-2) {
      |       ~^~~~~~~~~~~~~~~~~~~~
wiring.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int j=1; j<dp[i].size(); ++j) midp[i].pb(min(midp[i][midp[i].size()-1], dp[i][j]));
      |                ~^~~~~~~~~~~~~

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