Submission #19,292

19292

2025-12-03 18:08:03

cpp17

Time limit exceeded 45/75

300ms

868 KiB

// UUID: a0d67ea5-d22a-46ee-879b-c1bd9f84c59d
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//#define INT_MIN LLONG_MIN
//#define INT_MAX LLONG_MAX

// "szakasz" mint substr
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
	string s;
    cin >> n >> s;
    //for (uint32_t i=0; i<n; i++) if (s[i]=='A') for (uint32_t j=i+1; j<n; j++) if (s[j]=='T'&&(s.substr(i,j-i+1).find('G')!=string::npos)) c++;                             
    vector<int> nextG(n+1, n);
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == 'G') nextG[i] = i;
        else nextG[i] = nextG[i+1];
    }
    long long res = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != 'A') continue;
        for (int j = i; j < n; j++) {
            if (s[j] != 'T') continue;
            if (nextG[i] <= j) res++;
        }
    }

    cout << res;
}

	Sum	Test	Verdict		Time	Memory
base	45/75
		1	Accepted	0/0	1ms	500 KiB
		2	Time limit exceeded	0/0	293ms	820 KiB
		3	Accepted	3/3	1ms	316 KiB
		4	Accepted	4/4	1ms	316 KiB
		5	Accepted	4/4	1ms	316 KiB
		6	Accepted	4/4	1ms	316 KiB
		7	Accepted	4/4	1ms	316 KiB
		8	Accepted	3/3	2ms	316 KiB
		9	Accepted	3/3	1ms	316 KiB
		10	Accepted	4/4	1ms	316 KiB
		11	Accepted	4/4	1ms	316 KiB
		12	Accepted	4/4	1ms	316 KiB
		13	Accepted	4/4	2ms	316 KiB
		14	Accepted	4/4	1ms	328 KiB
		15	Time limit exceeded	0/3	300ms	820 KiB
		16	Time limit exceeded	0/4	300ms	820 KiB
		17	Time limit exceeded	0/4	300ms	820 KiB
		18	Time limit exceeded	0/4	277ms	824 KiB
		19	Time limit exceeded	0/4	287ms	820 KiB
		20	Time limit exceeded	0/4	287ms	868 KiB
		21	Time limit exceeded	0/3	300ms	820 KiB
		22	Time limit exceeded	0/4	284ms	820 KiB