Submission #811763

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
811763	2023-08-07 05:44:26	vjudge1	Triple Jump (JOI19_jumps)	C++14	19 / 100	520 ms	143156 KiB

jumps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 5e5, NS = 5e3 ;
int n, q, d[N + 1], dp[NS + 1][NS + 1], mx[NS + 1][NS + 1] ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
        cin >> d[i] ;
    cin >> q ;
    if(n <= 5000)
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = i ; j <= n ; j++)
                mx[i][j] = max(mx[i][j - 1], d[j]) ;
        for(int i = 1 ; i <= n - 2 ; i++)
            dp[i][i + 2] = d[i] + d[i + 1] + d[i + 2] ;
        for(int ln = 4 ; ln <= n ; ln++)
            for(int j = 1 ; j <= n - ln + 1 ; j++)
                dp[j][j + ln - 1] = max({dp[j][j + ln - 2], dp[j + 1][j + ln - 1], d[j] + d[j + ln - 1] + mx[j + 1][j + (ln - 1) / 2]}) ;
        while(q--)
        {
            int l, r ;
            cin >> l >> r ;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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