Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("gard.in");
  4. ofstream fout("gard.out");
  5. int n,i,j,lg,sc,fra,frr,frv,altsc,ci,lgmax=999999;
  6. char sir[100002];
  7. int fr[100002][4];
  8. int main()
  9. {
  10. fin>>n;
  11. sc=n/3;
  12. fin>>sir[0];
  13. if(sir[0]=='R')
  14. fr[0][1]=1;
  15. else if(sir[0]=='V')
  16. fr[0][2]=1;
  17. else fr[0][0]=1;
  18. for(i=1; i<n; ++i)
  19. {
  20. fr[i][1]=fr[i-1][1];
  21. fr[i][0]=fr[i-1][0];
  22. fr[i][2]=fr[i-1][2];
  23. fin>>sir[i];
  24. if(sir[i]=='R')
  25. fr[i][1]++;
  26. else if(sir[i]=='V')
  27. fr[i][2]++;
  28. else fr[i][0]++;
  29. }
  30. //fout<<fr[n-1][0]<<" "<<fr[n-1][1]<<" "<<fr[n-1][2]<<'\n';
  31. if(fr[n-1][0]==sc && fr[n-1][1]==sc && fr[n-1][2]==sc)
  32. {
  33. fout<<0;
  34. return 0;
  35. }
  36. altsc=max(max(fr[n-1][0],sc)-min(fr[n-1][0],sc),max(max(fr[n-1][1],sc)-min(fr[n-1][1],sc),max(fr[n-1][2],sc)-min(fr[n-1][2],sc)));
  37. //fout<<altsc;
  38. for(i=0;i<n;++i)
  39. {
  40. if(j==0)
  41. j=i;
  42. ci=i;
  43. while((fr[n-1][0]-(fr[j][0]-fr[i-1][0])>sc || fr[n-1][1] - (fr[j][1]-fr[i-1][1])>sc || fr[n-1][2] - (fr[j][2]-fr[i-1][2])>sc) && j<n)
  44. j++;
  45. if(j==n)
  46. continue;
  47. while((fr[n-1][0]-(fr[j][0]-fr[ci-1][0])<=sc && fr[n-1][1] - (fr[j][1]-fr[ci-1][1])<=sc && fr[n-1][2] - (fr[j][2]-fr[ci-1][2])<=sc) && ci<j)
  48. ci++;
  49. ci--;
  50. lgmax=min(lgmax,j-ci+1);
  51. i=max(i,ci);
  52. }
  53. fout<<lgmax;
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement