제출 #1086284

#제출 시각아이디문제언어결과실행 시간메모리
1086284RiverFlow선물상자 (IOI15_boxes)C++14
100 / 100
668 ms300364 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; const int N = (int)1e7 + 2; int n, k; long long l, pre[N], suf[N]; long long modk[N]; long long f(int x) { return l * ( (x / k) + (x % k != 0) ); } long long delivery(int N, int K, int L, int p[]) { n = N, k = K, l = L; long long ans = (long long)1e17; ans = min(ans, f(n) ); for(int i = 0; i < n; ++i) { long long c = 2LL * p[i]; if (i - k >= 0) { c += pre[i - k]; } pre[i] = c; } for(int i = n - 1; i >= 0; --i) { long long c = 2LL * (l - p[i]); if (i + k < n) { c += suf[i + k]; } suf[i] = c; } for(int i = 0; i < n; ++i) { ans = min(ans, pre[i] + f(n - i - 1)); ans = min(ans, suf[i] + f(i)); } int mi[2] = {(n - 1) % k, -1}; modk[ (n - 1) % k ] = f(n - 1) + suf[n - 1]; auto cmp = [&](int x, int y) { return modk[x] > modk[y] ? 1 : 0; }; for(int i = n - 2; i >= 0; --i) { int t = (i + 1) % k; ans = min(ans, pre[i] - f(i + 1) + modk[t]); for(int i = 0; i < 2; ++i) if (mi[i] != t and mi[i] != -1) { ans = min(ans, pre[i] - f(i + 1) + modk[mi[i]] + l); } int x = i % k; if (i + k < n) { modk[x] = min(modk[x], f(i) + suf[i]); } else { modk[x] = f(i) + suf[i]; } if (mi[0] == x) continue ; if (mi[1] == x) { if (cmp(mi[0], x)) mi[1] = x; } else { if (cmp(mi[0], x)) mi[1] = mi[0], mi[0] = x; else if (mi[1] == -1 or cmp(mi[1], x)) mi[1] = x; } } return ans; }

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

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:17:24: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   17 | long long delivery(int N, int K, int L, int p[]) {
      |                    ~~~~^
boxes.cpp:5:11: note: shadowed declaration is here
    5 | const int N = (int)1e7 + 2;
      |           ^
boxes.cpp:51:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   51 |         for(int i = 0; i < 2; ++i) if (mi[i] != t and mi[i] != -1) {
      |                 ^
boxes.cpp:48:13: note: shadowed declaration is here
   48 |     for(int i = n - 2; i >= 0; --i) {
      |             ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...