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. #define DN 500005
  11. #define LL long long
  12. using namespace std;
  13.  
  14. typedef pair<int,int> per;
  15.  
  16. int n,k,bst[DN];
  17. string cuv[DN];
  18. deque<int> ind[26];
  19.  
  20. int lst(string s) {
  21.     return s[s.size()-1]-'a';
  22. }
  23.  
  24. int fst(string s) {
  25.     return s[0]-'a';
  26. }
  27.  
  28. int r=1;
  29.  
  30. int main() {
  31.   ifstream f("raci.in");
  32.   ofstream g("raci.out");
  33.   f>>n>>k;
  34.   for(int i=0; i<n; ++i) {
  35.     string s; f>>s;
  36.     cuv[i]+=s[0];
  37.     cuv[i]+=s[s.size()-1];
  38.     //cout<<cuv[i]<<' ';
  39.     }
  40.   for(int i=0; i<n; ++i) {
  41.     int cc=fst(cuv[i]);
  42.     for(;ind[cc].size() && i-ind[cc].front()>k; ind[cc].pop_front());
  43.     if(ind[cc].size()) bst[i]=bst[ind[cc].front()]+1;
  44.     else bst[i]=1;
  45.     r=max(r,bst[i]);
  46.     cc=lst(cuv[i]);
  47.  
  48.     for(;ind[cc].size() && bst[i]>bst[ind[cc].back()];ind[cc].pop_back());
  49.     ind[cc].push_back(i);
  50.   }
  51.   g<<r;
  52.   return 0;
  53. }
Success #stdin #stdout 0s 7376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o76crl
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!