oj.uz

Submission #960891

# Submission time Handle Problem Language Result Execution time Memory
960891 2024-04-11T07:49:07 Z vjudge1 Split the sequence (APIO14_sequence) C++17
0 / 100
 3 ms 500 KB 
#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(){
    freopen("input.txt", "r", stdin);
    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]),
            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();
}

Compilation message

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:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 500 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -