Submission #17236475

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <cassert>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include "atcoder/all"
using namespace atcoder;
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i, n) for(int i=0;i<(n);i++)
#define P pair<int,int>
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

namespace ori{
    template <typename T>
    void erase(std::vector<T> &v)
    {
        std::sort(v.begin(),v.end());
        v.erase(std::unique(v.begin(),v.end()),v.end());
        return;
    }

    template<typename T>
    int find_index(std::vector<T> v, T find, string key)
    {
        std::sort(v.begin(),v.end());
        if(key=="left")
        {
            return (std::distance(v.begin(),lower_bound(v.begin(),v.end(),find)));
        }
        if(key=="right")
        {
            return (std::distance(v.begin(),upper_bound(v.begin(),v.end(),find))-1);
        }
        else
        {
            return -1;
        }
    }
}

vector<string> split(const string &s, char delim) {
    vector<string> elems;
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
        if (!item.empty()) {
            elems.push_back(item);
        }
    }
    return elems;
}


const int x8[] = {0, 0, 1, -1, -1, 1, -1, 1};
const int y8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int x4[] = {1, -1, 0, 0};
const int y4[] = {0, 0, -1, 1};
const int MOD = 1'000'000'007;

bool ok(char a, char b){
    if((a == 'A' && b == 'T') ||(a == 'T' && b == 'A') || (a == 'G' && b == 'C') ||(a == 'C' && b == 'G'))
    {
        return true;
    }
    else
        return false;
}

void task()
{
    int n; string s; ll ans = 0;
    cin >> n >> s;
    vector<int> a(n+1),g(n+1),c(n+1),t(n+1);
    rep(i,n){
        if(s[i] == 'A') a[i+1]++;
        if(s[i] == 'G') g[i+1]++;
        if(s[i] == 'C') c[i+1]++;
        if(s[i] == 'T') t[i+1]++;
    }
    for(int i = 1; i < n; ++i){
        a[i+1] += a[i];
        g[i+1] += g[i];
        c[i+1] += c[i];
        t[i+1] += t[i];
    }
    for(int i = 1; i < n+1; ++i)
    {
        for(int j = i+1; j <= n; ++j)
        {
            if(((a[j]-a[i-1]) == (t[j]-t[i-1])) && ((g[j]-g[i-1]) == (c[j]-c[i-1]))) ans++;
        }
    }
    cout << ans << endl;
}




int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    task();
    return 0;
}

Submission Info

Judge Result