結果
問題 | No.3050 Prefix Removal |
ユーザー |
![]() |
提出日時 | 2025-03-07 22:55:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 331 ms / 2,000 ms |
コード長 | 4,554 bytes |
コンパイル時間 | 3,827 ms |
コンパイル使用メモリ | 290,592 KB |
実行使用メモリ | 30,532 KB |
最終ジャッジ日時 | 2025-03-07 22:55:52 |
合計ジャッジ時間 | 16,802 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include<bits/stdc++.h> using namespace std; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define pb push_back #define all(a) begin(a),end(a) #define allr(a) rbegin(a),rend(a) #define ff first #define ss second template<class T> bool chmax(T& a,T b){return a<b?a=b,1:0;} template<class T> bool chmin(T& a,T b){return a>b?a=b,1:0;} using ll =long long; using pii =pair<int,int>; using pll=pair<long long,long long>; using vi=vector<int>; using vll=vector<ll>; inline bool ingrid(int a,int b,int h,int w){ return 0<=a&&a<h&&0<=b&&b<w; } const int INFI = numeric_limits<int>::max() / 2; const long long INFL = numeric_limits<long long>::max() / 2; constexpr pii dx4[4] = {pii{-1, 0}, pii{0, -1},pii{1, 0}, pii{0, 1} }; #define endl '\n' template< typename T, typename Compare = less< T >, typename RCompare = greater< T > > struct PrioritySumStructure { size_t k; T sum; priority_queue< T, vector< T >, Compare > in, d_in; priority_queue< T, vector< T >, RCompare > out, d_out; PrioritySumStructure(int k) : k(k), sum(0) {} void modify() { while(in.size() - d_in.size() < k && !out.empty()) { auto p = out.top(); out.pop(); if(!d_out.empty() && p == d_out.top()) { d_out.pop(); } else { sum += p; in.emplace(p); } } while(in.size() - d_in.size() > k) { auto p = in.top(); in.pop(); if(!d_in.empty() && p == d_in.top()) { d_in.pop(); } else { sum -= p; out.emplace(p); } } while(!d_in.empty() && in.top() == d_in.top()) { in.pop(); d_in.pop(); } } //上位 k 個の和(要素数がk個未満の場合すべての要素の和) T query() const { return sum; } //要素 x を追加する void insert(T x) { in.emplace(x); sum += x; modify(); } //要素 x を削除する void erase(T x) { assert(size()); if(!in.empty() && in.top() == x) { sum -= x; in.pop(); } else if(!in.empty() && RCompare()(in.top(), x)) { sum -= x; d_in.emplace(x); } else { d_out.emplace(x); } modify(); } //k を指定しなおす void set_k(size_t kk) { k = kk; modify(); } //k を返す size_t get_k() const { return k; } //全体の要素数を返す size_t size() const { return in.size() + out.size() - d_in.size() - d_out.size(); } }; //降順 k 個に指定 template< typename T > using MaximumSum = PrioritySumStructure< T, greater< T >, less< T > >; //昇順 k 個に指定 template< typename T > using MinimumSum = PrioritySumStructure< T, less< T >, greater< T > >; template<typename T,typename F> struct SegmentTree{ private: int n; vector<T> data; const F f; T ti; public: SegmentTree()=default; SegmentTree(int n,F f,T ti):n(n),f(f),ti(ti),data(n<<1,ti){} SegmentTree(vector<T> v,F f,T ti):n(v.size()),f(f),ti(ti),data(n<<1,ti){ for(int i=0;i<n;i++)data[i+n]=v[i]; for(int i=n-1;i>=1;i--)data[i]=f(data[i<<1],data[i<<1|1]); } void update(int k,const T& val){ k+=n; data[k]=val; for(k>>=1;k>=1;k>>=1){ data[k]=f(data[k<<1],data[k<<1|1]); } } const T operator[](const int &k){return data[k+n];} void apply(int k,const T& val){ update(k,f(data[k+n],val)); } const T prod(int l,int r){ l+=n;r+=n; T vl=ti,vr=ti; for(;l<r;l>>=1,r>>=1){ if(l&1)vl=f(vl,data[l++]); if(r&1)vr=f(data[--r],vr); } return f(vl,vr); } }; template<typename T,typename F> SegmentTree<T,F> get_SegmentTree(int n,F f,T ti){return SegmentTree<T,F>(n,f,ti);} template<typename T,typename F> SegmentTree<T,F> get_SegmentTree(vector<T> v,F f,T ti){return SegmentTree<T,F>(v,f,ti);} ll n,k; vll a; void solve(){ vll pref(n+1); rrep(i,n-1,0){ pref[i]=a[i]+pref[i+1]; } MaximumSum<ll> q(k-1); rep(i,1,k-1){ q.insert(pref[i]); } auto seg=get_SegmentTree(pref,[](ll a,ll b){return min(a,b);},INFL); ll ans=-INFL; rep(i,k-1,n){ q.insert(pref[i]); chmax(ans,pref[0]+q.query()-seg.prod(i+1,n+1)*k); } cout<<ans<<endl; } int main(){ cin>>n>>k; a.resize(n); rep(i,0,n)cin>>a[i]; solve(); return 0; } /* 上位k-1個の和を管理しながら 区間minをとる */