Submission #673653

#	Time	Username	Problem	Language	Result	Execution time	Memory
673653		Quan2003	Split the sequence (APIO14_sequence)	C++17	60 / 100	64 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 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,-INT_MAX};
        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(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)

sequence.cpp: In function 'std::pair<long long int, int> query(long long int)':
sequence.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (pointer >=M.size())
      |             ~~~~~~~~^~~~~~~~~~
sequence.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (pointer<M.size()-1&&
      |                ~~~~~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:44:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   44 |       for(int i = 1; i <= n; i++) scanf("%d",a + i);
      |                                          ~^  ~~~~~
      |                                           |    |
      |                                           int* long long int*
      |                                          %lld
sequence.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |      for(int i = 0; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~
sequence.cpp:43:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |       scanf("%d%d",&n,&k);
      |       ~~~~~^~~~~~~~~~~~~~
sequence.cpp:44:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |       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