#1050730 (C++23) No.3050 Prefix Removal

• 問題: No.3050 Prefix Removal
• ユーザー: Andrew8128
• 提出日時: 2025-03-07 22:14:18
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 852 ms / 2,000 ms
• コード長: 14,421 bytes
• コンパイル時間: 3,024 ms
• コンパイル使用メモリ: 129,096 KB
• 実行使用メモリ: 54,124 KB
• 最終ジャッジ日時: 2025-03-07 22:14:48
• 合計ジャッジ時間: 28,771 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 55

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;
const long long linf = 4610000000000000000;

/*
  Don't Remove this Comment !!
  https://qiita.com/NokonoKotlin/items/c108a603622c03c4c67b
  Copyright (c) NokonoKotlin (okoteiyu) 2024.
  Released under the MIT license(https://opensource.org/licenses/mit-license.php)
*/

#include<iostream>
#include<cassert>

template<class type_key , class type_value>
class MyMultiSet{
  private:
  struct SplayNode{
    SplayNode *parent = nullptr;// parent node
    SplayNode *left = nullptr;// left child
    SplayNode *right = nullptr;// left child

    type_key Key;// sorted key
    type_value Value;// value (sorted if key is same)

    type_key Sum_key;// Sum of Key in Subtree
    type_value Min_val,Max_val,Sum_val;// Min,Max,Sum of Value in Subtree

    int SubTreeSize = 1;// Size of Subtree under this node

    private:
    bool copied_instance = false;
    public:
    SplayNode copy(){
      assert(copied_instance == false);
      SplayNode res = *this;
      res.left = nullptr;
      res.right = nullptr;
      res.parent = nullptr;
      res.copied_instance = true;
      return res;
    }

    SplayNode(){}
    SplayNode(type_key key_ , type_value val_){
      Key = key_;
      Value = val_;
      update();
    }


    // rotate ( this node - parent )
    void rotate(){
      if(this->parent->parent){
        if(this->parent == this->parent->parent->left)this->parent->parent->left = this;
        else this->parent->parent->right = this;
      }

      this->parent->eval();
      this->eval();

      if(this->parent->left == this){
        this->parent->left = this->right;
        if(this->right)this->right->parent = this->parent;
        this->right = this->parent;
        this->parent = this->right->parent;
        this->right->parent = this;
        this->right->update();
      }else{
        this->parent->right = this->left;
        if(this->left)this->left->parent = this->parent;
        this->left = this->parent;
        this->parent = this->left->parent;
        this->left->parent = this;
        this->left->update();
      }

      this->update();
      return;
    }

    // direction of this parent (left or right)
    int state(){
      if(this->parent == nullptr)return 0;
      this->eval();
      if(this->parent->left == this)return 1;
      else if(this->parent->right == this)return 2;
      return 0;
    }

    // bottom-up splay
    void splay(){
      while(bool(this->parent)){
        if(this->parent->state() == 0){
          this->rotate();
          break;
        }
        if( this->parent->state() == this->state() )this->parent->rotate();
        else this->rotate();
        this->rotate();
      }
      this->update();
      return;
    }

    // update data member
    void update(){
      assert(copied_instance == false);

      this->eval();
      this->SubTreeSize = 1;
      this->Sum_key = this->Key;
      this->Max_val = this->Sum_val = this->Min_val = this->Value;

      // add left child
      if(bool(this->left)){
        this->left->eval();
        this->SubTreeSize += this->left->SubTreeSize;
        if(this->left->Min_val < this->Min_val)this->Min_val = this->left->Min_val;
        if(this->left->Max_val > this->Max_val)this->Max_val = this->left->Max_val;
        this->Sum_key += this->left->Sum_key;
        this->Sum_val += this->left->Sum_val;
      }

      // add right child
      if(bool(this->right)){
        this->right->eval();
        this->SubTreeSize += this->right->SubTreeSize;
        if(this->right->Min_val < this->Min_val)this->Min_val = this->right->Min_val;
        if(this->right->Max_val > this->Max_val)this->Max_val = this->right->Max_val;
        this->Sum_key += this->right->Sum_key;
        this->Sum_val += this->right->Sum_val;
      }

      return;
    }

    // evaluate Lazy Evaluation
    void eval(){
      // if it's necessary , write here.
      assert(copied_instance == false);
    }
  };


  /*
    1. order of node's Key if [paired_compare] is false.
    2. lexicographical order of node's (Key ,Value) if [paired_compare] is true.
  */
  constexpr bool CompareNode(SplayNode *a , SplayNode *b , bool paired_compare = false){
    a->eval();
    b->eval();
    if(!paired_compare)return a->Key <= b->Key;
    else{
      if(a->Key < b->Key)return true;
      else if(a->Key == b->Key){
        if(a->Value <= b-> Value)return true;
        else return false;
      }else return false;
    }
  }

  // get [index]th node pointer
  SplayNode *get_sub(int index , SplayNode *root){
    if(root==nullptr)return root;
    SplayNode *now = root;
    while(true){
      now->eval();
      int left_size = 0;
      if(now->left != nullptr)left_size = now->left->SubTreeSize;
      if(index < left_size)now = now->left;
      else if(index > left_size){
        now = now->right;
        index -= left_size+1;
      }else break;
    }
    now->splay();
    return now;
  }

  // merge 2 SplayTrees
  SplayNode *merge(SplayNode *leftRoot , SplayNode *rightRoot){
    if(leftRoot!=nullptr)leftRoot->update();
    if(rightRoot!=nullptr)rightRoot->update();
    if(bool(leftRoot ) == false)return rightRoot;
    if(bool(rightRoot) == false )return leftRoot;
    rightRoot = get_sub(0,rightRoot);
    rightRoot->left = leftRoot;
    leftRoot->parent = rightRoot;
    rightRoot->update();
    return rightRoot;
  }


  // split SplayTree at [leftnum]
  std::pair<SplayNode*,SplayNode*> split(int leftnum, SplayNode *root){
    if(leftnum<=0)return std::make_pair(nullptr , root);
    if(leftnum >= root->SubTreeSize)return std::make_pair(root, nullptr);
    root = get_sub(leftnum , root);
    SplayNode *leftRoot = root->left;
    SplayNode *rightRoot = root;
    if(bool(rightRoot))rightRoot->left = nullptr;
    if(bool(leftRoot))leftRoot->parent = nullptr;
    leftRoot->update();
    rightRoot->update();
    return std::make_pair(leftRoot,rightRoot);
  }



  // remove [index]th node
  std::pair<SplayNode*,SplayNode*> Delete_sub(int index , SplayNode *root){
    if(bool(root) == false)return std::make_pair(root,root);
    root = get_sub(index,root);
    SplayNode *leftRoot = root->left;
    SplayNode *rightRoot = root->right;
    if(bool(leftRoot))leftRoot->parent = nullptr;
    if(bool(rightRoot))rightRoot->parent = nullptr;
    root->left = nullptr;
    root->right = nullptr;
    root->update();
    return std::make_pair(merge(leftRoot,rightRoot) , root );
  }


  /*
    between 2 SplayNodes [A] and [B] , we define following order.
    - if [paired_compare] is false,
      - [A] [<] [B] represent a order of these Keys.
      - [A] [==] [B] represent these Keys are same
    - if [paired_compare] is true,
      - [A] [<] [B] represent a lexicographical order of these (Key , Value).
      - [A] [==] [B] represent these (Key , Value) are same

    This function finds the border index [B] which satisfies following.
    1. if [lower] is true, for any [i] smaller than [B] , {[i]th node} [<] {[Node] argument}
    2. if [lower] is false, for any [i] smaller than [B] , {[i]th node} [<] {[Node] argument} or  {[i]th node} [==] {[Node] argument}
  */
  std::pair<SplayNode*,int> bound_sub(SplayNode* Node , SplayNode *root , bool lower ,  bool paired_compare ){
    if(bool(root) == false)return std::make_pair(root,0);
    SplayNode *now = root;
    int res = 0;
    Node->update();
    while(true){
      now->eval();
      bool satisfy = CompareNode(now,Node,paired_compare); // upper_bound (now <= Node)
      if(lower)satisfy = !CompareNode(Node,now,paired_compare); // lower_bound (now < Node)
      if(satisfy){
        if(bool(now->right))now = now->right;
        else {
          res++;
          break;
        }
      }else{
        if(bool(now->left))now = now->left;
        else break;
      }
    }
    now->splay();
    if(bool(now->left))res += now->left->SubTreeSize;
    return std::make_pair(now ,res);
  }

  // insert [NODE]argument into SplayTree (in which nodes are sorted)
  SplayNode *insert_sub(SplayNode *NODE , SplayNode *root , bool paired_compare){
    NODE->update();
    if(bool(root) == false)return NODE;
    // find the border index [x] ( [x]th node [<] [NODE] argument ]
    root = bound_sub(NODE,root,true,paired_compare).first;
    root->eval();
    if(!CompareNode(NODE , root , paired_compare)){
      if(root->right != nullptr)root->right->parent = NODE;
      NODE->right = root->right;
      root->right = nullptr;
      NODE->left = root;
    }else{
      if(root->left != nullptr)root->left->parent = NODE;
      NODE->left = root->left;
      root->left = nullptr;
      NODE->right = root;
    }
    root->parent = NODE;
    root->update();
    NODE->update();
    return NODE;
  }

  protected:

  // root node of this tree
  SplayNode *m_Root = nullptr;

  // bluff node object (used as temporary node)
  SplayNode *m_bluff_object = nullptr;
  SplayNode* BluffObject(type_key k , type_value v){
    if(m_bluff_object == nullptr)m_bluff_object = new SplayNode(type_key(0),type_value(0));
    m_bluff_object->Key = k;
    m_bluff_object->Value = v;
    return m_bluff_object;
  }

  // flag of whether node's Values are defined
  // (Values might be undefined if we use insert() function)
  bool _paired = true;

  void release(){while(m_Root != nullptr)this->Delete(0);}

  void init(){
    m_Root = nullptr;
    _paired = true;
  }

  // pointer of leftmost node
  const SplayNode* const begin(){
    if(size() == 0)return nullptr;
    m_Root = get_sub(0,m_Root);
    return m_Root;
  }

  public:

  MyMultiSet(){init();}
  ~MyMultiSet(){release();}
  // don't copy this object
  MyMultiSet(const MyMultiSet<type_key,type_value> & x) = delete ;
  MyMultiSet& operator = ( const MyMultiSet<type_key,type_value> & x) = delete ;
  MyMultiSet ( MyMultiSet<type_key,type_value>&& x){assert(0);}
  MyMultiSet& operator = ( MyMultiSet<type_key,type_value>&& x){assert(0);}
  // this function makes whole new SplayTree object from [x] argument
  void copy(MyMultiSet<type_key,type_value>& x){
    if(this->begin() == x.begin())return;
    release();
    init();
    for(int i=0;i<x.size();i++){
      SplayNode t=x.get(i);
      this->insert_pair(t.Key,t.Value);
    }
    this->_paired = x._paired;
  }

  // tree size
  int size(){
    if(m_Root == nullptr)return 0;
    return m_Root->SubTreeSize;
  }

  // get copy object of [i]th node
  SplayNode get(int i){
    assert(0 <= i && i < size());
    m_Root = get_sub(i,m_Root);
    return m_Root->copy();
  }

  // get copy object node which covers interval [l,r)
  // Ex. we can get Sum of Key in [l,r)
  SplayNode GetRange(int l , int r){
    assert(0 <= l && l < r && r <= size());
    std::pair<SplayNode*,SplayNode*> tmp = split(r,m_Root);
    SplayNode* rightRoot = tmp.second;
    tmp = split(l,tmp.first);// get subtree
    SplayNode res = tmp.second->copy();
    m_Root = merge(merge(tmp.first,tmp.second),rightRoot);
    return res;
  }

  // insert key_
  void insert( type_key key_ ){
    _paired = false;// undefined Value was added
    m_Root = insert_sub(new SplayNode(key_,type_value(0)) ,m_Root , false);
    return;
  }

  // insert (key_ , value_)
  void insert_pair( type_key key_ , type_value val_){
    assert(_paired);
    m_Root = insert_sub(new SplayNode(key_,val_) ,m_Root,true);
    return;
  }

  // delete [index]th element
  void Delete(int index){
    assert(0 <= index && index < size());
    std::pair<SplayNode*,SplayNode*> tmp = Delete_sub(index,m_Root);
    m_Root = tmp.first;
    if(tmp.second != nullptr)delete tmp.second;
    return;
  }

  // erase element which has key_ as Key
  void erase(type_key key_){
    int it = find(key_);
    if(it!=-1)Delete(it);
    return;
  }

  // erase element which has (key_,value_) as (Key,Value)
  void erase_pair(type_key key_ , type_value val_){
    assert(_paired);
    int it = find_pair(key_ , val_);
    if(it!=-1)Delete(it);
    return;
  }

  // counts nodes which < (x)
  int lower_bound(type_key x){
    if(size() == 0)return 0;
    std::pair<SplayNode*,int> tmp = bound_sub(BluffObject(x,type_value(0)),m_Root,true,false);
    m_Root = tmp.first;
    return tmp.second;
  }

  // counts nodes which < (x,y)
  int lower_bound_pair(type_key x , type_value y){
    assert(_paired);
    if(size() == 0)return 0;
    std::pair<SplayNode*,int> tmp = bound_sub(BluffObject(x,y),m_Root,true,true);
    m_Root = tmp.first;
    return tmp.second;
  }

  // counts nodes which <= (x)
  int upper_bound(type_key x){
    if(size() == 0)return 0;
    std::pair<SplayNode*,int> tmp = bound_sub(BluffObject(x,type_value(0)),m_Root,false,false);
    m_Root = tmp.first;
    return tmp.second;
  }

  // counts nodes which <= (x,y)
  int upper_bound_pair(type_key x , type_value y){
    assert(_paired);
    if(size() == 0)return 0;
    std::pair<SplayNode*,int> tmp = bound_sub(BluffObject(x,y),m_Root,false,true);
    m_Root = tmp.first;
    return tmp.second;
  }

  // find the index [i] which [i]th node has x as Key (if some answer exist,return smallest)
  // if no answer is found, return -1
  int find(type_key x){
    if(size() == 0)return -1;
    if(upper_bound(x) - lower_bound(x) <= 0)return -1;
    return lower_bound(x);
  }

  // find the index [i] which [i]th node has (x,y) as (Key,Value) (if some answer exist,return smallest)
  // if no answer is found, return -1
  int find_pair(type_key x , type_value y){
    assert(_paired);
    if(size() == 0)return -1;
    if(upper_bound_pair(x,y) - lower_bound_pair(x,y) <= 0)return -1;
    return lower_bound_pair(x,y);
  }


  SplayNode back(){assert(size()>0);return get(size()-1);}
  SplayNode front(){assert(size()>0);return get(0);}
  void pop_back(){assert(size()>0);Delete(size()-1);}
  void pop_front(){assert(size()>0);Delete(0);}
  SplayNode operator [](int index){return get(index);}
};

int main()
{
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  MyMultiSet<ll, ll> mms;
  ll sum = 0;
  ll ans = -linf;
  for (int i = 0; i < N; i++)
  {
    sum += A[i];
    if (K-1 <= i)
    {
      if (K == 1)
      {
        ans = max(ans, sum);
      }
      else
      {
        ans = max(ans, sum * K - mms.GetRange(0, K-1).Sum_key);
      }
    }
    mms.insert(sum);
  }
  cout << ans << '\n';
  return 0;
}
/*
  File : ~/yukicoder/526/C.cpp
  Date : 2025/03/07
  Time : 21:45:15
*/