oj.uz

답안 #785962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
785962 2023-07-17T20:33:16 Z tosivanmak 수열 (APIO14_sequence) C++17
0 / 100
 20 ms 2588 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
struct LINE{
  ld m,c,ocpt;
  bool operator !=(const LINE &l)const{
      return m!=l.m||c!=l.c||ocpt!=l.ocpt;
  }
};
deque<LINE>q[2];
 
pair<ld,ld> int_pt(LINE a, LINE b){
    // a.mx+a.c=b.mx+b.c
    ld x=(b.c-a.c)/(a.m-b.m);
    ld y=(a.m*x+a.c);
    return {x,y};
}
void insert(ll id, LINE a){
    while(q[id].size()>1){
        // cout<<"bruh\n";
        if(a.m==q[id].front().m){
            if(a.c<q[id].front().c){
               break;
            }
            else{
                q[id].pop_front();
            }
        }
        else{
        if(int_pt(a,q[id].front()).first>=q[id].front().ocpt){
           q[id].pop_front();
        }
        else{
            break;
        }
        }
    }
    if(q[id].size()==0){
      a.ocpt=1e18;
      q[id].push_back(a);
    }
    else{
        if(a.m!=q[id].front().m){
    a.ocpt=int_pt(a,q[id].front()).first;
    q[id].push_front(a);
        }
        else if(a.c>q[id].front().c){
            q[id].pop_front();
            if(q[id].size()==0){
                a.ocpt=1e18;
                q[id].push_front(a);
            }
            else{
                a.ocpt=int_pt(a,q[id].front()).first;
                q[id].push_front(a);
            }
        }
    }
}
LINE qry(ll id, ld val){
    ll rid=1-id;
    LINE carry={-1e18,-1e18,-1e18};
    LINE init={-1e18,-1e18,-1e18};
   while(q[rid].size()>=1&&q[rid].back().ocpt>=val){
       carry=q[rid].back();
       q[rid].pop_back();
   }
   if(carry!=init){
       q[rid].push_back(carry);
   }
   return q[rid].back();
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  ll n,k;
  cin>>n>>k;
  ll arr[n+5];
  for(int i=1;i<=n;i++){
      cin>>arr[i];
  }
  ll psum[n+5];
  psum[0]=0;
  for(int i=1;i<=n;i++){
      psum[i]=psum[i-1]+arr[i];
  }
  ll dp[n+5][2];
  for(int i=1;i<=n;i++){
      dp[i][0]=0;
  }
  q[0].push_back({0,0,1e18});
  for(int j=1;j<=k;j++){
      ll id=j%2;
      
      for(int i=1;i<=n-1;i++){
          if(i>=j){
          ll dpcut=(psum[n]-psum[i])*psum[i];
        //   cout<<i<<": "<<j<<": "<<dpcut<<"\n";
          LINE store=qry(id,psum[n]-psum[i]);
          dp[i][id]=dpcut+store.c+store.m*(psum[n]-psum[i]);
         
          } 
          if(i>=j-1&&j!=1){
          LINE put={(ld)-psum[i],(ld)dp[i][(1-id)],0};
          insert((1-id),put);
        //   for(auto u: q[(1-id)]){
        //       cout<<u.m<<" "<<u.c<<" "<<u.ocpt<<"\n";
        //   }
        //   cout<<"\n";
          }
      }
      q[(1-id)].clear();
    //   cout<<j<<": ";
    //   for(int i=1;i<=n-1;i++){
    //        cout<<dp[i][id]<<" ";
    //     //    dp[i][(1-id)]=0;
    //   }
    //   cout<<"\n";
  }
  ll ck=k%2;
  ll ans=0;
  for(int i=1;i<=n-1;i++){
     ans=max(ans,dp[i][ck]);
    //  cout<<dp[i][ck]<<" ";
  }
  cout<<ans<<"\n";
}
// sum max =10^9
// dp transformation= assume nothing dp cut val + dp[op][k-1] - op[psum] * (psum[n] - cut pt)
// in cart plane, coordinate of x moves to the left
// search ocpt left
// slope= -op[psum]
// x= psum[n]-psum[i]

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 596 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 2588 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -