211692026-01-12 16:24:28PKBDNS szakaszok száma (75 pont)cpp17Hibás válasz 68/754ms1272 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
    /*
    


balról jobbra haladunk



lastG : utolsó G pozícioja

prefixA[i]: hány A van az elejétől i-ig


amikor T-t látunk (ez lehet a vége) : 



Ahhoz hogy a szakasz tartalmazzon Gt a kezdőpont legfeljebb lastG


Ahhoz hogy A-val kezdődjön, a kezdőpontnál A kell legyen







Az aktuális T re érvényes szakaszok = az A-k száma lastG-ig



*/
    int N;
    cin >> N;
    string szo;
    cin >> szo;
    vector<int>prefixA(N+1);
    prefixA[0] = 0;

    int lastG = -1;

    int megoldas = 0;
    int currentMegoldas = 0;
    
    for(int i = 0; i < N; i++){
        prefixA[i+1] = prefixA[i];
        if (szo[i] == 'A'){
            prefixA[i+1]++;
        }
    }
    
    for(int i = 0; i < N; i++){
        if (szo[i] == 'G') {
            lastG = i;
            currentMegoldas = prefixA[i+1];
        }
        if (szo[i] == 'T') {
            megoldas+=currentMegoldas;
        }
    }

    cout << megoldas;


}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base68/75
1Elfogadva0/01ms316 KiB
2Elfogadva0/04ms820 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva3/31ms316 KiB
9Elfogadva3/31ms316 KiB
10Elfogadva4/41ms316 KiB
11Elfogadva4/41ms316 KiB
12Elfogadva4/41ms316 KiB
13Elfogadva4/41ms384 KiB
14Elfogadva4/41ms560 KiB
15Elfogadva3/34ms928 KiB
16Elfogadva4/44ms820 KiB
17Elfogadva4/44ms828 KiB
18Elfogadva4/44ms1272 KiB
19Elfogadva4/44ms820 KiB
20Elfogadva4/44ms1012 KiB
21Hibás válasz0/34ms880 KiB
22Hibás válasz0/44ms936 KiB