Submission #679338

#	Time	Username	Problem	Language	Result	Execution time	Memory
679338		Cross_Ratio	Holiday (IOI14_holiday)	C++14	47 / 100	5063 ms	1904 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
int N, st, d;
int A[100005];
typedef pair<int, int> P;
ll findMaxAttraction(int _N, int _st, int _d, int attraction[]) {
    N = _N, st = _st, d = _d;
    int i, j;
    for(i=0;i<N;i++) A[i] = attraction[i];
    ll ans = 0;
    ll sum = 0;
    for(i=st;i>=0;i--) {
        int val = d;
        val -= 2*(st - i);
        if(val <= 0) break;
        priority_queue<int, vector<int>, greater<int>> PQ;
        ll cnt = 0;
        for(int j = i; j <= st; j++) {
            cnt += A[j];
            PQ.push(A[j]);
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
        }
        ans = max(ans, cnt);
        for(j=st+1;j<N;j++) {
            cnt += A[j];
            PQ.push(A[j]);
            val--;
            if(val <= 0) break;
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
            ans = max(ans, cnt);
        }
    }
    if(st==0) return ans;
    st = N-1-st;
    reverse(A, A+N);
    for(i=st;i>=0;i--) {
        int val = d;
        val -= 2*(st - i);
        if(val <= 0) break;
        priority_queue<int, vector<int>, greater<int>> PQ;
        ll cnt = 0;
        for(int j = i; j <= st; j++) {
            cnt += A[j];
            PQ.push(A[j]);
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
        }
        ans = max(ans, cnt);
        for(j=st+1;j<N;j++) {
            cnt += A[j];
            PQ.push(A[j]);
            val--;
            if(val <= 0) break;
            while(PQ.size()>val) {
                cnt -= PQ.top();
                PQ.pop();
            }
            ans = max(ans, cnt);
        }
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:23:28: 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]
   23 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:34:28: 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]
   34 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:53:28: 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]
   53 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:64:28: 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]
   64 |             while(PQ.size()>val) {
      |                   ~~~~~~~~~^~~~
holiday.cpp:13:8: warning: unused variable 'sum' [-Wunused-variable]
   13 |     ll sum = 0;
      |        ^~~

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