fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <set>
  7. #include <string>
  8. #include <deque>
  9. #include <fstream>
  10. #include <cctype>
  11. #include <cstring>
  12. #include <cstdio>
  13. #define DN 500005
  14. #define LL long long
  15. using namespace std;
  16.  
  17. typedef pair<int,int> per;
  18.  
  19. int n,k,bst[DN];
  20. char c[10],c1[DN],c2[DN];
  21. deque<int> ind[26];
  22.  
  23.  
  24. int fst(char s) {
  25.     return s-'a';
  26. }
  27.  
  28. int r=1;
  29.  
  30. int main() {
  31.   freopen("raci.in","r",stdin);
  32.   freopen("raci.out","w",stdout);
  33.   scanf("%d %d",&n,&k);
  34.   for(int i=0; i<n; ++i) {
  35.     scanf("%s",c);
  36.     c1[i]=c[0];
  37.     c2[i]=c[strlen(c)-1];
  38.   }
  39.   for(int i=0; i<n; ++i) {
  40.     int cc=fst(c1[i]);
  41.     for(;!ind[cc].empty() && i-ind[cc].front()>k; ind[cc].pop_front());
  42.     if(!ind[cc].empty()) bst[i]=bst[ind[cc].front()]+1;
  43.     else bst[i]=1;
  44.     r=max(r,bst[i]);
  45.     cc=fst(c2[i]);
  46.  
  47.     for(;!ind[cc].empty() && bst[i]>bst[ind[cc].back()];ind[cc].pop_back());
  48.     ind[cc].push_back(i);
  49.   }
  50.   printf("%d",r);
  51.   return 0;
  52. }
Success #stdin #stdout 0s 6356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vsYPYC
language:
C++14 (gcc 8.3)
created:
9 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!