fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. long long numOfSubsequences(string s) {
  6.         int n = s.size();
  7.         long long l=0;
  8.         long long lc=0;
  9.         long long lct=0;
  10.         vector<long long> prefix_lc(n,0);
  11.         vector<long long> prefix_l(n,0);
  12.  
  13.         for(int i=0;i<n;i++){
  14.             if(s[i]=='L'){
  15.                 l++;
  16.                 prefix_l[i];
  17.  
  18.             }
  19.             else if(s[i]=='C'){
  20.                 lc=lc+l;
  21.             }
  22.             else if(s[i]=='T'){
  23.                 lct=lct+lc;
  24.             }
  25.             prefix_l[i]=l;
  26.             prefix_lc[i]=lc;
  27.         }
  28.  
  29.         vector<long long> suffix_t(n+1,0);
  30.         vector<long long> suffix_ct(n+1,0);
  31.  
  32.         long long ans_3 = lct+prefix_lc[n-1];
  33.  
  34.         long long t=0;
  35.         long long ct=0;
  36.  
  37.  
  38.         for(int i=n-1;i>=0;i--){
  39.             if(s[i]=='T'){
  40.                 t++;
  41.             }
  42.             else if(s[i]=='C'){
  43.                 ct=ct+t;
  44.             }
  45.             suffix_t[i]=t;
  46.             suffix_ct[i]=ct;    
  47.         }
  48.  
  49.         long long ans_1 = lct+suffix_ct[0];
  50.         long long ans_2=0;
  51.  
  52.         for(int i=1;i<n;i++){
  53.             ans_2=max(ans_2,lct+(prefix_l[i-1]*suffix_t[i]));
  54.         }
  55.  
  56.         return max(ans_1,max(ans_2,ans_3));
  57. }
  58.  
  59. int main() {
  60.     string s;
  61.     cin >> s;
  62.  
  63.     cout << numOfSubsequences(s);
  64.  
  65.     return 0;
  66. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
LMCT
stdout
copy 
2
https://ideone.com/dHxXss
language:
C++14 (gcc 8.3)
created:
1 day 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!