Submission #1175395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175395		_ncng.nyr	Triple Jump (JOI19_jumps)	C++20	19 / 100	282 ms	247228 KiB

jumps

#include<bits/stdc++.h>

#define int long long
#define ii pair<int, int>

using namespace std;

const int N = 5e5 + 5;

int n, q;
int a[N];
ii query[N];

namespace sub1 {
  void solve() {
    for(int i = 1; i <= q; ++i) {
      auto [l, r] = query[i];
      int res = 0;
      for(int x = l; x <= r; ++x)
        for(int y = x + 1; y <= r; ++y)
          for(int z = y + (y - x); z <= r; ++z) res = max(res, a[x] + a[y] + a[z]);

      cout << res << '\n';
    }
  }
}

namespace sub2 {
  int f[5'005][5'005], mx[5'005][5'005];

  void solve() {
    for(int i = 1; i <= n; ++i) {
      mx[i][i] = a[i];
      for(int j = i + 1; j <= n; ++j) mx[i][j] = max(mx[i][j - 1], a[j]);
    }

    for(int i = 1; i <= n; ++i)
      for(int j = i + 2; j <= n; ++j)
        f[i][j] = a[i] + a[j] + mx[i + 1][(i + j >> 1)];

    for(int i = n; i; --i)
      for(int j = i + 3; j <= n; ++j) {
        f[i][j] = max({f[i][j], f[i + 1][j], f[i][j - 1]});
        if(j - i - 1 >= 3) f[i][j] = max(f[i][j], f[i + 1][j - 1]);
      }

    for(int i = 1; i <= q; ++i) cout << f[query[i].first][query[i].second] << '\n';
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];

  cin >> q;
  for(int i = 1; i <= q; ++i) cin >> query[i].first >> query[i].second;

  if(n <= 100 && q <= 100) sub1 :: solve();
  else if(n <= 5'000) sub2 :: solve();
}

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