fork download
copy 
  1. // Src : Vux2Code
  2. /* Note :
  3.  
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef int ll;
  11. typedef long double ld;
  12. typedef pair<ll, ll> pll;
  13.  
  14. #define fi first
  15. #define se second
  16.  
  17. #define pusb push_back
  18. #define popb pop_back
  19. #define pusf push_front
  20. #define popf pop_front
  21.  
  22. #define vec3d vector<vector<vector<ll>>>
  23. #define vec2d vector<vector<ll>>
  24. #define vec1d vector<ll>
  25. vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
  26. vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}
  27.  
  28. template<typename T>
  29. using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
  30.  
  31. #define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
  32. #define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
  33. #define foreach(i, j) for (ll i : (j))
  34.  
  35. #define all(a) (a).begin (), (a). end ()
  36. #define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())
  37.  
  38. const ll maxN = 2e3 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7, maxA = 2e3 + 5;
  39.  
  40. void maxi(ll &x, ll y) { x = max(x, y); }
  41. void mini(ll &x, ll y) { x = min(x, y); }
  42.  
  43. /* ---------HASHING-------- */
  44. const ll base = 31, mod2 = 1e9 + 9;
  45.  
  46. /* ---------BITMASK-------- */
  47. // ll count(ll x) { return __builtin_popcountll(x); }
  48. // ll fst(ll x) { return 63 - __builtin_clzll(x); }
  49. // ll last(ll x) { return __builtin_ctzll(x); }
  50. // bool bit(ll x, ll y) { return ((x >> y) & 1); }
  51.  
  52. ll t = 1;
  53.  
  54. ll n, cm [maxA] [maxA], f [maxA], atmp [maxA], m;
  55. char a [maxA];
  56. pll vec [maxN * maxN];
  57.  
  58. bool cmp(pll x, pll y){
  59.     ll lx = x.second - x.first;
  60.     ll ly = y.second - y.first;
  61.     if(lx != ly) return lx < ly;
  62.     int i = x.first, j = y.first;
  63.     int common = cm[i][j];
  64.     if(common > lx) return x. fi < y. fi;
  65.     return a[i + common] < a[j + common];
  66. }
  67.  
  68. bool cmp2(pll x, pll y){
  69.     ll lx = x.second - x.first;
  70.     ll ly = y.second - y.first;
  71.     return lx == ly && cm[x.first][y.first] > lx;
  72. }
  73. void update(int i, ll v){
  74.     for(; i <= n; i += i & -i)
  75.         f[i] = max(f[i], v);
  76. }
  77.  
  78. ll get(int i){
  79.     ll r = 0;
  80.     for(; i > 0; i -= i & -i)
  81.         r = max(r, f[i]);
  82.     return r;
  83. }
  84.  
  85. void solve() {
  86.     cin >> n;
  87.     forinc (i, 1, n)cin >> a[i];
  88.     fordec (i, n, 1) fordec (j, n, 1) {
  89.         if(a[i] == a[j]) cm[i][j] = cm[i+1][j+1] + 1;
  90.         else cm[i][j] = 0;
  91.     }
  92.     for(int i = 1; i <= n; i++){
  93.         if(a[i] == '0'){
  94.             vec [m ++] = {i, i};
  95.             continue;
  96.         }
  97.         for(int j = i; j <= n; j++){
  98.             vec [m ++] = {i, j};
  99.         }
  100.     }
  101.     sort(vec, vec + m, cmp);
  102.     fill (f, f + maxA, 0);
  103.     ll ans = 0;
  104.     for(int i = 0; i < m; i ++){
  105.         int L = vec[i].first;
  106.         ll atmp = get(L-1) + 1;
  107.         ans = max(ans, atmp);
  108.         int R = vec[i].second;
  109.         update(R, atmp);
  110.     }
  111.     cout << ans << "\n";
  112. }
  113.  
  114. int main() {
  115.     ios::sync_with_stdio(0);
  116.     cin.tie(0);
  117.     cout.tie(0);
  118.  #define TASK "catdayso"
  119.  if (fopen (TASK".inp", "r")) {
  120.      freopen (TASK".inp", "r", stdin);
  121.      freopen (TASK".out", "w", stdout);
  122.  }
  123.     // cin >> t;
  124.     while (t--) solve();
  125. }
  126.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xsOlBF
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!