이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int H = 1e3, N = 1e5;
int solveTestCase() {
int n;
cin >> n;
int h[n], w[n];
for (int i = 0; i < n; i++) cin >> h[i];
for (int i = 0; i < n; i++) cin >> w[i];
int best[H + 1];
fill(best, best + H + 1, 1e18);
best[h[0]] = -w[0];
int pref = w[0];
map<int, int> m;
m[h[0]] = -w[0];
for (int i = 1; i < n; i++) {
int temp = (h[i] - h[0]) * (h[i] - h[0]) + pref - w[0];
for (int j = 0; j <= 1e3 && j + h[i] <= H; j++) {
if (best[h[i] + j] == 1e18)
continue;
temp = min(temp, j * j + pref + best[h[i] + j]);
}
for (int j = -1; abs(j) <= 1e3 && j + h[i] >= 0; j--) {
if (best[h[i] + j] == 1e18)
continue;
temp = min(temp, j * j + pref + best[h[i] + j]);
}
if (h[0] <= h[n - 1]) {
auto itr = m.lower_bound(h[i]);
if (itr != m.begin())
--itr, temp = min(temp, (h[i] - itr->first) * (h[i] - itr->first) + pref + itr->second);
} else {
auto itr = m.lower_bound(h[i]);
if (itr != m.end())
temp = min(temp, (h[i] - itr->first) * (h[i] - itr->first) + pref + itr->second);
}
pref += w[i];
if (m.count(h[i]))
m[h[i]] = min(m[h[i]], temp - pref);
else
m[h[i]] = temp - pref;
best[h[i]] = min(best[h[i]], temp - pref);
if (i == n - 1)
return cout << temp, 0;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int test = 1;
// cin >> test;
while (test--)
solveTestCase();
}
컴파일 시 표준 에러 (stderr) 메시지
building.cpp: In function 'long long int solveTestCase()':
building.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |