oj.uz

Submission #172791

# Submission time Handle Problem Language Result Execution time Memory
172791 2020-01-02T16:07:26 Z RafaelSus Split the sequence (APIO14_sequence) C++14
0 / 100
 147 ms 125256 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

vector<ll>m,b,idx;
int ptr;

void add(ll _m,ll _b,ll _idx){
  while(m.size()>=2){
    if((b.back()-_b)*(_m-m[m.size()-2])>=(b[b.size()-2]-_b)*(_m-m.back())){
      m.pop_back();
      b.pop_back();
      idx.pop_back();
    }
    else break;
  }
  m.pb(_m);
  b.pb(_b);
  idx.pb(_idx);
}

ll func(int pos,ll x){
  return m[pos]*x+b[pos];
}

pair<ll,ll>get(ll x){
  if(ptr>=m.size())ptr=m.size()-1;
  while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
  return {func(ptr,x),ptr};
}
int path[N][305];

void print(int st,int k){
  if(path[st][k]==0){
    cout<<st<<' ';
    return;
  }
  print(path[st][k],k-1);
  cout<<st<<' ';
}
ll dp[2][N];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  
  int n,k;
  cin>>n>>k;
  ll a[n+1],pref[n+1]={};
  for(int i=1;i<=n;i++){
    cin>>a[i];
    pref[i]=pref[i-1]+a[i];
    path[i][1]=0;
  }
  
  for(int i=1;i<n;i++){
    dp[1][i]=pref[i]*(pref[n]-pref[i]);
    path[i][1]=0;
  }
  for(int i=2;i<=k;i++){
    int v=(i-1)%2;
    m.clear();
    b.clear();
    idx.clear();
    ptr=0;
    add(0,0,0);
    for(int j=1;j<n;j++){
      if(j<i){
        if(j==i-1){
          add(-pref[j],dp[v][j],j);
        }
        continue;
      }
      pair<ll,ll>tmp=get(pref[n]-pref[j]);
      dp[v^1][j]=tmp.first+(pref[n]-pref[j])*pref[j];
      path[j][i]=tmp.second;
      add(-pref[j],dp[v][j],j);
    }
  }
  ll mx=0,st=1;
  for(int i=1;i<=n;i++){
    if(dp[k%2][i]>mx){
      mx=dp[k%2][i];
      st=i;
    }
  }
  cout<<mx<<'\n';
  print(st,k);
}

Compilation message

sequence.cpp: In function 'std::pair<long long int, long long int> get(ll)':
sequence.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr>=m.size())ptr=m.size()-1;
      ~~~^~~~~~~~~~
sequence.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x))ptr++;
         ~~~~~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB declared answer doesn't correspond to the split scheme: declared = 108, real = 99
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB declared answer doesn't correspond to the split scheme: declared = 1093956, real = 1093871
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB declared answer doesn't correspond to the split scheme: declared = 610590000, real = 311130844
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1656 KB declared answer doesn't correspond to the split scheme: declared = 21503404, real = 21421146
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12920 KB declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1587103400
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 125256 KB declared answer doesn't correspond to the split scheme: declared = 19795776960, real = 19210632245
2 Halted 0 ms 0 KB -