This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,a[1000002];
ll dp[1000002],rm[1000002][21],po[2000002],pw[200],raod,mn;
ll lef[1000002],rig[1000002];
vector<ll>del[1000002];
ll get(ll x,ll y){
return a[y];
ll lo = po[y - x + 1];
if(rm[y][lo] > rm[x + pw[lo] - 1][lo])return rm[y][lo];
return rm[x + pw[lo] - 1][lo];
}
ll ind(ll x,ll y){
if(y == n)return -1;
ll l = y + 1,r = n,mid,ind = -1;
while(r >= l){
mid = (l + r) / 2;
if(dp[x] + get(x + 1 , mid) * (n - x) > dp[y] + get(y + 1 , mid) * (n - y)){
r = mid - 1;
ind = mid;
}
else
l = mid + 1;
}
return ind;
}
void delet(ll x){
if(lef[x] == rig[x] && lef[x] == -1)return;
if(lef[x] == -1){
lef[rig[x]] = -1;
mn = rig[x];
rig[x] = -1;
return;
}
rig[lef[x]] = rig[x];
lef[rig[x]] = lef[x];
ll cur = ind(lef[x] , rig[x]);
if(cur == -1){
lef[x] = rig[x] = -1;
return;
}
del[cur].pb(lef[x]);
lef[x] = rig[x] = -1;
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
//int cl = clock();
//n = 1000000;
//for(int i=1; i<=n; i++)
// a[i] = n-i+1;
pw[0] = 1;
for(int i=1; i<=21; i++){
pw[i] = pw[i - 1] * 2;
for(int j=pw[i - 1]; j<pw[i]; j++){
if(j <= 1000000)
po[j] = i - 1;
}
}
for(int i=0; i<=n; i++)
lef[i] = rig[i] = -1;
for(int i=1; i<=n; i++){
rm[i][0] = a[i];
for(int j=1; j<=20; j++){
if(i - pw[j] + 1 >= 1)
rm[i][j] = max(rm[i][j - 1] , rm[i - pw[j - 1]][j - 1]);
}
}
//cout << clock() - cl << '\n';
for(int i=1; i<=n; i++){
for(int j=0; j<del[i].size(); j++){
delet(del[i][j]);
}
dp[i] = dp[mn] + get(mn + 1 , i) * (n - mn);
rig[i - 1] = i;
lef[i] = i - 1;
ll cur = ind(i - 1 , i);
if(cur != -1)
del[cur].pb(i - 1);
}
//cout << "time: " << clock() - cl << " " << raod << '\n';
cout << dp[n];
return 0;
}
Compilation message (stderr)
Discharging.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
Discharging.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
Discharging.cpp: In function 'int main()':
Discharging.cpp:55:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
55 | scanf("%d",&n);
| ~^ ~~
| | |
| | long long int*
| int*
| %lld
Discharging.cpp:57:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
57 | scanf("%d",&a[i]);
| ~^ ~~~~~
| | |
| | long long int*
| int*
| %lld
Discharging.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int j=0; j<del[i].size(); j++){
| ~^~~~~~~~~~~~~~
Discharging.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Discharging.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
57 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
# | 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... |