| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 448226 | blue | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> R, B;
int N, M;
vector<int> S;
vector< vector<long long> > X;
vector< vector<long long> > Xsum;
const long long INF = 1'000'000'000'000'000'000LL;
long long get_score(int i, int p1, int p2)
{
long long size1 = S[i] - p1 + 1;
long long size2 = p2;
// cerr << "size ";
// cerr << size1 << ' ' << size2 << '\n';
long long ans = Xsum[i+1][size2] - (Xsum[i][S[i]] - Xsum[i][S[i] - size1]);
// cerr << "ans = " << ans << '\n';
// cerr << X[i+1][1] * (size1 - size2) << '\n';
if(size1 > size2) ans += X[i+1][1] * (size1 - size2);
else if(size1 < size2) ans -= X[i].back() * (size2 - size1);
// cerr << "get score " << i << ' ' << p1 << ' ' << p2 << ' ' << ans << '\n';
return ans;
}
struct segtree
{
int l;
int r;
long long mn = 0;
long long lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void add(int L, int R, long long V)
{
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
mn += V;
lp += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = lp + min(left->mn, right->mn);
}
}
long long rangemin(int L, int R)
{
if(R < l || r < L) return INF;
else if(L <= l && r <= R) return mn;
else return lp + min(left->rangemin(L, R), right->rangemin(L, R));
}
};
long long min_total_length(vector<int> r, vector<int> b)
{
//PART 0: GET INPUT AND DIVIDE INTO BLOCKS
R = r;
B = b;
N = R.size();
M = B.size();
int I[N+M];
for(int i = 1; i <= N; i++) I[i-1] = i;
for(int j = 1; j <= M; j++) I[N+j-1] = -j;
sort(I, I+N+M, [] (int x, int y)
{
int px = x > 0 ? R[x-1] : B[-(x+1)];
int py = y > 0 ? R[y-1] : B[-(y+1)];
return px < py;
});
for(int j = 0; j < N+M; j++)
{
// cerr << "j = " << I[j] << '\n';
int new_vector = (j == 0 || ((I[j] > 0) != (I[j-1] > 0)));
if(new_vector)
{
S.push_back(0);
X.push_back(vector<long long>(1, 0));
}
int i = I[j];
X.back().push_back(i > 0 ? R[i-1] : B[-(i+1)]);
S[S.size()-1]++;
}
Xsum = X;
for(int i = 0; i < X.size(); i++)
{
for(int j = 1; j < X[i].size(); j++)
{
Xsum[i][j] += Xsum[i][j-1];
}
// cerr << i << ' ' << S[i] << ": ";
// for(int j = 0; j < X[i].size(); j++) cerr << X[i][j] << ' ';
// cerr << "| ";
// for(int j = 0; j < Xsum[i].size(); j++) cerr << Xsum[i][j] << ' ';
// cerr << '\n';
}
// cerr << get_score(6, 2, 1) << '\n';
vector<long long> res[X.size()];
// cerr << "blocks = " << X.size() << '\n';
res[0] = vector<long long>(X[0].size());
res[0][0] = 0;
for(int j = 1; j < res[0].size(); j++)
{
// cerr << 0 << ' ' << j << ' ' << X[0][j] << ' ' << INF << '\n';
res[0][j] = INF;
}
res[1] = vector<long long>(X[1].size());
res[1][0] = INF;
for(int j = 1; j < res[1].size(); j++)
{
res[1][j] = get_score(0, 1, j);
// cerr << 1 << ' ' << j << ' ' << X[1][j] << ' ' << res[1][j] << '\n';
}
// cerr << "yes\n";
for(int i = 2; i < X.size(); i++)
{
// cerr << "i = " << i << '\n';
res[i] = vector<long long>(X[i].size());
res[i][0] = res[i-1].back();
// cerr << i << ' ' << 0 << ' ' << '?' << ' ' << res[i][0] << '\n';
segtree S(0, res[i-1].size() + 5);
for(int K = 1; K < res[i-1].size(); K++)
S.add(K, K, min(res[i-1][K-1], res[i-1][K]));
int prev_size = res[i-1].size();
//j = 1
for(int k = 1; prev_size - k >= 1; k++)
S.add(prev_size - k, prev_size k, k * (+1 * X[i][1]));
for(int K = 1; K < res[i-1].size(); K++)
S.add(K, K, -1 * (Xsum[i-1].back() - Xsum[i-1][K-1]));
if(1 < res[i].size())
res[i][1] = S.rangemin(1, res[i-1].size()-1);
for(int j = 2; j < res[i].size(); j++)
{
res[i][j] = INF;
for(int j1 = 1; j1 < res[i-1].size(); j1++)
res[i][j] = min(res[i][j], min(res[i-1][j1-1], res[i-1][j1]) + get_score(i-1, j1, j));
// cerr << i << ' ' << j << ' ' << X[i][j] << ' ' << res[i][j] << '\n';
}
}
return res[X.size()-1].back();
}