Submission #39754

#	Time	Username	Problem	Language	Result	Execution time	Memory
39754		funcsr	Holiday (IOI14_holiday)	C++14	0 / 100	516 ms	12524 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 dpL[300000], dpR[300000];
inline long long top_sum_less_than(priority_queue<P> &erased, int r, int lim) {
  vector<int> backup;
  long long s = 0;
  while (!erased.empty() && backup.size() < lim) {
    int x = erased.top()._2;
    erased.pop();
    if (x >= r) continue;
    backup.pb(x);
    s += A[x];
  }
  for (int x : backup) erased.push(P(A[x], x));
  return s;
}
inline long long top_sum_greater_than(priority_queue<P> &erased, int l, int lim) {
  vector<int> backup;
  long long s = 0;
  while (!erased.empty() && backup.size() < lim) {
    int x = erased.top()._2;
    erased.pop();
    if (x <= l) continue;
    backup.pb(x);
    s += A[x];
  }
  for (int x : backup) erased.push(P(A[x], x));
  return s;
}

long long solve(int start) {
  rep(i, D+1) dpL[i] = dpR[i] = 0;
  if (start < N-1) {
    int r = N-1;
    long long s = 0;
    set<P> pq;
    priority_queue<P> erased;
    for (int x=start+1; x<N; x++) s += A[x], pq.insert(P(A[x], x));
    for (int d=(N-1-start)*2; d>=0; d--) {
      bool bad = false;
      while (!pq.empty() && r-start+pq.size() > d) {
        int x = pq.begin()->_2;
        if (x == r) {
          bad = true;
          break;
        }
        erased.push(P(A[x], x));
        s -= A[x];
        pq.erase(pq.begin());
      }
      long long e = 0;
      if (!bad) e = top_sum_less_than(erased, r, 2);
      if (bad || e > A[r]) {
        s -= A[r];
        pq.erase(P(A[r], r));
        r--;
      }
      while (!erased.empty() && r-start+pq.size() < d) {
        int x = erased.top()._2;
        erased.pop();
        if (x > r) continue;
        pq.insert(P(A[x], x));
        s += A[x];
      }
      if (d <= D) dpR[d] = s;
    }
  }
  if (start > 0) {
    int l = 0;
    long long s = 0;
    set<P> pq;
    priority_queue<P> erased;
    for (int x=0; x<start; x++) s += A[x], pq.insert(P(A[x], x));
    for (int d=start*3; d>=0; d--) {
      bool bad = false;
      while (!pq.empty() && (start-l)*2+pq.size() > d) {
        int x = pq.begin()->_2;
        if (x == l) {
          bad = true;
          break;
        }
        erased.push(P(A[x], x));
        s -= A[x];
        pq.erase(pq.begin());
      }
      long long e = 0;
      if (!bad) e = top_sum_greater_than(erased, l, 3);
      if (bad || e > A[l]) {
        s -= A[l];
        pq.erase(P(A[l], l));
        l++;
      }
      while (!erased.empty() && (start-l)*2+pq.size() < d) {
        int x = erased.top()._2;
        erased.pop();
        if (x < l) continue;
        pq.insert(P(A[x], x));
        s += A[x];
      }
      if (d <= D) dpL[d] = s;
    }
  }

  long long m = 0;
  rep(l, D+1) {
    m = max(m, dpL[l] + dpR[D-l]);
    if (D-l-1>0) m = max(m, dpL[l] + dpR[D-l-1] + A[start]);
  }
  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;
  m = max(m, solve(start));
  reverse(A, A+N);
  m = max(m, solve(N-1-start));
  return m;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int top_sum_less_than(std::priority_queue<std::pair<int, int> >&, int, int)':
holiday.cpp:25:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (!erased.empty() && backup.size() < lim) {
                                           ^
holiday.cpp: In function 'long long int top_sum_greater_than(std::priority_queue<std::pair<int, int> >&, int, int)':
holiday.cpp:38:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (!erased.empty() && backup.size() < lim) {
                                           ^
holiday.cpp: In function 'long long int solve(int)':
holiday.cpp:59:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (!pq.empty() && r-start+pq.size() > d) {
                                               ^
holiday.cpp:76:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (!erased.empty() && r-start+pq.size() < d) {
                                                   ^
holiday.cpp:94:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (!pq.empty() && (start-l)*2+pq.size() > d) {
                                                   ^
holiday.cpp:111:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (!erased.empty() && (start-l)*2+pq.size() < d) {
                                                       ^
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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53