fork download 
  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. #define PII pair<int,int>
  4. #define PIL pair<int,LL>
  5. #define PLI pair<LL,int>
  6. #define PIII pair<int,PII>
  7. #define PLL pair<LL,LL>
  8. #define PLII pair<LL,PII>
  9. #define VI vector<int>
  10. #define VVI vector<VI>
  11. #define VL vector<LL>
  12. #define VVL vector<VL>
  13. #define VPII vector<PII>
  14. #define FF first
  15. #define SS second
  16. #define MP make_pair
  17. #define PB push_back
  18. #define sqr(x) ((x) * (x))
  19. #define all(x) x.begin(),x.end()
  20. #define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
  21. #define mset(a,v) memset(a,v,sizeof(a))
  22. #define setp(x) cout<<fixed<<setprecision(x)
  23. #define EPS 0.00000000001
  24. #define PI acos(-1)
  25. #define loop(i,b,n) for(int i=b;i<n;++i)
  26. #define rev_loop(i,b,n) for(int i=b;i>=n;--i)
  27. using namespace std;
  28.  
  29. const int MOD = 1e9 + 7;
  30. const LL MX = 1e9;
  31. const LL INF = 1e9;
  32.  
  33. void solve()
  34. {
  35.     int n,m;
  36.     cin>>n>>m;
  37.     int N = n+m+1, a[N];
  38.     loop(i,0,n) cin>>a[i];
  39.     a[n] = INF;
  40.     loop(i,n+1,N) cin>>a[i];
  41.  
  42.     VI z(N,0);
  43.     LL ps[n+1] = {0};
  44.  
  45.     for (int i = 1, l = 0, r = 0; i < N; ++i)
  46.     {
  47.         if (i <= r) z[i] = min (r - i + 1, z[i - l]);
  48.         while (i + z[i] < N && a[z[i]] == a[i + z[i]]) ++z[i];
  49.         if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  50.  
  51.         if(i > n) ++ps[z[i]];
  52.     }
  53.  
  54.     LL mx = -1, mxl = 0;
  55.     rev_loop(i,n,1)
  56.     {
  57.         LL len = i;
  58.         if(i != n) ps[i] += ps[i+1];
  59.         if(mx < (i * ps[i])) {mx = (i * ps[i]); mxl = i;}
  60.     }
  61.  
  62.     cout<<mxl<<'\n';
  63. }
  64.  
  65. int main()
  66. {
  67.     //ofstream out("output.txt");
  68.     //ifstream in("input.txt");
  69.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  70.  
  71.     int t;
  72.     cin>>t;
  73.  
  74.     while(t--)
  75.     {
  76.         solve();
  77.     }
  78.  
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 5416KB
comments (?)
stdin 
2
3 6
1 1 2
1 3 1 1 1 2
4 10
3 1 2 5
3 1 2 3 1 2 3 1 2 7
stdout 
2
3
https://ideone.com/oQPKGZ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!