Submission #673638

#	Time	Username	Problem	Language	Result	Execution time	Memory
673638		Quan2003	Split the sequence (APIO14_sequence)	C++17	60 / 100	58 ms	131072 KiB

sequence

#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 sf[sz];
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 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][1] = opt.first + pf[i]*sf[i + 1];
                 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;
           }     
      }
      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);
      |                                   ~~~~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29