#include <bits/extc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) do{auto y = x; cout << #x << " = " << y << endl;}while(0)
// #define endl "\n"
#define unordered_map __gnu_pbds::gp_hash_table
using pii = pair<int, int>;
const int inf = 1ll << 60;
const int MOD = 1e9 + 7;
int fastlog2(int x) {
return 63 - __builtin_clzll(x);
}
struct sparsetable {
vector<vector<int>> t;
sparsetable() {}
sparsetable(vector<int>& a) {
int n = a.size();
t.resize(fastlog2(n) + 1, vector<int>(n));
t[0] = a;
for(int i = 1; i <= fastlog2(n); i++) {
for(int j = 0; j + (1 << i) <= n; j++) {
t[i][j] = max(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
}
}
}
int query(int ql, int qr) {
int lg = fastlog2(qr - ql);
return max(t[lg][ql], t[lg][qr - (1 << lg)]);
}
};
int n;
sparsetable st;
int eval(pii f, int x) {
if(x >= f.f) return inf;
return (n - x) * st.query(x, f.f) + f.s;
}
struct lichao {
int tl, tr;
pii f;
lichao *lc, *rc;
void insert(pii f2) {
int tm = (tl + tr) / 2;
if(eval(f2, tm) < eval(f, tm)) swap(f, f2);
if(tl + 1 == tr) return;
// if(eval(f2, tl) <= eval(f, tl)) {
if(!lc) {
lc = new lichao{tl, tm, f2};
} else {
lc->insert(f2);
}
// }
// if(eval(f2, tr - 1) <= eval(f, tr - 1)) {
if(!rc) {
rc = new lichao{tm, tr, f2};
} else {
rc->insert(f2);
}
// }
}
int query(int x) {
int tm = (tl + tr) / 2;
int res = eval(f, x);
if(x < tm && lc) return min(res, lc->query(x));
if(x >= tm && rc) return min(res, rc->query(x));
return res;
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
vector<int> t(n);
for(int i = 0; i < n; i++) {
cin >> t[i];
}
st = sparsetable(t);
vector<int> dp(n);
lichao lct{0, n, {n, 0}};
for(int i = n - 1; i >= 0; i--) {
dp[i] = lct.query(i);
lct.insert({i, dp[i]});
}
cout << dp[0] << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
596 KB |
Output is correct |
2 |
Correct |
39 ms |
596 KB |
Output is correct |
3 |
Correct |
36 ms |
636 KB |
Output is correct |
4 |
Correct |
34 ms |
596 KB |
Output is correct |
5 |
Correct |
38 ms |
596 KB |
Output is correct |
6 |
Correct |
36 ms |
644 KB |
Output is correct |
7 |
Correct |
37 ms |
628 KB |
Output is correct |
8 |
Correct |
46 ms |
596 KB |
Output is correct |
9 |
Correct |
35 ms |
536 KB |
Output is correct |
10 |
Correct |
37 ms |
596 KB |
Output is correct |
11 |
Correct |
37 ms |
716 KB |
Output is correct |
12 |
Correct |
35 ms |
596 KB |
Output is correct |
13 |
Correct |
34 ms |
624 KB |
Output is correct |
14 |
Correct |
39 ms |
636 KB |
Output is correct |
15 |
Correct |
40 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
596 KB |
Output is correct |
2 |
Correct |
39 ms |
596 KB |
Output is correct |
3 |
Correct |
36 ms |
636 KB |
Output is correct |
4 |
Correct |
34 ms |
596 KB |
Output is correct |
5 |
Correct |
38 ms |
596 KB |
Output is correct |
6 |
Correct |
36 ms |
644 KB |
Output is correct |
7 |
Correct |
37 ms |
628 KB |
Output is correct |
8 |
Correct |
46 ms |
596 KB |
Output is correct |
9 |
Correct |
35 ms |
536 KB |
Output is correct |
10 |
Correct |
37 ms |
596 KB |
Output is correct |
11 |
Correct |
37 ms |
716 KB |
Output is correct |
12 |
Correct |
35 ms |
596 KB |
Output is correct |
13 |
Correct |
34 ms |
624 KB |
Output is correct |
14 |
Correct |
39 ms |
636 KB |
Output is correct |
15 |
Correct |
40 ms |
596 KB |
Output is correct |
16 |
Execution timed out |
1098 ms |
297724 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
297900 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
49 ms |
596 KB |
Output is correct |
16 |
Correct |
39 ms |
596 KB |
Output is correct |
17 |
Correct |
36 ms |
636 KB |
Output is correct |
18 |
Correct |
34 ms |
596 KB |
Output is correct |
19 |
Correct |
38 ms |
596 KB |
Output is correct |
20 |
Correct |
36 ms |
644 KB |
Output is correct |
21 |
Correct |
37 ms |
628 KB |
Output is correct |
22 |
Correct |
46 ms |
596 KB |
Output is correct |
23 |
Correct |
35 ms |
536 KB |
Output is correct |
24 |
Correct |
37 ms |
596 KB |
Output is correct |
25 |
Correct |
37 ms |
716 KB |
Output is correct |
26 |
Correct |
35 ms |
596 KB |
Output is correct |
27 |
Correct |
34 ms |
624 KB |
Output is correct |
28 |
Correct |
39 ms |
636 KB |
Output is correct |
29 |
Correct |
40 ms |
596 KB |
Output is correct |
30 |
Correct |
36 ms |
652 KB |
Output is correct |
31 |
Correct |
37 ms |
640 KB |
Output is correct |
32 |
Correct |
34 ms |
596 KB |
Output is correct |
33 |
Correct |
36 ms |
660 KB |
Output is correct |
34 |
Correct |
34 ms |
596 KB |
Output is correct |
35 |
Correct |
40 ms |
596 KB |
Output is correct |
36 |
Correct |
35 ms |
596 KB |
Output is correct |
37 |
Correct |
34 ms |
596 KB |
Output is correct |
38 |
Correct |
38 ms |
644 KB |
Output is correct |
39 |
Correct |
42 ms |
648 KB |
Output is correct |
40 |
Correct |
32 ms |
596 KB |
Output is correct |
41 |
Correct |
36 ms |
596 KB |
Output is correct |
42 |
Correct |
37 ms |
584 KB |
Output is correct |
43 |
Correct |
41 ms |
596 KB |
Output is correct |
44 |
Correct |
34 ms |
596 KB |
Output is correct |
45 |
Correct |
37 ms |
596 KB |
Output is correct |
46 |
Correct |
37 ms |
596 KB |
Output is correct |
47 |
Correct |
38 ms |
596 KB |
Output is correct |
48 |
Correct |
34 ms |
596 KB |
Output is correct |
49 |
Correct |
34 ms |
596 KB |
Output is correct |
50 |
Correct |
35 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
49 ms |
596 KB |
Output is correct |
16 |
Correct |
39 ms |
596 KB |
Output is correct |
17 |
Correct |
36 ms |
636 KB |
Output is correct |
18 |
Correct |
34 ms |
596 KB |
Output is correct |
19 |
Correct |
38 ms |
596 KB |
Output is correct |
20 |
Correct |
36 ms |
644 KB |
Output is correct |
21 |
Correct |
37 ms |
628 KB |
Output is correct |
22 |
Correct |
46 ms |
596 KB |
Output is correct |
23 |
Correct |
35 ms |
536 KB |
Output is correct |
24 |
Correct |
37 ms |
596 KB |
Output is correct |
25 |
Correct |
37 ms |
716 KB |
Output is correct |
26 |
Correct |
35 ms |
596 KB |
Output is correct |
27 |
Correct |
34 ms |
624 KB |
Output is correct |
28 |
Correct |
39 ms |
636 KB |
Output is correct |
29 |
Correct |
40 ms |
596 KB |
Output is correct |
30 |
Execution timed out |
1098 ms |
297724 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |