oj.uz

Submission #570629

# Submission time Handle Problem Language Result Execution time Memory
570629 2022-05-30T19:34:31 Z MohammadAghil Triple Jump (JOI19_jumps) C++14
46 / 100
 634 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';
     }
}

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 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 1 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 596 ms 397180 KB Output is correct
12 Correct 581 ms 397040 KB Output is correct
13 Correct 607 ms 397240 KB Output is correct
14 Correct 593 ms 397088 KB Output is correct
15 Correct 634 ms 397092 KB Output is correct
16 Correct 621 ms 396528 KB Output is correct
17 Correct 611 ms 396448 KB Output is correct
18 Correct 606 ms 396472 KB Output is correct
19 Correct 633 ms 397020 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 29288 KB Output is correct
2 Correct 155 ms 29428 KB Output is correct
3 Correct 104 ms 29544 KB Output is correct
4 Correct 129 ms 29496 KB Output is correct
5 Correct 133 ms 29464 KB Output is correct
6 Correct 139 ms 28748 KB Output is correct
7 Correct 134 ms 28940 KB Output is correct
8 Correct 127 ms 28712 KB Output is correct
9 Correct 133 ms 29052 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 596 ms 397180 KB Output is correct
12 Correct 581 ms 397040 KB Output is correct
13 Correct 607 ms 397240 KB Output is correct
14 Correct 593 ms 397088 KB Output is correct
15 Correct 634 ms 397092 KB Output is correct
16 Correct 621 ms 396528 KB Output is correct
17 Correct 611 ms 396448 KB Output is correct
18 Correct 606 ms 396472 KB Output is correct
19 Correct 633 ms 397020 KB Output is correct
20 Correct 161 ms 29288 KB Output is correct
21 Correct 155 ms 29428 KB Output is correct
22 Correct 104 ms 29544 KB Output is correct
23 Correct 129 ms 29496 KB Output is correct
24 Correct 133 ms 29464 KB Output is correct
25 Correct 139 ms 28748 KB Output is correct
26 Correct 134 ms 28940 KB Output is correct
27 Correct 127 ms 28712 KB Output is correct
28 Correct 133 ms 29052 KB Output is correct
29 Runtime error 273 ms 524288 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -