oj.uz

Submission #1096661

# Submission time Handle Problem Language Result Execution time Memory
1096661 2024-10-05T00:03:10 Z HotStepBroz Triple Jump (JOI19_jumps) C++14
0 / 100
 4000 ms 4096 KB 
#include<bits/stdc++.h> 
#include "ext/pb_ds/assoc_container.hpp" 
using namespace __gnu_pbds;
using namespace std ;
typedef unsigned long long ull;
typedef long double ld;
typedef long long ll ;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FOR(i, l, r) for (ll i = l; i <= r; i++)
#define FORTYPE(type, i, l, r) for (type i = l; i <= r; i++)
#define FOD( i, l, r) for (ll i  = l; i >= r; i--)
#define _USE_MATH_DEFINES
#define fi first
#define se second
#define pb push_back
const ll N = 2e5 + 5;
const ll MOD = 1e9 + 7;
const int INF =  1e9;
const ld  PI = 3.14159265358979323846 ;


int n , a[N] , ans[1003][1003] , q , l  , r ;

main(){
    

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


    for( int i =  1 ; i <= n ; i++)
    {
        for( int j = i + 1 ; j <= n ; j++)
        {
            for( int k = i - 1 ; k >= 1 ; k--)
            {
                if( j - i >= i - k )
                {
                    ans[k][j] = max({ ans[k][j] , ans[k+1][j] , ans[k][j-1]}) ;
                    ans[k][j] = max(ans[k][j] , a[j] + a[i] + a[k]) ;
                }
            }
        }
    }
    for( int i =  1 ; i <= n ; i++)
    {
        for( int j = i + 1 ; j <= n ; j++)
        {
            for( int k = i - 1 ; k >= 1 ; k--)
            {
                if( j - i >= i - k )
                {
                    ans[k][j] = max({ ans[k][j] , ans[k+1][j] , ans[k][j-1]}) ;
                    //ans[k][j] = max(ans[k][j] , a[j] + a[i] + a[k]) ;
                }
            }
        }
    }

    cin >> q ;
    while(q--)
    {
        cin >> l >> r ;
        cout << ans[l][r] << '\n' ;
    }

}

Compilation message

jumps.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 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 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4029 ms 4096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

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