oj.uz

Submission #570516

# Submission time Handle Problem Language Result Execution time Memory
570516 2022-05-30T10:55:45 Z MohammadAghil Triple Jump (JOI19_jumps) C++14
19 / 100
 726 ms 401880 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
    typedef pair<long double, ll> pp;
     #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
       #define per(i,r,l) for(int i = (r); i >= (l); i--)
         #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e3 + 5, lg = 10, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} 

ll n, q, a[maxn]; 

void slv2(){
     vector<vector<ll>> mx(n, vector<ll>(n, -inf));
     rep(i,0,n){
          mx[i][i] = a[i]; 
          rep(j,i+1,n) mx[i][j] = max(mx[i][j-1], a[j]);
     }
     vector<vector<ll>> ans(n, vector<ll>(n, -inf));
     rep(l,3,n+1){
          rep(i,0,n-l+1){
               int j = i + l - 1;
               ans[i][j] = max({ans[i+1][j], ans[i][j-1], a[i] + a[j] + mx[i+1][(i+j)>>1]});
          }
     }
     while(q--){
          int l, r; cin >> l >> r;
          cout << ans[--l][--r] << '\n';
     }
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> n;
     rep(i,0,n) cin >> a[i];
     cin >> q;
     slv2();
     return 0; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 720 ms 401872 KB Output is correct
12 Correct 656 ms 401740 KB Output is correct
13 Correct 686 ms 401864 KB Output is correct
14 Correct 674 ms 401880 KB Output is correct
15 Correct 719 ms 401816 KB Output is correct
16 Correct 678 ms 401200 KB Output is correct
17 Correct 673 ms 401108 KB Output is correct
18 Correct 711 ms 401236 KB Output is correct
19 Correct 726 ms 401692 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 720 ms 401872 KB Output is correct
12 Correct 656 ms 401740 KB Output is correct
13 Correct 686 ms 401864 KB Output is correct
14 Correct 674 ms 401880 KB Output is correct
15 Correct 719 ms 401816 KB Output is correct
16 Correct 678 ms 401200 KB Output is correct
17 Correct 673 ms 401108 KB Output is correct
18 Correct 711 ms 401236 KB Output is correct
19 Correct 726 ms 401692 KB Output is correct
20 Runtime error 2 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -