Submission #258428

#	Time	Username	Problem	Language	Result	Execution time	Memory
258428		sandoval	Holiday (IOI14_holiday)	C++11	23 / 100	44 ms	65540 KiB

holiday

#include <bits/stdc++.h>

using namespace std;
using ii = pair<int,int>;
using ll = long long;

constexpr int MAXN = 5+3000;

long long memo[2][MAXN][2*MAXN+(MAXN/2)];
vector<int> a;

long long dp(int i, int d) {
  if (i >= (int)a.size() || d <= 0) return 0;
  long long& ans = memo[0][i][d];
  if (ans != -1) return ans;
  return ans = max(a[i]+dp(1+i,d-2), dp(1+i,d-1));
}

long long dp2(int i, int d) {
  if (i < 0 || d <= 0) return 0;
  long long& ans = memo[1][i][d];
  if (ans != -1) return ans;
  return ans = max(a[i]+dp2(i-1,d-2), dp2(i-1,d-1));
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
  a.resize(n);
  for (int i = 0; i < n; ++i) a[i] = attraction[i];

  long long ans = 0;
  if (n <= 3000) { // Subtask 1,3.
    memset(memo, -1, sizeof memo);
    for (int i = start; i >= 0; --i) {
      ans = max(ans, dp(i,d-abs(start-i)));
    }
    for (int i = start; i < n; ++i) {
      ans = max(ans, dp2(i,d-abs(start-i)));
    }
  } else {
    if (start == 0) { //Subtask 2.
      vector<int> cnt(101,0);
      for (int i = 0; i < n; ++i) {
        cnt[a[i]]++;

        int rem = d-i;
        long long r = 0;
        for (int j = 100; j >= 1 && rem >= 1; --j) {
          if (cnt[j] >= rem) {
            r += (1LL*rem*j);
            rem = 0;
          } else {
            r += (1LL*cnt[j]*j);
            rem -= cnt[j];
          }
        }

        ans = max(ans, r);
      }
    } else {
      assert(false); // Subtask 4.
    }
  }
  return ans;
}

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