oj.uz

Submission #1096985

# Submission time Handle Problem Language Result Execution time Memory
1096985 2024-10-05T15:42:31 Z Tame Triple Jump (JOI19_jumps) C++14
5 / 100
 61 ms 24772 KB 
#include <bits/stdc++.h>
#define pu push
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 500010;
const int inf = (int)1e9+7;
const ll INF = (ll)1e18;
using namespace std;

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

int nLength, nQuery;
int a[MAX_SIZE];

vector<pair<int,int>>queries, tmp;

struct SegmentTree{
    int n; vector<pair<int,int>>st;
    SegmentTree(int _n=0){
        n=_n; st.resize(4*n+5);
    }
    void build(int id, int l, int r){
        if (l==r){
            st[id]=make_pair(a[l], l); return;
        }
        int m = (l+r)>>1;
        build(2*id,l,m); build(2*id+1,m+1,r);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    void update(int id, int l, int r, int v, int k){
        if (r<v || v<l) return;
        if (l==r){
            st[id].fi=k; return;
        }
        int m = (l+r)>>1;
        update(2*id, l, m, v, k); update(2*id+1, m+1, r, v, k);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    pair<int,int>get(int id, int l, int r, int u, int v){
        if (r<u || v<l){
            pair<int,int>e = make_pair(-inf, -inf);
            return e;
        }
        if (l>=u && r<=v) return st[id];
        int m = (l+r)>>1;
        pair<int,int>x=get(2*id, l, m, u, v), y=get(2*id+1, m+1, r, u, v);
        if (x.fi > y.fi) return x;
        return y;
    }
};
SegmentTree IT(MAX_SIZE);

void init(){
    cin>>nLength;
    for (int i=1; i<=nLength; i++){
        cin>>a[i];
    }
    cin>>nQuery;
    for (int i=1; i<=nQuery; i++){
        int l, r; cin>>l>>r;
        queries.pb(make_pair(l, r));
    }
}

bool cmp(const pair<int,int>&x, pair<int,int>&y){
    return x.se < y.se;
}

namespace subtask1{
    bool check(){
        return max(nLength, nQuery)<=100;
    }

    ll board[105][105];

    void solve(){
        memset(board, -0x3f, sizeof(board));
        for (int i=1; i<=nLength; i++){
            for (int j=i+1; j<=nLength; j++){
                for (int k=i+1; k<j; k++){
                    if (abs(k-i) <= abs(j-k)) maximize(board[i][j], a[i]+a[j]+a[k]);
                }
            }
        }
        for (int i=0; i<(int)queries.size(); i++){
            int l=queries[i].fi, r=queries[i].se; ll ans=0;
            for (int u=l; u<=r; u++){
                for (int v=u; v<=r; v++){
                    maximize(ans, board[u][v]);
                }
            }
            cout<<ans<<"\n";
        }
    }
}

void ilovesunshine(){
    init();

    if (subtask1::check()) return subtask1::solve();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ilovesunshine();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 8 ms 15964 KB Output is correct
3 Correct 7 ms 16004 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 8 ms 15964 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 8 ms 16208 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 8 ms 15964 KB Output is correct
3 Correct 7 ms 16004 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 8 ms 15964 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 8 ms 16208 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct
11 Incorrect 61 ms 24772 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 8 ms 15964 KB Output is correct
3 Correct 7 ms 16004 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 8 ms 15964 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 8 ms 16208 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct
11 Incorrect 61 ms 24772 KB Output isn't correct
12 Halted 0 ms 0 KB -