Submission #1075385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075385		mindiyak	Holiday (IOI14_holiday)	C++14	47 / 100	5009 ms	2748 KiB

holiday

#include"holiday.h"
#include <vector>
#include <set>
#include <iostream>
#include <queue>
using namespace std;
#define ll long long 

ll ans = 0;

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {

    if(n<=20){
        for(int k=1;k<(1<<n);k++){
            int len = 32 - (__builtin_clz(k) + __builtin_ctz(k)) - 1;
            int a = __builtin_ctz(k);
            int b = 31 - __builtin_clz(k);
            int cost = __builtin_popcount(k) + len + min(abs(a - start), abs(b - start));

            if(cost > d)continue;

            ll val = 0;
            for(int i=0;i<n;i++){
                if(((1<<i)&k)>0){
                    val += attraction[i];
                }
            }

            ans = max(ans,val);
        }

        return ans;
    }

    if(start == 0){
        priority_queue<ll> pq;
        ll ans = 0;
        ll cur = 0;

        for(int i = 0;i<min(n,d);i++){
            pq.push(-attraction[i]);
            cur += attraction[i];

            while(i+pq.size() > d){
                cur += pq.top();pq.pop();
            }

            ans = max(ans,cur);
        }

        return ans;
    }

    // cerr << "started" << endl;

    ll ans = 0;
    for(int s=0;s<n;s++){
        priority_queue<ll> pq;
        ll cur = 0;

        for(int i = s;i<n;i++){
            int dis = (i-s) + min(abs(start-s),abs(start-i));
            // cerr << i << " " << s << " " << dis << endl;

            if(dis >= d)break;;

            pq.push(-attraction[i]);
            cur += attraction[i];

            while(dis+pq.size() > d){
                cur += pq.top();pq.pop();
            }

            ans = max(ans,cur);
        }
    }

    return ans;

    
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:44:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |             while(i+pq.size() > d){
      |                   ~~~~~~~~~~~~^~~
holiday.cpp:70:33: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             while(dis+pq.size() > d){
      |                   ~~~~~~~~~~~~~~^~~

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