제출 #960902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960902		boyliguanhan	수열 (APIO14_sequence)	C++17	0 / 100	751 ms	81848 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int lead[100100][200],zero[100100];
ll pre[100100],val[100100];
struct Ln{
    ll k,b,ii;
    Ln(){k=b=0;}
    Ln(ll a,ll x,ll i){k=a,b=x,ii=i;}
    ll inter(Ln x){
        return (b-x.b)/(x.k-k);
    }
    ll val(int x){
        return k*x+b;
    }
};
deque<Ln>ch;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    set<int>st;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
        if(!pre[i])
            st.insert(i+zero[i-1]+zero[i]),
            n--,zero[i--]++;
        else
            pre[i]+=pre[i-1],
            zero[i]+=zero[i-1];
    }
    if(k>=n-1){
        ll v=0;
        int x=k-n+1;
        while(st.size()>x)
            st.erase(st.begin());
        for(int i=2;i<=n;i++)
            v+=(pre[i]-pre[i-1])*pre[i-1];
        cout<<v<<'\n';
        for(int i=1;i<n;i++)
            st.insert(i+zero[i]);
        for(auto i:st)
            cout<<i<<' ';
        return 0;
    }
    for(int i=1;i<=k;i++){
        ch.push_back(Ln(pre[i],val[i]-pre[i]*pre[i],i));
        for(int j=i+1;j<=n;j++){
            while(ch.size()>1&&ch[0].inter(ch[1])<pre[j])
                ch.pop_front();
            ll V=ch[0].val(pre[j]);
            lead[j][i]=ch[0].ii;
            Ln L(pre[j],val[j]-pre[j]*pre[j],j);
            while(ch.size()>1&&L.inter(ch[ch.size()-2])<=ch.back().inter(ch[ch.size()-2]))
                ch.pop_back(); ch.push_back(L);
            val[j]=V;
        }
        ch.clear();
    }
    cout<<val[n]<<'\n';
    stack<int>stk;
    int cnt=k+1;
    while(--cnt)
        stk.push(n=lead[n][cnt]);
    while(stk.size())
        cout<<stk.top()+zero[stk.top()]<<' ',stk.pop();
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:36:24: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while(st.size()>x)
      |               ~~~~~~~~~^~
sequence.cpp:55:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   55 |             while(ch.size()>1&&L.inter(ch[ch.size()-2])<=ch.back().inter(ch[ch.size()-2]))
      |             ^~~~~
sequence.cpp:56:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   56 |                 ch.pop_back(); ch.push_back(L);
      |                                ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29