Submission #1084919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084919		Phuoc	Triple Jump (JOI19_jumps)	C++14	5 / 100	47 ms	9084 KiB

jumps

#include <bits/stdc++.h>


using namespace std;

#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define el '\n'
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define fi first
#define se second


template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b){a = b; return true;} return false;
    }

template <class T1, class T2>   
    bool maximize(T1 &a, T2 b) {
        if(a < b){a = b; return true;} return false;
    }

const int MAX = 500500;
const ll INF = (ll)1e18 + 10LL;

int n, q;
long long a[MAX];
pair <int, int> queries[MAX];

void init (void) {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    for(int i = 1; i <= q; i++) cin >> queries[i].fi >> queries[i].se;
}

namespace subtask1 {
    ll f[111][111];

    void solve (void) {
        // memset(f, 0x3f, sizeof f);
        for(int i = 1; i <= n; i++) for(int j = i + 2; j <= n; j++) {
            for(int k = i + 1; k < j; k++) {
                if(k - i <= j - k)  maximize(f[i][j], a[i] + a[j] + a[k]);
            }
        }

        for(int i = 1; i <= q; i++) {
            int l = queries[i].fi, r = queries[i].se;

            ll ans = 0;
            for(int i = l; i <= n; i++) for(int j = i + 2; j <= r; j++) maximize(ans, f[i][j]);
            cout << ans << el;
        }
    }
}

namespace subtask2 {
    ll f[5010][5010], max_a[5010][5010], g[5010][5010];

    void solve (void) {
        for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) maximize(max_a[i][j], a[j]);
        for(int i = 1; i <= n; i++) {
            for(int j = i + 2; j <= n; j++){
                f[i][j] = max_a[i + 1][(i + j) / 2] + a[i] + a[j];    
                g[i][j] = max(g[i][j - 1], f[i][j]);
            }
        } 

        cin >> q;
        for(int i = 1; i <= q; i++) {
            int l, r; cin >> l >> r;
            ll ans = 0;
            for(int i = l; i <= n - 2; i++) maximize(ans, g[i][r]); 
            cout << ans << el;
        }
    }
}

namespace subtask3{
    ll f[200200], g[200200];

    void solve (void) {
        ll cur = a[1];
        for(int i = 2; i <= n; i++) {
            g[i] = a[i] + cur;
            maximize(g[i], g[i - 1]);
            maximize(cur, a[i]);
        }

        ll ans = 0;

        for(int i = 3; i <= n; i++) {
            f[i] = g[(i + 1) / 2] + a[i];
            maximize(ans, f[i]);
        }

        cout << ans << el;
    }
}

void solve (void) { 
    if(n <= 100 && q <= 100) {subtask1::solve(); return;}
    // if(n <= 5000) subtask2::solve();
    if(n <= 200000 && q == 1 && queries[1].fi == 1 && queries[1].se == n) {subtask3::solve(); return;}
}

int main (void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int ntest = 1;
    srand(time(0));
    // cin >> ntest;
    while(ntest--) {
        init();
        solve();
    }
    return 0;
}

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