Submission #90545

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

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=100000+5;

int n,k,pre[N];

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

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

pair<ll,int>split(int st,int dr)
{
    if(st==dr)
    {
        return {-1,-1};
    }
    ll a=0LL;
    int id;
    for(int 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(int st,int dr)
{
    pair<ll,int>aux=split(st,dr);
    cur.push_back({st,dr,aux.first,aux.second});
}

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

vector<int>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(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        pre[i]=x+pre[i-1];
    }
    add(1,n);
    ll ans=0LL;
   // print();
    for(int va=1;va<=k;va++)
    {
        ll mx=0LL;
        int id;
        for(int i=0;i<cur.size();i++)
        {
            mx=max(mx,cur[i].val);
            if(mx==cur[i].val)
            {
                id=i;
            }
        }
        int st=cur[id].st;
        int dr=cur[id].dr;
        int 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(int)':
sequence.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=p;i+1<cur.size();i++)
                 ~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<cur.size();i++)
                     ~^~~~~~~~~~~
sequence.cpp: In function 'std::pair<long long int, int> split(int, int)':
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:22: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int 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