제출 #54432

#제출 시각아이디문제언어결과실행 시간메모리
54432leejseo전선 연결 (IOI17_wiring)C++14
0 / 100
2 ms576 KiB
#include <bits/stdc++.h> #include "wiring.h" using namespace std; #define abs(x) std::max(x, -(x)) typedef long long lld; typedef pair<int, int> pii; class triple{ public: int x, y, z; triple (int x_, int y_, int z_) { x = x_, y = y_, z = z_; } }; vector<triple> X; vector<pii> Y; lld S[200005]; int con[200001]; int lst[400002]; lld D[200002]; long long min_total_length(vector<int> A, vector<int> B) { int N = A.size(), M = B.size(); int K = N+M; int i = 0, j = 0; while (i+j < K){ if (j >= M || (i < N && A[i] <= B[j])){ X.push_back(triple(A[i], i, 0)); if (j >= M) Y.push_back(pii(abs(A[i] - B.back()), M-1)); else Y.push_back(min(pii(abs(A[i]-B[j-1]), j-1), pii(abs(A[i]-B[j]), j))); i++; } else{ X.push_back(triple(B[j], j, 1)); if (i >= N) Y.push_back(pii(abs(B[j] - A.back()), N-1)); else Y.push_back(min(pii(abs(A[i-1]-B[j]), i-1), pii(abs(A[i]-B[j]), i))); j++; } } int cur = 0; for (int i=0; i<K; i++) con[i] = -2; for (int i=0; i<K+K+1; i++) lst[i] = -2; lst[K] = -1; for (int i=0; i<K; i++){ if (X[i].z == 1){ cur++; S[i] = X[i].x; } else{ cur--; S[i] = -X[i].x; } if (i > 0) S[i] += S[i-1]; if (lst[cur+K] >= -1) con[i] = lst[cur+K]; lst[cur+K] = i; } for (int i=0; i<K; i++){ D[i] = D[(i-1)%(K+1)] + Y[i].first; if (con[i] >= -1){ int j = con[i]; D[i] = min(D[i], D[(j % (K+1))] + abs(S[i]-S[j])); } } return D[K-1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...