Submission #90542

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

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100000 + 5;

int n, k;
int p[N];

int ask(int st, int dr)
{
    return p[dr] - p[st - 1];
}

vector <pair <int, int>> G;
vector <ll> cost;
vector <int> poz;

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

pair<ll, int> get(int st, int dr)
{
    ll ans = 0LL;
    int id;
    for (int p = st; p < dr; p++)
    {
        ll a = ask(st, p);
        ll b = ask(p + 1, dr);
        ans = max(ans, a * b);
        if (a * b == ans)
        {
            id = p;
        }
    }
    return {ans, id};
}

void add(int st, int dr)
{
    G.push_back({st, dr});
    pair <ll, int> aux = get(st, dr);
    cost.push_back(aux.first);
    poz.push_back(aux.second);
}

int Find()
{
    ll mx = 0LL;
    int id;
    for (int i = 0; i < G.size(); i++)
    {
        mx = max(mx, cost[i]);
        if (cost[i] == mx)
        {
            id = i;
        }
    }
    return id;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        p[i] = p[i - 1] + x;
    }

    vector <int> pozitions;

    add(1, n);
    ll ans = 0LL;
    for (int i = 1; i <= k; i++)
    {
        int id = Find();
        int st = G[id].first;
        int dr = G[id].second;
        int p = poz[id];
        ll addX = cost[id];
        ans += addX;
        del(p);
        add(st, p);
        add(p + 1, dr);
        pozitions.push_back(p);
    }

    cout << ans << "\n";
    for (auto &it : pozitions)
    {
        cout << it << " ";
    }
    cout << "\n";
}

Compilation message (stderr)

sequence.cpp: In function 'void del(int)':
sequence.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = p; i + 1 < G.size(); i++)
                     ~~~~~~^~~~~~~~~~
sequence.cpp: In function 'int Find()':
sequence.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < G.size(); i++)
                     ~~^~~~~~~~~~
sequence.cpp: In function 'std::pair<long long int, int> get(int, int)':
sequence.cpp:48:20: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return {ans, id};
                    ^
sequence.cpp: In function 'int Find()':
sequence.cpp:71:12: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return id;
            ^~

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