Submission #44902

#	Time	Username	Problem	Language	Result	Execution time	Memory
44902		PowerOfNinjaGo	Candies (JOI18_candies)	C++17	100 / 100	589 ms	71472 KiB

candies

#include <cstdio>
#include <map>
#include <queue>
#include <utility>
using namespace std;
typedef pair<long long,int> pi;
typedef map<int,bool> mp;

priority_queue<pi > pq;
mp viable;

int n,k;
long long a[200005];

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=n-1; i>= 0; i--) {
        pq.push(pi(a[i],i));
        viable[i] = 1;
    }
    long long res = 0;
    for (int i=0; i<(n+1)/2; i++)
    {
        int p = pq.top().second; pq.pop();
        if(viable.count(p) == 0){
            i--;
            continue;
        }
        res += a[p];
        printf("%lld\n", res);
        viable.erase(viable.find(p));
        mp::iterator it = viable.upper_bound(p);
        long long x = 0; int cont = 0;
        if(it != viable.end()){
            x += a[(*it).first];
            viable.erase((*it).first);
        }
        else cont = 1;
        it = viable.upper_bound(p);
        if(it != viable.begin()){
            it--;
            x += a[(*it).first];
            viable.erase((*it).first);
        }
        else cont = 1;
        if(cont) continue;
        viable[p] = 1;
        a[p] = x - a[p];
        pq.push(pi(a[p],p));
    }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:18:25: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&a[i]);
                    ~~~~~^
candies.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
candies.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~

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