oj.uz

Submission #570630

# Submission time Handle Problem Language Result Execution time Memory
570630 2022-05-30T19:39:09 Z MohammadAghil Triple Jump (JOI19_jumps) C++14
46 / 100
 594 ms 524288 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 = 5e5 + 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';
     }
}

template<class T> struct Rmq{
     vector<vector<T>> rmq;
     vector<int> lgg;
     T comb(T a, T b){
          return max(a, b);
     }
     Rmq(vector<T> a){
          int n = sz(a);
          lgg.resize(n + 1);
          rep(i,2,n + 1) lgg[i] = lgg[i>>1] + 1;
          rmq.assign(lgg[n] + 1, vector<T>(n));
          rmq[0] = a;
          rep(i,1,lgg[n] + 1){
               rep(j,0,n-(1<<i)+1){
                    rmq[i][j] = comb(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
               }
          }
     }
     T get(int l, int r){ // 0-base [l, r]
          int g = lgg[r - l + 1];
          return comb(rmq[g][l], rmq[g][r - (1<<g) + 1]);
     }
};

void slv3(){
     int l, r; cin >> l >> r; l--, r--, n = r - l + 1;
     vector<int> b(a + l, a + r + 1); 
     Rmq<int> rmq(b);
     auto get_max = [&](int l, int r){
          if(l > r || r < 0) return -1;
          l = max(0, l), r = min(r, n-1);
          return rmq.get(l, r);
     };
     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(int(log2(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 0 ms 212 KB Output is correct
2 Correct 1 ms 468 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 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 468 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 580 ms 397128 KB Output is correct
12 Correct 587 ms 397036 KB Output is correct
13 Correct 585 ms 397124 KB Output is correct
14 Correct 577 ms 397260 KB Output is correct
15 Correct 574 ms 397168 KB Output is correct
16 Correct 594 ms 396628 KB Output is correct
17 Correct 587 ms 396492 KB Output is correct
18 Correct 593 ms 396524 KB Output is correct
19 Correct 591 ms 397132 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 19148 KB Output is correct
2 Correct 52 ms 19080 KB Output is correct
3 Correct 41 ms 19128 KB Output is correct
4 Correct 69 ms 19180 KB Output is correct
5 Correct 69 ms 19112 KB Output is correct
6 Correct 65 ms 19156 KB Output is correct
7 Correct 58 ms 19072 KB Output is correct
8 Correct 59 ms 19156 KB Output is correct
9 Correct 54 ms 19156 KB Output is correct

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 468 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 580 ms 397128 KB Output is correct
12 Correct 587 ms 397036 KB Output is correct
13 Correct 585 ms 397124 KB Output is correct
14 Correct 577 ms 397260 KB Output is correct
15 Correct 574 ms 397168 KB Output is correct
16 Correct 594 ms 396628 KB Output is correct
17 Correct 587 ms 396492 KB Output is correct
18 Correct 593 ms 396524 KB Output is correct
19 Correct 591 ms 397132 KB Output is correct
20 Correct 65 ms 19148 KB Output is correct
21 Correct 52 ms 19080 KB Output is correct
22 Correct 41 ms 19128 KB Output is correct
23 Correct 69 ms 19180 KB Output is correct
24 Correct 69 ms 19112 KB Output is correct
25 Correct 65 ms 19156 KB Output is correct
26 Correct 58 ms 19072 KB Output is correct
27 Correct 59 ms 19156 KB Output is correct
28 Correct 54 ms 19156 KB Output is correct
29 Runtime error 250 ms 524288 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -