oj.uz

Submission #570628

# Submission time Handle Problem Language Result Execution time Memory
570628 2022-05-30T19:33:49 Z MohammadAghil Triple Jump (JOI19_jumps) C++14
19 / 100
 889 ms 402004 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 = 19, 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 a[maxn]; 
int n, q;

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';
     }
}

void slv3(){
     int l, r; cin >> l >> r; l--, r--, n = r - l + 1;
     vector<int> b(a + l, a + r + 1); 
     
     vector<vector<int>> rmq(n, vector<int>(lg));
     vector<int> lgg(n + 1);
     rep(i,2,n+1) lgg[i] = lgg[i>>1] + 1;
     rep(i,0,n) rmq[i][0] = b[i];
     rep(j,1,lg) rep(i,0,n-(1<<j)+1) rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
     auto get_max = [&](int l, int r){
          if(r < 0 || l > r) return -1;
          l = max(l, 0), r = min(n-1, r);
          int k = lgg[r-l+1];
          return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
     };

     auto clc = [&](int i){
          ll res = -inf;

          // right
          rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(j-(i-j),j-1));

          // center
          rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(i+(i-j),n-1));

          // left
          rep(j,i+1,n) res = max(res, 1ll*b[i] + b[j] + get_max(j+(j-i),n-1)); 

          return res;
     };
     
     vector<int> c(n); iota(all(c), 0), sort(all(c), [&](int i, int j){ return b[i] > b[j]; }); 
     ll ans = 0; int g = min(lgg[n]+3, n);
     rep(i,0,g){
          ans = max(ans, clc(c[i]));
     }
     cout << ans << '\n';
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 452 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 452 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 1 ms 212 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 452 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 452 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 616 ms 401868 KB Output is correct
12 Correct 614 ms 401800 KB Output is correct
13 Correct 618 ms 401724 KB Output is correct
14 Correct 889 ms 401876 KB Output is correct
15 Correct 613 ms 402004 KB Output is correct
16 Correct 619 ms 401104 KB Output is correct
17 Correct 589 ms 401104 KB Output is correct
18 Correct 604 ms 401136 KB Output is correct
19 Correct 603 ms 401868 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 1 ms 212 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 452 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 452 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 616 ms 401868 KB Output is correct
12 Correct 614 ms 401800 KB Output is correct
13 Correct 618 ms 401724 KB Output is correct
14 Correct 889 ms 401876 KB Output is correct
15 Correct 613 ms 402004 KB Output is correct
16 Correct 619 ms 401104 KB Output is correct
17 Correct 589 ms 401104 KB Output is correct
18 Correct 604 ms 401136 KB Output is correct
19 Correct 603 ms 401868 KB Output is correct
20 Runtime error 2 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -