Submission #258438

#	Time	Username	Problem	Language	Result	Execution time	Memory
258438		sandoval	Holiday (IOI14_holiday)	C++11	47 / 100	86 ms	1024 KiB

holiday

#include <bits/stdc++.h>

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

constexpr int MAXN = 5+3000;
constexpr int MAXD = 5+2*MAXN+(MAXN/2);

long long dp[2][2][MAXD];

long long findMaxAttraction(int n, int start, int days, int attraction[]) {
  long long res = 0;
  if (n <= 3000) { // Subtask 1,3.
    for (int i = n; i >= 0; --i) {
      int b = i&1, l = b^1;
      for (int d = 0; d < MAXD; ++d) {
        long long& ans = dp[0][b][d] = 0;
        if (i >= n || d == 0) continue;
        if (d == 1) {
          ans = max(dp[0][l][d-1], 1LL*attraction[i]);
        } else {
          assert(d >= 2);
          ans = max(dp[0][l][d-2]+attraction[i], dp[0][l][d-1]);
        }
      }
      if (i <= start && days-abs(i-start) >= 0) {
        res = max(res, dp[0][b][days-abs(i-start)]);
      }
    }

    for (int i = 0; i < n; ++i) {
      int b = i&1, l = b^1;
      for (int d = 0; d < MAXD; ++d) {
        long long& ans = dp[1][b][d] = 0;
        if (d == 0) continue;
        if (i == 0) {
          ans = attraction[i];
          continue;
        }

        if (d == 1) {
          ans = max(dp[1][l][d-1], 1LL*attraction[i]);
        } else {
          assert(d >= 2);
          ans = max(dp[1][l][d-2]+attraction[i], dp[1][l][d-1]);
        }
      }
      if (i >= start && days-abs(i-start) >= 0) {
        res = max(res, dp[1][b][days-abs(i-start)]);
      }
    }
  } else {
    if (start == 0) { //Subtask 2.
      vector<int> cnt(101,0);
      for (int i = 0; i < n; ++i) {
        cnt[attraction[i]]++;

        int rem = days-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];
          }
        }

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

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