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=3e5+10;
const int mod = 1e9 + 7;
int n,k,m,q,dis,lim;
ll timer=1;
long long sf[sz];
long long pf[sz];
long long dp[sz][201];
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 i = n; i > 0 ; i--) sf[i] = sf[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(sf[i + 1]);
dp[i][j] = opt.first + pf[i]*sf[i + 1];
add(-pf[i], dp[i][j - 1], i);
par[i][j] = {opt.second,j - 1};
}
//for(int i = 1; i <= n; i++) add(-pf[i],dp[i][j]);
}
long long ans = - LLONG_MAX;
int pos = 0;
for(int i = 1; i <= n; i++){
if(ans < dp[i][k]){
ans = dp[i][k];
pos = i;
}
}
cout<<ans<<endl;
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());
for(int i = 0; i < res.size(); i++) cout<<res[i]<<' ';
}
Compilation message (stderr)
sequence.cpp: In function 'std::pair<long long int, int> query(long long int)':
sequence.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (pointer >=M.size())
| ~~~~~~~~^~~~~~~~~~
sequence.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while (pointer<M.size()-1&&
| ~~~~~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:45:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
45 | for(int i = 1; i <= n; i++) scanf("%d",a + i);
| ~^ ~~~~~
| | |
| int* long long int*
| %lld
sequence.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < res.size(); i++) cout<<res[i]<<' ';
| ~~^~~~~~~~~~~~
sequence.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
sequence.cpp:45:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | for(int i = 1; i <= n; i++) 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... |