akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include<bitset>
#include <utility>
using namespace std;
#define rank rankk
#define mp make_pair
#define pb push_back
#define xo(a,b) ((b)&1?(a):0)
//#define LL ll
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,int> pli;
const int INF=0x3f3f3f3f;
const ll INFF=0x3f3f3f3f3f3f3f3fll;
//#define xs1 xs
//#define xs2 x
//const ll M=1e9+7;
//const ll maxn=2e5+7;
//const int MAXN=1005;
const int MAX=2e3+5;
const int MAX_N=MAX;
//const int N=55;
const ll MOD=1000000007;
const long double pi=acos(-1.0);
//const double eps=0.00000001;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
template<typename T>inline T abs(T a) {return a>0?a:-a;}
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
inline ll powMM(ll a,ll b,ll M){
    ll ret=1;
    a%=M;
//    b%=M;
    while (b){
        if (b&1) ret=ret*a%M;
        b>>=1;
        a=a*a%M;
    }
    return ret;
}
void open()
{
    freopen("1009.in","r",stdin);
    freopen("out.txt","w",stdout);
}
char a[MAX],b[MAX];
int l[MAX],r[MAX],len,an,cnt,tem;
int x[MAX];//在某个x时最大的y
int main()
{
    scanf("%s%s",a,b);an=INF;
    len=strlen(a);
    bool st1,st2;st1=st2=true;
    for(int i=0;i<len&&st1;i++)if(a[i]=='1')st1=false;
    for(int i=0;i<len&&st2;i++)if(b[i]=='1')st2=false;
    if(st2)
    {
        if(st1)printf("0\n");else printf("-1\n");return 0;
    }
    for(int i=0;i<len;i++)
    {
        int j=0;
        for(;b[(i+j)%len]!='1';)++j;
        r[i]=j;
    }
    for(int i=0;i<len;i++)
    {
        int j=0;for(;b[(i-j+len)%len]!='1';)++j;
        l[i]=j;
    }
    for(int d=0;d<len;d++)//枚举d
    {
        cnt=0;tem=INF;memset(x,0,sizeof(x));
        //最终向右移动
        for(int i=0;i<len;i++)
        {
            if(a[i]!=b[(i+d)%len]){
                    ++cnt;
                    if(r[i]<=d)continue;//不需要加
                    x[l[i]]=max(x[l[i]],r[(i+d)%len]);
            }
        }
        for(int i=len-1;i>=0;i--){
                x[i]=max(x[i],x[i+1]);
//                printf("%d ",x[i]);
                tem=min(x[i+1]+i,tem);
        }
        an=min(an,2*tem+d+cnt);
//        printf("\n");
//        printf("d=%d teman=%d cnt=%d\n",d,2*tem+d+cnt,cnt);
        cnt=0;tem=INF;memset(x,0,sizeof(x));
        for(int i=0;i<len;i++)
        {
            if(a[i]!=b[(i-d+len)%len])
            {
                ++cnt;
                if(l[i]<=d)continue;//不需要加
                x[l[(i-d+len)%len]]=max(x[l[(i-d+len)%len]],r[i]);
            }
        }
        for(int i=len-1;i>=0;i--)
        {
            x[i]=max(x[i],x[i+1]);
            tem=min(x[i+1]+i,tem);
        }
        an=min(an,2*tem+d+cnt);
    }
    printf("%d\n",an);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int m, n;
bool tront[90][90];
bool memo[90][90];

int dfs(int y, int x) {
	int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
	int rep = 0;

	REP(i, 4) {
		int nx = x + dx[i], ny = y + dy[i];
		if (! (nx >= 0 && nx < m && ny >= 0 && ny < n)) continue;
		if (! tront[ny][nx] || memo[ny][nx]) continue;
		memo[ny][nx] = true;
		rep = max(rep, dfs(ny, nx));
		memo[ny][nx] = false;
	}
	return rep + 1;
}


int main() {
	while (true) {
		int ans = 0;
		cin >> m >> n;
		if (n == 0 && m == 0) break;
		REP(i, n) REP(j, m) cin >> tront[i][j];

		REP(i, n) REP(j, m) if (tront[i][j]) {
			memo[i][j] = true;
			ans = max(ans, dfs(i, j));
			memo[i][j] = false;
		}

		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1176
#include <cstdio>

using namespace std;

int main(){
	
	int a, b, n;
	int c;
	
	while (scanf("%d %d %d", &a, &b, &n) != EOF){
		c = 0;
		
		if (a / b != 0){
			a %= b;
		}
		
		for (int i = 0; i < n; i++){
			if (a / b == 0){
				a *= 10;
			}
			c += a / b;
			a %= b;
		}
		
		printf("%d\n", c);
	}
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

void get_N1234 (int64 *n1, int64 *n2, int64 *n3, int64 *n4)
{
  int cnt;

  if (n2 == NULL) {
    cnt = scanf("%lld", n1);
    return;
  }
  if (n3 == NULL) {
    cnt = scanf("%lld %lld", n1, n2);
    return;
  }
  if (n4 == NULL) {
    cnt = scanf("%lld %lld %lld", n1, n2, n3);
    return;
  }
  cnt = scanf("%lld %lld %lld %lld", n1, n2, n3, n4);
  return;
}

void omit_LF (void)
{
  char c;
  int  cnt;
  
  cnt = scanf("%c", &c);
  return;
}

char *get_S (int64 n)
{
  char *buf;
  int  i;
  int  cnt;

  buf = malloc((size_t)(n * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  return buf;
}

char *get_SN (int64 max, int64 *size)
{
  char *buf;
  int  i;
  int  n;
  int  cnt;

  buf = malloc((size_t)(max * sizeof(char)));
  if (buf == NULL) {
    return NULL;
  }

  cnt = scanf("%s", buf);

  n = strlen(buf);

  *size = n;
  
  return buf;
}

int64 *get_NSeq (int64 n)
{
  int64 *buf;
  int64 i;

  buf = malloc((size_t)(n * sizeof(int64)));
  for (i=0; i<n; i++) {
    get_N(&buf[i]);
  }

  return buf;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;

typedef int64 simple_t;

int compare_simple(const void *a, const void *b)
{
  simple_t *x;
  simple_t *y;

  x = (simple_t *)a;
  y = (simple_t *)b;

  if (x > y) return 1;
  if (y < x) return -1;

  return 0;
}
void qsort_simple (simple_t *array, int size)
{
  qsort(array, size, sizeof(simple_t), compare_simple);
}

int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

int64 wk[(2*(10*10*10*10*10))];

int main()
{
  int64 N;
  int64 *A;
  int64 i;
  int64 total = 0;
  int64 play=0;
  
  get_N(&N);
  A = get_NSeq((N-1));

  for (i=0; i < (N-1); i++) {
    wk[A[i] - 1]++;
  }

  for (i=0; i<N; i++) {
    printf("%lld\n",wk[i]);
  }
  return 0;
}



Measured memory_bytes: 4832
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 100000;
const long long inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int,P> PP;
typedef pair<int,PP> PPP;
struct edge { int to;  int cost; };
P a[100006];
signed main() {
	int n, m; cin >> n >> m;

	rep(i, n) {
		int x, y; cin >> x >> y; a[i] = P(x, y);
	}
	sort(a, a + n);
	int sum = 0;
	int itr = 0;
	while (m) {
		int pa = a[itr].first, pb = a[itr].second;
		if (m > pb) {
			sum += pa*pb;
			m -= pb;
		}
		else {
			sum += pa*m;
			m = 0;
		}
		itr++;
	}
	cout << sum << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
int a[8]={},b[8]={},c[15]={},d[15]={},ans[8][8]={};
void print(void);
void dfs(int);
 
int main(){
  int n,r,c1;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>r>>c1;
    ans[r][c1]=1;
  }
  dfs(0);
  return 0;
}
void dfs(int x){
  if(x==8){
  for(int i=0;i<8;i++)
    for(int j=0;j<8;j++)
      if(ans[i][j]==1)
	if(a[i]!=j)return;
 
  for(int i=0;i<8;i++){
    for(int j=0;j<8;j++)
      if(a[i] == j)printf("Q");
      else printf(".");
    printf("\n");
  }
    return;
  }
 
  for(int i=0;i<8;i++){
    if(b[i]==1||c[x+i]==1||d[x-i+7]==1)continue;
    a[x]=i;
    b[i]=c[x+i]=d[x-i+7]=1;
    dfs(x+1);
    a[x]=b[i]=c[x+i]=d[x-i+7]=0;
  }
}

Measured memory_bytes: 1112
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k){ll b=1;k=min(n-k,k);DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

ll N, K;
ll A[100001];
ll X[100001], Y[100001];

int main() {
    fastio();
    cin >> N >> K;
    REP(i, N) cin >> A[i];
    ll sx = 0, sy = 0;
    REP(i, N) {
        sx += A[i];
        if(A[i] >= 0) sy += A[i];
        X[i] = sx;
        Y[i] = sy;
    }
    ll ans = Y[N - 1] - Y[K - 1];
    if(X[K - 1] > 0) ans += X[K - 1];
    FOR(i, K, N - 1) {
        ll xk = X[i] - X[i - K];
        if (xk < 0) xk = 0;
        ans = max(ans, xk + (Y[N - 1] - Y[i] + Y[i - K]));
    }
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

// Integral Rectangles
// 2013/08/13
public class Main{
	Scanner sc=new Scanner(System.in);

	String line;

	void run(){
		for(int T=sc.nextInt(); T>0; T--){
			line=sc.next();
			solve();
		}
	}

	void solve(){
		println(dfs(0, line.length())+"");
	}

	int dfs(int s, int t){
		if(line.charAt(s+1)!='['){
			return Integer.parseInt(line.substring(s+1, t))/2+1;
		}
		int stack=0, left=0;
		ArrayList<Integer> list=new ArrayList<Integer>();
		for(int i=s+1; i<=t-1; i++){
			if(line.charAt(i)=='['){
				if(stack++==0){
					left=i;
				}
			}else if(line.charAt(i)==']'){
				if(--stack==0){
					int right=i;
					list.add(dfs(left, right));
				}
			}
		}
		sort(list);
		int sum=0;
		for(int i : list.subList(0, list.size()/2+1)){
			sum+=i;
		}
		return sum;
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 40924
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define dd double
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;



int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ios_base& scientific (ios_base& str);

string A, B, C;
cin >> A >> B >> C;
int a(0), b(0), c(0);
char now = 'a';

while(true){
	if(now=='a'){
		if(a==A.size()){
			cout << 'A' << endl;
			return 0;
		}
		now = A[a];
		a=a+1;
	}

	else if(now == 'b'){
		if(b == B.size()){
			cout << 'B' << endl;
			return 0;
		}

		now = B[b];
		b= b+1;
	}

	else{
		if(c ==C.size()){
			cout << 'C' << endl;
			return 0;
		}

		now = C[c];
		c=c+1;
	}
}


return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef set<ll> sl;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

int k;
vl a;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	cin >> k;
	a.resize(k);
	rep(i,0,k) {
		cin >> a[i];
	}
	reverse(all(a));
	ll l = 2; ll r = 2;
	rep(i,0,k) {
		ll nr = (r/a[i]) * a[i];
		ll nl = (l/a[i]) * a[i];
		if(l%a[i]) {
			nl = (l/a[i] + 1) * a[i];
		}
		if(nl > r) {
			cout << -1 << endl;
			return 0;
		}
		if(nr < l) {
			cout << -1 << endl;
			return 0;
		}
		nr = nr + a[i] - 1;
		l = nl;
		r = nr;
	}
	cout << l << ' ' << r << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI  = acos(-1.0);


int main(){
	int r,c;
	while(cin>>r>>c,r&&c){
		if(r*c%2){
			cout<<"no"<<endl;
		}else{
			cout<<"yes"<<endl;
		}
	}
}

Measured memory_bytes: 1148
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<bitset>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        if(n == 0)return 0;
        vector<double>s(n);
        double sum=0;
        double ave;
        for(int i=0; i < n; i++){
            cin >> s[i];
            sum += s[i];
        }
        ave = sum / n;
        double lsum = 0;
        for(int i=0; i < s.size(); i++){
            lsum += pow(s[i]-ave,2)/n;
        }
        cout << setprecision(12) << sqrt(lsum) << endl;
    }
}


Measured memory_bytes: 3284
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using node = pair<string,ll>;
const ll inf = numeric_limits<ll>::max()/3;
const ll mod = 1e9+7;

int main(void) {
  int n;
  cin >> n;
  bool win = false;
  for(int i = 0;i < n;++i){
    int tmp;
    cin >> tmp;
    if(tmp % 2 == 1){
      win = true;
    }
  }
  cout << (win?"first":"second") << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
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; }

const char B = 'o';
const char W = 'x';
const char S = '.';
char board[8][8];

int reversible(char player, int y, int x) {
	if (board[y][x] != S)return 0;
	int ret = 0;
	for (int dy = -1; dy <= 1; dy++)
		for (int dx = -1; dx <= 1; dx++)
			if (!(dy == 0 && dx == 0)) {
				int cnt = 0;
				int yy = y + dy, xx = x + dx;
				while (true) {
					if (!(0 <= yy && yy < 8 && 0 <= xx && xx < 8))break;
					char c = board[yy][xx];
					if (c == S) break;
					if (c == player) {
						ret += cnt;
						break;
					}
					yy += dy; xx += dx;
					cnt++;
				}
			}
	return ret;
}

void reverse(char player, int y, int x, int dy, int dx) {
	int yy = y + dy, xx = x + dx;
	while (true) {
		if (!(0 <= yy && yy < 8 && 0 <= xx && xx < 8)) return;
		char c = board[yy][xx];
		if (c == S) return;
		if (c == player) break;
		yy += dy; xx += dx;
	}
	while (true) {
		yy -= dy; xx -= dx;
		if (yy == y && xx == x) break;
		board[yy][xx] = player;
	}
}

void reverse(char player, int y, int x) {
	assert(reversible(player, y, x));
	board[y][x] = player;
	for (int dy = -1; dy <= 1; dy++)
		for (int dx = -1; dx <= 1; dx++)
			if (!(dy == 0 && dx == 0))
				reverse(player, y, x, dy, dx);
}

pair<int, int> status() {
	int cntB = 0, cntW = 0;
	for (int y = 0; y < 8; y++) {
		for (int x = 0; x < 8; x++) {
			char c = board[y][x];
			if (c == B) cntB++;
			if (c == W) cntW++;
		}
	}
	return make_pair(cntB, cntW);
}

signed main() {
	for (int y = 0; y < 8; y++)
		for (int x = 0; x < 8; x++)
			cin >> board[y][x];
	while (true) {
		int Bx, By, Bmaxcnt = 0;
		rep(y, 0, 8)rep(x, 0, 8)
			if (chmax(Bmaxcnt, reversible(B, y, x)))
				Bx = x, By = y;
		if (Bmaxcnt)reverse(B, By, Bx);
		int Wx, Wy,Wmaxcnt = 0;
		rrep(y, 0, 8)rrep(x, 0, 8)
			if (chmax(Wmaxcnt, reversible(W, y, x)))
				Wx = x, Wy = y;
		if (Wmaxcnt)reverse(W, Wy, Wx);
		if (Bmaxcnt == 0 && Wmaxcnt == 0)break;
	}
	rep(i, 0, 8) {
		rep(j, 0, 8) {
			cout << board[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod (int)1e9+7
#define inf (int)1e16
#define rep(i,n) for (int i = 0; i < n; i++)
#define Rep(i,n) for (int i = n; i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define P pair<int, int>
#define prique priority_queue<P, vector<P>, greater<P>>
struct edge { int to, cost; };
using namespace std;
int n;
string s[11111];
int cnt = 0;
vector<int>A, B;
int mi = 0;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> s[i];
		string a = s[i];
		int m = s[i].size();
		for (int j = 0; j < m - 1; j++) {
			if (a[j] == 'A' && a[j + 1] == 'B') cnt++;
		}
		if (a[m - 1] == 'A') A.push_back(i);
		if (a[0] == 'B') B.push_back(i);
		if (a[m - 1] == 'A' && a[0] == 'B') {
			mi++;
		}
	}
	if (A.size() == B.size()) {
		if (mi) {
			if (1 <= A.size() - mi && 1 <= B.size() - mi) {
				cout << A.size() + cnt << endl;
			}
			else {
				cout << max((int)0, (int)A.size() + cnt - (int)1) << endl;
			}
		}
		else cout << A.size() + cnt << endl;
	}
	else {
		cout << cnt + min(A.size(), B.size()) << endl;
	}
}


Measured memory_bytes: 1024
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Aizu Online Judge. Quick Sort
import sys

class Card():
    def __init__(self, suit, val, pos):
        self.suit = suit
        self.val = val
        self.pos = pos

def partition(A, p, r):
    x = A[r].val
    i = p-1
    for n in range (p,r):
        if A[n].val <= x:
            i += 1
            A[i], A[n] = A[n], A[i]
    A[i+1], A[r] = A[r], A[i+1]

    return i+1

def quicksort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)

def check_stable(A):
    prev_val = None
    for card in A:
        if card.val == prev_val:
            if card.pos < prev_pos:
                print('Not stable')
                return
        prev_val = card.val
        prev_pos = card.pos

    print('Stable')
    return


n = int(sys.stdin.readline())
A = list()
for pos in range(n):
    suit, val_s = sys.stdin.readline().split()
    A.append(Card(suit, int(val_s), pos))

quicksort(A, 0, n-1)
check_stable(A)
for card in A:
    print(card.suit, card.val)



Measured memory_bytes: 29920
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
int n, m;
vector <int> a[nax];
bool vis[nax];
int to[nax];

int main () {


    scanf("%d %d", &n, &m);


    for (int i = 1 ; i <= m ; ++ i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    queue <int> q;
    q.push(1);
    vis[1] = true;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        for (int i : a[x]) {
            if (!vis[i]) {
                to[i] = x;
                vis[i] = true;
                q.push(i);
            }
        }
    }

    for (int i = 2; i <= n ;++ i) {
        if (to[i] == 0) return !printf("No");
    }

    printf("Yes\n");

    for (int i = 2 ; i <= n ;++ i) {
        printf("%d\n", to[i]);
    }
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 15472
import math
N = int(input())
ans = 1
prea = 1; preb = 1
for i in range(N):
  a,b = map(int,input().split())
  MIN = max((prea+a-1)//a,(preb+b-1)//b)
  #print(MIN)
  ans = MIN*(a+b)
  prea = a*MIN; preb = b*MIN
  #print(MIN,ans)
print(ans)

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//MOD
//--------------------------------------------
#define MUL(a,b) (((a) % MOD) * ((b) % MOD)) % MOD

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

int main(int argc, char const* argv[])
{
	int n,q;
	cin >> n >> q;
	string s;
	cin >> s;
	VL rui(n+1,0);
	for (int i = 1; i < n; i++) {
		rui[i+1] = rui[i];
		if (s[i-1] == 'A' and s[i] == 'C') {
			rui[i+1]++;
		}
	}
	VL l(q), r(q);
	for (int i = 0; i < q; i++) {
		cin >> l[i] >> r[i];
	}

	for (int i = 0; i < q; i++) {
		LL ans = rui[r[i]] - rui[l[i]];
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int N=110000;
vi adj[N];

int mind(int x) {
    vi h;
    for(int y:adj[x]) h.pb(mind(y));
    sort(all(h));
    int ans=sz(h);
    for(int i=0; i<sz(h); i++)
        ans=max(ans, h[i]+sz(h)-i);
    return ans;
}

int main() {
    int i, n, t;
    scanf("%d", &n);
    for(i=2; i<=n; i++) {
        scanf("%d", &t);
        adj[t].pb(i);
    }
    printf("%d\n", mind(1));
    return 0;
}

Measured memory_bytes: 15360
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main()
{
	int A,B;
	cin >> A >> B;
	cout << max(0,A-2*B) << endl;
	return 0;
}

Measured memory_bytes: 256
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,j,d):
  if i>=j:
    return 0
  if z[i][j]==-1:
    q=1<<64
    for k in xrange(i,j):
      q=min(q,s[j+1]-s[i]+f(i,k,d)+f(k+1,j,d))
    z[i][j]=q
  return z[i][j]
n=input()
a=map(int,raw_input().split())
s=[0]
for i in a:
  s.append(s[-1]+i)
z=[[-1]*n for i in xrange(n)]
print f(0,n-1,{})

Measured memory_bytes: 35560
#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 1000000
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
int f[N],s[N],nxt[N][3]; char c[N];
int main()
{	scanf("%s",c+1); int n=strlen(c+1),ans=0,tag=1;
	for(rint i=1;i<=n;i++) s[i]=(s[i-1]+1+(c[i]=='b'))%3,tag&=(c[i]!=c[i+1]);
	if(tag) return !printf("1");
	for(rint i=n;i>=1;i--)
	memcpy(nxt[i],nxt[i+1],sizeof(nxt[i])),nxt[i][s[i]]=i;
	f[nxt[1][1]]=f[nxt[1][2]]=1;
	for(rint i=1;i<=n;i++)
	{	for(rint j=1;j<=2;j++)
		if(nxt[i+1][(s[i]+j)%3]) (f[nxt[i+1][(s[i]+j)%3]]+=f[i])%=mod;
		if(s[n]==s[i]) (ans+=f[i])%=mod;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 7552
# 係数ソート
def countingSort(A, B, k, n):
    c = [0] * (k+1)
        
    for i, a in enumerate(A):
        c[a] += 1

    for i in range(1, k+1):
        c[i] = c[i] + c[i-1]
        
    for j, a in enumerate(reversed(A)):
        B[c[a]-1] = a
        c[a] -= 1
        
    print(*b)
    return

import sys
import copy
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
b = [0] * n
k = max(a)

countingSort(a, b, k, n)


Measured memory_bytes: 224960
import sys
sys.setrecursionlimit(100000)
n,k=map(int,input().split())
ans=k
t=[set()for i in range(n)]
dp=[k]+[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b)
  t[b-1].add(a)
no=1
w=k
b=True
def a(noo):
  global ans
  w=k
  for i in t[noo-1]:
    t[i-1].discard(noo)
    if w==0:print(0);exit()
    dp[i-1]=w-2;ans=(ans*(w-2))%(10**9+7)
    w-=1
    a(i)
for i in t[no-1]:
  t[i-1].discard(no)
  w-=1
  dp[i-1]=w;ans=(ans*w)%(10**9+7)
  a(i)
print(ans)

Measured memory_bytes: 100632
def countingSort(A, k=None):
    if not k:
        k = max(A)
    C = [ 0 for i in range(k+1)]
    for j in range(len(A)):
        C[A[j]] += 1
    total = 0
    for k in range(len(C)):
        total += C[k]
        C[k] = total
    B = [ 0 for l in range(len(A))]
    for _A in A[::-1]:
        B[C[_A]-1] = _A
        C[_A] -= 1
    return B


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    print(' '.join(map(str,countingSort(A))))


Measured memory_bytes: 233764
//#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>

using namespace std;

#define ll long long

void solve()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    ll sum = 0;
    for (ll i = 0; i < N; i++)
    {
        cin >> A.at(i);
        sum += A.at(i);
    }

    ll fom = sum / (4 * M);
    bool isDiv = sum % (4 * M) == 0;
    ll selectable = 0;
    for (ll i = 0; i < N; i++)
    {
        if (isDiv && A.at(i) >= fom || !isDiv && A.at(i) > fom)
        {
            selectable++;
        }
    }

    if (selectable >= M)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    void Calc()
    {
        var sc = new Scanner();
        int hyahha = sc.NextInt();
        int h, m, s;
        h = hyahha / 3600;
        m = hyahha % 3600 / 60;
        s = hyahha % 3600 % 60;
        Console.WriteLine(h+":"+m+":"+s);
    }

    static void Main()
    {
        new Program().Calc();
    }

    class Scanner
    {
        string[] s = new string[0];
        int i = 0;
        char[] cs = new char[] { ' ' };

        public string Next()
        {
            if (i < s.Length) return s[i++];
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return s[i++];
        }
        public int NextInt() { return int.Parse(Next()); }
        public long NextLong() { return long.Parse(Next()); }
        public double NextDouble() { return double.Parse(Next()); }
    }
}

Measured memory_bytes: 17884
from itertools import accumulate
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = [0]
a.extend(map(int,input().split()))
a = list(accumulate(a))
c = Counter(a)
ans = 0
for i in c.values():
  ans+=i*(i-1)//2
print(ans)

Measured memory_bytes: 34040
n = int(input())
a,b = map(int, input().split())
p = [int(i) for i in input().split()] 
count1 = 0
count2 = 0
count3 = 0
for i in p:
    if i <= a:
        count1 += 1
    if a+1 <= i <= b:
        count2 += 1
    if b+1 <= i:
        count3 += 1
print(min(count1,count2,count3))

Measured memory_bytes: 3064
def calcNext(s):
    n = len(s)
    res = [[n+1] * 26 for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        for j in range(26):
            res[i][j] = res[i+1][j]
        res[i][ord(s[i]) - ord('a')] = i
    return res

def solve(s):
    n = len(s)
    nx = calcNext(s)
    dp = [n + 1] * (n + 1)
    recon = ['a'] * (n + 1)
    dp[n] = 1
    for i in range(n-1, -1, -1):
        for j in range(26):
            if nx[i][j] == n + 1:
                if dp[i] > 1:
                    dp[i] = 1
                    recon[i] = chr(ord('a') + j)
            else:
                if dp[nx[i][j] + 1] + 1 < dp[i]:
                    dp[i] = dp[nx[i][j] + 1] + 1
                    recon[i] = chr(ord('a') + j)
    res = ''
    idx = 0
    while idx <= n:
        res += recon[idx]
        idx = nx[idx][ord(recon[idx]) - ord('a')] + 1
    return res

S = input()
print(solve(S))

Measured memory_bytes: 112160
#include <bits/stdc++.h>
#define LARB 1
#define RARB 30000
#define inf 1e18
#define zeros(x) ((x^(x-1))&x)
#define endl '\n'
#define eps 1e-9
#define mod 1000000007
#define NMAX 300

using namespace std;

typedef long long ll;
typedef long double ld;

ll n, m, k, nxt, F[305][305];
string s[305];


int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>k;
    for (int i=0; i<n; i++)
        cin>>s[i];

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<s[i].size(); j++)
        {
            if (s[i][j] == '#')
            {
                F[i][j] = ++nxt;
            }
        }
        for (int j=1;j<s[i].size(); j++)
        {
            if (F[i][j] == 0)
                F[i][j] = F[i][j-1];
        }

        for (int j=s[i].size()-2; j>=0; j--)
        {
            if (F[i][j] == 0)
                F[i][j] = F[i][j+1];
        }
    }

    for (int j=0; j<m; j++)
    {
        for (int i=1; i<n; i++)
            if (F[i][j] == 0)
                F[i][j] = F[i-1][j];
        for (int i=n-2; i>=0; i--)
            if (F[i][j] == 0)
                F[i][j] = F[i+1][j];
    }

    for (int i=0; i<n; i++, cout<<endl)
        for (int j=0; j<m; j++)
            cout<<F[i][j]<<" ";
    return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>

using namespace std;

int main() {
        int n, k;
        cin >> n >> k;
        string s; cin >> s; 
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1])ans++;
        }
        if (ans + 2 * k > n - 1)cout << n - 1 << endl;
        else cout << ans + 2 * k << endl;
    }
    


Measured memory_bytes: 512
#include <stdio.h>
#define len 100005
typedef struct q{
    char name[100];
    int time;
}q;
q pro[len];
int head,tail,n;
q enqueue(q x){
    pro[tail]=x;
    tail=(tail+1)%len;
}
q dequeue(void){
    q x=pro[head];
    head=(head+1)%len;
    return x;
}
int main(void){
    int n,max,total=0,i;
    q x;
    scanf("%d %d",&n,&max);
    for(i=0;i<n;i++)
        scanf("%s %d",pro[i].name,&pro[i].time);
    head=0,tail=n;
    while(head != tail){
        x=dequeue();
        if(x.time <= max){
            total+=x.time;
            printf("%s %d\n",x.name,total);
        }
        else{
            total+=max;
            x.time-=max;
            enqueue(x);
        }
    }
    return 0;
}



Measured memory_bytes: 11864
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

#define NUMMAX 500010

int L[NUMMAX/2], R[NUMMAX/2];
int cnt;

void merge(int A[], int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i, n1) L[i] = A[left+i];
    rep(i, n2) R[i] = A[mid+i];
    L[n1] = INT32_MAX;
    R[n2] = INT32_MAX;
    int i = 0;
    int j = 0;
    rep(n, n1+n2) {
        cnt++;
        if (R[j] < L[i]) {
            A[left+n] = R[j];
            j++;
        } else {
            A[left+n] = L[i];
            i++;
        }
    }
}

void mergeSort(int A[], int left, int right){
    if (left+1 < right){
        int mid = (left+right)/2;
        mergeSort(A, left, mid);
        mergeSort(A, mid, right);
        merge(A, left, mid, right);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int s[n];
    rep(i,n) scanf("%d", &s[i]);
    mergeSort(s, 0, n);
    
    rep(i,n) {
        if (i) cout << " ";
        cout << s[i];
    }
    cout << endl;
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 7096
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, Y);
  rep(i, 0, N + 1) {
    rep(j, 0, N - i + 1) {
      int k = N - i - j;
      int sum = i * 10000 + j * 5000 + k * 1000;
      if (sum == Y) {
        cout << i << ' ' << j << ' ' << k << endl;
        return;
      }
    }
  }
  print("-1 -1 -1");
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
//#include<bits/stdc++.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#define  si(a)       scanf("%d",&a)
#define  sl(a)       scanf("%lld",&a)
#define  sii(a,b)    scanf("%d%d",&a,&b)
#define  sll(a,b)    scanf("%lld%lld",&a,&b)
#define  queues      priority_queue
#define mod 998244353
#define mem(a)  memset(a,0,sizeof(a));
#define def(a) ((a)&(-a))
#define fi  first
#define se  second
#define mp  make_pair
#define  pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
typedef long long ll;
//priority_queue<ll,vector<ll >,greater<ll > >q;
const int INF=0x3f3f3f3f;
//const double E=exp(1);
//const double PI=acos(-1);
using namespace std;
//__builtin_popcount
//priority_queue
const ll MAX=100000;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll kc(ll a,ll b)
{
    ll c=1;
    while(b)
    {
        if(b&1)c=(c*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return c;
}
bool cmp(double x,double y)
{
    return x>y;
}
ll F[50003*3];
ll Find(ll a)
{
    return F[a]<0?a:F[a]=Find(F[a]);
}
ll same(ll a,ll b)
{
    if(Find(a)==Find(b))return 1;
    return 0;
}
ll up1(ll a,ll b)
{
    ll x,y;
    x=Find(a);
    y=Find(b);
    if(x!=y)
        F[x]=y;
    return 0;
}
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
 
int main()
{
   // ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int sum=0;
    for(int i=1;i<=t;i++)
    {
        int a;
        cin>>a;
        if(a!=i)sum++;
    }
    if(sum==2||sum==0)cout<<"YES\n";
    else cout<<"NO\n";
}

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

int main(){
   long long N;
   cin >> N;
    int f = 100;
    int s;
   for(long long i = 1; i <= sqrt(N); i++) {
       s = 0; 
       long long it;
       
       if(N % i == 0) {
        if(N / i >= i)
        it = N / i;
        else if(N / i < i)
        it = i;
        
       while(it > 0) {
           it /= 10;
           s++;
       }
        if(f > s) f = s;
       }  
   }

   cout << f;
    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

int mod_pow(int a,int b,int M = MOD)
{
    int res = 1;
    
    while(b)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}

const int N = 1e5 + 10;

int mp[N];

void solve()
{
   int n,q;
    cin >> n ;
   
   int a[n];
    f(i,n) cin >> a[i];
    
   cin >> q;
    
   int b,c; 
    
   int sum = 0;
    
   f(i,n) sum+=a[i];
   f(i,n) mp[a[i]]++;
    
   while(q--)
   {
       cin >> b >> c;
       
       sum-=mp[b]*b;
       sum+=mp[b]*c;
       
       mp[c]+=mp[b];
       mp[b] = 0;
       
       cout << sum << '\n';
   }
   
    
    
}

signed main()
{
    fast;
    
    int t = 1;
    
//    cin >> t;
    
    while(t--)
        
    solve();
}

Measured memory_bytes: 5116
s=input().replace('\n', '')
t=input().replace('\n', '')
begin, end = len(s) - len(t), len(s)
ans=''
while begin>=0:
    origin = s[begin:end]
    flag=1
    
    for i in range(len(t)):
        if origin[i]!=t[i] and origin[i]!='?':
            flag=0
            break
    if flag:
        ans = s[:begin]+t+s[end:]
        break
    begin-=1
    end-=1
print("UNRESTORABLE" if not len(ans) else ans.replace('?', 'a'))


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

int D[100][100];
int main(){
	int n,w,h,x,y,s,t,cnt,maxn;
	while(1){
		cin>>n;
		if(n==0) break;
		cin>>w>>h;
		for(int i=0;i<100;i++)for(int j=0;j<100;j++) D[i][j]=0;
		for(int i=0;i<n;i++){
			cin>>x>>y;
			D[y-1][x-1]=1;
		}
		cin>>s>>t;
		maxn=0;
		for(int i=0;i<=h-t;i++){
			for(int j=0;j<=w-s;j++){
				cnt=0;
				for(int p=0;p<t;p++){
					for(int q=0;q<s;q++){
						if(D[p+i][q+j]==1) cnt++;
					}
				}
				maxn=max(maxn,cnt);
			}
		}
		cout<<maxn<<endl;
	}
	return 0;
}


Measured memory_bytes: 3104
import java.util.*;
import java.io.*;
public class Main
{
    static BufferedReader br;
    static BufferedWriter bw;
    static void solve()throws Exception
    {
        int input[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int A = input[0];
        int B= input[1];
        int C = input[2];
        int  k= input[3];
        int sum = 0;
        if(k>=A)
        {
            sum+=A;
            k = k-A;
            A = 0;
        }
        else
        {
            sum+=k;
            k=0;
            A=A-k;
        }
        if(k>=B)
        {
            k = k-B;
            B = 0;
        }
        else
        {
            k=0;
            B=B-k;
        }
        if(k>=C)
        {
            sum-=C;
            k = k-C;
            C = 0;
        }
        else
        {
            sum-=k;
            k=0;
            C=C-k;
        }
        bw.write(Integer.toString(sum));
    }
    public static void main(String []args)throws Exception
    {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        solve();
        br.close();
        bw.close();
    }
}

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

int main(){
    int n, x;
    cin >> n >> x;
    int m[n];
    int ans = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> m[i];
        sum += m[i];
    }
    x -= sum;
    ans += n;
    sort(m, m+n);
    if (x > 0){
        ans += (x / m[0]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int P = sc.nextInt();
    int Q = sc.nextInt();
    int R = sc.nextInt();
    System.out.println(Math.min(Math.min(P + Q, Q + R), R + P));
  }
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=10000000007;

int main(){
  int n,m;cin>>n>>m;
  int v[n];
  rep(i,n) v[i]=0;
  int p;
  string s;
  int ca=0,cw=0;
  rep(i,m){
    cin>>p>>s;
    p--;
    if(s=="AC"){
      if(v[p]!=-1){
        ca++;
        cw+=v[p];
        v[p]=-1;
      }
    }
    if(s=="WA"){
      if(v[p]!=-1){
        v[p]++;
      }
    }
  }
  
  cout<<ca<<' '<<cw<<endl;
}



Measured memory_bytes: 640
N = int(input())
S = str(input())
ctr = 0

if N == 3:
	if S[0 : 3] == "ABC":
		ctr += 1
else:
	for i in range(N - 2):
		if S[i : i + 3] == "ABC":
			ctr += 1
		
print(ctr)


Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

class Tree {
	int N;
	vector<vector<int>> edge;
	vector<int> lazy;

public:
	Tree(int N) : N(N), edge(N), lazy(N) {}
	void input() {
		REP(i, N - 1) {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			edge[a].emplace_back(b);
			edge[b].emplace_back(a);
		}
	}
	void add(int p, int x) {
		lazy[p] += x;
	}
	void dfs(int i = 0, int p = -1) {
		if (p >= 0) lazy[i] += lazy[p];
		for (auto &j : edge[i]) {
			if (j != p) {
				dfs(j, i);
			}
		}
	}
	void ans() {
		dfs();
		REP(i, N) {
			cout << lazy[i] << " ";
		}
		cout << endl;
	}
};

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

	int N, Q;
	cin >> N >> Q;
	Tree tree(N);
	tree.input();
	REP(q, Q) {
		int p, x;
		cin >> p >> x;
		--p;
		tree.add(p, x);
	}
	tree.ans();

	return 0;
}

Measured memory_bytes: 24296
#include<bits/stdc++.h>
using namespace std;
#define ll long long
unordered_map<ll,ll>mp;
bool tell(ll n)
{
	if(mp[n]>1){return false;}
	if(mp[1]>0 and n!=1){return false;}
	if(mp[1]>1){return false;}
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			if((n/i)==n && mp[n]==1){continue;}
			if(n/i!=i)
			{
				
				if(mp[n/i]>0 ||mp[i]>0)
				{
					return false;
				}
			}
			else
			{
				if(mp[i]>0){return false;}
			}
		}
	}
	
	return true;
}


int main() 
{
	ll n; cin>>n;
	//set<int>s;
	ll a[n];
	//map<int,int>mp;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}

	ll cnt=0;
	for(int i=0;i<n;i++)
	{
		if(tell(a[i]) )
		{cnt++;}
	
	}
	cout<<cnt<<endl;

}

Measured memory_bytes: 33308
#include<stdio.h>
#include<stdlib.h>

int cmp(const void* a,const void* b){
	return *((int *)b)-*((int *)a);
}
int main(void){
	int n=0,alice=0,bob=0;
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	qsort(a,n,sizeof(a[0]),cmp);
	for(int i=0;i<n;i++){
		if(i%2==0){
			alice+=a[i];
		}else{
			bob+=a[i];
		}
	}
	printf("%d",alice-bob);
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int N, Q; cin >> N >> Q;
  vector<int> c(N);
  for(int i=0; i<N; i++) cin >> c[i];
  sort(c.begin(), c.end());
  int v_max = c.back();

  while(Q--) {
    int q; cin >> q;
    int lb = 0, ub = q, ans = 0;
    for(; lb < v_max; lb += q, ub += q) {
      int idx = lower_bound(c.begin(), c.end(), ub) - c.begin() - 1;
      if(idx < 0) continue;
      ans = max(ans, c[idx] % q);
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3804
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

int main() {
	int n;
	cin >> n;

	vector<int> h(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}

	int ans = 0;
	for (int i = 0; i < n; ) {
		if (h[i] == 0) {
			i++;
			continue;
		}

		ans++;
// printf("---\n");
		for (int j = i; j < n; j++) {
			if (h[j] == 0) {
				break;
			}
			h[j] -= 1;

// printf("%d\n", j);

		}
	}

	cout << ans << endl;
	return 0;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

vector<vector<int>> to;
vector<int> dp;

int dfs(int v) {
    if (dp[v] != -1) return dp[v];
    int len = 0;
    for (int nv : to[v]) {
        chmax(len, dfs(nv) + 1);
    }
    return dp[v] = len;
}

int main() {
    int N, M;
    cin >> N >> M;
    to.resize(N);
    dp.resize(N, -1);

    rep(i, M) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        to[x].push_back(y);
    }

    int ans = 0;
    rep(i, N) chmax(ans, dfs(i));

    cout << ans << endl;
}


Measured memory_bytes: 8192
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int n,k;
    cin>>k>>n;
    int a[n];
    int d=0;
    int min=10000000;
    rep(i,0,n-1) cin>>a[i];
    rep(i,0,n-1)
    {
        if(i==0) d = a[n-1]-a[0];
        else{
            d = k-a[i] + a[i-1];
        }
        if(d<min) min = d;
    }
    printf("%d\n",min);
    return 0;
}

Measured memory_bytes: 1656