akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int X, A, B;
   cin >> X >> A >> B;
   if (A - B >= 0) cout << "delicious" << endl;
   else if (B - A <= X) cout << "safe" << endl;
   else cout << "dangerous" << endl;
   return 0;
}


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

int main(){
  int h,w; cin>>h>>w;
  int count=0;
  vector<string> s(h);
  for(int i=0;i<h;i++){
    string str; cin>>str;
    bool flag=false;
    for(int j=0;j<w;j++){
      if(str[j]=='#'){
        flag = true;
        break;
      }
    }
    if(flag){
      s[count]=str;
      count++;
    }
  }
  vector<int> skip;
  for(int i=0;i<w;i++){
    for(int j=0;j<count;j++){
      if(s[j][i]=='#') break;
      if(j==count-1) skip.push_back(i);
    }
  }
  for(int i=0;i<count;i++){
    for(int j=0;j<w;j++){
      bool flag = true;
      for(int k=0;k<skip.size();k++){
        if(skip[k]==j) flag=false;
      }
      if(flag) cout<<s[i][j];
    }
    cout<<endl;
  }
}

Measured memory_bytes: 256
n = int(input())
s = input()

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1

print(ans)

Measured memory_bytes: 3064
A,V = list(map(int,input().split()))
B,W = list(map(int,input().split()))
T = int(input())

if A<B:
    if A+T*V >= B+T*W:
        print("YES")
    else:
        print("NO")
elif A>B:
    if A-T*V <= B-T*W:
        print("YES")
    else:
        print("NO")
else:
    print("YES")

Measured memory_bytes: 61860
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef long long int lli;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

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

int h, w, k;
vector<string> s;
int ans;

void dfs(vector<int> hUse, vector<int> wUse, int n){
    if (hUse.size() + wUse.size() == h + w){
        int sum = 0;
        rep(i, h) rep(j, w){
            if (hUse[i] == 1) continue;
            if (wUse[j] == 1) continue;
            if (s[i][j] == '#') sum++;
        }
        if (sum == k) ans++;
        return;
    }

    if (hUse.size() < h){
        hUse.push_back(0);
        dfs(hUse, wUse, n+1);
        hUse.back()++;
        dfs(hUse, wUse, n+1);
        hUse.pop_back();
    } else{
        wUse.push_back(0);
        dfs(hUse, wUse, n+1);
        wUse.back()++;
        dfs(hUse, wUse, n+1);
        wUse.pop_back();
    }
}

int main(){
    cin >> h >> w >> k;
    s.resize(h);
    rep(i,h) cin >> s[i];
    vector<int> hUse, wUse;
    ans = 0;
    dfs(hUse, wUse, 0);
    cout << ans << endl;
}

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    
    int h, w, n;
    cin >> h >> w >> n;
    
    int tab[h][w];
    
    int x = 0, y = 0;
    int dir = 1;
    
    FOR(i,1,n) {
        int cnt;
        cin >> cnt;
        
        while (cnt--) {
            tab[x][y] = i;
            
            if (y + dir >= 0 && y + dir < w) {
                y += dir;
            } else {
                x++;
                dir *= -1;
            }
        }
    }
    
    FOR(i,0,h-1) FOR(j,0,w-1) {
        cout << tab[i][j] << " \n"[j == w-1];
    }

    return 0;
}

/*************************************************************************/


Measured memory_bytes: 384
import java.util.*;
import java.util.stream.*;

public class Main {

	public static void main(String[] args){
		
		// 方針：タブーリスト付きの深さ優先探索、この手に限る
		
		// 隣接行列、0か1なのでbooleanで十分
		boolean[][] adjacencyMatrix = createAdjacencyMatrix();
		int n= adjacencyMatrix.length;
		// 訪問履歴、タブーリスト
		boolean[] history = new boolean[n];
		// 1番のノード（インデックスの0）から探索を始めるよ
		history[0] = true;
		int eulerianTrailNum = traverseAndCountEulerianTrail(0, adjacencyMatrix, history);
		System.out.println(eulerianTrailNum);
		
	}
	
	// 入力から隣接行列を作る
	public static boolean[][] createAdjacencyMatrix(){
		
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int m = scan.nextInt();
		
		boolean[][] ret = new boolean[n][n];
		
		IntStream.range(0, m)
			.forEach(nouse -> {
				// 配列の番号じゃなくて、ノード番号で渡されるので-1
				int p = scan.nextInt() - 1;
				int q = scan.nextInt() - 1;
				ret[p][q] = true;
				ret[q][p] = true;
			});
		
		scan.close();
		return ret;
		
	}
	
	// 再帰して探索
	public static int traverseAndCountEulerianTrail(int currentNode, boolean[][] adjacencyMatrix, boolean[] history) {
		
		int n = history.length;
		if(IntStream.range(0, n).boxed()
				// 自分以外行ったことある？
				.filter(index -> index != currentNode).allMatch(index -> history[index])) {
			// ここがゴールだったみたいです。1本見つけましたよ
			return 1;
		}
		
		// 自分に行ったしるしをつける
		history[currentNode] = true;
		
		// ゴールじゃなかったので再帰して木探索してきてね
		int ans  = IntStream.range(0, n)
						// 隣接してて、行ったことのないところに行きたい
						.filter(index -> adjacencyMatrix[currentNode][index] && history[index] == false)
						// 再帰していってきます
						.map(index ->  traverseAndCountEulerianTrail(index, adjacencyMatrix, history))
						.sum();
		
		// この順番で自分に来るパターンは探索し終えたので忘れる
		history[currentNode] = false;
		
		return ans;
		
	}

}


Measured memory_bytes: 47988
import sys

input = sys.stdin.readline
k = int(input())
num = 7%k
soln = False
for i in range(1, k+1):
    if num == 0: print(i); soln = 1; break
    num = ((((num%k) * (10%k))%k) + (7%k))%k
if not soln: print(-1)
    

        


Measured memory_bytes: 9140
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

void print(string str, int a, int b)
{
	for (int i = a; i <= b; i++)
	{
		cout << str[i];
	}
	cout << endl;
}

void replace(string &str, int a, int b, string p)
{
	str = str.substr(0, a) + p + str.substr(b + 1, str.size() - b);
}



void reverse(string &str, int a, int b)
{
	string str3 = str.substr(a, b - a + 1);
	reverse(str3.begin(), str3.end());
	str = str.substr(0, a) + str3  + str.substr(b + 1, str.size() - b);
}

int main()
{
	string str;
	string command,str2;
	int a,b,c;
	cin >> str>>c;
	for (int i = 0; i < c; i++)
	{
		cin >> command;
		if (command == "print")
		{
			cin >> a >> b;
			print(str, a, b);
			
		}
		if (command == "replace")
		{
			cin >> a >> b >> str2;
			replace(str, a, b, str2);
		}
		if (command == "reverse")
		{
			cin >> a >> b;
			reverse(str, a, b);
		}
	}
}
	



Measured memory_bytes: 3204
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val s = next()
    val K = nextInt()
    val set = HashSet<String>()
    for (i in s.indices) {
        for (j in 1..K) {
            if (i + j > s.length) break
            set.add(s.substring(i, i + j))
        }
    }
    println(set.sorted()[K - 1])
}

Measured memory_bytes: 42600
#include<iostream>
#include<algorithm>
using namespace std;
static const int N=100;
int main(){
 int n,p[N+1],m[N+1][N+1];
 cin>>n;
 for(int i=1;i<=n;i++)cin>>p[i-1]>>p[i];
 for(int i=1;i<=n;i++)m[i][i]=0;
 for(int l=2;l<=n;l++){
  for(int i=1;i<=n-l+1;i++){
   int j=i+l-1;
   m[i][j]=(1<<21);
   for(int k=i;k<=j-1;k++){
    m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]);
   }
  }
 }
 cout<<m[1][n]<<endl;
 return 0;
}


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

int main(){
  int N,MX,X=0;
  int counter=1;
  int i=0;
  cin>>N>>MX;
  vector<int> hop(N);

  while(N>i){
    cin>>hop.at(i);
    i++;
  }
  i=0;
  while(N>i){
    X+=hop.at(i);
    if(MX>=X){
      counter++;
    }
    i++;
  }
  cout<<counter;




  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define dec(i, n)  decID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
#define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__);
void IN_() { };
template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); };
template<typename T> void OUT(T && a) { cout << a << endl; }
template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); }

// ---- ----

int main() {
	IN(int, n);
	printf("%.9f\n", n * n * n / 27.0);
}


Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
#include <vector>
//#include <unordered_map>
//#include <string>
//typedef long long LL;
//typedef long double LD;
using namespace std;

//#define MOD 1000000007

int main() {
    int s;
    vector<int> a;
    int tmp_a;
    int ans=0;
    bool done=false;

    cin >> s;
    a.push_back(s);
    while(true){
        if(a[ans]%2==0){
            tmp_a = a[ans]/2;
        }else{
            tmp_a = 3*a[ans]+1;
        }
        a.push_back(tmp_a);
        ans++;
        for(int i=0; i<ans; i++){
            if(tmp_a==a[i]){
                done=true;
                break;
            }
        }
        if(done){
            break;
        }
    }
    ans++;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,sum;
    cin>>n;
    sum=0;
    for(long long int i=1; i<=n; i++)
    {
        if((i%3!=0&&i%5!=0)&&(i%3!=0)&&(i%5!=0))
            sum+=i;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3584
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	// ABC059
	string a, b, c;
	cin >> a >> b >> c;

	// 減量中
	//cout<<(char)toupper(a[0])<<(char)toupper(b[0])<<(char)toupper(c[0])<<endl;
	//cout<<(char)(a[0]-0x20)<<(char)(b[0]-0x20)<<(char)(c[0]-0x20)<<endl;
	//cout<<(char)(a[0]-' ')<<(char)(b[0]-' ')<<(char)(c[0]-' ')<<endl;
	printf("%c%c%c\n",a[0]-' ',b[0]-' ',c[0]-' ');
	return 0;
}


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

constexpr int mod = 1000000007;

int N, X, Y, Z;
int dp[44][1 << 17 + 1] = {};
int main()
{
	cin >> N >> X >> Y >> Z;
	int bitsize = 1 << (X + Y + Z);
	int mask = (1 << (Z - 1)) | (1 << (Z + Y - 1)) | (1 << (X + Y + Z - 1));
	
	dp[0][0] = 1;
	for ( int i = 0; i < N; i++ ) {
		for ( int bit = 0; bit < bitsize; bit++ ) {
			for ( int j = 1; j <= 10; j++ ) {
				int nbit = ((bit << j) | (1 << (j - 1))) & (bitsize - 1);
				if ( (nbit & mask) == mask ) {
					(dp[i + 1][bitsize] += dp[i][bit]) %= mod;
				} else {
					(dp[i + 1][nbit] += dp[i][bit]) %= mod;
				}
			}
		}
		dp[i + 1][bitsize] = (dp[i + 1][bitsize] + (long long)dp[i][bitsize] * 10) % mod;
	}
	
	cout << dp[N][bitsize] << endl;

	return ( 0 );
}


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


void solve(long long N, std::vector<std::vector<long long>> A){
    ll ans = 0;
    for(ll i=0; i< N; i++){
        ll cnt =0;
        for(ll j=0; j<=i; j++){
            cnt += A[0][j];
        }
        for(ll j=i; j<N; j++){
            cnt += A[1][j];
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<std::vector<long long>> A(2, std::vector<long long>(N));
    for(int i = 0 ; i < 2 ; i++){
        for(int j = 0 ; j < N ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    solve(N, std::move(A));
    return 0;
}


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

void Main()
{
    int n, m;
    cin >> n >> m;
    vector<pair<long, int>> h;
    vector<int> h2(1);
    vector<vector<int>> p(n+1); //i番目の展望台がつながっている先の一覧
    for (int i = 0; i < n; i++)
    {
        int height;
        cin >> height;
        h.push_back(make_pair<long, int>(height, i+1));
        h2.push_back(height);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        p[a].push_back(b);
        p[b].push_back(a);
    }

    int n_good = 0;
    vector<int> del(n+1);
    sort(h.rbegin(), h.rend());
    for (int i = 0; i < n; i++)
    {
        if(del[h[i].second] == 0){
            del[h[i].second] = 1;
            int good = 1;
            for (auto j: p[h[i].second])
            {
                if(h[i].first <= h2[j]){
                    good = 0;
                }
                del[j] = 1;
            }
            n_good += good;
        }
    }
    
    cout << n_good << endl;
}

int main(int argc, char **argv)
{
    Main();
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

ll f(ll n, ll r){
	ll res1 = 1;
	repr(i,n,n-r+1){
		res1 *= ll(i);
		res1 %= mod;
	}

	ll res2 = 1;
	repi(i,1,r+1){
		res2 *= ll(i);
		res2 %= mod;
	}
	return (res1 * power(res2, mod-2))%mod;
}

int main()
{
	ll n,a,b;
	cin>>n>>a>>b;
	cout<<(power(2LL,n) - f(n,a) - f(n,b) - 1 + 10*mod) % mod<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String[] s = scanner.nextLine().split(" ");
        int m = Integer.MAX_VALUE;
        for (int i = 0; i < s.length; i++) {
            int a = Integer.parseInt(s[i]);
            int b = 0;
            while (a % 2 == 0) {
                b++;
                a /= 2;
            }
            if (b < m) {
                m = b;
            }
            if (b == 0) {
                break;
            }
        }

        System.out.println(m);
        scanner.close();
    }
}


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

int main()
{
	int r, c;
	cin >> r >> c;
	vector<vector<int>> v(r + 1, vector<int>(c + 1, 0));
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> v[i][j];
			cout << v[i][j] << " ";
		}
		v[i][c] = accumulate(v[i].begin(), v[i].end(), 0);
		cout << v[i][c] << endl;
	}
	for (int i = 0; i < c + 1; i++)
	{
		int acc = 0;
		for (int j = 0; j < r; j++)
		{
			acc += v[j][i];
		}
		string s = (i == c) ? "\n" : " ";
		cout << acc << s;
	}
	return 0;
}

Measured memory_bytes: 3232
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
bool marked[MAXN];
long long a[MAXN];
vector<long long> v;
int main()
{
  int n;
  cin >> n;
  long long t = 0;
  for(int i = 0;i < n;i ++)
  {
    cin >> a[i];
    t ^= a[i];
    v.push_back(a[i] ^ (a[i] - 1));
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin() , v.end()) - v.begin());
  reverse(v.begin() , v.end());
  int cnt = 0;
  for(int i = 0;i < (int)v.size(); i ++)
  {

    int lst = 0;
    while(lst < 32 && (v[i] & (1 << lst)))
      lst ++;
    lst --;

    if(t & (1 << lst))
    {
      t ^= v[i];
      cnt ++;
    }
  }

  if(t == 0)
    cout << cnt << endl;
  else
    cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 2040
#include <iostream>
#include <string>
#include <vector> 
using namespace std;
 
int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  
  vector<int> sum(S.size()+1, 0);
  // 0 0 1
  for(int i = 1; i < S.size(); i++)
    sum[i+1] = sum[i] + (S[i-1] == 'A' && S[i] == 'C');
  
  while(Q--) {
    int l, r;
    cin >> l >> r;
    cout << sum[r] - sum[l] << "\n";
  }
  return 0;
}

Measured memory_bytes: 1472
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
ll  n, k;
int main(){
    string s;
    while(cin>>s>>k){
        ll ans=0;
        n=s.length();
        s.append(s);
        bool l=1;
        for(ll i=0; i+1<n; ++i){
            if(s[i]!=s[i+1]){
                l=0;
            }
        }
        vector <ll> v[111];
        ll tmp;
        for(ll i=0; i<n; ++i){
            tmp=i;
            while(s[tmp]==s[tmp+1]){
                ++tmp;
            }
//            assert(tmp+1<n*2);
            v[i].push_back(tmp-i+1);
            i=tmp;
        }
        bool f=0;
        for(ll i=0; i<n; ++i){
            if(v[i].size()==0)
                continue;
//            cout<<i<<" "<<v[i][0]<<endl;
            if(v[i][0]+i-1>=n){
                f=1;
                ans+=(k-1)*(v[i][0]/2);
            }
            else{
                if(i==0){
                }
                else{
                    ans+=(v[i][0]/2)*(k);
                }
            }
        }
        tmp=n-1;
        while(tmp>0&&s[tmp]==s[tmp-1]){
            --tmp;
        }
        if(f){
            ans+=v[0][0]/2;
            ans+=(n-tmp)/2;
        }
        else{
            ans+=v[0][0]/2*k;
        }
        if(l){
            ans=n*k/2;
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 256
//Linear Search
#include <iostream>

using namespace std;

bool search(int S[], int n, int key) {
    int i = 0;
    while(i < n) {
        if(S[i] == key) break;
        i++;
    }
    return i != n;
}

int main() {
    int n, q;
    cin >> n;
    int S[n];
    for(int i=0; i<n; i++) cin >> S[i];
    cin >> q;

    int cnt = 0;
    for(int i=0; i<q; i++) {
        int t;
        cin >> t;
        if(search(S, n, t)) cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3080
a,b,c,d = list(map(int, input().split()))

i = 0
while True:
    if i % 2 == 0:
        c = c - b
    else:
        a = a - d
    if a <= 0:
        print("No")
        exit()
    if c <= 0:
        print("Yes")
        exit()
    i += 1

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    copy_n(istream_iterator<int>(cin), n, A.begin());

    int ma = 0;
    int64_t ans = 0;
    for (const auto &a: A){
        ans += max(0, ma - a);
        ma = max(ma, a);
    }

    cout << ans << endl;
}

Measured memory_bytes: 4044
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<string>
#include<cstdlib>
#include<cctype>
#include<unordered_map>
#include<sstream>
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1LL << 60;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
};
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------

int main(){
  string S;
  cin >> S;
  ll K;
  cin >> K;
  int cnt = 0;
  int num;
  for(int i=0; i<S.size(); i++){
    if(S[i] == '1'){
      cnt++;
    }else{
      num = S[i] - '0';
      break;
    }
  }
  if(K <= cnt){
    cout << 1 << endl;
  }else{
    cout << num << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll
#define INF 1e16
#define mod 1000000007
int main(){
    double n,k;
    cin>>n>>k;
    double ans = 0;
    rep(i,n){
        double num = i+1;
        if(num>=k) ans+=1;
        else {
            double cnt = 1;
            while(num<k) {
                cnt*=0.5;
                num*=2;
            }
            ans += cnt;
        }
    }
    cout<<std::setprecision(12)<<ans/n<<endl;
    return 0;
}

Measured memory_bytes: 256
# ABC121C - Energy Drink Collector
import sys
input = sys.stdin.readline

def main():
    n, m = list(map(int, input().rstrip().split()))
    lst = sorted(list(map(int, input().split())) for _ in range(n))
    ans = 0
    for i in lst:
        while i[1] > 0 and m > 0:
            ans += i[0]
            i[1] -= 1
            m -= 1
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 27812
N = int(input())
H = list(map(int,input().split()))

maxh = 10 ** 10
for i in range(len(H) - 1, -1, -1):
  if H[i] > maxh + 1:
    print("No")
    break
  if H[i] == maxh + 1:
    maxh = H[i] - 1
  else:
    maxh = H[i]
else:
  print("Yes")


Measured memory_bytes: 20656
use proconio::{fastout, input};
use std::collections::{HashMap, HashSet};

fn trial_division(mut n: usize) -> HashMap<usize, usize> {
    let mut primes = HashMap::new();
    let mut i = 2;

    //  n を root n 以下の整数で割り切れるまで割っていく
    while i * i <= n {
        while n % i == 0 {
            n /= i;
            if primes.contains_key(&i) {
                let x = primes.get_mut(&i).unwrap();
                *x += 1;
            } else {
                primes.insert(i, 1);
            }
        }
        i += 1;
    }

    // 最後にnが素数になっている場合はそれ自身も素因数に含めて終了
    if n > 1 {
        if primes.contains_key(&n) {
            let x = primes.get_mut(&n).unwrap();
            *x += 1;
        } else {
            primes.insert(n, 1);
        }
    }
    primes
}

#[fastout]
fn main() {
    input! {
        a: usize,
        b: usize,
    }

    println!(
        "{}",
        trial_division(a)
            .keys()
            .cloned()
            .collect::<HashSet<_>>()
            .intersection(&trial_division(b).keys().cloned().collect::<HashSet<_>>())
            .count()
            + 1
    );
}


Measured memory_bytes: 2140
/* In the name of Allah */

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

// const int INF = 20000000;

#define ll long long
#define _SetBit(A, k) (A[(k / 32)] |= (1 << (k % 32)))
#define _ClearBit(A, k) (A[(k / 32)] &= ~(1 << (k % 32)))
#define _CheckBit(A, k) (A[(k / 32)] & (1 << (k % 32)))
#define SetBit(x, k) (x |= (1 << k))
#define ClearBit(x, k) (x &= ~(1 << k))
#define CheckBit(x, k) (x & (1 << k))

int main()
{
  unsigned ll n, k;
  cin >> n >> k;
  while (n > k)
  {
    n = n % k;
  }

  if (n < k - n)
    cout << n << "\n";
  else
    cout << k - n << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

int main(int argc, const char *argv[])
{
  int n;
  cin >> n;

  using pint = pair<int, int>;
  auto compare = [](pint &a, pint &b) { return b.second < a.second; };
  priority_queue<pint, vector<pint>, decltype(compare)> jobs(compare);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    jobs.push(make_pair(a, b));
  }
  
  int t = 0;
  string ans = "Yes";
  while (!jobs.empty()) {
    auto &job = jobs.top();
    t += job.first;
    if (t > job.second) {
      ans = "No";
      break;
    }

    jobs.pop();
  }

  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 2420
#include<stdio.h>

int main(void){
  int h,w;
  int i,j;



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


  return 0;
}

Measured memory_bytes: 1776
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

N=intput()
xy=[]
wa=[]
sa=[]
for i in range(N):
    x,y=mint()
    wa.append(x+y)
    sa.append(x-y)
print(max(max(wa)-min(wa), max(sa)-min(sa)))

Measured memory_bytes: 102908
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> proc(string s) {
  deque<char>dq;
  for(auto c : s) {
    if(c == ' ')continue;
    if(c == '(' || dq.empty())dq.push_back(c);
    else if(c == ')') {
      if('(' == dq.back())dq.pop_back();
      else dq.push_back(c);
    }
  }
  pair<long long, long long> ans(0, 0);
  while(!dq.empty()) {
    if(dq.front() == ')')ans.first++;
    else ans.second++;
    dq.pop_front();
  }
  return ans;
}
void solve() {
  int n;
  string s;
  cin >> n;
  vector< pair<long long, long long> >lf, rg, mid;
  cin.ignore();
  for(int i = 0; i < n; ++i) {
    getline(cin, s);
    pair<long long, long long>p = proc(s);
    if(p.first > 0 && p.second > 0)mid.push_back(p);
    else if(p.first > 0)rg.push_back(p);
    else if(p.second > 0) lf.push_back(p);
  }
  long long ll = 0;
  for(auto x : lf)ll += x.second;
  sort(mid.begin(), mid.end(), [&](auto p1, auto p2) {
    long long diff1 = p1.second - p1.first;
    long long diff2 = p2.second - p2.first;
    if(diff1 >= 0 && diff2 < 0)return true;
    if(diff2 >= 0 && diff1 < 0)return false;
    if(diff1 >= 0 && diff2 >= 0) {
      return p1.first < p2.first;
    }
    return p1.second > p2.second;

    if(p1.first != p2.first) return p1.first < p2.first;
    else return p1.second > p2.second; 
  });
  for(auto x : mid) {
    if(ll < x.first) {
      cout << "No\n";
      return;
    }
    ll-=x.first;
    ll+=x.second;
  }
  for(auto x : rg) {
    if(ll < x.first) {
      cout << "No\n";
      return;
    }
    ll-= x.first;
  }
  if(ll == 0)cout << "Yes\n";
  else cout << "No\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tc = 1;
  // cin >> tc;
  for(int i = 1; i <= tc; ++i) {
    // cout << "Case #" << i <<": ";
    solve();
  }
  return 0;
}

Measured memory_bytes: 19060
#後方一致文字数を探索
def count_substr(s1, s2):
    s2_length = len(s2)
    for i in range(s2_length):
        substr = s2[0:(s2_length - i)]
        if s1.endswith(substr):
            return (len(substr))
    return 0

#文字列を取得
s = input()
t = input()

#部分一致文字数を探索
match_count = count_substr(s, t)

is_match = False
#後方一致が見つかった場合
if match_count > 0:
    #文字列を回転
    slice  = len(s) - match_count
    s = s[slice:] + s[0:slice]
    is_match = (s == t)

#出力
print("Yes" if is_match else "No")

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;
typedef long double ld;


int main(){
  ll n;
  cin >> n;
  set <string> s;
  for (ll i = 0; i < n; i++)
  {
    string temp;
    cin >> temp;
    s.insert(temp);
  }
  cout << s.size();

    
  
}

Measured memory_bytes: 19140
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
//return x's prime factor as map
map<ll,ll> primefactor(ll x){
  ll nn = x;
  map<ll,ll> res;
  for(ll i=2;i*i<=nn;++i){
    while(nn%i==0){
      res[i]++;
      nn /= i;
    }
  }
  if(nn!=1) res[nn] = 1;
  return res;
}

int main()
{
  ll n; cin >> n;
  map<ll,ll> mp = primefactor(n);

  ll cnt = 0;
  for(auto m: mp) {
    ll x = m.second;
    ll y = 1;
    while(x > 0) {
      x -= y;
      if(x < 0) break;
      y++;
      cnt++;
    }
  }
  cout << cnt << "\n";
  return 0;
}


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str;
 
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define endl '\n'
 
const ll MOD = 1000000007;

int main() {
   int n; scanf("%d", &n);
   vector<ll> a(n);
   for (ll &i : a)
      scanf("%lld", &i);
   ll ans = 0;
   for (ll i : a) {
      ans += i;
      ans = ans % MOD;
   }
   ans *= ans;
   ans = ans % MOD;
   for (ll i : a) {
      ans -= i * i;
      if (ans < 0) {
         ll temp = (-ans + MOD - 1) / MOD;
         ans += temp * MOD;
      }
      ans = ans % MOD;
   }
   ans *= 500000004;
   ans = ans % MOD;
   printf("%lld", ans);
   return 0;
}

Measured memory_bytes: 4852
from itertools import accumulate as r;n,k=map(int,input().split());m=10**9+7;j=int(n**0.5);c=[n//(i+1)-n//(i+2) for i in range(n//(j+1))]+[1]*j;x=c;exec("x=[(y*d)%m for y,d in zip(r(x[::-1]),c)];"*k);print(x[-1])

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

#define all(s) s.begin(), s.end()
#define vi vector<int>
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second

const int N = 200005;
const int MOD = 1000000007;

int dp[N], c[N];
vi v[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        v[c[i]].pb(i);
        if (v[c[i]].size() == 1) {
            dp[i] = dp[i - 1];
            continue;
        }
        int u = v[c[i]][v[c[i]].size() - 2];
        if (u == i - 1) {
            dp[i] = dp[u];
        } else {
            dp[i] = (dp[i - 1] + dp[u]) % MOD;
        }
    }
    cout << dp[n];
    return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long int ll;
typedef unsigned long long int ull;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c;
  double p=3.141592;
  string s,t;
  cin >>a;
  cout <<(double)(a)*2*p;
}

Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> par;
int read(){
	int x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int fa[1000005];
map <par,int>m,a;
multiset<int>s[100005];
queue<par>q;
par makep(int x,int y){
	if (x>y) return par(y,x);
	else return par(x,y);
}
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}
int main(){
	int n=read();
	for (int i=1;i<=2*n-2;i++){
		int u=read(),v=read();
		par w=makep(u,v);
		m[w]++; 
		if (m[w]>1&&a[w]==0){
			a[w]=1; q.push(w);
		}
		if (i<=n) fa[i]=i; 
		s[v].insert(u); s[u].insert(v);
	}
	for (int k=1;k<n;k++){
		int x,y;
		while (1){
			if (q.empty()){printf("NO\n"); return 0;}
			par w=q.front(); q.pop();
			x=find(w.first); y=find(w.second);
			if (x!=y) break;
		}
		if (s[x].size()>s[y].size()) swap(x,y);
		fa[x]=y;
		for (set<int>::iterator i=s[x].begin();i!=s[x].end();i++){
			int v=find(*i);
			if (v==y) continue;
			par z=makep(v,y);
			m[z]++; 
			if (m[z]>1&&a[z]==0){
				q.push(z); a[z]=1;
			}
			s[v].erase(s[v].find(x)); s[y].insert(v); s[v].insert(y);
		}
		s[y].erase(x);
		s[x].clear();
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 42240
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N = in.nextInt
  val K = in.nextLong
  val As = Array.fill(N)(in.nextInt - 1)
  val visited = Array.fill(N)(0)

  def teleport(pos: Int, step: Int): Int = {
    val next = As(pos)
    if (step == K) next
    else if (visited(next) == 0) {
      visited(next) = step + 1
      teleport(next, step + 1)
    } else {
      val diff = step + 1 - visited(next)
      val remain = (K - step) % diff
      def find(p: Int, r: Int): Int = if (r == 0) As(p) else find(As(p), r - 1)
      find(pos, remain.toInt)
    }
  }

  println(teleport(0, 1) + 1)
}

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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    int n = s.size();
    ll cnt = 0LL;
    ll m = 0;
    vector<int> widx;
    for(int i = 0; i < n; ++i){
        if(s[i] == 'W'){
            widx.push_back(i);
        }
    }

    for(int i = 0; i < widx.size(); ++i){
        cnt += widx[i] - m;
        m++;
    }

    ppp(cnt);


    return 0;
}


Measured memory_bytes: 1552
import math

while True:
    list = input().split()
    if list[1] == "?":
        break
    else:
        a = int(list[0])
        op = list[1]
        b = int(list[2])

    if op == "+":
        print(a + b)
    elif op == "-":
        print(a - b)
    elif op == "*":
        print(a * b)
    else:
        print(math.floor(a / b))
    

    


Measured memory_bytes: 5660
N = int(input())
S = input()

cum_sum_b = [0]
cum_sum_w = [0]

sum_b = 0
sum_w = 0
for i, s in enumerate(S):
    if s == '#':
        sum_b += 1
    else:
        sum_w += 1
    cum_sum_b.append(sum_b)
    cum_sum_w.append(sum_w)

ans = N
for i in range(0, len(S) + 1):
    count = cum_sum_b[i] + cum_sum_w[len(S)] - cum_sum_w[i]
    ans = min(ans, count)

print(ans)

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

long long calc(int n, int c1, int c2, int s1, int s2, const vector<int>& options,
               int d, int nt, int ot) {
  int b1(d-1), a1(d+1), b2(d-1), a2(d+1);
  while (b1 >= 0 && options[b1] != nt) b1--;
  while (b2 >= 0 && options[b2] != ot) b2--;
  while (a1 < n && options[a1] != nt) a1++;
  while (a2 < n && options[a2] != ot) a2++;
  int x1(d-b1), y1(a1-d), z1(y1-x1), x2(d-b2), y2(a2-d), z2(y2-x2);
  int diff1 = z1*(z1-1)/2-x1*(x1-1)/2-y1*(y1-1)/2;
  int diff2 = z2*(z2-1)/2-x2*(x2-1)/2-y2*(y2-1)/2;
  return (long long) diff1 * c1 - (long long) diff2 * c2 + s1 - s2;
}

int main() {
  int n;
  cin >> n;
  vector<int> c(26);
  vector<array<int, 26>> s(n);
  
  vector<int> last(26, -1);
  
  for (int i = 0; i < 26; ++i)
    cin >> c[i];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < 26; ++j)
      cin >> s[i][j];
  
  long long total(0);
  vector<int> options(n);
  
  for (int i = 0; i < n; ++i) {
    int neg(0), test(-1);
    for (int j = 0; j < 26; ++j) {
      neg -= c[j] * (i - last[j]);
    }
    
    int max_score = -1e9;
    for (int j = 0; j < 26; ++j) {
      int ss = s[i][j] + neg + c[j] * (i - last[j]);
      if (ss > max_score) {
        max_score = ss;
        test = j;
      }
    }
    total += max_score;
    options[i] = test;
    last[test] = i;
  }
  
  for (int t = 1; t <= 500; ++t) {
    for (int dd = n - 1; dd >= 0; --dd) {
      for (int tt = 25; tt >= 0; --tt) {
        if (tt == options[dd]) continue;
        int ot = options[dd];
        long long ns = calc(n, c[tt], c[ot], s[dd][tt], s[dd][ot],
                            options, dd, tt, ot);
        //cout << ns << endl;
        if (ns > 0) {
          total += ns;
          options[dd] = tt;
    	}
      }
    }
  }
  for (const int& i: options) cout << i + 1 << endl;
  
  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;

int main()
{
    int D;
    long long G;
    int p[10];
    long long c[10];
    long long sum[10];
    long long ans = 10000000;
    
    cin >> D >> G;
    for (int i = 0;i < D;i++){
        cin >> p[i] >> c[i];
        sum[i] = 100*(i+1)*p[i] + c[i];
    }
    
    for (int i = 0;i < (1<<D);i++){
        long long res = 0;
        long long pre = 0;
        for (int j = 0;j < D;j++){
            if ((i>>j)%2){
                res += sum[j];
                pre += p[j];
            }
        }
        if (res < G){
            for (int j = D-1;j >= 0;j--){
                if ((i>>j)%2==0){
                    for (int k = 0;k < p[j]-1;k++){
                        res += 100*(j+1);
                        pre++;
                        if (res >= G){
                            goto EXIT;
                        }
                    }
                }
            }
        }
        EXIT:
        if(res >= G){
            ans = min(ans,pre);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3640
import java.util.*;
public class Main {
	Scanner sc = new Scanner(System.in);
	int n, k;
	int[] w;
	int ans;
	
	//入力
	public void input() {
		n = sc.nextInt();
		k = sc.nextInt();
		w = new int[n];
		for(int i=0; i<n; i++) { w[i] = sc.nextInt(); }
		ans = solve();
	}
	
	public int solve() {
		int left = 0;
		//荷物の個数*1個あたりの最大重量
		int right = 100000 * 10000;
		int mid;
		
		while(right-left > 1) {
			mid = (left+right) / 2;
			//mid == pを決めて何個積めるかチェック
			int v = check( mid );
			if(v >= n) right = mid;
			else left = mid;
		}
		return right;
	}
	
	//最大積載量pのk台のトラックえ何個の荷物を積めるか？
	public int check(int p) {
		int i = 0;
		for(int j=0; j<k; j++) {
			int s = 0;
			while(s+w[i] <= p) {
				s += w[i];
				i++;
				if(i == n) return n;
			}
		}
		return i;
	}
	
	public void output() {
		//答えの出力
		System.out.println( ans );
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.input();
		obj.output();
	}
}



Measured memory_bytes: 71480
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define PI 3.14159265358979323846
const int MOD = 1e9 + 7 ;
const int EPS = 1e-9;
int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N=201010;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 
      int n;
      cin>>n;
      string a[n];
      int ans=0,ans1=0;
      
      for(int i=0;i<n;i++)
      {
            cin>>a[i];
            for(int j=0;j<(int)a[i].length()-1;j++)
            {
                  if(a[i][j]=='A'&&a[i][j+1]=='B') ans++,ans1++; 
            }
      }
      int cnt1=0,cnt2=0,cnt3=0;
      for(int i=0;i<n;i++)
      {
            if(a[i][0]=='B'&&a[i][(int)a[i].length()-1]=='A') cnt1++;
            else if(a[i][(int)a[i].length()-1]=='A') cnt2++;
            else  if(a[i][0]=='B') cnt3++;

      }
      if(cnt1>0) ans1+=cnt1-1;
      if(cnt1>0)
      {
            if(cnt2>0) ans1++;
            if(cnt3>0 ) ans1++;
            ans1+=min(cnt2-1,cnt3-1);
      }
      if(cnt1>0) ans+=cnt1-1;
      int mn=min(cnt2,cnt3);
      ans+=mn;
      cnt2-=mn;
      cnt3-=mn;
      if(cnt1>0&&(cnt2>0||cnt3>0)) ans++;
      cout<<max(ans,ans1);
} 

// B...A
// A... B
// A....
// ....B
// B...
// ....A
// .....
// B..A B..A B..A ....
// B...A
// ...A B..A B....

Measured memory_bytes: 768
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int N = 1000;

int lcs(string X, string Y) {
	int c[N + 1][N + 1];
	int m = X.size();
	int n = Y.size();
	int maxl = 0;
	X = " " + X;
	Y = " " + Y;
	for(int i = 0; i <= m; i++) c[i][0] = 0;
	for(int j = 0; j <= n; j++) c[0][j] = 0;
	
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= n; j++) {
			if(X[i] == Y[j]) {
			c[i][j] = c[i - 1][j - 1] + 1;
		} else {
			c[i][j] = max(c[i - 1][j], c[i][j - 1]);
		}
		maxl = max(maxl, c[i][j]);
	    }
	}
	
	return maxl;
}  

int main() {
	string s1, s2;
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
	    cin >> s1 >> s2;
		cout << lcs(s1, s2) << endl;  
	}
	
	return 0;
}

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

using namespace std;


int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int num;
  cin >> num;
  unsigned long long int arr[num], ans = 1;
  bool zero = false, over = false;
  for (int i = 0; i < num; i++){
    cin >> arr[i];
    if (arr[i] == 0){
      zero = true;
      cout << '0' << '\n';
      break;
    }
  }
  if (!zero){
    for (int i = 0; i < num; i++){
      if (arr[i] > 1000000000000000000 / ans){
	cout << "-1" << '\n';
	over = true;
	break;
      }
      else
	ans *= arr[i];
    }
    if (!over)
      cout << ans << '\n';
  }
  return 0;
}


Measured memory_bytes: 4404