# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
671107 | vuavisao | Discharging (NOI20_discharging) | C++14 | 100 ms | 19484 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ld long double
using namespace std;
const ll N = 1e6 + 10;
const ll INF = 1e18;
struct line {
ll a = 0, b = 0;
line() {};
line(ll _a, ll _b) { a = _a; b = _b; }
ll Fn(const ll& x) { return this -> a * x + this -> b; }
};
bool bad(line A, line B, line C) {
return (ld) (C.b - A.b) / (A.a - C.a) < (ld) (B.b - A.b) / (A.a - B.a);
}
struct CHT {
vector<line> memo = {};
ll ptr = 0; /// for a query where x has been sorted
void add_line(const line& cur) {
ll k = memo.size();
while(k >= 2 && bad(memo[k - 2], memo[k - 1], cur)) {
memo.pop_back();
-- k;
}
memo.push_back(cur); ++ k;
if(ptr >= k) ptr = k - 1;
}
ll Query_bs(const ll& x) {
if(memo.empty()) return INF;
ll l = 0, r = memo.size() - 1;
while(l < r) {
ll mid = (l + r) >> 1;
if(memo[mid].Fn(x) < memo[mid + 1].Fn(x)) r = mid;
else l = mid + 1;
}
return memo[l].Fn(x);
}
ll Query_ptr(const ll& x) {
if(memo.empty()) return INF;
while(ptr < memo.size() - 1 && memo[ptr].Fn(x) > memo[ptr + 1].Fn(x)) ++ ptr;
return memo[ptr].Fn(x);
}
void clear() {
this -> memo.clear();
this -> ptr = 0;
}
};
ll n, a[N];
ll dp[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("Discharging.inp", "r")) {
freopen("Discharging.inp", "r", stdin);
freopen("Discharging.out", "w", stdout);
}
cin >> n;
for(ll i = 1; i <= n; ++ i) cin >> a[i];
reverse(a + 1, a + 1 + n);
deque<ll> dq = {};
for(ll i = 1; i <= n; ++ i) {
while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
}
CHT cht = {};
cht.add_line(line(a[dq[0]], 0));
for(ll i = 1; i <= (ll) dq.size(); ++ i) {
dp[i] = cht.Query_ptr(dq[i - 1]);
if(i < (ll) dq.size()) cht.add_line(line(a[dq[i]], dp[i]));
}
cout << dp[dq.size()];
return 0;
}
/// Code by vuavisao
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |