Submission #234042

#	Time	Username	Problem	Language	Result	Execution time	Memory
234042		DS007	Candies (JOI18_candies)	C++14	100 / 100	1082 ms	58748 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define int long long

int solveTestCase(int test) {
    int n;
    cin >> n;

    int a[n + 2] = {};
    for (int i = 1; i <= n; i++) cin >> a[i];

    int p1[n + 2] = {}, p2[n + 2] = {};
    p1[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (i % 2)
            p1[i] = a[i] + p1[i - 2];
        else
            p2[i] = a[i] + p2[i - 2];
    }

    set<pair<int, pair<int, int>>, decltype(greater<>())> s;
    map<int, int> begin, end;
    map<pair<int, int>, int> rev;
    for (int i = 1; i <= n; i++) {
        s.insert(make_pair(a[i], make_pair(i, i)));
        begin[i] = i;
        end[i] = i;
        rev[{i, i}] = a[i];
    }

    int ans = 0;
    for (int i = 1; i <= (n + 1) / 2; i++) {
        auto temp = s.begin();
        bool check = true;
        ans += temp->first;
        cout << ans << "\n";

        pair<int, int> next = temp->second;
        end.erase(next.second);
        begin.erase(next.first);
        rev.erase(next);

        auto it1 = begin.find(next.second + 1);
        if (it1 != begin.end()) {
            next.second = it1->second - 1;
            s.erase(make_pair(rev[*it1], *it1));
            rev.erase(*it1);
            end.erase(it1->second);
            begin.erase(it1);
        } else check = false;

        auto it2 = end.find(next.first - 1);
        if (it2 != end.end()) {
            next.first = it2->second + 1;
            s.erase(make_pair(rev[{it2->second, it2->first}], make_pair(it2->second, it2->first)));
            rev.erase({it2->second, it2->first});
            begin.erase(it2->second);
            end.erase(it2);
        } else check = false;

        int off = 0;
        if (next.second == n)
            next.second--, off += a[n];
        else
            next.second++;

        if (next.first == 1)
            next.first++, off += a[1];
        else
            next.first--;

        s.erase(temp);
        //assert((next.second - next.first) % 2 == 0 && next.second - next.first != 0);

        int val = -off;
        if (next.second != next.first && check) {
            val += next.second % 2 ? p1[next.second] - p1[next.first] + a[next.first] - (p2[next.second - 1] - p2[next.first + 1] + a[next.first + 1]) : p2[next.second] - p2[next.first] + a[next.first] - (p1[next.second - 1] - p1[next.first + 1] + a[next.first + 1]);
            s.insert(make_pair(val, next));
            rev[next] = val;
            begin.insert(next);
            end[next.second] = next.first;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message (stderr)

candies.cpp: In function 'long long int solveTestCase(long long int)':
candies.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92