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>
using namespace std;
#define N 300005
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second
ll T, n, k, a[N], p[N];
set <pair<int,int>> s;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
p[i] = p[i-1] + a[i];
}
s.insert({1,n});
ll ans = 0;
while(k--){
ll mx = 0, l1 = 0, r1 = 0, ind = 0;
for(auto i : s){
int l = i.ff, r = i.ss;
ll x = 0;
for(int i = l; i < r; i++){
x = (p[i]-p[l-1]);
x *= (p[r]-p[i]);
if(x > mx){
mx = x;
ind = i;
l1 = l;
r1 = r;
}
}
}
s.erase({l1,r1});
s.insert({l1,ind});
s.insert({ind+1,r1});
ans += mx;
}
cout << ans;
return 0;
}
# | 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... |