#define _CRT_SECURE_NO_WARNINGS
#include "wiring.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define sz(l,r) (r-l+1)
#define sum(l,r) ((long long)((int)r>=(int)l ? (long long)(pre[r]-(l==0 ? 0ll:pre[l-1])):0ll) -sz(l,r)*val[l])
#define sum1(l,r) abs(((long long)((int)r>=(int)l ? (long long)(pre[r]-(l==0 ? 0ll:pre[l-1])):0ll) -sz(l,r)*val[r]))
const int N = 2e5 + 7;
struct seg {
int tl, tr;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
vector<pair<int, int>> all;
for (int to : r)all.push_back({ to,0 });
for (int to : b)all.push_back({ to,1 });
int n = all.size();
sort(all.begin(), all.end());
vector<int> kind, val,left(n,0);
for (int i = 0; i < n; ++i) {
kind.push_back(all[i].second);
val.push_back(all[i].first);
if (i == 0 || kind[i] != kind[i - 1]) {
left[i] = i;
}
else left[i] = left[i - 1];
}
vector<long long> dp(n, (long long)1e18),pre(n,0),dpmx(n,(long long)1e18);
for (int i = 0; i < n; ++i)if (i == 0)pre[i] = val[i]; else pre[i] = val[i] + pre[i - 1];
int opt=-1;
for (int i = 0; i < n; ++i) {
// cout << "current i = "<<i<<" opt= "<<opt<<":\n"<< endl;
if (left[i] == 0) {
dp[i] = 0; continue;
}
auto gum=[&] (int l, int r) {
int m = left[r];
// cout << "left=="<<l<<" and Left of "<<r<<" is "<<m <<":\n"<< endl;
// cout << "sum(" << l << "," << m - 1 << ") = " << sum(l, m - 1) << endl;
// cout << "sum(" << m << "," << r << ") = " << sum(m,r) << endl;
return sum1(l, m - 1) + sum(m, r) + max(sz(l, m - 1), sz(m, r))*(val[m]-val[m-1]);
};
if (left[left[i] - 1] == 0) {
dp[i] = gum(left[left[i]-1],i);
}
else if (i == left[i]) {
opt = left[left[i] - 1] + (left[left[i-1]-1]==0);
for (; opt < left[i] - 1; ++opt) {
if (gum(opt, i) + dpmx[opt - 1] >= gum(opt + 1, i) + dpmx[opt]) {
continue;
}
break;
}
dp[i] = gum(opt, i) + dpmx[opt - 1];
}
else {
int L = left[left[i] - 1];
if (opt == L) {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
else {
// cout << i << " " << opt << endl;
if (left[i] - 1 - opt > i - left[i]-1) {
dp[i] = dp[i - 1] + val[i] - val[i - 1];
}
else {
if (left[i] - opt - 1 == i - left[i]-1) {
if (opt-1>=L+(left[left[opt]-1]==0)&&dpmx[opt - 2] + gum(opt-1, i) <= dpmx[opt-1]+gum(opt,i)) {
dp[i] = dpmx[opt - 2] + gum(opt - 1, i);
opt--;
}
else {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
}
else {
dp[i] = dp[i - 1] + val[i] - val[left[i] - 1];
}
}
}
}
if (i != n - 1 && left[i + 1] != left[i]) {
for (int r = i; r >= 0; r--) {
if (r == i)dpmx[r] = dp[r];
else if (dpmx[r] <= dpmx[r + 1] && dpmx[r] <= dp[r])break;
else dpmx[r] = min(dp[r], dpmx[r + 1]);
}
}
}
int C;
for (int i = 0; i < n; ++i) {
// cout << "dp["<<i<<"] = " << dp[i] << ":\n";
}
return dp[n-1];
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:94:6: warning: unused variable 'C' [-Wunused-variable]
int C;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
248 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25466' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
480 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
9664 KB |
3rd lines differ - on the 1st token, expected: '41596985758595', found: '74924604526513' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
9664 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
9664 KB |
3rd lines differ - on the 1st token, expected: '17703', found: '17694' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
9664 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
13444 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '315900839' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
248 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '25466' |
| 2 |
Halted |
0 ms |
0 KB |
- |
