oj.uz

답안 #56573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56573 2018-07-11T19:02:10 Z naderjemel 전선 연결 (IOI17_wiring) C++14
0 / 100
 4 ms 584 KB 
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 1000000;

const long long inf = 1LL<<60;

int nex[MAXN];
long long sum[MAXN], dp[MAXN], f[MAXN];

inline long long get_sum(const int lo, const int hi){
	return sum[lo] - sum[hi+1];
}

long long min_total_length(vector <int> red, vector <int> blue){
	int n = blue.size(), m = red.size();
	vector< pair<int,int> > q;
	int pb = 0, pr = 0;
	while (pb < n || pr < m){
		if ((pr == m) || (pb < n && blue[pb] < red[pr]))
			q.push_back(make_pair(blue[pb++], 0));
		else
				q.push_back(make_pair(red[pr++], 1));
	}
	int nm = n + m;
	sum[nm] = 0, f[nm] = 0;
	dp[nm-1] = inf, nex[nm-1] = nm, sum[nm-1] = q[nm-1].first;
	for (int i = nm - 2; i >= 0; i--){
		dp[i] = inf;
		sum[i] = sum[i+1] + q[i].first;
		nex[i] = q[i].second == q[i+1].second ? nex[i+1] : i+1;
		if (nex[i] == i+1){
			for (int j = nex[i+1]-1; j >= i+1; j--)
				f[j] = min(dp[j], q[j].first - q[i].first + dp[j+1]);
		}
		if (nex[i] == nm)
			continue;
		dp[i] = min(inf, dp[i+1] + q[nex[i]].first - q[i].first);
		int sz = nex[i] - i;
	
			dp[i] = min(dp[i], get_sum(nex[i], nex[i]+sz-1) - get_sum(i, nex[i]-1) + f[nex[i]+sz]);
		}
	
	return dp[0];
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '19417'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 488 KB 3rd lines differ - on the 1st token, expected: '904', found: '624'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 544 KB Output is correct
2 Incorrect 3 ms 544 KB 3rd lines differ - on the 1st token, expected: '17703', found: '17909'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 584 KB 3rd lines differ - on the 1st token, expected: '27', found: '-27'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB 3rd lines differ - on the 1st token, expected: '25859', found: '19417'
2 Halted 0 ms 0 KB -