oj.uz

Submission #44901

# Submission time Handle Problem Language Result Execution time Memory
44901 2018-04-09T08:09:47 Z PowerOfNinjaGo Candies (JOI18_candies) C++17
8 / 100
 22 ms 3868 KB 
#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[100005];

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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 612 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 772 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 864 KB Output is correct
7 Correct 4 ms 884 KB Output is correct
8 Correct 4 ms 904 KB Output is correct
9 Correct 4 ms 924 KB Output is correct
10 Correct 3 ms 1176 KB Output is correct
11 Correct 4 ms 1176 KB Output is correct
12 Correct 5 ms 1176 KB Output is correct
13 Correct 5 ms 1176 KB Output is correct
14 Correct 4 ms 1256 KB Output is correct
15 Correct 4 ms 1256 KB Output is correct
16 Correct 4 ms 1256 KB Output is correct
17 Correct 4 ms 1256 KB Output is correct
18 Correct 5 ms 1256 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1288 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 612 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 4 ms 772 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 864 KB Output is correct
7 Correct 4 ms 884 KB Output is correct
8 Correct 4 ms 904 KB Output is correct
9 Correct 4 ms 924 KB Output is correct
10 Correct 3 ms 1176 KB Output is correct
11 Correct 4 ms 1176 KB Output is correct
12 Correct 5 ms 1176 KB Output is correct
13 Correct 5 ms 1176 KB Output is correct
14 Correct 4 ms 1256 KB Output is correct
15 Correct 4 ms 1256 KB Output is correct
16 Correct 4 ms 1256 KB Output is correct
17 Correct 4 ms 1256 KB Output is correct
18 Correct 5 ms 1256 KB Output is correct
19 Correct 4 ms 1272 KB Output is correct
20 Correct 4 ms 1288 KB Output is correct
21 Runtime error 22 ms 3868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -