# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
673644 | Quan2003 | Split the sequence (APIO14_sequence) | C++17 | 57 ms | 131072 KiB |
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;
typedef long long ll;
const int sz=1e5+10;
const int mod = 1e9 + 7;
int n,k,m,q,dis,lim;
ll timer=1;
long long pf[sz];
long long dp[sz][2];
long long a[sz];
vector <long long>M;
vector <long long>B;
vector <long long>C;
pair<int,int>par[sz][201];
bool bad(int l1,int l2,int l3)
{
return (B[l3]-B[l1])*(M[l1]-M[l2]) >= (B[l2]-B[l1])*(M[l1]-M[l3]);
}
void add(long long m,long long b, long long t)
{
C.push_back(t);
M.push_back(m);
B.push_back(b);
while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
{
M.erase(M.end()-2);
B.erase(B.end()-2);
C.erase(C.end()-2);
}
}
int pointer;
pair<long long,int>query(long long x)
{
if(M.size() == 0) return {0,0};
if (pointer >=M.size())
pointer=M.size()-1;
while (pointer<M.size()-1&&
M[pointer+1]*x+B[pointer+1]>M[pointer]*x+B[pointer])
pointer++;
return {M[pointer]*x+B[pointer],C[pointer]};
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1; i <= n; i++) scanf("%d",a + i);
for(int i = 1; i <= n; i++) pf[i] = pf[i - 1] + a[i];
for(int j = 1; j <= k; j++){
M.clear(); B.clear(); C.clear();
for(int i = 0; i <= n; i++){
pair<long long,int>opt = query(pf[n] - pf[i]);
dp[i][1] = opt.first + pf[i]*(pf[n] - pf[i]);
add(-pf[i], dp[i][0], i);
par[i][j] = {opt.second,j - 1};
}
for(int i = 1; i <= n; i++) dp[i][0] = dp[i][1];
}
long long ans = - LLONG_MAX;
int pos = 0;
for(int i = 1; i <= n; i++){
if(ans < dp[i][1]){
ans = dp[i][1];
pos = i;
}
}
int move = k;
vector<int>res;
while(move > 0 and pos > 0){
res.push_back(pos);
pair<int,int>opt = par[pos][move];
pos = opt.first;
move = opt.second;
}
reverse(res.begin(),res.end());
cout << ans << '\n';
for(int i = 0; i < res.size(); i++) {
cout << res[i] << ' ';
}
cout << '\n';
}
Compilation message (stderr)
# | 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... |