Submission #38938

#TimeUsernameProblemLanguageResultExecution timeMemory
38938moonrabbit2Wiring (IOI17_wiring)C++14
100 / 100
66 ms12180 KiB
// 자꾸 범위 초과해서 테스트. // 출처: http://blog.myungwoo.kr/117 [PS 이야기] #include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long lld; #define MAXN 100005 #define sz(v) ((int)(v).size()) int N, M, K; int A[MAXN], B[MAXN]; int near[MAXN*2], sp[MAXN*2]; lld S[MAXN*2]; int last[MAXN*4]; lld D[MAXN*2]; struct Z{ int x; bool t; } C[MAXN*2]; lld min_total_length(vector<int> r, vector<int> b) { N = sz(r); M = sz(b); K = N+M; for (int i=1;i<=N;i++) A[i] = r[i-1]; for (int i=1;i<=M;i++) B[i] = b[i-1]; /* Merge */ for (int i=1,j=1,k=1;k<=K;k++){ if (j > M || i <= N && A[i] < B[j]) C[k] = {A[i++], 0}; else C[k] = {B[j++], 1}; } /* Get nearest point */ for (int i=1;i<=K;i++) near[i] = 2e9; { int rec[2] = {0,}; for (int i=1;i<=K;i++){ if (rec[!C[i].t]) near[i] = min(near[i], C[i].x-C[rec[!C[i].t]].x); rec[C[i].t] = i; } } { int rec[2] = {0,}; for (int i=K;i>0;i--){ if (rec[!C[i].t]) near[i] = min(near[i], C[rec[!C[i].t]].x-C[i].x); rec[C[i].t] = i; } } for (int i=1;i<=K;i++) sp[i] = -1; for (int i=0;i<=K+K;i++) last[i] = -1; last[K] = 0; int now = 0; for (int i=1;i<=K;i++){ if (C[i].t) now++, S[i] = C[i].x; else now--, S[i] = -C[i].x; S[i] += S[i-1]; if (last[now+K] >= 0) sp[i] = last[now+K]; last[now+K] = i; } for (int i=1;i<=K;i++){ D[i] = D[i-1] + near[i]; if (sp[i] >= 0){ int j = sp[i]; D[i] = min(D[i], D[j] + abs(S[i]-S[j])); } } return D[K]; }

Compilation message (stderr)

wiring.cpp: In function 'lld min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:31:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (j > M || i <= N && A[i] < B[j])
                             ^
#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...