Submission #441483

#	Time	Username	Problem	Language	Result	Execution time	Memory
441483		peijar	Triple Jump (JOI19_jumps)	C++17	27 / 100	30 ms	9392 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> strengh(N);
  for (int i = 0; i < N; ++i)
    cin >> strengh[i];
  vector<int> suffix(N);
  for (int i = N - 1; i >= 0; --i) {
    suffix[i] = strengh[i];
    if (i + 1 < N)
      suffix[i] = max(suffix[i], suffix[i + 1]);
  }
  vector<pair<int, int>> curRecords;
  int ret = 0;
  for (int b = 1; b < N; ++b) {
    while (!curRecords.empty() and curRecords.back().first <= strengh[b - 1])
      curRecords.pop_back();
    curRecords.emplace_back(strengh[b - 1], b - 1);
    for (int i = (int)curRecords.size() - 1; i >= 0; --i) {
      auto [val, pos] = curRecords[i];
      if (b - pos + b < N)
        ret = max(ret, val + strengh[b] + suffix[2 * b - pos]);
      if (val >= strengh[b])
        break;
    }
  }
  cout << ret << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54