Submission #39730

#	Time	Username	Problem	Language	Result	Execution time	Memory
39730		funcsr	Holiday (IOI14_holiday)	C++14	47 / 100	387 ms	4304 KiB

holiday

#include "holiday.h"
#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define INF (1LL<<60)
#define _1 first
#define _2 second

int N, D;
int A[100000];
long long solve(int start) {
  long long m = 0;
  rep(left, start+1) {
    int rest = D-(start-left)*2;
    if (rest < 0) continue;
    priority_queue<P, vector<P>, greater<P> > pq;
    long long sum = 0;
    for (int x=left; x<start; x++) sum += A[x], pq.push(P(A[x], x));
    for (int r=start; r<N; r++) {
      int cnt = rest-(r-start);
      if (cnt <= 0) break;
      sum += A[r];
      pq.push(P(A[r], r));
      while (pq.size() > cnt) {
        sum -= pq.top()._1;
        pq.pop();
      }
      m = max(m, sum);
    }
  }
  return m;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
  N = n, D = d;
  rep(i, N) A[i] = attraction[i];
  long long m = 0;
  if (start == 0) {
    priority_queue<P, vector<P>, greater<P> > pq;
    long long sum = 0;
    for (int r=0; r<min(D, N); r++) {
      int cnt = D-r;
      sum += A[r];
      pq.push(P(A[r], r));
      while (pq.size() > cnt) {
        sum -= pq.top()._1;
        pq.pop();
      }
      m = max(m, sum);
    }
  }
  else if (N <= 3000) {
    m = max(m, solve(start));
    reverse(A, A+N);
    m = max(m, solve(N-1-start));
  }
  else abort();
  return m;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int solve(int)':
holiday.cpp:33:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (pq.size() > cnt) {
                        ^
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (pq.size() > cnt) {
                        ^
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^

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