- [ABC263D] Left Right Operation
C++
- 2024-10-6 10:24:08 @
#include <bits/stdc++.h>
using namespace std;
long long a[200005];
long long sum[200005];
//f(x,y) = L*x +R*y + (sum[n-y] - sum[x])
// f(x,y) = (L*x - sum[x]) + ( R*y + sum[n-y] );//归类x,y
//枚举x,y时间超限, 归类后预处理 R*y + sum[n-y] 后缀最小值;
// x+y <= n // 不能重叠 1----x-----y-----n
long long mina[200005];
int main() {
long long n,L,R;
cin >> n >> L >> R;
for(int i=1;i<=n;i++){
cin >> a[i];
sum[i] = sum[i-1]+a[i];
}
mina[0] = R*0 + sum[n-0];
for(int y=1;y<=n;y++){
mina[y] = min(mina[y-1], R*y + sum[n-y]);
}
long long ans = 1e19;
for(int x=0;x<=n;x++){
ans = min(ans,L*x-sum[x] + mina[n-x]);
}
cout << ans ;
return 0;
}
0 comments
No comments so far...
Information
- ID
- 2450
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 21
- Accepted
- 3
- Uploaded By