akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define yn(x) ((x) ? "Yes" : "No")

typedef pair <int, int> ii;
typedef pair <int, ii> iii;

const int siz = 2e5 + 10;
const int SIZ = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const int MAXX = 1e18;
const string file = "3";



int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

//    freopen ((file + ".inp").c_str(), "r", stdin);
//    freopen ((file + ".out").c_str(), "w", stdout);

    string s, t;
    cin >> s >> t;

    for (int i = 0; i < sz(s); i++) {
        if (s[i] != t[i]) {
            return cout << yn(0) << "\n", 0;
        }
    }

    cout << yn(1) << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

    return 0;
}


Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  int count_c = 10000;
  int count_f = -1;
  for(int i = 0; i < s.size(); i++) {
    if(s[i] == 'C') count_c = i;
    if(s[i] == 'F') count_f = i;
  }
  if(count_c < count_f) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3560
import java.util.*;
import java.math.BigInteger;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		BigInteger bi = BigInteger.ONE;
		for(int i=0; i<N; i++){
			BigInteger next = sc.nextBigInteger();
			if(!bi.equals(BigInteger.valueOf(-1))){
				if(bi.multiply(next).compareTo(BigInteger.valueOf(1000000000000000000L)) > 0){
					bi =  BigInteger.valueOf(-1);
				}else{
					bi = bi.multiply(next);
				}
			}else if(next.equals(BigInteger.ZERO)){
				bi = BigInteger.valueOf(0);
			}
		}
		System.out.print(bi);
	}
}



Measured memory_bytes: 60828
using System;

class Program
{
    static void Main()
    {
        var count = 1;
        var i = 1;
        
        while (i != 0)
        {
            i = int.Parse(Console.ReadLine());
            if (i != 0) Console.WriteLine("Case {0}: {1}", count, i);
            count ++;
        }
    }
}


Measured memory_bytes: 19936
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    string s;
    cin >> s;
    bool flag[26] = {};
    rep(i, s.size()) flag[s[i] - 'a'] = 1;

    rep(i, 26)
    {
        if (flag[i] == 0)
        {
            OP(char('a' + i));
            return 0;
        }
    }
    OP("None");
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,h[maxn];
vector<int>G[maxn];
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++) scanf("%d",&h[i]);
	int u,v;
	for(int i = 1;i <= m;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int ans = 0;
	for(int i = 1;i <= n;i++){
		int len = G[i].size();
		for(int j = 0;j < len;j++){
			int now = G[i][j];
			if(h[i] <= h[now]){
				ans++;
				break;
			}
		}
	}
	printf("%d\n",n - ans);
	return 0;
}

Measured memory_bytes: 9348
k = gets.to_i

dp = Array.new(k,47)
dp[1] = 1
deq = [1]

v = 0
loop  do
  
  break if deq[0] == 0 
  
  v = deq[0]
  
  deq.shift
  u = ( v * 10 ) % k
  if dp[u] > dp[v] then
    dp[u] = dp[v]
    deq.unshift(u)
  end
  
  u = ( v + 1 ) % k
  if dp[u] > dp[v] + 1 then
    dp[u] = dp[v] + 1
    deq.push(u)
  end
end

puts dp[0]

Measured memory_bytes: 3148
#include<bits/stdc++.h>
int n, m, u, v;
std::vector<int> G[100005];
std::deque<int> q;
bool vis[100005];

int find(bool f){
  int v = f ? q.front(): q.back();
  for(auto u : G[v])
    if(!vis[u]){
      vis[u] = true;
      return u;
    }
  return 0;
}

int main(){
  scanf("%d%d", &n, &m);
  for(int i = 0;i < m; ++i){
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  q.push_front(1); q.push_front(G[1][0]);
  vis[1] = vis[G[1][0]] = true;
  while(true) {
    int a, b;
    a = find(true);
    b = find(false);
    if(a + b) {
      if(a) q.push_front(a);
      if(b) q.push_back(b);
    }else break;
  }
  printf("%d\n", (int) q.size());
  for(int i = q.size() - 1;i >= 0; --i)
    printf("%d ",q[i]);
  return 0;
}


Measured memory_bytes: 6784
//538B
#include<bits/stdc++.h>

using namespace std;



int main(){

    cout << fixed;
    cout << setprecision(0);

    int n;
    cin >> n;
    
    int arr[n];
    
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    int minm=1e6,  maxm=0; 
    
    for(int i=0; i<n; i++){
        
        if(minm > arr[i])
            minm = arr[i];
        
        if(maxm < arr[i])
            maxm = arr[i];
        
    }
    
    cout << (maxm - minm );

	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

long long Prime = 1000000007;
long long power(long long pow, int m, int n)
{
	long long tmp;
	if (n == 0) {
		return 1;
	}

	if (n%2) {
		tmp = (pow * m) % Prime;
		return (tmp * power(1, m, n - 1)) % Prime;
	} else {
		tmp = power(1, m, n/2);
		return (pow * tmp * tmp) % Prime;
	}
}
	
int main()
{
	int n,m,i;
	long long pow = 1;
	scanf("%d %d",&m, &n);

    pow = power(1, m, n);
	printf("%lld\n", pow);
	return 0;
}

Measured memory_bytes: 596
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();

		String ans = "Yes";
		if(A == 2 || B == 2) {
			ans = "No";
		}

		System.out.println(ans);

		sc.close();
	}

}


Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;

const int maxn=2100;
const int mod=64;
typedef unsigned long long uLL;

int n;
int a[maxn];
uLL f[maxn*maxn/mod+1];
uLL ex2[mod];
int ans, total;

void read()
{
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
}
void solve()
{
	ex2[0]=1;
	for (int i=1; i<mod; ++i) ex2[i]=ex2[i-1]<<1 | 1;
	for (int i=1; i<=n; ++i) total+=a[i];
	f[0]=1;
	for (int i=1; i<=n; ++i)
		for (int j=total/mod; j>=a[i]/mod; --j)
		{
			int R=(j+1)*mod-1;
			int L=j*mod;
			R-=a[i]; L-=a[i];
			if (L%mod==0) f[j]|=f[R/mod];
			else
			{
				if (L<0) f[j]|=((f[R/mod]&ex2[R%mod])<<(-L));
				else
				f[j]|=((f[R/mod]&ex2[R%mod])<<(mod-L%mod))|(f[L/mod]>>(L%mod));
			}
		}
	ans=(total+1)/2;
	while (!((f[ans/mod]>>(ans%mod)) & 1)) ans++;
	printf("%d\n", ans);
}
int main()
{
	read();
	solve();
	return 0;
}

Measured memory_bytes: 768
#include<stdio.h>
int main(){
    int white_h,white_w;
    int black_h,black_w;
    scanf("%d %d %d %d",&white_h,&white_w,&black_h,&black_w);
    printf("%d",(white_h-black_h)*(white_w-black_w));
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
 
int main(void){
    int a,b,c,i,ans = 0;
    scanf("%d %d",&a,&b);
    
    if (b == 100){
        c = b + a * 1000;
    }else if (b>9&&b<100){
        c = b + a * 100;
    }else{
        c = b + a * 10;
    }
    
    
    
    for (i = 0; i*i <= c; i++){
        if (i*i == c) ans = 1;
    }
    
    if (ans == 1){
        puts("Yes"); 
    }else{
        puts("No");
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int v,e;
vector<P>G[111111];
bool visit[111111];
int t[111111];
int main() {
    cin>>v>>e;
    rep(i,e){
        int a,b,c;
        cin>>a>>b>>c;
        G[a].pb(mp(b,c));
        G[b].pb(mp(a,c));
    }
    priority_queue<P,vector<P>,greater<P> >q;

    q.push(mp(0,0));

    while(!q.empty()){
        int cost=q.top().first,from=q.top().second;
        q.pop();
        if(visit[from])
            continue;
        visit[from]=1;
        t[from]=cost;
        //cout<<from<<" "<<cost<<endl;
        for(int i=0;i<G[from].size();i++){
            int to=G[from][i].first,next_cost=G[from][i].second;
            q.push(mp(next_cost,to));
        }
    }
    int ans=0;
    rep(i,v)ans+=t[i];
    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 10272
#include <stdio.h>

int main(void)
{
  int n, k, x, y;
  int sum;

  scanf("%d", &n);
  scanf("%d", &k);
  scanf("%d", &x);
  scanf("%d", &y);

  if (n - k < 0){
    sum = n * x;
  }
  else {
    sum = k * x;
    sum = sum + ((n - k) * y);
  }
  printf("%d\n", sum);

  return (0);
}

Measured memory_bytes: 128
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, W = lr()
WV = [lr() for _ in range(N)]
# 重さの総和は0か w1<total<(w1+3)*100
base = WV[0][0]
W0 = [0] + sorted([v for w, v in WV if w == base + 0], reverse=True)
W1 = [0] + sorted([v for w, v in WV if w == base + 1], reverse=True)
W2 = [0] + sorted([v for w, v in WV if w == base + 2], reverse=True)
W3 = [0] + sorted([v for w, v in WV if w == base + 3], reverse=True)
W0cum = np.array(W0).cumsum()
W1cum = np.array(W1).cumsum()
W2cum = np.array(W2).cumsum()
W3cum = np.array(W3).cumsum()
answer = 0
for a in range(len(W0)):
    for b in range(len(W1)):
        for c in range(len(W2)):
            for d in range(len(W3)):
                remain = W - a * base - b * (base+1) - c * (base+2) - d * (base+3)
                if remain < 0:
                    continue
                answer = max(answer, W0cum[a] + W1cum[b] + W2cum[c] + W3cum[d])

print(answer)


Measured memory_bytes: 12512
#include<bits/stdc++.h>
using namespace std;
#define ll long long
short cnt12[2020][2020];
short cnt21[2020][2020];
short cnt22[2020][2020];
short cnt11[2020][2020];
short org1[2020];
short org2[2020];
int dp[2020][2020];
int n;
int sol(int i,int j) {
    if (i==n && j==n)return 0;
    if (dp[i][j]!=-1)return dp[i][j];
    int& ret = dp[i][j];
    ret = 1e9;
    int id = i+j+1;
    if (i<n) {
        int id2 = org1[i+1]+cnt12[i+1][j]+cnt11[i+1][i];
        ret = min(ret, sol(i+1,j) + abs(id2-id));
    }
    if (j<n) {
        int id2 = org2[j+1]+cnt21[j+1][i]+cnt22[j+1][j];
        ret = min(ret, sol(i, j+1) + abs(id-id2));
    }
    return ret;
}
int a[1000000];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=2*n;i++) {
        char x;
        cin>>x;
        cin>>a[i];
        if (x=='W')org1[a[i]]=i;
        else org2[a[i]]=i;
        for (int j=1;j<i;j++) {
            if (org1[a[j]]==j && x=='B'){
                cnt12[a[j]][a[i]]=1;
            } else if (org2[a[j]]==j && x=='W'){
                cnt21[a[j]][a[i]]=1;
            } else if (org1[a[j]]==j && x=='W'){
                cnt11[a[j]][a[i]]=1;
            } else if (org2[a[j]]==j && x=='B'){
                cnt22[a[j]][a[i]]=1;
            }
        }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cnt11[i][j]+=cnt11[i][j-1], cnt12[i][j]+=cnt12[i][j-1],
                    cnt21[i][j]+=cnt21[i][j-1], cnt22[i][j]+=cnt22[i][j-1];
    memset(dp,-1,sizeof(dp));
    cout<<sol(0,0)<<endl;
}

Measured memory_bytes: 50176
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
//小数点以下　cout << fixed << setprecision(10) << num << endl;
//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA
//long*long<0で判定するな　オーバーフローする
//開区間と閉区間どうにかしろ
//アルファベットが何番目かは x=s[i]-'a'
const ll MOD = 1000000007;
int h,w;
string s[444];


ll bfs(){
    bool visit[h][w];
    memset(visit,0,sizeof(visit));
    ll ans=0;
    rep(i,h){
        rep(j,w){
            if(!visit[i][j]){
                
    ll bl=0,wh=0;
    queue<P> q;
    q.push({i,j});
    visit[i][j]=1;
    if(s[i][j]=='#') bl++;
    else wh++;
    int dy[4]={1,0,-1,0};
    int dx[4]={0,1,0,-1};
    while(!q.empty()){
        P d=q.front(); q.pop();
        rep(k,4){
            int ny=d.fi+dy[k]; int nx=d.se+dx[k];
            if(0<=ny && ny<h && 0<=nx && nx<w && s[d.fi][d.se]!=s[ny][nx] && (!visit[ny][nx])){
                q.push({ny,nx});
                visit[ny][nx]=1;
                if(s[ny][nx]=='#') bl++;
                else wh++;
        
            }
        }
    }
    ans+=bl*wh;
            }
        }
    }
    return ans;
}

int main(){
    cin >> h >> w;
    rep(i,h) cin >> s[i];
    cout << bfs() << endl;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>

using namespace std;

int main() {
	long n,k;
	cin >> n >> k;
	long k0 = 0,k2 = 0;
	for (long i=1;i<=n;++i) {
		if (i%k==0) ++k0;
		if (k%2==0 && i%k==k/2) ++k2;
	}
	cout << k0*k0*k0+k2*k2*k2 << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main(){
	int h, w;
	while(1){
		scanf("%d %d", &h, &w);
		if(h==0 && w==0){
			break;
		}
		for(int j=0; j<h; j++){
			for(int i=0; i<w; i++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2588
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
local function array(dimension, default_val) local n=dimension local m={}if default_val~=nil then m[1]={__index=function()return default_val end}end for i=2,n do m[i]={__index=function(p, k)local c=setmetatable({},m[i-1])rawset(p,k,c)return c end}end return setmetatable({},m[n])end
----
local A, B = read.nn()
local price_base = B * 10
for i=0,9 do
    local p = price_base + i
    if p * 8 // 100 == A then
        print(p)
        return
    end
end
print(-1)


Measured memory_bytes: 508
import java.util.*;

public class Main{
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int [][] A = new int [N][M];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                A[i][j] = sc.nextInt() - 1;
            }
        }
        System.out.println(calcAns(N,M,A));
    }

    public static int calcAns(int N,int M,int [][] A) {
        int [] c = new int [M];
        int [] x = new int [N];
        for(int i = 0; i < N; i++) {
            c[A[i][0]] += 1;
        }
        int ret = N;
        for(int cnt = 0; cnt < M - 1; cnt++) {
            // most appeared color
            int p = 0;
            for(int i = 1; i < M; i++) {
                if(c[i] > c[p]) {
                    p = i;
                }
            }
            // update ret
            if(c[p] < ret) ret = c[p];
            // delete color p
            c[p] = -1;
            for(int i = 0; i < N; i++) {
                c[A[i][x[i]]] -= 1;
                while(c[A[i][x[i]]] < 0) {
                    x[i] = x[i] + 1;
                }
                c[A[i][x[i]]] += 1;
            }
        }
        return ret;
    }
}


Measured memory_bytes: 50264
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

#define ll long long
using namespace std;
static ll imin = std::numeric_limits<ll>::min();
static ll imax = std::numeric_limits<ll>::max();
#define rep(i, n) for(int i = 0; i<n; ++i)
#define rep1(i, n) for(int i = 1; i<n; ++i)
#define debug(x) cout << #x << ":" << x << "\n";
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  for(int i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T>
std::istream& operator >> (std::istream& is, std::vector<T>& vec){
  T tmp;
  is >> tmp;
  vec.push_back(tmp);
  return is;
}
template <class T>
auto mkVec(unsigned int x){
  return std::vector<int>(x);
}

template <class T>
auto mkVec2(unsigned int x, unsigned int y){
  return std::vector<std::vector<T>>(x, std::vector<T>(y));
}

template <class T>
auto mkVec3(unsigned int x, unsigned int y, unsigned int z){
  return std::vector<std::vector<std::vector<T>>>(x, std::vector<std::vector<T>>(y, std::vector<T>(z)));
}

// 113C
// #ifndef BOOST_TEST_MAIN
// int main(int const argc, char const** argv){
//   int N, M;
//   cin >> N >> M;
//   vector<ll> P;
//   vector<ll> Y;
//   auto X = mkVec2<ll>(N + 1, 0);
//   rep(i, M){
//     ll p, y;
//     cin >> p >> y;
//     P.push_back(p);
//     Y.push_back(y);
//     X[p].push_back(y);
//   }
//   rep(i, N + 1){
//     sort(X[i].begin(), X[i].end());
//   }
//   rep(i, M) {
//     ll y;
//     rep(j, N + 1){
//       auto x = find(X[j].begin(), X[j].end(), Y[i]);
//       if(x != X[j].end()){
//         y = x - X[j].begin();
//         break;
//       }
//     }
//     printf("%06lld%06lld\n", P[i], y + 1);
//   }
// }
// #endif

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  int N;
  cin >> N;

  vector<int> s;
  rep(i, N){
    char c;
    cin >> c;
    if(c == 'W'){
      s.push_back(0);
    }else{
      s.push_back(1);
    }
  }
  auto l = mkVec<ll>(N);
  int x = 0;
  rep(i, N){
    if(s[i] == 0){
      x++;
    }
    l[i] = x;
  }
  auto r = mkVec<ll>(N);
  x = 0;
  for(int i = N - 1;i != -1; i--){
    if(s[i] == 1){
      x++;
    }
    r[i] = x;
  }

  ll res = imax;
  rep(i, N){
    res = min(res, (ll)l[i] + r[i] - 1);
  }
  cout << res;
}
#endif


Measured memory_bytes: 3824
import java.util.*

fun main(args : Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextLong()
    println(problem55b(n))
}

fun problem55b(n: Long): Long {
    val mod: Long = (Math.pow(10.0, 9.0) + 7).toLong()
    var answer = 1L
    (1..n).forEach { i ->
        answer *= i
        answer %= mod
    }
    return answer
}

Measured memory_bytes: 29344
#include <bits/stdc++.h>  

const int INF =1e9;
const int MOD =1e9+7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int dx[4] ={ 1, 0, -1, 0 };
int dy[4] ={ 0, 1, 0, -1 };


int main()
{
    int k;
    cin>>k;
    vector<ll> ans;
    queue<ll> Q;
    FOR(i,1,10)
        Q.push(i);
    while(ans.size()<100000){
        queue<ll> Q2;
        while(!Q.empty()){
            ll q=Q.front();
            Q.pop();
            ans.push_back(q);
            for(int i=-1;i<=1;i++){
                if(0<=(q%10+i)&&(q%10+i)<10){
                    Q2.push(q*10+(q%10+i));
                }
            }
        }
        Q=Q2;
    }
    cout<<ans[k-1]<<endl;
}

Measured memory_bytes: 11088
#include <stdio.h>

int main(){
    int N;
    char S[300000];
    int A[300000] = {0}; //i番目をリーダーとしたときの手数
    scanf("%d", &N);
    scanf("%s",S);

    
    for(int j = 0; j < N; j++)
    {
        if(j < 0 && S[j] == 'W'){ A[0]++; /*printf("i=%d,j=%d,A[%d]=%d count up!\n",0,j,0,A[0]);*/}
        if(j > 0 && S[j] == 'E'){ A[0]++; /*printf("i=%d,j=%d,A[%d]=%d count up!\n",0,j,0,A[0]);*/}
    }
    
    
    for(int i = 1; i < N; i++)
    {
        A[i] = A[i-1];
        if(S[i-1] == 'W'){A[i]++; }
        if(S[i] == 'E'){A[i]--;}
    }

    int small = N;
    for(int i = 0; i < N; i++)
    {
        //printf("A[%d]=%d",i,A[i]);
        if(A[i] < small){ small = A[i]; }
    } 
    
    printf("%d",small);
    
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
static const ll maxLL = (ll)1 << 62;
const int mod=1000000007,INF=1001001001;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};


#define int ll

int n,W,a,b,x,sum=0,cnt,ans=0;
vector<vint> w;


signed main(){
    w=vector<vint>(4,vint(25,0));
    cin>>n>>W;
    rep(i,0,n){
        cin>>a>>b;
        if(i==0){x=a;w[0].pb(b);}
        else {
            w[a-x].pb(b);
        }
    }
    rep(i,0,4)sort(w[i].begin(),w[i].end(),greater<int>());
    
    rep(i,0,w[0].size())rep(j,0,w[1].size())rep(k,0,w[2].size())rep(l,0,w[3].size()){
        cnt=0;
        cnt+=i*x+j*(x+1)+k*(x+2)+l*(x+3);
        if(W<cnt)continue;
        sum=0;
        rep(z,0,i)sum+=w[0][z];
        rep(z,0,j)sum+=w[1][z];
        rep(z,0,k)sum+=w[2][z];
        rep(z,0,l)sum+=w[3][z];
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
//  SMOKE SHISHA PLAY FIFA  // 
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define MP make_pair
#define ff first
#define ss second
#define PB push_back
#define mod 1000000007
#define lp(i,start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	ll n;
	cin>>n;
	cout<<n+n*n+n*n*n<<endl;
	return 0;	
}


Measured memory_bytes: 3608
s = list(input())
# print(s)
n = len(s)
m = []
m.append(s[0])
del s[0]
count = 0
# print(n)
while count < n:
    try:
        if m[-1] == s[count]:
            m.append(s[count] + s[count + 1])
            count += 2
        else:
            m.append(s[count])
            count += 1
    except:
        m[-1] = m[-1] + s[-1]
        count += 2
# print(m)
print(len(m))

Measured memory_bytes: 9636
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,K,ans=0;
  cin>>N>>K;
  vector<int> A(N),B(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
    B.at(A.at(i)-1)++;
  }
  sort(B.begin(),B.end());
  reverse(B.begin(),B.end());
  for(int i=K;i<N;i++){
    ans+=B.at(i);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>

#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long int ll;
const ll INF = 1000000000000000000;
const double PI = acos(-1);

struct Edge {
    int id;
    int to;
};

vector<vector<Edge>> node;
vector<int> c;
int max_c = 0;

void dfs(int n, int p, int c_p) {
    int c_now = 0;
    rep(i, node[n].size()) {
        Edge edge = node[n][i];       // 今見ている辺
        if (edge.to == p) continue;   // 今見ている辺がn->pの辺だったらスキップ
        c_now++;
        if (c_now == c_p) c_now++;    // p->nの辺と同じ色だったら色を1つ進める
        c[edge.id] = c_now;           // 色を塗る
        dfs(edge.to, n, c_now);
    }
    max_c = max(max_c, c_now);
    return;
}

int main()
{
    int n;
    cin >> n;
    node.resize(n);
    c.resize(n - 1);
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        Edge edge1 = { i, b };  // a->bの辺
        Edge edge2 = { i, a };  // b->aの辺
        node[a].push_back(edge1);
        node[b].push_back(edge2);
    }
    dfs(0, -1, -1);
    cout << max_c << endl;
    rep(i, n - 1) {
        cout << c[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 11108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 1000000007;

int main(){
  ll h,w;
  cin >> h >> w;
  
  ll ans,ans1,ans2,ans3,ans4;
  ll hemain=h%3,wemain=w%3;
  ll hart1=(h-hemain)/3,wart1=(w-wemain)/3;
  ll hart2=h/2,wart2=w/2;
  ll hact,wact;
  
  if(hemain==0 || wemain==0){
   cout << 0 << endl;
   return 0;
  }
  
  ans1=w;
  ans2=h;
  ans=min(ans1,ans2);
  
  if(hemain==2){
    hact=hart1+1;
    ans3=w*hact-wart2*(h-hact);
  }
  else{
    hact=hart1;
    ans3=w*hact-(w-wart2)*(h-hact);
  }
  
  if(ans3<0)ans3*=-1;
  ans=min(ans,ans3);
  
  
  if(wemain==2){
    wact=wart1+1;
    ans4=h*wact-hart2*(w-wact);
  }
  
  else{
    wact=wart1;
    ans4=h*wact-(h-hart2)*(w-wact);
  }
  if(ans4<0)ans4*=-1;
  ans=min(ans,ans4);
  
  
  
  cout << ans << endl;
  
  
  
  
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

int main() {
  uint32_t N;
  cin >> N;
  vector<uint32_t> A(N + 1);
  for (uint32_t i = 1; i < N + 1; ++i) cin >> A[i];

  uint32_t BallNum = 0;
  for (uint32_t i = N; i > 0; --i) {
    uint32_t tmp = (uint32_t)(N / i);
    uint32_t sum = 0;
    for (uint32_t j = 1; j <= tmp; ++j) {
      sum += A[i * j];
    }
    if ((sum & 0x01) != A[i]) {
      A[i] ^= 0x01;
    }
    BallNum += A[i];
  }
  cout << BallNum << endl;
  for (uint32_t i = 1; i < N + 1; ++i) {
    if (A[i]) cout << i << " ";
  }
  cout << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void solution(int x, int y) {
		if((x+y)%2==0) {
			System.out.println((x+y)/2);
		}
		else {
			System.out.println("IMPOSSIBLE");
		}
	}
		
	
	public static void main(String args []) {
		Scanner obj = new Scanner(System.in);
		int x = obj.nextInt();
		int y = obj.nextInt();
		solution(x,y);
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;

long long x[1005],y[1005],z[1005],xyz[3000010],X,Y,Z,K;

bool cmp(const long long &x, const long long &y)
{
	return x>y;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> X >> Y >> Z >> K;
	for(int i = 1; i <= X; i++) cin >> x[i];
	for(int i = 1; i <= Y; i++) cin >> y[i];
	for(int i = 1; i <= Z; i++) cin >> z[i];
	sort(x+1,x+X+1,cmp);
	sort(y+1,y+Y+1,cmp);
	sort(z+1,z+Z+1,cmp);
	int cnt = 0;
	for(int i = 1; i <= X; i++)
		for(int j = 1; j <= Y; j++)
			for(int k = 1; k <= Z; k++){
				if(i*j*k > K) break;
				cnt++;
				xyz[cnt] = x[i]+y[j]+z[k];
			}
	sort(xyz+1,xyz+cnt+1,cmp);
	for(int l = 1; l <= K; l++)
		cout<<xyz[l]<<"\n";

	return 0;
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll dp[100001];
ll w[100000], v[100000];
int main() {
	int N, W;
	cin >> N >> W;
	for (int i = 0; i < N; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = W; j >= 0; j--) {
			if (w[i] <= j) {
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	}
	cout << dp[W] << endl;
}


Measured memory_bytes: 1024
from itertools import permutations
N,C=map(int,input().split())
D=[]
for c in range(C):
    D.append(list(map(int,input().split())))
c=[]
for i in range(N):
    c.append(list(map(lambda x:int(x)-1,input().split())))
color=[[0]*(C) for i in range(3)]
cost=[[0]*(C) for i in range(3)]
for i in range(N):
    for j in range(N):
        mod=(i+j+2)%3
        oldc=c[i][j]
        for ci,cl in enumerate(D[oldc]):
            cost[mod][ci]+=cl
mnc=float('inf')
for i,j,k in permutations(range(C),3):
    cst=cost[0][i] + cost[1][j]+cost[2][k]
    if cst<mnc:
        mnc=cst
print(mnc)

Measured memory_bytes: 5620
#include<stdio.h>
#include<stdlib.h>
typedef struct{
  int parent;
  int id;
  int left;
  int right;
    }Node;
int Postorder(Node *A,int key){
  if(key != -1){
    Postorder(A,A[key].left);
    Postorder(A,A[key].right);
    printf(" %d",A[key].id);
  }
}
int Inorder(Node *A,int key){
  if(key !=-1){
    Inorder(A,A[key].left);
    printf(" %d",A[key].id);
    Inorder(A,A[key].right);
  }
}
int Preorder(Node *A,int key){
  if(key !=-1){
    printf(" %d",A[key].id);
    Preorder(A,A[key].left);
    Preorder(A,A[key].right);
  }
}
int main(){
  int n,l,r,id,root;
  int i;
  Node *A;
  scanf("%d",&n);
  A=(Node*)malloc(sizeof(Node)*n);
  for(i=0;i<n;i++){//parentの初期化(-1)
    A[i].parent=-1;
  }
  for(i=0;i<n;i++){//入力
    scanf("%d%d%d",&id,&l,&r);
    A[id].id=id;
    A[id].left=l;
    A[id].right=r;
    A[r].parent=id;
    A[l].parent=id;
  }
  for(i=0;i<n;i++){
    if(A[i].parent==-1)root=A[i].id;
  }
  printf("Preorder\n");
  Preorder(A,root);
  printf("\nInorder\n");
  Inorder(A,root);
  printf("\nPostorder\n");
  Postorder(A,root);
  printf("\n");
  
  return 0; 
}



Measured memory_bytes: 2112
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 2345678;
const LL MOD = (LL)1e9 + 7;
LL fac[MAXN], ifac[MAXN];
LL drang[MAXN];

LL mul(LL a, LL b) {
    return (a * b) % MOD;
}

LL qpow(LL x, LL n) {
    LL ans = 1, base = x;
    while (n) {
        if (n % 2) ans = mul(ans, base);
        base = mul(base, base);
        n /= 2;
    }
    return ans;
}

LL C(LL n, LL m) {
    if (m > n) return 0;
    return mul(mul(fac[n], ifac[m]), ifac[n - m]);
}

void init() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = mul(fac[i - 1], i);
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 1; i--)
        ifac[i] = mul(ifac[i + 1], i + 1);
}

int main() {
    init();
    int N, M;
    scanf("%d %d", &N, &M);
    LL coef = mul(C(M, N), fac[N]);
    LL offs = M - N;
    drang[0] = 1;
    for (int i = 1; i <= N; i++) {
        drang[i] = mul(drang[i - 1], offs);
        drang[i] = (drang[i] + mul(drang[i - 1], i - 1)) % MOD;
        if (i > 1) {
            drang[i] = (drang[i] + mul(drang[i - 2], i - 1)) % MOD;
        }
    }
    printf("%lld\n", mul(coef, drang[N]));


    return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
by Benq;
*/


Measured memory_bytes: 44340
// A - Mahmoud and Ehab and the MEX: http://codeforces.com/contest/862/problem/A
// 0から順に操作が要るかどうかを考える

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define _D(p) std::cout<<"L"<<__LINE__<<" : " #p " = "<<(p)<<std::endl;
#define _D2(p,q) std::cout<<"L"<<__LINE__<<" : " #p " = "<<(p) << ", " #q " = "<<(q)<<std::endl;
#define _DN(v) std::cout<<"L"<<__LINE__<<" : " #v " = ["; rep(i,(v).size()) {std::cout<<v[i]<<(i==v.size()-1?"":", ");}std::cout<<"]"<<std::endl;
#define _DNN(v) std::cout<<"L"<<__LINE__<<" : " #v " = [" << std::endl; rep(i,(v).size()) {std::cout<<"    [";rep(j,(v)[0].size()){std::cout<<v[i][j]<<(j==v[0].size()-1?"":", ");}std::cout<<"],"<<std::endl;}std::cout<<"]"<<std::endl;
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
const int mod = 1000000007;


int main(int argc, char const *argv[]) {
    int N, M, K;
    cin >> N >> M >> K;
    bool flag = false;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            int c = i * (M - j) + j * (N - i);
            if (c == K) {
                flag = true;
            }
        }
    }
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define dunk(a) cout << (a) << endl
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;

int main() {
	string s, t; cin >> s >> t;
	dunk(t + s);
	return 0;
}


Measured memory_bytes: 256
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())

x=max(a,b,c,d,e)
y=min(a,b,c,d,e)


if x-y>k:
    print(':(')
else:
    print('Yay!')
    



Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>

struct node{
	int n_chilledren;
	int *id_chilledren;
	int id_parent;
	int depth;
	char type[15];
};

struct tree{
	int n_nodes;
	node *nodes;
};

void link(tree t, int id){
	int i, id_child;
	for(i=0;i<t.nodes[id].n_chilledren;i++){
		id_child = t.nodes[id].id_chilledren[i];
		t.nodes[id_child].id_parent = id;
		if(t.nodes[id_child].n_chilledren == 0){
			strcpy(t.nodes[id_child].type, "leaf");
		}
		else{
			strcpy(t.nodes[id_child].type, "internal node");
		}
	}
}

void printNodes(tree t){
	int i,j,n;
	n = t.n_nodes;
	for(i=0;i<n;i++){
		printf("node %d: ", i);
		printf("parent = %d, ", t.nodes[i].id_parent);
		printf("depth = %d, ", t.nodes[i].depth);
		printf("%s, ", t.nodes[i].type);
		printf("[");
		if(t.nodes[i].n_chilledren>0){
			for(j=0;j<t.nodes[i].n_chilledren-1;j++){
				printf("%d, ", t.nodes[i].id_chilledren[j]);
			}
			printf("%d",t.nodes[i].id_chilledren[j]);
		}
		printf("]\n");
		
	}
}

void setDepth(tree t, int id, int d){
	int i;
	t.nodes[id].depth = d;
	for(i=0;i<t.nodes[id].n_chilledren;i++){
		setDepth(t, t.nodes[id].id_chilledren[i], d+1);
	}
}

int main(void){
	tree t;
	int i,j, id, n;
	scanf("%d", &t.n_nodes);
	t.nodes = new node[t.n_nodes];
	
	for(i=0;i<t.n_nodes;i++){
		t.nodes[id].id_parent = -1;
		scanf("%d %d", &id, &n);
		t.nodes[id].n_chilledren = n;
		if(n>=0){
			t.nodes[id].id_chilledren = new int[n];
			for(j=0; j<n; j++){
				scanf("%d", &t.nodes[id].id_chilledren[j]);
			}
		}
	}
	for (i=0;i<t.n_nodes;i++){
		if(t.nodes[i].n_chilledren >0) link(t, i);
	}
	for (i=0;i<t.n_nodes;i++){
		if(t.nodes[i].id_parent == -1){
			strcpy(t.nodes[i].type, "root");
			id = i;
			break;
		}
	}
	setDepth(t, id, 0);
	printNodes(t);
	delete []t.nodes;

	return 0;
}

Measured memory_bytes: 9672
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 10005
int dp[MAX_N];
const int num[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int INF = 1000000000;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(M); for (int& a : A) cin >> a;
  sort(A.begin(), A.end(), greater<int>());
  for (int i = 1; i <= N; i++) {
    for (int a : A) {
      int Nj = num[a];
      if (0 <= i - Nj) {
        dp[i] = max(dp[i], dp[i - Nj] + 1);
      }
    }
    if (dp[i] == 0) dp[i] = -INF;
  }
  int D = dp[N];
  for (int i = 0; i < D; i++) {
    for (int a : A) {
      int Nj = num[a];
      if (N - Nj < 0) continue;
      if (dp[N - Nj] == dp[N] - 1) {
        cout << a;
        N -= Nj;
        break;
      }
    }
  }
  cout << endl;
}

Measured memory_bytes: 256
N = int(raw_input())
a = map(int, raw_input().split())
c = [0] * 9
for r in a:
    if r <= 399:
        c[1] = c[1] + 1
    elif r <= 799:
        c[2] = c[2] + 1
    elif r <= 1199:
        c[3] = c[3] + 1
    elif r <= 1599:
        c[4] = c[4] + 1
    elif r <= 1999:
        c[5] = c[5] + 1
    elif r <= 2399:
        c[6] = c[6] + 1
    elif r <= 2799:
        c[7] = c[7] + 1
    elif r <= 3199:
        c[8] = c[8] + 1
    elif 3200 <= r:
        c[0] = c[0] + 1
ans = 0
for i in c[1:]:
    if i != 0:
        ans = ans + 1
mn = ans
mx = ans + c[0]
if mn == 0:
    print 1, mx
else:
    print mn, mx

Measured memory_bytes: 2696
class Group
  attr_accessor :arrival, :number, :sojourn
  attr_accessor :in, :out
  def initialize(arrival, number, sojourn)
    @arrival, @number, @sojourn = arrival, number, sojourn
  end
  def sit(time)
    @in = time
    @out = @in + sojourn
  end
  def show
    p [@arrival, @number, @sojourn]
  end
end

group = 100.times.map{|i| Group.new(5 * i, (i % 5 == 1 ? 5 : 2), (17 * (i % 2) + 3 * (i % 3) + 19))}
seat = Array.new(17)

time = 0
head = 0
until head == 100
  # out
  seat.map! do |s|
    if s
      group[s].out <= time ? nil : s
    else
      nil
    end
  end

  # in
  until head == 100 || group[head].arrival > time
    ok = false
    n = group[head].number
    (17 - n + 1).times do |i|
      next unless seat[i, n].all?(&:nil?)
      group[head].sit(time)
      seat[i, n] = n.times.map{head}
      head += 1
      ok = true
      break
    end
    break unless ok
  end

  # update
  time += 1
end

while gets
  n = $_.to_i
  p (group[n].in - group[n].arrival)
end

Measured memory_bytes: 6120
W = list(raw_input())
flagArray = [True for i in range(26)]
for w in W:
	flagArray[ord(w)-97] = not(flagArray[ord(w)-97])
flag = True
for f in flagArray:
	if not f:
		print "No"
		flag = False
		break
if flag:
	print "Yes"

Measured memory_bytes: 2568
const main = (): void => {
  const s = getParams();
  console.log(solve(s));
};

const getParams = (): string =>
  getStdin();

const getStdin = (): string =>
  require('fs').readFileSync('/dev/stdin', 'utf8').trim();

const solve = (s: string): string =>
  s.split('').map(replace).join('');

const replace = (c: string): string =>
  c === '1' ? '9' : '1';

main();


Measured memory_bytes: 7372
s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)

Measured memory_bytes: 9392
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
AC
*/


ll n,q,dp[100010],l[100010],r[100010];
string s;

int main(void){
	cin>>n>>q;
	cin>>s;
	rep(i,q){
		cin>>l[i]>>r[i];
	}
	dp[0]=0;
	reg(i,1,n-1){
		dp[i]=dp[i-1];
		if(s[i-1]=='A' && s[i]=='C'){
			dp[i]++;
		}
	}
	// rep(i,n)cout<<dp[i]<<endl;
	rep(i,q){
		cout<<dp[r[i]-1]-dp[l[i]-1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()		// begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)				// repeat
#define repr(i, begin, end) for (ll i = end - 1; begin <= i; i--)		// repeat reverse

#endif

class ABC121D
{
public:
	ABC121D()
	{
		cin >> a >> b;
	}
	void Run(void)
	{
		if (b == 0)
		{
			cout << 0;
			return;
		}

		vector<ll> ans((ll)(log(b) / log(2) + 1));

		rep(i, 1, (ll)ans.size() + 1)
			ans[i - 1] = (BitCount(i, b) - BitCount(i, a-1)) % 2;

		ll value = 0;
		rep(i, 0, (ll)ans.size())
			value |= (ans[i] << i);

		cout << value;
	}
private:
	ll BitCount(ll n, ll x)
	{
		if (x <= 0)
			return 0;

		ll div = x / ((ll)1 << (n - 1));
		ll rem = x % ((ll)1 << (n - 1));

		if (div % 2 == 0)
			return ((ll)1 << (n - 1)) * (ll)(div / 2);
		else
			return ((ll)1 << (n - 1)) * (ll)(div / 2) + (rem + 1);
	}
	ll a;
	ll b;
};

int main(void)
{
	ABC121D abc121d;
	abc121d.Run();

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	void solve() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] a = new int[n + 1];
		int[] b = new int[n];
		long before = 0;
		for(int i = 0; i < n + 1; i++) {
			a[i] = scan.nextInt();
			before += a[i];
		}
		for(int i = 0; i < n; i++) b[i] = scan.nextInt();
		long after = 0;
		for(int i = 0; i < n; i++) {
			if(a[i] <= b[i]) {
				b[i] -= a[i];
				a[i] = 0;
				a[i + 1] -= b[i] - a[i];
				if(a[i + 1] < 0) a[i + 1] = 0;
			} else {
				a[i] -= b[i];
				b[i] = 0;
			}
		}
		for(int i = 0; i < n + 1; i++) {
			a[i] = Math.max(a[i], 0);
			after += a[i];
		}
		System.out.println(before - after);
		scan.close();
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}


Measured memory_bytes: 60756
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  vector<ll> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  ll k;
  cin >> k;
  cout << a[k - 1] << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] $) {
		Scanner sc = new Scanner(System.in);
		String s=sc.next();
		long k=sc.nextLong();
		if(k==1) {
			System.out.println(s.substring(0, 1));
		}else {
			for(int i=0;i<s.length();i++) {
				if(i+1==k&&s.substring(i, i+1).equals("1")) {
					System.out.println(s.substring(i, i+1));
					break;
				}
				if(!s.substring(i, i+1).equals("1")) {
					System.out.println(s.substring(i, i+1));
					break;
				}
			}
		}
	}
}



Measured memory_bytes: 21844
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

////////////////////////////////////////
///        templates                 ///
////////////////////////////////////////

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readBigLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func strSprit(str string) []string {
	cols := strings.Split(str, " ")
	return cols
}

func parseInt(str string) int {
	n, _ := strconv.Atoi(str)
	return n
}

func intSprit(str string) []int {
	strs := strSprit(str)
	cols := make([]int, len(strs))
	for i, v := range strs {
		cols[i] = parseInt(v)
	}
	return cols
}

func bitCount(n uint) int {

	x := uint64(n)

	const m = 1<<64 - 1
	const m0 = 0x5555555555555555
	const m1 = 0x3333333333333333
	const m2 = 0x0f0f0f0f0f0f0f0f

	x = x>>1&(m0&m) + x&(m0&m)
	x = x>>2&(m1&m) + x&(m1&m)
	x = (x>>4 + x) & (m2 & m)
	x += x >> 8
	x += x >> 16
	x += x >> 32

	return int(x) & (1<<7 - 1)
}

func bitExist(n, i int) bool {
	return ((n >> uint(i)) & 1) == 1
}

func setBit(d, n int) int {
	t := 1 << uint(n)
	return d | t
}

func intAbs(n int) int {
	return int(math.Abs(float64(n)))
}

////////////////////////////////////////
///        end templates             ///
////////////////////////////////////////
func xors(n int64) int64 {
	ret := int64(0)
	if n%2 == 0 {
		if (n/2)%2 == 0 {
			ret = int64(0) ^ n
		} else {
			ret = int64(1) ^ n
		}
	} else {
		if ((n+1)/2)%2 == 0 {
			ret = int64(0)
		} else {
			ret = int64(1)
		}
	}
	return ret
}

func main() {
	line := nextLine()
	spl := strSprit(line)

	A, _ := strconv.ParseInt(spl[0], 10, 64)
	B, _ := strconv.ParseInt(spl[1], 10, 64)

	xa := xors(A - 1)
	xb := xors(B)

	fmt.Println(xa ^ xb)
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, i, j, k, ans, s;
	cin >> n;
	vector<int> a(n);
	for (i = 0; i < n; i++) cin >> a[i];
	ans = 1E9;
	for (i = 0; i <= 100; i++) {
		s = 0;
		for (auto p : a) s += (i - p) * (i - p);
		ans = min(ans, s);
	}
	cout << ans << "\n";


	return 0;
}



Measured memory_bytes: 256
a,b,c,k = map(int,input().split())

ans = 0
if k-a>=0:
    ans+= a
    k-=a
else:
    ans += k
    print(ans)
    exit()
if k-b>=0:
    ans += 0
    k-=b
else:
    print(ans)
    exit()
if k-c >=0:
    ans += (-1)*c
    print(ans)
    exit()
else:
    ans += (-1)*k
    print(ans)

Measured memory_bytes: 9140
/*
    Written by Nitrogens
    Desire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

const int maxn = 3e3+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;

#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl

char input[maxn];
ll dp[maxn][maxn], prefix[2][maxn], suffix[2][maxn];

int main()
{
    //ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);

    int n;
    scanf("%d", &n);
    scanf("%s", input + 1);

    fill(prefix[0] + 1, prefix[0] + 1 + n, 1);
    fill(suffix[0] + 1, suffix[0] + 1 + n, 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            if(i == 1)
            {
                dp[i][j] = 1LL;
                prefix[1][j] = (prefix[1][j - 1] + dp[i][j]) % Mod;
            }
            else
            {
                /*
                if(input[i - 1] == '<')
                {
                    for(int k = 1; k < j; k++)  dp[i][j] += dp[i - 1][k];
                }
                else
                {
                    for(int k = j; k <= n; k++)  dp[i][j] += dp[i - 1][k];
                }
                */
                if(input[i - 1] == '<') dp[i][j] = prefix[0][j - 1];
                else                    dp[i][j] = suffix[0][j];
                prefix[1][j] = (prefix[1][j - 1] + dp[i][j]) % Mod;
            }
        }
        for(int j = n; j >= 1; j--) suffix[1][j] = (suffix[1][j + 1] + dp[i][j]) % Mod;
        memcpy(prefix[0], prefix[1], sizeof(prefix[1]));
        memcpy(suffix[0], suffix[1], sizeof(suffix[1]));
        memset(prefix[1], 0, sizeof(prefix[1]));
        memset(suffix[1], 0, sizeof(suffix[1]));
    }

    printf("%lld\n", prefix[0][n]);

    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


Measured memory_bytes: 69120
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
	int n, k, x;
	scanf("%d %d", &n, &k);
	vector<ll> e, ne;
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		e.push_back(x);
		if (i) e[i] += e[i - 1];
	}
	ll pre = 0, pat = 0;
	for (int i = 0; i < n; pre = e[i++])
		for (int j = i; j < n; j++)
			ne.push_back(e[j] - pre);
	for (ll b = 1LL << 60; b; b >>= 1) {
		pat += b;
		e.clear();
		for (int i = 0; i < ne.size(); i++)
			if ((ne[i] & pat) == pat)
				e.push_back(ne[i]);
		if (e.size() < k) pat -= b;
		else ne = e;
	}
	cout << pat << endl;
}

Measured memory_bytes: 6524