Submission #879227

#	Time	Username	Problem	Language	Result	Execution time	Memory
879227		12345678	Triple Jump (JOI19_jumps)	C++17	5 / 100	21 ms	34396 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;
int n, a[nx], mx[nx][nx], dp[nx][nx], q, l, r;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i], mx[i][i]=a[i];
    for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++) mx[i][j]=max(mx[i][j-1], a[j]);
    for (int k=2; k<=n; k++) for (int i=1; i<=n; i++) dp[i][i+k]=max({dp[i][i+k-1], dp[i+1][i+k], a[i]+a[i+k]+mx[i+1][(i+i+k)/2]});
    cin>>q;
    while (q--) cin>>l>>r, cout<<dp[l][r]<<'\n';
}

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