Submission #1073975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073975		deera	Holiday (IOI14_holiday)	C++14	47 / 100	5076 ms	1992 KiB

holiday

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

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (d == 0) {return 0;}
    if (d == 1) {return attraction[start];}

    if (n <= 20) {
        // iterate over all the subtasks
        long long max_ans = 0;
        long long ans = 0;
        for (int32_t i = 0; i < (1 << n); i++) {
            int len = 32 - (__builtin_clz(i) + __builtin_ctz(i)) - 1;
            int a = __builtin_ctz(i);
            int b = 31 - __builtin_clz(i);
            int cost = __builtin_popcount(i) + len + min(abs(a - start), abs(b - start));
            
            // if (i == 30) {
            //     for (int j = 0; j < n; j++) {
            //         cerr << ((i & (1 << j)) ? 1 : 0) << " ";
            //     }
            //     cerr << endl;
            //     cerr << cost << endl;
            //     cerr << a << " " << b << endl;
            // }

            if (cost > d) continue;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    ans += attraction[j];
                }
            }

            max_ans = max(max_ans, ans);
            ans = 0;
        }

        return max_ans;
    }

    if (start == 0) {
        long long max_ans = 0;
        priority_queue<int, vector<int>, greater<int>> pq;
        long long sum = 0;

        for (int i = 0; i < n; i++) {
            int cost = abs(i - start);
            pq.push(attraction[i]);
            sum += attraction[i];

            while (cost + pq.size() > d) {
                sum -= pq.top();
                pq.pop();
            }

            max_ans = max(max_ans, sum);
        }

        return max_ans;
    }

    if (n <= 3000) {
        long long max_ans = 0;
        for (int s = 0; s < n; s++) {
            priority_queue<int, vector<int>, greater<int>> pq;
            long long sum = 0;

            for (int i = s; i < n; i++) {
                int cost = abs(i - s) + min(abs(s - start), abs(i - start));
                if (cost > d) break;
                pq.push(attraction[i]);
                sum += attraction[i];

                while (cost + pq.size() > d) {
                    sum -= pq.top();
                    pq.pop();
                }

                max_ans = max(max_ans, sum);
            }
        }

        return max_ans;

    }
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:51:37: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |             while (cost + pq.size() > d) {
      |                    ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:74:41: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |                 while (cost + pq.size() > d) {
      |                        ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
   86 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53