ahamed210

Timus_maximum

Dec 3rd, 2021
735
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef int l;
  4. typedef long long int ll;
  5. #define loop(a, b) for(int i = a; i < b; i++)
  6.  
  7. l seq[1000002];
  8. void precal(){
  9.     seq[0] = 0; seq[1] = 1;
  10.     seq[2] = 1; seq[3] = 2;
  11.     for(l i = 4; i <= 1000000; i++){
  12.         if(i&1){
  13.             l j = (i>>1);
  14.             seq[i] = seq[j] + seq[j+1];
  15.         }else seq[i] = seq[(i>>1)];
  16.     }
  17. }
  18.  
  19. l max_seq[1000002];
  20. void precal1(){
  21.     max_seq[0] = 0; max_seq[1] = 1;
  22.     max_seq[2] = 1; max_seq[3] = 2;
  23.     l ma = 2;
  24.     for(l i = 4; i <= 1000000; i++){
  25.         if(seq[i] > ma){
  26.             max_seq[i] = seq[i];
  27.             ma = seq[i];
  28.         }else max_seq[i] = ma;
  29.     }
  30. }
  31.  
  32. int main()
  33. {
  34.     run();
  35.     precal();
  36.     precal1();
  37.     l n;while(cin >> n && n){
  38.         cout << max_seq[n] << endl;
  39.     }
  40.     return 0;
  41. }
RAW Paste Data