이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7, inf = mod; //!
int t, bef[N], pos[N], a[N], ID[N];
map<int,int> id;
int f(int k,int x,int l) {
return k * x + l;
}
pii tree[4 * N];
void insert(int u,int l,int r, int k,int b) {
if(l == r) {
if(f(k, pos[l], b) < f(tree[u].f, pos[l], b)) tree[u] = {k, b};
return;
}
int mid = (l + r) / 2;
if(k < tree[u].f) {
swap(k, tree[u].f);
swap(b, tree[u].s);
}
if(f(k, pos[mid], b) <= f(tree[u].f, pos[mid], tree[u].s)) {
insert(2 * u + 1, mid + 1, r, tree[u].f, tree[u].s);
tree[u].f = k; tree[u].s = b;
return;
}
insert(2 * u, l, mid, k, b);
}
int get(int u,int l,int r,int id) {
if(l > id || r < id) return inf;
if(l == r) {
return f(tree[u].f, pos[l], tree[u].s);
}
int mid = (l + r) / 2;
return min(f(tree[u].f, pos[id], tree[u].s), min(get(2 * u, l, mid, id), get(2 * u + 1, mid + 1,r, id)));
}
main() {
// ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin >> n;
vector<int> x;
int mx = 0;
x.push_back(0);
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] > mx) {
bef[x.size()] = i - 1;
ID[x.size()] = i;
x.push_back(i);
mx = i;
}
}
bef[x.size()] = n;
for(int i = 0; i < x.size(); i++) {
id[x[i]] = i;
pos[i] = a[x[i]];
}
int ANS = 0;
for(int i = 1; i < x.size(); i++) {
int ans = get(1, 1, x.size() - 1, i) + n * a[x[i]];
//cout << i << " __ " << get(1, 1, x.size() - 1, i) << " " << (n - bef[i]) * a[x[i]] << " " << ans << endl;
insert(1, 1, x.size() - 1, -bef[i + 1], ans);
if(i + 1 == x.size()) ANS = ans;
}
cout << ANS;
}
컴파일 시 표준 에러 (stderr) 메시지
Discharging.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
40 | main() {
| ^~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
Discharging.cpp:64:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 1; i < x.size(); i++) {
| ~~^~~~~~~~~~
Discharging.cpp:70:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(i + 1 == x.size()) ANS = ans;
| ~~~~~~^~~~~~~~~~~
# | 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... |