CSES - HIIT Open 2016 - Results
Submission details
Task:HIIT remains
Sender:Game of Nolife
Submission time:2016-05-28 11:28:46 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

ll dp[101010][4];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++) {
		string s;
		cin>>s;
		int n=s.size();
		if (s[0]=='H') dp[0][0]=1;
		else dp[0][0]=0;
		for (int i=1;i<n;i++) {
			for (int j=0;j<4;j++) dp[i][j]=dp[i-1][j];
			if (s[i]=='H') dp[i][0]++;
			if (s[i]=='I') {
				dp[i][1]+=dp[i-1][0];
				dp[i][2]+=dp[i-1][1];
			}
			if (s[i]=='T') dp[i][3]+=dp[i-1][2];
		}
		cout<<dp[n-1][3]<<"\n";
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
100
IIITIIIHITHTHIIITIII
HIHIIIIIIHIIITHIIIII
ITTIIIITIIIIIIITIIIT
IITHITITIHHIITTTIIII
...

correct output
12
84
0
37
96
...

user output
12
84
0
37
96
...

Test 2

Verdict: ACCEPTED

input
100
TIIHHITTITITIHTHIIIITHIHHIIHTI...

correct output
606723862
621369559
655243897
550750615
717769300
...

user output
606723862
621369559
655243897
550750615
717769300
...

Test 3

Verdict: ACCEPTED

input
10
TTHTHHTIIIIIITHIIHIITITTITTIIH...

correct output
64668032062669502
66159978956790306
65755072918424640
64408596558953628
65238005187079543
...

user output
64668032062669502
66159978956790306
65755072918424640
64408596558953628
65238005187079543
...

Test 4

Verdict: ACCEPTED

input
3
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

correct output
781234375000000000
4999750003
0

user output
781234375000000000
4999750003
0