#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <tuple>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <functional>
#include <numeric>
#include <iomanip>
#include <stdio.h>
#include <assert.h>
#include <cstring>
#define f first
#define s second
#define f first
#define s second
#define int long long
#define pii pair<int,int>
#define MAXV 200007
#define MAXE 100007
#define f first
#define s second
#define pii pair<int,int>
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define drep(i,n) for(int i = n-1 ; i >= 0 ; i--)
#define crep(i,x,n) for(int i = x ; i < n ; i++)
#define lnf 3999999999999999999
#define inf 999999999
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())
using namespace std;
const int N = 1e5 + 5,K = 200;
int t,n,k,a[N],s[N],ans,bef[N][K + 5],last;
vector<pair<pii,int> > st[K + 5];
int f(int x,pii y) {
return y.f * x + y.s;
}
long double x_(pii x1,pii x2) {
return (long double) (x2.s - x1.s) / (x1.f - x2.f);
}
void add(int j,pii x,int i) {
while(st[j].size() > 1) {
pii cur = st[j].back().f;
pii prev = st[j][(int)st[j].size() - 2].f;
if(cur.f == x.f) {
st[j].pop_back();
continue;
}
if(x_(cur,x) <= x_(cur,prev)) st[j].pop_back();
else break;
}
st[j].push_back({x,i});
}
void query(int j,int c,int i) {
while(st[j].size() >= 2) {
pii cur = st[j].back().f;
pii prev = st[j][(int)st[j].size() - 2].f;
if(f(c,cur) > f(c,prev)) break;
st[j].pop_back();
}
if(!st[j].size()) return;
pii cur_ans;
cur_ans.s = f(c,st[j].back().f) - c * c;
cur_ans.f = c;
bef[i][j] = st[j].back().s;
add(j + 1,cur_ans,i);
if(j == k - 1) {
if(cur_ans.s > ans) {
ans = cur_ans.s;
last = i;
}
}
}
main(){
cin>>n>>k;
for(int i=1;i<=n;i++) {
cin >> a[i];
}
for(int i=n;i>=1;i--) {
s[i] = s[i+1] + a[i];
}
st[0].push_back({{s[1],0},1});
for(int i=2;i<=n;i++){
for(int j=k-1;j>=0;j--) {
query(j,s[i],i);
}
}
cout<<ans<<"\n";
int cur = k-1;
vector<int> ans;
while(cur >= 0) {
ans.push_back(last-1);
last = bef[last][cur];
cur--;
}
while(ans.size()) {
cout<<ans.back()<<" ",ans.pop_back();
}}
Compilation message
sequence.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
93 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Incorrect |
1 ms |
204 KB |
contestant didn't find the optimal answer: 908 < 999 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
contestant didn't find the optimal answer: 1090726 < 1093956 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
588 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
1 ms |
560 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Incorrect |
1 ms |
588 KB |
contestant didn't find the optimal answer: 1019415406153 < 1499437552673 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1868 KB |
contestant didn't find the optimal answer: 20166072 < 21503404 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
16460 KB |
contestant didn't find the optimal answer: 1695400000 < 1818678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
78 ms |
131076 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |