#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e15;
const int N = 1502;
template<typename T>
struct li_chao_min {
static const T identity = numeric_limits<T>::max();
struct Line {
T m, c;
Line() {
m = 0;
c = identity;
}
Line(T m, T c) : m(m), c(c) {}
T val(T x) { return m * x + c; }
};
struct Node {
Line line;
Node *lc, *rc;
Node() : lc(0), rc(0) {}
};
T L, R, eps;
deque<Node> buffer;
Node* root;
Node* new_node() {
buffer.emplace_back();
return &buffer.back();
}
li_chao_min() {}
li_chao_min(T _L, T _R, T _eps) {
init(_L, _R, _eps);
}
void init(T _L, T _R, T _eps) {
L = _L;
R = _R;
eps = _eps;
root = new_node();
}
void insert(Node* &cur, T l, T r, Line line) {
if (!cur) {
cur = new_node();
cur->line = line;
return;
}
T mid = l + (r - l) / 2;
if (r - l <= eps) return;
if (line.val(mid) < cur->line.val(mid))
swap(line, cur->line);
if (line.val(l) < cur->line.val(l)) insert(cur->lc, l, mid, line);
else insert(cur->rc, mid + 1, r, line);
}
T query(Node* &cur, T l, T r, T x) {
if (!cur) return identity;
T mid = l + (r - l) / 2;
T res = cur->line.val(x);
if (r - l <= eps) return res;
if (x <= mid) return min(res, query(cur->lc, l, mid, x));
else return min(res, query(cur->rc, mid + 1, r, x));
}
void insert(T m, T c) { insert(root, L, R, Line(m, c)); }
T query(T x) { return query(root, L, R, x); }
};
signed main() {
std::ios::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
int n; cin >> n;
vector<int> a(n + 1), dp(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
li_chao_min<int> lct(0, 1000000, 0);
dp[1] = a[1] * n;
lct.insert(n, 0); //querying all n at one time
int mx = a[1];
for(int i = 2; i <= n; i++) {
mx = max(mx, a[i]);
lct.insert(n - i + 1, dp[i - 1]);
dp[i] = lct.query(mx);
//we can qry for mx cuz the x coordinate has to be atleast mx (all under same time mx)
}
cout << dp[n] << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
273 ms |
15960 KB |
Output is correct |
2 |
Correct |
271 ms |
15964 KB |
Output is correct |
3 |
Correct |
271 ms |
15964 KB |
Output is correct |
4 |
Correct |
271 ms |
15972 KB |
Output is correct |
5 |
Correct |
268 ms |
15960 KB |
Output is correct |
6 |
Correct |
273 ms |
15948 KB |
Output is correct |
7 |
Correct |
268 ms |
15960 KB |
Output is correct |
8 |
Correct |
268 ms |
16068 KB |
Output is correct |
9 |
Correct |
290 ms |
15956 KB |
Output is correct |
10 |
Correct |
272 ms |
15948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |