fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. long long numOfSubsequences(string s) {
  7.  
  8.     // Count number of "LCT" subsequences
  9.     long long l = 0;
  10.     long long lc = 0;
  11.     long long lct = 0;
  12.  
  13.     for (int i = 0; i < s.size(); i++) {
  14.  
  15.         if (s[i] == 'L') {
  16.             l++;
  17.         }
  18.  
  19.         if (s[i] == 'C') {
  20.             lc = lc + l;
  21.         }
  22.  
  23.         if (s[i] == 'T') {
  24.             lct = lct + lc;
  25.         }
  26.     }
  27.  
  28.     // Count number of "CT" subsequences
  29.     long long ct = 0;
  30.     long long c = 0;
  31.  
  32.     for (int i = 0; i < s.size(); i++) {
  33.  
  34.         if (s[i] == 'C') {
  35.             c++;
  36.         }
  37.  
  38.         if (s[i] == 'T') {
  39.             ct = ct + c;
  40.         }
  41.     }
  42.  
  43.     // Insert L
  44.     long long insertl = lct + ct;
  45.  
  46.     // Insert T
  47.     long long insertt = lct + lc;
  48.  
  49.     // Insert C
  50.     long long insertc = 0;
  51.  
  52.     long long leftL = 0;
  53.     long long totalT = 0;
  54.  
  55.     // Count total T
  56.     for (int i = 0; i < s.size(); i++) {
  57.         if (s[i] == 'T') {
  58.             totalT++;
  59.         }
  60.     }
  61.  
  62.     long long rightT = totalT;
  63.  
  64.     // Try inserting C at every position
  65.     for (int i = 0; i < s.size(); i++) {
  66.  
  67.         insertc = max(insertc, leftL * rightT);
  68.  
  69.         if (s[i] == 'L') {
  70.             leftL++;
  71.         }
  72.  
  73.         if (s[i] == 'T') {
  74.             rightT--;
  75.         }
  76.     }
  77.  
  78.     // Insert C at the end
  79.     insertc = max(insertc, leftL * rightT);
  80.  
  81.     // Maximum answer
  82.     return max({
  83.         insertl,
  84.         insertt,
  85.         lct + insertc,
  86.         lct
  87.     });
  88. }
  89.  
  90. int main() {
  91.  
  92.     string s;
  93.     cin >> s;
  94.  
  95.     cout << numOfSubsequences(s) << endl;
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
LMCT
stdout
copy 
2
https://ideone.com/yY0w5q
language:
C++ (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!