oj.uz

Submission #242234

# Submission time Handle Problem Language Result Execution time Memory
242234 2020-06-27T07:10:07 Z errorgorn Triple Jump (JOI19_jumps) C++14
19 / 100
 504 ms 128120 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct sparse{
    long long ST[100005][20];

    sparse(){}

    long long func(long long i,long long j){return max(i,j);}    
                                                   ///change this

    void build(int n,long long arr[]){ ///build sparse table
        for (int x=0;x<n;x++){
            ST[x][0]=arr[x];
        }
        int j=1,logj=1;
        while (j<=(n>>1)){
            for (int x=0;x<=(n-(j<<1));x++){
                ST[x][logj]=func(ST[x][logj-1],ST[x+j][logj-1]);
            }
            j<<=1;
            logj++;
        }
    }
    long long query(int i, int j){ ///in range [i,j]
        j=j-i+1;
        int row=31-__builtin_clz(j);
        j-=1<<row;
        return func(ST[i][row],ST[i+j][row]);
    }
} ST;


int n,q;
ll arr[200005];

ll memo[5005][5005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x];
	
	ST.build(n,arr);
	
	rep(x,2,n){
		rep(l,0,n-x){
			int r=l+x;
			//cout<<l<<" "<<r<<endl;
						
			memo[l][r]=max(memo[l+1][r],memo[l][r-1]);
			
			memo[l][r]=max(memo[l][r],arr[l]+arr[r]+ST.query(l+1,l+x/2));
		}
	}
	
	cin>>q;
	int l,r;
	while (q--){
		cin>>l>>r;
		l--,r--;
		cout<<memo[l][r]<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 504 ms 127928 KB Output is correct
12 Correct 497 ms 127736 KB Output is correct
13 Correct 503 ms 127736 KB Output is correct
14 Correct 484 ms 127992 KB Output is correct
15 Correct 485 ms 128120 KB Output is correct
16 Correct 495 ms 127208 KB Output is correct
17 Correct 481 ms 127096 KB Output is correct
18 Correct 473 ms 127100 KB Output is correct
19 Correct 480 ms 127736 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 37240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 504 ms 127928 KB Output is correct
12 Correct 497 ms 127736 KB Output is correct
13 Correct 503 ms 127736 KB Output is correct
14 Correct 484 ms 127992 KB Output is correct
15 Correct 485 ms 128120 KB Output is correct
16 Correct 495 ms 127208 KB Output is correct
17 Correct 481 ms 127096 KB Output is correct
18 Correct 473 ms 127100 KB Output is correct
19 Correct 480 ms 127736 KB Output is correct
20 Runtime error 64 ms 37240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -