oj.uz

Submission #714517

# Submission time Handle Problem Language Result Execution time Memory
714517 2023-03-24T21:21:42 Z MohammadAghil Candies (JOI18_candies) C++17
100 / 100
 939 ms 13700 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #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) begin(x), end(x)
             #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...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 2e5 + 5, sq = 400, ln = maxn/sq + 5, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

int a[maxn];

vector<ll> comb(vector<ll> a, vector<ll> b){
     vector<ll> res(sz(a) + sz(b) - 1);
     rep(i,0,sz(res)){
          int l = max(0, i - sz(b) + 1);
          int r = min(sz(a)-1, i) + 1;
          auto get = [&](int x){
               return a[x] + b[i - x];
          };
          while(l + 1 < r){
               int mid = (l + r)>>1;
               ll w = get(mid) - get(mid-1);
               if(w > 0) l = mid;
               else r = mid;
          }
          res[i] = get(l);
     }
     return res;
}

vector<vector<vector<ll>>> slv(int l, int r){
     if(l + 1 == r){
          return {{{0, -inf}, {-inf, -inf}}, {{-inf, -inf}, {-inf, a[l]}}};
     }
     int mid = (l + r)>>1;
     auto resl = slv(l, mid), resr = slv(mid, r);
     int len = (r - l + 1)/2 + 1;
     vector<vector<vector<ll>>> res(2, vector<vector<ll>>(2));
     rep(i,0,2){
          rep(j,0,2){
               res[i][j] = comb(resl[i][0], resr[0][j]);
               rep(t,0,2){
                    vector<ll> tmp = comb(resl[i][t], resr[t^1][j]);
                    rep(k,0,sz(tmp)) res[i][j][k] = max(res[i][j][k], tmp[k]); 
               }
               res[i][j].resize(len);
          }
     }
     return res;
}

int main(){ IOS();
     int n; cin >> n;
     rep(i,0,n) cin >> a[i];
     auto res = slv(0, n);
     vector<ll> ans = res[0][0];
     rep(i,0,2) rep(j,0,2){
          rep(k,0,sz(ans)) ans[k] = max(ans[k], res[i][j][k]);
     }
     rep(i,1,((n+1)>>1)+1){
          cout << ans[i] << '\n';
     }
     return 0-0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 6 ms 416 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 7 ms 408 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 7 ms 412 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 6 ms 468 KB Output is correct
20 Correct 6 ms 468 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 6 ms 416 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 7 ms 408 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 6 ms 468 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 7 ms 412 KB Output is correct
18 Correct 6 ms 468 KB Output is correct
19 Correct 6 ms 468 KB Output is correct
20 Correct 6 ms 468 KB Output is correct
21 Correct 784 ms 13404 KB Output is correct
22 Correct 799 ms 13516 KB Output is correct
23 Correct 781 ms 13504 KB Output is correct
24 Correct 803 ms 13368 KB Output is correct
25 Correct 798 ms 13348 KB Output is correct
26 Correct 794 ms 13396 KB Output is correct
27 Correct 871 ms 13444 KB Output is correct
28 Correct 895 ms 13544 KB Output is correct
29 Correct 896 ms 13584 KB Output is correct
30 Correct 910 ms 13448 KB Output is correct
31 Correct 891 ms 13552 KB Output is correct
32 Correct 906 ms 13476 KB Output is correct
33 Correct 860 ms 13252 KB Output is correct
34 Correct 879 ms 13252 KB Output is correct
35 Correct 863 ms 13492 KB Output is correct
36 Correct 764 ms 13596 KB Output is correct
37 Correct 756 ms 13700 KB Output is correct
38 Correct 768 ms 13440 KB Output is correct
39 Correct 802 ms 13520 KB Output is correct
40 Correct 805 ms 13260 KB Output is correct
41 Correct 812 ms 13324 KB Output is correct
42 Correct 886 ms 13528 KB Output is correct
43 Correct 889 ms 13476 KB Output is correct
44 Correct 880 ms 13652 KB Output is correct
45 Correct 894 ms 13696 KB Output is correct
46 Correct 939 ms 13532 KB Output is correct
47 Correct 887 ms 13492 KB Output is correct
48 Correct 863 ms 13244 KB Output is correct
49 Correct 861 ms 13348 KB Output is correct
50 Correct 861 ms 13208 KB Output is correct