제출 #570630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570630		MohammadAghil	3단 점프 (JOI19_jumps)	C++14	46 / 100	594 ms	524288 KiB

jumps

      #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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54