oj.uz

Submission #90542

# Submission time Handle Problem Language Result Execution time Memory
90542 2018-12-22T10:16:47 Z 314rate Split the sequence (APIO14_sequence) C++14
0 / 100
 8 ms 1088 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Incorrect 2 ms 504 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB position 24 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 504 KB position 197 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 528 KB position 492 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 564 KB position 9995 occurs twice in split scheme
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1088 KB position 28624 occurs twice in split scheme
2 Halted 0 ms 0 KB -