Submission #1096985

#TimeUsernameProblemLanguageResultExecution timeMemory
1096985TameTriple Jump (JOI19_jumps)C++14
5 / 100
61 ms24772 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...