Submission #90546

#	Time	Username	Problem	Language	Result	Execution time	Memory
90546		314rate	Split the sequence (APIO14_sequence)	C++14	0 / 100	8 ms	1512 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=100000+5;

ll n,k,pre[N];

ll s(ll st,ll dr)
{
    return pre[dr]-pre[st-1];
}

struct info
{
    ll st;
    ll dr;
    ll val;
    ll p;
};

pair<ll,ll>split(ll st,ll dr)
{
    if(st==dr)
    {
        return {-1,-1};
    }
    ll a=0LL;
    ll id;
    for(ll p=st;p<dr;p++)
    {
        ll X=s(st,p);
        ll Y=s(p+1,dr);
        ll pr=X*Y;
        a=max(a,pr);
        if(a==pr)
        {
            id=p;
        }
    }
    return {a,id};
}

vector<info>cur;

void add(ll st,ll dr)
{
    pair<ll,ll>aux=split(st,dr);
    cur.push_back({st,dr,aux.first,aux.second});
}

void del(ll p)
{
    for(ll i=p;i+1<cur.size();i++)
    {
        cur[i]=cur[i+1];
    }
    cur.pop_back();
}

vector<ll>who;

void print()
{
    cout<<"GAYYY::\n\n";
    for(auto &x:cur)
    {
        cout<<x.st<<" "<<x.dr<<" : "<<x.val<<"\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pre[i]=x+pre[i-1];
    }
    add(1,n);
    ll ans=0LL;
   // print();
    for(ll va=1;va<=k;va++)
    {
        ll mx=0LL;
        ll id;
        for(ll i=0;i<cur.size();i++)
        {
            mx=max(mx,cur[i].val);
            if(mx==cur[i].val)
            {
                id=i;
            }
        }
        ll st=cur[id].st;
        ll dr=cur[id].dr;
        ll p=cur[id].p;
        ans+=mx;
        del(id);
       /// cout<<st<<" "<<dr<<" : "<<p<<"\n";
        add(st,p);
        add(p+1,dr);
      //  print();
      who.push_back(p);
    }
    cout<<ans<<"\n";
    for(auto &x:who)
    {
        cout<<x<<" ";
    }
    cout<<"\n";
    return 0;
}
/**

7 3
4 1 3 4 0 2 3

**/

Compilation message (stderr)

sequence.cpp: In function 'void del(ll)':
sequence.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=p;i+1<cur.size();i++)
                ~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0;i<cur.size();i++)
                    ~^~~~~~~~~~~
sequence.cpp: In function 'std::pair<long long int, long long int> split(ll, ll)':
sequence.cpp:43:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return {a,id};
                 ^
sequence.cpp: In function 'int main()':
sequence.cpp:99:21: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ll st=cur[id].st;
                     ^

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