Submission #95828

#	Time	Username	Problem	Language	Result	Execution time	Memory
95828		Kastanda	Candies (JOI18_candies)	C++11	100 / 100	503 ms	19600 KiB

candies

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, L[N], R[N];
ll A[N];
set < pair < ll , int > > S;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &A[i]);
        L[i] = i - 1; R[i] = i + 1;
        S.insert({A[i], i});
    }
    ll Mx = 0;
    for (int i = 0; i < (n + 1 >> 1); i++)
    {
        int id = S.rbegin()->second;
        S.erase(*S.rbegin());
        Mx += A[id];
        printf("%lld\n", Mx);
        int le = L[id], ri = R[id];
        S.erase({A[le], le});
        S.erase({A[ri], ri});
        if (le <= 0 || ri <= 0 || ri > n || le > n)
        {
            L[R[ri]] = 0;
            R[L[le]] = n + 1;
            continue;
        }
        A[id] = A[le] + A[ri] - A[id];
        L[id] = L[le];
        R[id] = R[ri];
        L[R[id]] = id;
        R[L[id]] = id;
        S.insert({A[id], id});
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:18:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     for (int i = 0; i < (n + 1 >> 1); i++)
                          ~~^~~
candies.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
candies.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &A[i]);
         ~~~~~^~~~~~~~~~~~~~~

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