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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(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 PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL l, n, x[200002], d[200001], s[200002];

LL ID(int l, int r) { return s[r] - s[l]; }
LL CD(int l, int r) { return s[r] - s[l + 1]; }

int main() {
	cin >> l >> n;
	x[0] = 0;
	inc1(i, n) { cin >> x[i]; }
	x[n + 1] = l;
	n++;
	
	LL ans = 0;
	inc(k, 2) {
		inc(i, n + 1) { x[i] = l - x[i]; }
		reverse(x, x + n + 1);
		inc(i, n) { d[i] = x[i + 1] - x[i]; }
		inc(i, n) { s[i + 1] = s[i] + d[i]; }
		
		LL sum = 0;
		inc(i, n) {
			if(i == 0) {
				sum += ID(1, n);
			} else {
				int z = 2 * i % n;
				if(2 * i < n) { sum += +2 * (ID(0, i) - CD(i, z) + CD(z, n)) - d[i]; }
				else          { sum += -2 * (ID(0, z) - CD(z, i) + CD(i, n)) - d[i]; }
			}
			setmax(ans, sum);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 4992
N = int(input())
e = [0] * (N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j

def num(m):
    return len(list(filter(lambda x: x>=m-1, e)))

print(num(75) + num(25) * (num(3) -1) + num(15) * (num(5) -1)
    +num(5) * (num(5) -1 ) * (num(3) - 2) //2)

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}


int t[1005][1005];

int main2() {
  CLR(t, 0);

  int H = nextInt();
  int W = nextInt();
  int A = nextInt();
  int B = nextInt();

  REP(i, B) REP(j, A) {
    t[i][j] = 1;
  }
  REP(i, H-B) REP(j, W-A) {
    t[H-1-i][W-1-j] = 1;
  }

  REP(i, H) {
    REP(j, W) cout << t[i][j];
    cout << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 5120
# -*- coding: utf-8 -*-
K,N = map(int, input().split())
houses = list(map(int, input().split()))
M = N - 1
lis = []
a = 0
while M > 0:
    lis.append(houses[a+1] - houses[a])
    M -= 1
    a += 1
lis.append(K - houses[N-1] + houses[0])
hou = sorted(lis, reverse = True)
del hou[0]
print(sum(hou))

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

using namespace std;

bool can_pay(int value, const vector<int> D) {
	string str = to_string(value);
	for (int i = 0; i < D.size(); ++i) {
		if (str.find(to_string(D[i])) >= 0 &&
		    str.find(to_string(D[i])) <= D.size() - 1) {
			return false;
		}
	}
	return true;
}

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> D(K);
	for (int i = 0; i < K; ++i) {
		cin >> D[i];
	}

	int pay_money = N;
	while (!can_pay(pay_money, D)) {
		pay_money++;
	}

	cout << pay_money << endl;
}


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

using namespace std;

vector<int> solve(int l, int r, int ind){
	vector<int> ans;
	if(ind == 0){
		ans={l&1,r&1};
		return ans;
	}
	if(((l>>ind)&1) == ((r>>ind)&1)){
		ans.resize(1<<(ind+1));
		
		auto sub = solve(l,r,ind-1);
		if((l>>ind)&1){
			for(int i=0; i<sub.size();i+=2){
				ans[2*i]=sub[i]+(1<<ind);
				ans[2*i+1]=sub[i];
				ans[2*i+2]=sub[i+1];
				ans[2*i+3]=sub[i+1]+(1<<ind);
			}
		}
		else{
			for(int i=0; i<sub.size();i+=2){
				ans[2*i]=sub[i];
				ans[2*i+1]=sub[i]+(1<<ind);
				ans[2*i+2]=sub[i+1]+(1<<ind);
				ans[2*i+3]=sub[i+1];
			}
			
		}
	}
	else{
		auto subl = solve(l,l^1,ind-1), subr = solve(l^1,r,ind-1);
		ans.insert(ans.end(),subl.begin(),subl.end());
		ans.insert(ans.end(),subr.begin(),subr.end());
		if(((r>>ind)&1))
			for(int i=(1<<ind); i<(1<<(ind+1)); i++){
				ans[i]+=(1<<ind);
			}
		else
			for(int i=0;i<(1<<ind); i++){
				ans[i]+=(1<<ind);
			}
	}
	return ans;
}

int main(){
	int n; cin >> n;
	int l,r; cin >> l >> r;
	int tb = __builtin_popcount(l)+
			__builtin_popcount(r);
	if(((tb)&1)==0){
		cout << "NO" << endl;
		return 0;
	}
	
	auto ans = solve(l,r, n-1);
	
	cout << "YES" << endl;
	for(auto x:ans){
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1840
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <vector>
#define MAXN 200010
int n, p[MAXN], fa[MAXN], c[MAXN][2], d[MAXN];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
std::vector<int> next[MAXN];
struct frac_t {
	int a, b;
	inline frac_t(int a, int b) : a(a), b(b) {}
	inline bool friend operator<(const frac_t& a, const frac_t& b) {
		return 1LL * a.a * b.b < 1LL * b.a * a.b;
	}
	inline bool friend operator==(const frac_t& a, const frac_t& b) {
		return a.a == b.a && a.b == b.b;
	}
};
std::set<std::pair<frac_t, int>> S;
long long ans = 0;
int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &p[i]);
		d[p[i]]++;
	}
	for (int i = 1, v; i <= n; i++) {
		scanf("%d", &v);
		c[i][v]++;
		fa[i] = i;
	}
	for (int i = 2; i <= n; i++) S.emplace(frac_t(c[i][1], c[i][0]), i);
	for (int i = 2; i <= n; i++) {
		int x = S.begin()->second, y = find(p[x]);
		S.erase(S.begin());
		fa[x] = y;
		ans += 1LL * c[y][1] * c[x][0];
		if (y != 1) S.erase(std::make_pair(frac_t(c[y][1], c[y][0]), y));
		c[y][0] += c[x][0];
		c[y][1] += c[x][1];
		if (y != 1) S.emplace(frac_t(c[y][1], c[y][0]), y);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 21376
#include <iostream>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    for(int i=0; i<s.size(); ++i)
    {
        if(s[i]>=97 && s[i]<=122)s[i]-=32;
		else if(s[i]>=65 && s[i]<=90)s[i]+=32;
    }
    cout << s << endl;
    return 0;
}

//if(s[i]>='a'&&s[i]<='z')s[i]-='a'-'A';
//else if(s[i]>='A'&&s[i]<='Z')s[i]+='a'-'A';


Measured memory_bytes: 3156
def main():
    N, K = map(int, input().split())
    x = Base_10_to_n(N, K)
    print(len(x))


def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X % n)
    return str(X % n)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(100000)

def tree_path():
    # 辺と長さが与えられる
    # 頂点1からの各点の距離を計算する
    # 距離が偶数か奇数かで色分け
    sys.setrecursionlimit(100000)
    n = int(input())
    path = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        # 無向グラフ
        path[u].append((v, w))
        path[v].append((u, w))
    # d[0]は使わない
    d = [-1] * (n + 1)

    def walk(i, c):
        if d[i] == -1:
            d[i] = c
            for x, w in path[i]:
                walk(x, c + w)

    walk(1, 0)
    for i in d[1:]:
        print(i % 2)

        
tree_path()

Measured memory_bytes: 92408
import sys

readline = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    A, B, C, K = map(int, readline().split())
    if A + B >= K:
        print(min(A,K))
    else:
        tmp = K - A - B
        print(A-tmp)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9180
#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 main(){
    int n, h;
    cin >> n >> h;
    vector<int> t(n);
    int maxA = 0;
    rep(i,n){
        int a, b;
        cin >> a >> b;
        maxA = max(maxA, a);
        t[i] = b;
    }
    ll ans = 0;
    sort(rall(t));
    rep(i,n){
        if (t[i] < maxA) break;
        if (h <= 0){
            h = 0;
            break;
        }
        h -= t[i];
        ans++;
    }
    ans += ceil((double)h / maxA);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3776
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll x;
int main(){
	cin>>x;
	for(ll i=-4000;i<=4000;i++){
		for(ll j=i+1;j<=4000;j++){
			if(j*j*j*j*j-i*i*i*i*i==x)return cout<<j<<' '<<i<<endl,0;
		}
	}
}


Measured memory_bytes: 3644
n, d = map(int, input().split())
sqs = set([i ** 2 for i in range(500)])
lst = []
for i in range(n):
  temp = list(map(int, input().split()))
  lst.append(temp)
cnt = 0
for i in range(n - 1):
  for j in range(i + 1, n):
    nrm = 0
    for k in range(d):
      nrm += (lst[i][k] - lst[j][k]) ** 2
    if nrm in sqs:
      cnt += 1
print(cnt)

Measured memory_bytes: 9188
# B - Papers, Please
N = int(input())
A = list(map(int, input().split(' ')))
flag = True
for i in A:
    if i % 2 == 0:
        if i % 5 == 0 or i % 3 == 0:
            pass
        else:
            flag = False

if flag:
    print("APPROVED")
else:
    print("DENIED")


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

int main(void) {
  int N, p, ans = 0, min = INT_MAX;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p;
    if (p <= min) {
      ans++;
      min = p;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define P pair<int, int>
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const int MAX_NM = 510 * 2;

int N, M, B[MAX_NM], R[MAX_NM];
int match[MAX_NM];
bool used[MAX_NM];
vector<int> G[MAX_NM];

bool dfs(int v){
  used[v] = true;
  REP(tmp_u, G[v].size()){
    int u = G[v][tmp_u];
    int w = match[u];
    if(w < 0 || (!used[w] && dfs(w))){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int bipartiteMatching(int V){
  memset(match, -1, sizeof(match));
  memset(used, 0, sizeof(used));
  int ret = 0;
  REP(v, V){
    if(match[v] < 0){
      memset(used, 0, sizeof(used));
      if(dfs(v)) ++ret;
    }
  }
  return ret;
}

int canGet(int a, int b){
  //cout <<"    " <<a <<", " <<b <<endl;
  if(b == 0) return a;
  return canGet(b, a % b);
}

int main() {
  while(cin >>M >>N && M){
    REP(i, MAX_NM) G[i].clear();
    //cout <<"------------" <<endl;
    REP(i, M) cin >>B[i];
    REP(i, N) cin >>R[i];
    REP(i, M){
      REP(j, N){
        //int dfs = (canGet(max(B[i], R[j]), min(B[i], R[j])));
        //cout <<"dfs = " <<dfs <<endl;
        //if(B[i] == 6 && R[j] == 2) cout <<B[i] <<", " <<R[j] <<", " <<(canGet(max(B[i], R[j]), min(B[i], R[j]))) <<endl;
        if(canGet(max(B[i], R[j]), min(B[i], R[j])) != 1){
          G[i].push_back(M + j);
          G[M + j].push_back(i);
        }
      }
    }
    int ans = bipartiteMatching(M + N);
    //debug start
    //cout <<"BLUE "; REP(i, M) cout <<B[i] <<", "; cout <<endl;
    //cout <<"RED "; REP(i, N) cout <<R[i] <<", "; cout <<endl;
    //REP(i, M){
    //  cout <<B[i] <<" : ";
    //  REP(j, G[i].size()) cout <<R[G[i][j] - M] <<", ";
    //  cout <<endl;
    //}
    //REP(i, M) cout <<R[match[i] - M] <<", "; cout <<endl;
    //debug end
    cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 3380
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N; cin >> N;
    vec A(N);
    vector<bool> s(N - 1, false);
    char c;
    REP(i, N - 1){
        cin >> A[i] >> c;
        if(c == '+') s[i] = true;
    }
    cin >> A[N - 1];

    vec sumA(N + 1);
    sumA[0] = 0;
    REP(i, N) sumA[i + 1] = sumA[i] + A[i];

    int ans = -1 * INF;
    int tmp = A[0];
    REP(i, N - 1){
        if(s[i]){
            tmp += A[i + 1];
        }else{
            tmp -= A[i + 1];
            int tmp2 = tmp;
            FOR(j, i + 1, N - 1){
                if(s[j]){
                    tmp2 -= A[j + 1];
                }else{
                    tmp2 += sumA[N] - sumA[j + 1];
                    break;
                }
            }
            ans = max(ans, tmp2);
        }
    }
    ans = max(ans, tmp);

    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

struct Result {
    int py, px, ny, nx;
};

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    int field[501][501];
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> field[i][j];
        }
    }
    std::vector<Result> result;
    int y = 1, x = 1;
    int py, px;
    while (1) {
        py = y;
        px = x;
        if (x % 2 == 1) {
            if (y + 1 <= h) {
                y++;
            } else {
                x++;
            }
        } else {
            if (y - 1 >= 1) {
                y--;
            } else {
                x++;
            }
        }
        if (x > w)
            break;
        if (field[py][px] % 2 == 1) {
            field[py][px]--;
            field[y][x]++;
            Result push_result;
            push_result.px = px;
            push_result.py = py;
            push_result.nx = x;
            push_result.ny = y;
            result.push_back(push_result);
        }
    }

    cout << result.size() << endl;
    for (auto i : result) {
        cout << i.py << " " << i.px << " " << i.ny << " " << i.nx << endl;
    }
    return 0;
}


Measured memory_bytes: 5232
H, W = map(int, input().split())
s = [input() for _ in range(H)]
#print(s)

f1 = True
for i in range(H):
  if not f1:
    break
  for j in range(W):
    if not f1:
      break
    if s[i][j] == '.':
      continue
    f = False
    if i >= 1 and s[i-1][j] == '#':
      f = True
    if j <= W-2 and s[i][j+1] == '#':
      f = True
    if i <= H-2 and s[i+1][j] == '#':
      f = True
    if j >= 1 and s[i][j-1] == '#':
      f = True
    if not f:
      f1 = False

#print(s)
if f1:
  print('Yes')
else:
  print('No')


Measured memory_bytes: 3064
implicit none
integer:: x,a,b,c,count,i,j,k
read(5,*) a,b,c,x
count=0
 
do i=0,a
do j=0,b
do k=0,c
    if (x==500*i+100*j+50*k) then
        count=count+1
    endif
enddo
enddo
enddo

write(6,*) count
 
end

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };



int main() {
	int n;
	string s;
	cin >> n >> s;
	llint a[3] = { 0 };
	rep(i, 0, n)a[s[i] % 3]++;
	llint ans = a[0] * a[1] * a[2];
	
	rep(i, 0, n-2) {
		rep(j, i + 1, n-1) {
			int z = (j - i)+j;
			if (z < n) {
				if (s[i] == s[j])continue;
				if (s[j] == s[z])continue;
				if (s[i] == s[z])continue;
				ans--;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3596
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let a: usize = read();
    let b: usize = read();
    let mut cnt = 0;

    for i in 1..n + 1 {
        let ns: Vec<char> = i.to_string().chars().collect();
        let mut tmp = 0;
        for i in 0..ns.len() {
            let nsi = ns[i];
            tmp += nsi.to_digit(10).unwrap();
        }

        if tmp >= a as u32 && tmp <= b as u32 {
            cnt += i;
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 4352
fn main() {
    let x: Vec<i32> = read_vec();
    println!("{}", solve(&x));
}

fn read<T: std::str::FromStr>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn solve(x: &[i32]) -> usize {
    x.iter().position(|&x| x == 0).unwrap() + 1
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_solve_1() {
        assert_eq!(1, solve(&[0, 2, 3, 4, 5]));
    }

    #[test]
    fn test_solve_2() {
        assert_eq!(3, solve(&[1, 2, 0, 4, 5]));
    }
}


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

using namespace std;

int main(){
	int n;
	cin >> n;
	vector<int> Hi(n,0);
	vector<int> Low(n,0);
	
	for(int i=0;i<n;i++){
		cin >> Hi[i];
	}
	
	int Low_sum=0;
	for(int i=0;i<n;i++){
		cin >> Low[i];
		Low_sum+=Low[i];
	}	
	
	int Hi_now=0,Low_now=0,sum=0;
	for(int i=0;i<n;i++){
		 Hi_now+=Hi[i];
		 if(i>=1)Low_now+=Low[i-1];
		 sum=max(sum,Hi_now+Low_sum-Low_now);
	}	
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){

  int D,N;
  int ans;
  scanf("%d %d", &D, &N);

  ans = N;

  if(N==100) ans++;
  for(int i=0; i<D; i++){
    ans *= 100;
  }

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
import sys

n=int(input())
A=list(map(int,input().split()))
A.sort()

if n==2:
    print(A[1],A[0])
    sys.exit()

p=A[-1]
h=p/2
for i in range(n-1):
    if A[i]>=h:
        break
if abs(A[i-1]-h)<=abs(A[i]-h):
    q=A[i-1]
else:
    q=A[i]
print(p,q)

Measured memory_bytes: 14052
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int main()
{
    long long int i,j,k,n,x;
    vector<long long int>v,u;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>k;
        v.push_back(k);
    }
    u=v;
    sort(v.begin(),v.end());
    for(i=0;i<v.size();i++)
    {
        if(u[i]>v[n/2-1])
        {
            cout<<v[n/2-1]<<endl;
        }
        else
            cout<<v[n/2]<<endl;
    }
   // x=n/2;

    return 0;
}


Measured memory_bytes: 5488
for i in range(3):
        h,m,s,nh,nm,ns = map(int,input().split())
        t = nh * 3600 + nm * 60 + ns - (h * 3600 + m * 60 + s)
        h = t // 3600
        m = t % 3600 // 60
        s = t % 60
        print(h,m,s)

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

typedef std::pair <int, int> pr;
const int N = 100054, M = N * 2, INF = 0x3f3f3f3f;

int n, E = 0;
int to[M], first[N], next[M];
int d[N];
std::priority_queue <pr, std::vector <pr>, std::greater <pr> > pq;

inline void addedge(int u, int v) {
	to[++E] = v, next[E] = first[u], first[u] = E;
	to[++E] = u, next[E] = first[v], first[v] = E;
}

bool Dakstrij() {
	int i, x, y, D;
	for (; !pq.empty(); ) {
		std::tie(D, x) = pq.top(), pq.pop();
		if (d[x] != D) return false;
		for (i = first[x]; i; i = next[i])
			if (d[y = to[i]] >= INF)
				pq.emplace(d[y] = D + 1, y);
			else if (d[y] > D + 1) return false;
	}
	return true;
}

int main() {
	int i, u, v, m; bool succ;
	scanf("%d", &n);
	for (i = 1; i < n; ++i) scanf("%d%d", &u, &v), addedge(u, v);
	memset(d, 63, sizeof d);
	for (scanf("%d", &m); m; --m) scanf("%d%d", &u, &v), pq.emplace(d[u] = v, u);
	succ = Dakstrij();
	for (i = 1; i <= E && succ; i += 2) succ &= abs(d[to[i]] - d[to[i + 1]]) == 1;
	puts(succ ? "Yes" : "No");
	for (i = 1; i <= n && succ; ++i) printf("%d\n", d[i]);
	return 0;
}

Measured memory_bytes: 4212
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
even = 0
odd = 0
four = 0
ans = false
a.each do |i|
    if i % 4 == 0 then
        four += 1
    elsif i % 2 == 0 then
        even += 1
    else
        odd += 1
    end
end

if odd.zero? then
    ans = true
elsif even.zero? && four >= odd-1 then
    ans = true
elsif four >= odd then
    ans = true
end

puts ans ? "Yes" : "No"

Measured memory_bytes: 9476
import java.util.*;
public class Main {
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int C = 0;
        List<Integer> list = new ArrayList<>();
		// MAX
		int N = sc.nextInt();
      	int tmp = 0;
      	//System.out.println(N);
        // 3 nest for 
        for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= N ; j++){
                for(int k = 1 ; k <= N ; k++){
                    tmp = (i * 100) + (j * 10) + k; 
                    	//System.out.println(tmp);
                        list.add(tmp);
                    
                }
            }
        }
		// 出力
		System.out.println(list.size());
	}
}

Measured memory_bytes: 21716
// abc131b.cpp : Bite Eating
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N, L; cin>>N>>L;
	int R = L + N - 1;
	cout<< (L+R)*N/2 - (0<L? L: R<0? R: 0) <<"\n";
}

Measured memory_bytes: 256
#pragma GCC optimize(3)
#include <stdio.h>
int math[]={-1,1};
int main()
{
	int a[4];register int i,j,k;
	for(i=0; i<4; ++i)
	{
		char c=getchar();
		a[i]=c-'0';
	}
	for (i=0; i<2; ++i)
		for (j=0; j<2; ++j)
			for (k=0; k<2; ++k)
				if(a[0]+math[i]*a[1]+math[j]*a[2]+math[k]*a[3]==7)
				{
					printf("%d",a[0]);
					printf("%c",i==0?'-':'+');
					printf("%d",a[1]);
					printf("%c",j==0?'-':'+');
					printf("%d",a[2]);
					printf("%c",k==0?'-':'+');
					printf("%d",a[3]);
					printf("=7\n");
					return 0;
				}
}


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

using namespace std;

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)

#define AB 0
#define A 1
#define B 2

lli check(string str){
	lli rtn = 0;
	REP(i,0,str.size()-1){
		if(str.at(i)=='A'&&str.at(i+1)=='B'){
			rtn++;
		}
	}
	return rtn;
}

signed main(){

	lli n;
	cin>>n;
	vector<string> s(n);
	lli ans = 0;
	lli dp[3]={0};

	/*最初がBで最後がA*/
	/*最初がBのみ*/
	/*最後がAのみ*/
	/*この3つをカウントする*/
	
	REP(i,0,n){
		cin>>s[i];
		ans += check(s[i]);
		if(s[i].at(0) == 'B' && s[i].at(s[i].size()-1) == 'A')dp[AB]++;
		else if(s[i].at(0)=='B')dp[B]++;
		else if(s[i].at(s[i].size()-1)=='A')dp[A]++;
		else ;
	}

	/*dp[A]が1つ以上あるなら、それを先頭にした後、dp[AB]を消化し続ける*/
	if(dp[A]){
		ans += dp[AB];
		dp[AB]=0;
		dp[A]--;
		/*そのあとdp[B]が1つ以上あるなら1個消化してABを作る*/
		if(dp[B]){
			ans++;
			dp[B]--;
		}
		/*その後、dp[A]dp[B]の少ないほうを足す*/
		ans += min(dp[A],dp[B]);
	}
	else if(dp[B]){
		ans += dp[AB];
		dp[AB]=0;
	}
	else if(dp[AB]){
		ans += dp[AB]-1;
	}

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

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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};


signed main(){
    gearup;
    string s; cin >> s;
    int a = s[0]-'0';
    int b = s[1]-'0';
    int c = s[2]-'0';
    int d = s[3]-'0';
    if(a+b+c+d==7)printf("%d+%d+%d+%d=7\n",a,b,c,d);
    else if(a+b+c-d==7)printf("%d+%d+%d-%d=7\n",a,b,c,d);
    else if(a+b-c-d==7)printf("%d+%d-%d-%d=7\n",a,b,c,d);
    else if(a+b-c+d==7)printf("%d+%d-%d+%d=7\n",a,b,c,d);
    else if(a-b+c+d==7)printf("%d-%d+%d+%d=7\n",a,b,c,d);
    else if(a-b-c-d==7)printf("%d-%d-%d-%d=7\n",a,b,c,d);
    else if(a-b+c-d==7)printf("%d-%d+%d-%d=7\n",a,b,c,d);
    else if(a-b-c+d==7)printf("%d-%d-%d+%d=7\n",a,b,c,d);
}



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



int main()
{
    ll a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<=b;i++){
        if((a*i)%b==c){
            cout<<"YES";return 0;
        }
    }
    cout<<"NO";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

/*
    有向グラフであることに注意 !!
    計算量 : O(FE)
*/
template <typename T>
struct FordFulkerson {
    struct edge {
        int to;
        T cap;
        int rev;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    vector<vector<edge>> G;
    vector<bool> used;

    FordFulkerson(int n) : G(n), used(n) {}

    void add_edge(int from, int to, T cap) {
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, 0, G[from].size() - 1);
    }

    T dfs(int v, int t, T f) {
        if (v == t) return f;
        used[v] = true;
        for (edge& e : G[v]) {
            if (!used[e.to] && e.cap > 0) {
                T d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    T flow(int s, int t, T INF = 1e9) {
        T fl = 0;
        while (true) {
            fill(used.begin(), used.end(), false);
            T f = dfs(s, t, INF);
            if (f == 0) break;
            fl += f;
        }
        return fl;
    }
};

signed main() {
    int h, w;
    cin >> h >> w;
    string a[h];
    rep(i, h) {
        cin >> a[i];
    }
    FordFulkerson<int> ff(h + w + 2);
    rep(i, h) {
        rep(j, w) {
            if (a[i][j] == 'S') {
                ff.add_edge(0, i + 2, INF);
                ff.add_edge(0, j + h + 2, INF);
            } else if (a[i][j] == 'T') {
                ff.add_edge(i + 2, 1, INF);
                ff.add_edge(j + h + 2, 1, INF);
            } else if (a[i][j] == 'o') {
                ff.add_edge(i + 2, j + h + 2, 1);
                ff.add_edge(j + h + 2, i + 2, 1);
            }
        }
    }
    int ans = ff.flow(0, 1, INF);
    cout << (ans < INF ? ans : -1) << endl;
    return 0;
}

Measured memory_bytes: 4276
#include <iostream>
#include <set>
#include <string>
#include <queue>
using namespace std;

#define mkp(x, y) (make_pair(x, y))

int main() {
	string in;

	while(cin >> in, in != "0") {
		set<string> appeared;
		queue<pair<string, int> > q;
		int loop_flag = -1;

		appeared.insert(in);
		q.push(mkp(in, 0));

		while(!q.empty()) {
			string worm;
			int count;
			pair<string, int> p;
			bool complete_flag = true;
			p = q.front(); q.pop();
			worm = p.first;
			count = p.second;

			for(int i = 1; i < worm.size(); i++) {
				if(worm[i - 1] != worm[i]) {
					string tmp(worm);
					tmp[i - 1] = tmp[i] = 'r' + 'g' + 'b' - worm[i - 1] - worm[i];
					if(appeared.find(tmp) == appeared.end()) {
						q.push(mkp(tmp, count + 1));
						appeared.insert(tmp);
					}
					complete_flag = false;
				}
			}

			if(complete_flag) {
				loop_flag = count;
				break;
			}
		}

		if(loop_flag != -1)
			cout << loop_flag << endl;
		else
			cout << "NA" << endl;
	}

	return 0;
}

Measured memory_bytes: 2668
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def convert(s, a, b):
    res = []
    ca = ord('a')
    for c in s:
        if c == ' ':
            res.append(" ")
        else:
            res.append(chr((((ord(c) - ca)*a + b) % 26) + ca))
    return "".join(res)

def solve():
    s = readline().strip()
    for a in range(26):
        for b in range(26):
            s1 = convert(s, a, b)
            if "that" in s1 or "this" in s1:
                write(s1)
                write("\n")
T = int(readline())
for i in range(T):
    solve()



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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;

int main(){
  ll K,A,B;
  cin>>K>>A>>B;
  if(B - A > 2){
    cout << A + ((K-A+1)/2)*(B-A) + (K-A+1)%2 << endl;
  }else{
    cout << K+1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}

int gcd(int a, int b){
  int ma = max(a,b);
  int mi = min(a,b);
  if(mi == 0) return ma;

  return gcd(mi, ma%mi);
}

int main(){
  llong R = 0;
  llong G = 0;
  llong B = 0;
  llong N;
  string S;
  cin >> N >> S;
  for(llong i=0; i<N; ++i){
    if(S[i] == 'R') ++R;
    else if(S[i] == 'G') ++ G;
    else if(S[i] == 'B') ++ B;
  }
  llong minus = 0;
  for(llong i=0; i<N-2; ++i){
    for(llong j=1; i+j+j<N; ++j){
      if(S[i] != S[i+j]) if(S[i+j] != S[i+j+j]) if(S[i+j+j] != S[i]) ++minus;
    }
  }
  cout << R*G*B - minus << endl;
}

Measured memory_bytes: 3636
A, B = map(int, input().split())
S = input()

for i in range(A):
  if not '0' <= S[i] <= '9':
    print("No")
    exit()
if S[A] != '-':
  print("No")
  exit()
for i in range(A+1, A+B+1):
  if not '0' <= S[i] <= '9':
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 38256
#include <iostream>
#include <string>
#include <vector>
#include <sstream>

template <typename T>
void quicksort(T* a, int begin, int end) {
    if (begin < end) {
        int mid = (begin + end) / 2;
        auto pivot = a[mid];

        int left = begin;
        int right = end;

        while (true) {
            while (a[left] < pivot) {
                left++;
            }
            while (pivot < a[right]) {
                right--;
            }
            if (left >= right) {
                break;
            }

            int tmp = a[left];
            a[left] = a[right];
            a[right] = tmp;

            left++;
            right--;
        }

        quicksort(a, begin, left - 1);
        quicksort(a, right + 1, end);
    }
}

int main()
{
    int num;
    std::cin >> num;

    std::vector<int> a(num);

    std::string s;
    while (std::getline(std::cin, s)) {
        if (!s.empty()) {
            break;
        }
    }

    std::stringstream ss(s);

    int cnt = 0;
    std::string buf;

    while (std::getline(ss, buf, ' ')) {
        a[cnt++] = ::atoi(buf.c_str());
    }

    quicksort(&a[0], 0, num - 1);

    int player_pos = 0;
    int player[2] = { 0 };

    int array_pos = num - 1;

    while (array_pos >= 0) {
        player[player_pos] += a[array_pos--];
        player_pos = 1 - player_pos;
    }

    int result = player[0] - player[1];

    std::cout << result << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <functional>
#include <ostream>
#include <queue>
#include <random>
#include <string>
#include <stack>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using ll = long long;

template<typename T>
std::ostream& operator << (std::ostream& os, std::vector<T> v) {
  os << "[";
  for (int i = 0; i < int(v.size()); ++i) {
    os << v[i] << (i == int(v.size()) - 1 ? "" : ", ");
  }
  cerr << "]";
  return os;
}

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

  std::string s;
  int x, y;

  static bool dp[4010][16010]; // dp[i][d] := i回目の移動でdに到達できるか
  std::vector<int> xd, yd;

  cin >> s;
  cin >> x >> y;

  bool ans = true;
  int cnt = 0;

  // s を圧縮
  for (int i = 0; i < int(s.size()); ++i) {
    if (s[i] == 'T') {
      if (xd.size() == yd.size()) {
        xd.push_back(cnt);
      }
      else {
        yd.push_back(cnt);
      }
      cnt = 0;
    }
    else {
      cnt++;

      if (int(s.size()) - 1 == i) {
        if (xd.size() == yd.size()) {
          xd.push_back(cnt);
        }
        else {
          yd.push_back(cnt);
        }
      }
    }
  }

  std::memset(dp, false, sizeof dp);

  // x 座標に関して, s を実行した後に目的の座標に到達できるか
  dp[0][8000] = dp[1][xd[0] + 8000] = true;

  for (int i = 1; i < int(xd.size()); ++i) {
    for (int _x = -8000; _x <= 8000; ++_x) {
      if (dp[i][_x + 8000]) {
        int nx1 = _x + xd[i] + 8000, nx2 = _x - xd[i] + 8000;
        dp[i + 1][nx1] = dp[i + 1][nx2] = true;
      }
    }
  }

  ans &= dp[xd.size()][x + 8000];

  std::memset(dp, false, sizeof dp);

  // y 座標に関しても同様
  dp[0][8000] = true;

  for (int i = 0; i < int(yd.size()); ++i) {
    for (int _y = -8000; _y <= 8000; ++_y) {
      if (dp[i][_y + 8000]) {
        int ny1 = _y + yd[i] + 8000, ny2 = _y - yd[i] + 8000;
        dp[i + 1][ny1] = dp[i + 1][ny2] = true;
      }
    }
  }

  ans &= dp[yd.size()][y + 8000];

  if (ans) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 62976
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i], C[i] = map(int,input().split())
    
num = [0]*100001
for i in A:
    num[i] += 1

S = [0]*(Q+1)
S[0] = sum(A)
change = 0
for i in range(Q):
    change = num[B[i]]
    S[i+1] = S[i] + change*(C[i]-B[i])
    num[B[i]] -= change
    num[C[i]] += change
    
for i in S[1:]:
    print(i)

Measured memory_bytes: 28316
fun main(arr:Array<String>) {
    val n = readLine()!!.toInt()
    val numbers = readLine()!!.split(" ").map { it.toInt() }

    val ans = (0 until n).map { if(it==0) 1 else numbers[it] - numbers.take(it).max()!!  }.filter { it >= 0 }.count()
    println(ans)
}


Measured memory_bytes: 37720
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    print(max(A+B, A-B, A*B))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <string>
using namespace std;
int main()
{
  string S;
  cin >> S;
  bool ans = true;
  
  int N = S.length();
  for (int i = 0; i < N/2; i++) {
    if (S[i] != S[N-1-i]) ans = false;
  }
  
  for (int i = 0; i < N/2/2; i++) {
    if (S[i] != S[N/2-1-i]) ans = false;
  }

  for (int i = 0; i < N/2/2; i++) {
    if (S[i+N/2+1] != S[N-1-i]) ans = false;
  }
  
  if (ans) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
A = [1,3,5,7,8,10,12]
B = [4,6,9,11]
C = [2]
x,y = map(int, input().split())

if (x in A and y in A) or (x in B and y in B) or (x in C and y in C):
  print("Yes")
else:
  print("No")


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

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define deg(x) cout<<x<<" "


using ll = long long;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//#ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	//#endif
	int n,k;
	cin >> n >> k;
	char c;
	f(i,1,n+1){
		cin >> c;
		if(i==k){
			if(c=='A') cout << 'a';
			else if(c=='B') cout << 'b';
			else cout << 'c';
		}
		else{
			cout << c ;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[20][20];
int main() {
	ll i,j,p,q,k,flag,cnt;
	for (i=0;i<=9;i++)
		f[1][i]=1;
	for (i=2;i<=10;i++) {
		f[i][0]=f[i-1][0]+f[i-1][1];
		for (j=1;j<=8;j++)
			f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1];
		f[i][9]=f[i-1][8]+f[i-1][9];
	}
	cin>>k;
	flag=0; cnt=0;
	for (i=1;i<=10;i++) {
		for (j=1;j<=9;j++) {
//			cout<<i<<' '<<j<<' '<<f[i][j]<<endl;
			cnt+=f[i][j];
			if (cnt>=k) {
				flag=1; break;
			}
		}
		if (flag) break;
	}
	p=i; q=j;
	for (i=p;i>=1;i--) {
		cout<<q;
		cnt-=f[i][q];
		if (q==0){
			if (cnt+f[i-1][q]>=k) 
			 	cnt+=f[i-1][q];
			else cnt+=f[i-1][q]+f[i-1][q+1],q++;
		}
		else if (cnt+f[i-1][q-1]>=k) 
			cnt+=f[i-1][q-1],q--;
		else if (cnt+f[i-1][q-1]+f[i-1][q]>=k)
			cnt+=f[i-1][q-1]+f[i-1][q];
		else cnt+=f[i-1][q-1]+f[i-1][q]+f[i-1][q+1],q++;
	}
	cout<<endl;
	return 0;
}

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

int main( void )
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    
    if ( abs(b-a) <= d && abs(c-b) <= d || abs(c-a) <= d )
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


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

using namespace std;

int gcd(int a, int b)
{
	while (b != 0) {
		int t = b;
		b = a % b;
		a = t;
	}
	return a;
}


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

	int n, x, i, j, k, g, xx;
	cin >> n >> xx;
	for (i = 0; i < n; i++) {
		cin >> x;
		if (i == 0) g = abs(xx - x);
		else g = gcd(g, abs(x - xx));
	}
	cout << g << "\n";

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

long gcd(long ,long );
long lcm(long ,long );


int main(void){
	long a, b, g, l;

	while ((scanf("%d %d", &a, &b)) != EOF) {	
		if (a > 2000000000) {
			printf("Error!\n\a");
			continue;
		} else if (b > 2000000000) {
			printf("Error!\n\a");
			continue;
		} else {
			g = gcd(a, b);
			l = lcm(a, b);
			if (l > 2000000000) {
				printf("Error!\n\a");
				continue;
			}
			printf("%d %d\n", g, l);
		}
	}
	return 0;
}
long gcd(long a, long b) {
	if ((!a) || (!b)) {
		printf("Error!\n\a");
		return 0;
	}

	while (a != b) {
		if (a > b)
			a = a - b;
		else
			b = b - a;
	}
	return a;
}

long lcm(long a, long b) {
	if ((!a) || (!b)) {
		printf("Error!\n\a");
		return 0;
	}

	return (a / gcd(a, b) * b);
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        vector<int> ws(n);
        for (auto &&x: ws) cin >> x;

        vector<vector<bool>> memo(n, vector<bool>(n, false));

        // 隣接した２つのブロックが消せるか
        for (int l = 0; l<n-1; l++) {
            int r = l+1;
            if (abs(ws[l]-ws[r]) < 2) 
              memo[l][r] = true;
        }

        // ２つのブロックを指定し、その間の区間が消せるか
        for (int len = 2; len<n; len++) {
            for (int l = 0; l+len<n; l++) {
                int r = l+len;
                for (int c = l+1; c<r; c++)
                    if (memo[l][c-1] && memo[c][r])  
                        memo[l][r] = true;

                if (memo[l+1][r-1] && abs(ws[l]-ws[r]) < 2)  
                    memo[l][r] = true;
            }
        }

        vector<int> dp(n, 0);
        for (int r=1; r<n; r++) {
            dp[r] = dp[r-1];
            for (int l=0; l<n; l++) {
                if (memo[l][r]) {
                    if (l == 0) dp[r] = max(dp[r], r-l+1);
                    else        dp[r] = max(dp[r], dp[l-1] + r-l+1);
                }
            }
        }

        // for (auto x: dp) cout << setw(3) << x; cout << endl;
        cout << *(max_element(dp.begin(), dp.end())) << endl;
    }
}



Measured memory_bytes: 3160
n = int(input())
s = str(input())

ans = 0

for i in range(n):
    x = set(s[:i+1])
    y = set(s[i+1:])

    z = 0
    for w in x:
        if w in y:
            z +=1
    if z > ans:
        ans = z
print(ans)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
 
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
 
int main(){
    int a,b,g,l;
    while(cin>>a>>b){
        g=gcd((a>=b)?a:b,(a>=b)?b:a);
        l=(a/g)*b;
        cout<<g<<" "<<l<<endl;
    }
    return 0;
}

Measured memory_bytes: 3024
#include <stdio.h>

int main(){

  int a,b,r;

  scanf("%d%d",&a,&b);

  if(a<b){

    r=a;
    a=b;
    b=r;

}

  while(1){

    r=a%b;
    if(r==0) break;
    a=b;
    b=r;

}

  printf("%d\n",b);

  return 0;

}

Measured memory_bytes: 592
#include<iostream>
#include<stdio.h>
#include<vector>
#include<ctype.h>
#include<string>
#include<cmath>
#include<string.h>
#include<sstream>
#include<limits.h>
using namespace std;

long long A,B,V,W,T;

int main(){
    cin>>A>>V>>B>>W>>T;
    if(abs(A-B)<=(V-W)*T){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3636
import Control.Monad
import Data.Char
import Data.Maybe

main = do
    n <- readLn
    replicateM n $ plus2num

plus2num = do
    [n1,n2] <- replicateM 2 getLine
    putStrLn $ fromMaybe "overflow" $ plusMaybe n1 n2

checkOverFlow :: String -> Maybe String
checkOverFlow str = if length str > 80 then Nothing else Just str

plusMaybe :: String -> String -> Maybe String
plusMaybe n1 n2 = do
    a <- checkOverFlow n1
    b <- checkOverFlow n2
    checkOverFlow $ plus a b

plus :: String -> String -> String
plus n1 n2 = reverse $ plus' 0 (reverse n1) (reverse n2)

plus' :: Int -> String -> String -> String
plus' carry [] []     = if carry == 0 then [] else intToDigit carry:[]
plus' carry (y:ys) [] = n : plus' (digitToInt c) [] ys
    where
        num = digitToInt y + carry
        [c,n] = if num < 10 then '0':show num else show num
plus' carry [] (y:ys) = n : plus' (digitToInt c) [] ys
    where
        num = digitToInt y + carry
        [c,n] = if num < 10 then '0':show num else show num
plus' carry (x:xs) (y:ys) = n:plus' (digitToInt c) xs ys
    where
        num = digitToInt x + digitToInt y + carry
        [c,n] = if num < 10 then '0':show num else show num

Measured memory_bytes: 3832
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>

using namespace std;



int main()
{
	int A,P;

	cin >> A >> P;

	int ans = (A*3 + P) / 2;


	printf("%d",ans);

	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int i,n,k,x,y,total=0;
    scanf("%d%d%d%d",&n,&k,&x,&y);
    for(i=1;i<=k;i++){
      if(i>n) break;
      total+=x;
    }
    if(n<=k) {printf("%d",total);return 0;}
    for(i=1;i<=n-k;i++){
        total+=y;
    }
    printf("%d",total);
    return 0;
}

Measured memory_bytes: 128
n,k = map(int,input().split())
ans = 0

for i in range(k, n+2):
  a = 0.5* i* (i-1)
  b = 0.5* n* (n+1) - 0.5* (n-i)* (n-i+1)
  ans += int(b-a+1)
  
print(ans%(10**9+7))


Measured memory_bytes: 9124
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int vis[26];
int n,ans,c;
string a;
int main()
{
	ans=0;
    memset(vis,0,sizeof(vis));
    cin>>n;
    cin>>a;
    for(int i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        c=0;
        for(int j=0;j<=i;j++)
        {
            for(int k=i+1;k<n;k++)
            {
                if(a[j]==a[k] && vis[a[j]-'a']==0)
                {
                    c++;
                    vis[a[j]-'a']=1;
                }
            }
        }
        ans=max(ans,c);
    }
    printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256