oj.uz

Submission #441483

# Submission time Handle Problem Language Result Execution time Memory
441483 2021-07-05T09:04:48 Z peijar Triple Jump (JOI19_jumps) C++17
27 / 100
 30 ms 9392 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5200 KB Output is correct
2 Correct 27 ms 5180 KB Output is correct
3 Correct 30 ms 9392 KB Output is correct
4 Correct 29 ms 5076 KB Output is correct
5 Correct 30 ms 5068 KB Output is correct
6 Correct 25 ms 4440 KB Output is correct
7 Correct 24 ms 4412 KB Output is correct
8 Correct 24 ms 4444 KB Output is correct
9 Correct 26 ms 4676 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -