제출 #968532

#제출 시각아이디문제언어결과실행 시간메모리
968532nguyentunglam전선 연결 (IOI17_wiring)C++17
45 / 100
1093 ms14428 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N], b[N]; int c[N], d[N]; long long pref[N], _pref[N], suff[N], _suff[N], sum[N]; long long min_total_length(std::vector<int> R, std::vector<int> B) { int n = R.size(), m = B.size(); for(int i = 1; i <= n; i++) a[i] = R[i - 1]; for(int i = 1; i <= m; i++) b[i] = B[i - 1]; a[n + 1] = b[m + 1] = 1e9; for(int i = 1, j = 1, k = 0, sum = 0; i <= n || j <= m;) { if (a[i] < b[j]) { c[++k] = a[i++]; d[k] = 0; } else { c[++k] = b[j++]; d[k] = 1; } } for(int i = 1; i <= n + m; i++) sum[i] = sum[i - 1] + c[i]; for(int i = 0; i <= n + m; i++) pref[i] = suff[i] = 1e16; for(int i = 0; i <= n + m; i++) _pref[i] = _suff[i] = 1e16; pref[0] = 0; for(int i = 1, cnt = 0; i <= n + m; ) { int j = i; while (j <= n + m && d[j] == d[i]) j++; j--; for(int k = cnt + 1; k <= j - i + 1; k++) pref[k] = min(pref[k], pref[k - 1]); // cout << i << " " << j << "@" << endl; // cout << pref[2] << endl; for(int k = i - 1; k <= j; k++) { if (i == 1 && k > 0) break; long long f = sum[k] - sum[i - 1] + min(pref[k - i + 1] - 1LL * (k - i + 1) * c[i - 1], suff[k - i + 1] - 1LL * (k - i + 1) * c[i]); _pref[j - k] = f - (sum[j] - sum[k]) + 1LL * (j - k) * c[j]; _suff[j - k] = f - (sum[j] - sum[k]) + 1LL * (j - k) * c[j + 1]; if (k == i && k == j) { _pref[j - k + 1] = min(_pref[j - k + 1], f - (sum[j] - sum[k]) + c[j]); _suff[j - k + 1] = min(_suff[j - k + 1], f - (sum[j] - sum[k]) + c[j + 1]); } } for(int i = 0; i <= max(j - i + 1, cnt); i++) pref[i] = suff[i] = 1e18; cnt = j - i + 1; for(int i = 0; i <= cnt; i++) pref[i] = _pref[i], suff[i] = _suff[i]; for(int k = 2; k <= cnt; k++) pref[k] = min(pref[k - 1], pref[k]); for(int k = cnt - 1; k >= 0; k--) suff[k] = min(suff[k + 1], suff[k]); i = j + 1; } return pref[0]; } #ifdef ngu int main() { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); int n, m; assert(2 == scanf("%d %d", &n, &m)); vector<int> r(n), b(m); for(int i = 0; i < n; i++) assert(1 == scanf("%d", &r[i])); for(int i = 0; i < m; i++) assert(1 == scanf("%d", &b[i])); long long res = min_total_length(r, b); printf("%lld\n", res); return 0; } #endif // ngu

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:32: warning: unused variable 'sum' [-Wunused-variable]
   20 |   for(int i = 1, j = 1, k = 0, sum = 0; i <= n || j <= m;) {
      |                                ^~~
wiring.cpp:40:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   40 |     while (j <= n + m && d[j] == d[i]) j++; j--;
      |     ^~~~~
wiring.cpp:40:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   40 |     while (j <= n + m && d[j] == d[i]) j++; 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...