제출 #646218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646218		Tenis0206	수열 (APIO14_sequence)	C++11	0 / 100	8 ms	1876 KiB

sequence

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n,k;
int v[100005];

int sp[100005];

priority_queue<pair<pair<int,int>,pair<int,int>>> h;

int sum(int st, int dr)
{
    if(st > dr)
    {
        return 0;
    }
    return sp[dr] - sp[st - 1];
}

void Add(int l, int r)
{
    if(l >= r)
    {
        return;
    }
    int poz = 0;
    int st = l;
    int dr = r;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(sum(l,mij)<=sum(mij+1,r))
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    int rez1 = sum(l,poz) * sum(poz+1,r);
    int rez2 = sum(l,poz+1) * sum(poz+2,r);
    int val = rez1;
    if(rez2 > rez1)
    {
        val = rez2;
        ++poz;
    }
    h.push({{val,poz},{l,r}});
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    Add(1,n);
    int rez = 0;
    vector<int> r;
    for(int i=1;i<=k;i++)
    {
        rez += h.top().first.first;
        int poz = h.top().first.second;
        int st = h.top().second.first;
        int dr = h.top().second.second;
        h.pop();
        Add(st,poz);
        Add(poz+1,dr);
        r.push_back(poz);
    }
  /*  cout<<rez<<'\n';
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    cout<<'\n';
    */
    int aux = 0;
    int last = 0;
    sort(r.begin(),r.end());
    for(auto it : r)
    {
        aux += sum(last+1,it) * sum(it + 1, n);
        last = it;
    }
    cout<<aux<<'\n';
    for(auto it : r)
    {
        cout<<it<<' ';
    }
    return 0;
}

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