akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import sys

money = 100000

for s in sys.stdin:
    count = 0
    d = int(s)
    for i in range(10):
        if i > d :
            pass
        for j in range(10):
            if i + j > d:
                pass
            for k in range(10):
                if i + j + k :
                    pass
                for l in range(10):
                    if i + j + k + l > d :
                        pass
                    if i + j + k + l == d :
                        count += 1
    print count

Measured memory_bytes: 4208
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
  char ch[1200];
  int count[26], i, n;

  //zero  
    
  for(i = 0; i < 1200; i++)
  {
    ch[i] = '\n';
  }
  for(i = 0; i < 26; i++)
  {
    count[i] = 0;
  }

  while(cin >> ch[n])
  {
    if('A' <= ch[n] && ch[n] <= 'Z')
    {
      ch[n] += 32;
    }
    if('a' <= ch[n] && ch[n] <= 'z')
    {
      count[ ch[n] - 'a' ]++;
    }
    n++;
  }
    
  //out
      
  for(i = 0; i < 26; i++)
  {
    printf("%c : %d\n", i + 97, count[i]);
  }

  return 0;
}


Measured memory_bytes: 3224
# coding: utf-8
import sys
from collections import defaultdict
from bisect import bisect_right

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

# Aの中で次に同じ数字が出てくるindex
N, K = lr()
A = lr()
next_index = [-1] * N
dict = defaultdict(list)
for i in range(N):
    dict[A[i]].append(i)

for i in range(N):
    a = A[i]
    length = len(dict[a])
    j = bisect_right(dict[a], i)
    next_index[i] = dict[a][j%length]

cur = 0
time = 1
while cur != N:
    ne = next_index[cur]
    if ne <= cur:
        time += 1
    cur = ne + 1
# timeで一周する
K %= time
time = 0
cur = 0
while time < K:
    ne = next_index[cur]
    if ne <= cur:
        time += 1
    if time == K:
        break
    cur = ne + 1

answer = []
while cur < N:
    ne = next_index[cur]
    if ne <= cur:
        answer.append(A[cur])
        cur += 1
    else:
        cur = ne + 1

print(*answer)
# 14

Measured memory_bytes: 59692
#include <bits/stdc++.h>
//#define Ak

using namespace std;

template< class t>
long long int gcd( t g,t h )
{
    return ( h==0 ? g : gcd(h,g%h) );
}

int main()
{
    #ifdef Ak
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long int n,c,k,i,j,t[100005],temp,ans=0;
    
    list< long long int >v,tl;
    
   // map< long long int >m;
   
    cin>>n>>c>>k;;
    
    for(i=0;i<n;i++)
    {
        cin>>t[i];
    }
    
    sort(t,t+n);
    
    for(i=0;i<n-1;i++)
    {temp=i;
        for(j=temp+1;j<min(temp+c,n);j++)
        {
            if(t[temp]+k>=t[j])
            {
              i++;
              t[j]=0;
            }
            else
            {
                break;
            }
        }
        t[temp]=0;
        ans++;
    }
    
    for(i=0;i<n;i++)
    {
        if(t[i]!=0)
        {
            ans++;
        }
    }
    
    cout<<ans;
    
    return 0;
    
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
	int n, a[100], i, j, r = 0;

	cin >> n;
	for (i = 0; i < n; ++i)
		cin >> a[i];

	for (i = 0; i < n; ++i)
		for (j = n-1; j > i; --j)
			if (a[j] < a[j-1])
				swap(a[j], a[j-1]), ++r;

	for (i = 0; i < n; ++i)
	{
		cout << a[i];
		if (i < n-1)
			cout << " ";
	}
	cout << endl << r << endl;

	return 0;
}

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

const int bB = 8;
const int B = 1 << bB;

int up(int x) {
	return (x + (1 << bB) - 1) >> bB;
}

int down(int x) {
	return x >> bB;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	const int H = up(n);
	vector<int> bv(H, 0), v(n, 0);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y; x--;
		if (com == 0) {
			v[x] += y;
			bv[down(x)] += y;
		}
		else {
			int res = 0;
			for (int i = x; i < y && i < (up(x) << bB); i++) {
				res += v[i];
			}
			if (up(x) <= down(y)) {
				for (int i = up(x); i < down(y); i++) {
					res += bv[i];
				}
				for (int i = down(y) << bB; i < y; i++) {
					res += v[i];
				}
			}
			printf("%d\n", res);
		}
	}
	return 0;
}



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

ll gcd(ll a,ll b){return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(void){
    int N;
    cin>>N;
    ll res=1,t;
    rep(i,N){
        cin>>t;
        res = lcm(res,t);
    }
    cout<<res<<endl;
    return 0;
}


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

using namespace std;
using i64 = long long;

bool solve(){
    int n,m;cin >> n >> m;
    if(n == 0)return 0;
    vector<string> vec;
    for(int i = 0;i < n;i++){
        string s;cin >> s;
        vec.push_back(s);
    }
    string s;cin >> s;
    long long ans = 0;
    pair<int,int> now = make_pair(0, 0);
    for(int i = 0;i < s.size();i++){
        bool t = false;
        for(int j = 0;j < n;j++){
            for(int k = 0;k < m;k++){
                if(vec.at(j).at(k) == s.at(i)){
                    t = true;
                    ans += abs(now.first - j);
                    ans += abs(now.second - k);
                    now = make_pair(j, k);
                    break;
                }
            }
            if(t)break;
        }
    }
    cout<<ans+s.size()<<endl;
    return true;
}

signed main()
{
    while(solve());
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;



int main(){
	int h, a;
	cin >> h >> a;
	int ans = h/a;
	if(h%a){
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    std::ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n-1);
    for(int i=0;i<n;++i){
        cin >> a[i];
        --a[i];
    }

    int ans = 0;
    for(int i=0;i<n;++i) {
        cin >> b[i];
        ans += b[i];
    }

    for(int i=0;i<n-1;++i) {
        cin >> c[i];
    }

    for(int i=1;i<n;++i) {
        if(a[i-1] + 1 == a[i]) {
            ans += c[a[i-1]];
        }
    }

    cout << ans << endl;

}


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

int main(){
	int N;
	while (cin >> N){
		if (N == 0) break;
		vector<int>K(N);
		for (int i = 0; i < N; i++){
			cin >> K[i];
		}
		bool isOk = false;
		for (int i = 0; i < K.size(); i++){
			if (K[i] >= 2) isOk = true;
		}
		if (!isOk){
			cout << "NA" << endl;;
		}
		else{
			int ans = 0;
			for (int i = 0; i < K.size(); i++){
				if (K[i] >= 1) ans++;
			}
			ans++;
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 1232
#include<stdio.h>
int main(){
int a,b,c,d,i,e=0;
while(1){
scanf("%d\n",&a);
if(a==0){
break;
}
else{
scanf("%d\n",&b);
for(i=0;i<b;i++){
scanf("%d %d\n",&c,&d);
e=e+(d-c);
}
if(e>=a){
printf("OK\n");
}
else{
printf("%d\n",a-e);
}
e=0;
}
}
return 0;
}


Measured memory_bytes: 2056
class Line
	include Math

	def self.through_two_points(x1, y1, x2, y2)
		a = y1 - y2
		b = x2 - x1
		c = a * x1 + b * y1
		new(a, b, c, x1, y1, x2, y2)
	end

	def parallel?(l)
		@a * l.b == @b * l.a
	end

	def cross?(l)
		return false if parallel?(l)
		(@a * l.x1 + @b * l.y1 - @c) * (@a * l.x2 + @b * l.y2 - @c) <= 0 &&
		(l.a * @x1 + l.b * @y1 - l.c) * (l.a * @x2 + l.b * @y2 - l.c) <= 0
	end

	def dist(x, y)
		a = hypot(@x1 - x, @y1 - y)
		b = hypot(@x2 - x, @y2 - y)
		c = hypot(@x1 - @x2, @y1 - @y2)
		return a if a*a + c*c < b*b
		return b if b*b + c*c < a*a
		(@a * x + @b * y - @c).abs / sqrt(@a ** 2 + @b ** 2)
	end

	private_class_method :new

	def initialize(*args)
		@a, @b, @c, @x1, @y1, @x2, @y2 = args	
		if @a < 0
			@a *= -1
			@b *= -1
			@c *= -1
		elsif @a == 0 && @b < 0
			@b *= -1
			@c *= -1
		end
	end

	attr_reader :a, :b, :c, :x1, :y1, :x2, :y2
end

loop do
	n = gets.to_i
	break if n == 0
	xs, ys, xe, ye = gets.split.map(&:to_i)
	course = Line.through_two_points(xs, ys, xe, ye)
	blocks = (1..n).map {gets.split.map(&:to_i)}
	rs = blocks.map do |x1, y1, x2, y2, h|
		next 0 if x1 <= xs && xs <= x2 && y1 <= ys && ys <= y2
		next 0 if x1 <= xe && xe <= x2 && y1 <= ye && ye <= y2

		l = Line.through_two_points(x1, y1, x1, y2)
		next 0 if l.cross?(course)
		r = Line.through_two_points(x2, y1, x2, y2)
		next 0 if r.cross?(course)
		b = Line.through_two_points(x1, y1, x2, y1)
		next 0 if b.cross?(course)
		t = Line.through_two_points(x1, y2, x2, y2)
		if t.cross?(course)
			p course
			p t
			next 0
		end

		ds = [
			course.dist(x1, y1),
			course.dist(x1, y2),
			course.dist(x2, y1),
			course.dist(x2, y2),
			l.dist(course.x1, course.y1),
			r.dist(course.x1, course.y1),
			b.dist(course.x1, course.y1),
			t.dist(course.x1, course.y1),
			l.dist(course.x2, course.y2),
			r.dist(course.x2, course.y2),
			b.dist(course.x2, course.y2),
			t.dist(course.x2, course.y2),
		]

		rs = ds.map do |d|
			if d < h
				d
			else
				(d * d / h + h) / 2
			end
		end
		
		rs.min
	end
	p rs.min
end

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


long long int B(long long int n){
	long long int result = 0;

	for(long long int i = 1; i<=n ; i++){
			if((i%3 != 0) && (i%5 != 0)){
				result = result +i;
		
			}
	}

	return result;

}

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

	
	long long int x = B(n);

	cout<<x;
}

Measured memory_bytes: 3648
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	var arr = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}

	sort.Sort(sort.Reverse(sort.IntSlice(arr)))
	fmt.Println(arr[0] - arr[n-1])
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){
  int k;
  cin>>k;

  int a,b,c;
  int ans=0;

  for(int a=1;a<=k;a++){
     for(int b=1;b<=k;b++){
        for(int c=1;c<=k;c++){
           int d=gcd(gcd(a,b),gcd(b,c));
          
           ans+=d;
        }
     }
  }
  cout<<ans;



  
return 0;
}


Measured memory_bytes: 3636
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    n1 = sum([int(i) for i in list(x)])
    if n1 > 1:
        sums = [n1 - 1, n1 + 1]
    else:
        sums = [None, n1 + 1]
    ns = len(sums)
    remainders = [[0] * n for _ in range(len(sums))]
    total_remainder = [0] * ns
    for i in range(ns):
        if sums[i] != None:
            remainders[i][0] = 1 % sums[i]
            if x[-1] == "1":
                total_remainder[i] = remainders[i][0]
            for j in range(1, n):
                remainders[i][j] = remainders[i][j-1] * 2 % sums[i]
                if x[-1-j] == "1":
                    total_remainder[i] = (total_remainder[i] +  remainders[i][j]) % sums[i]
                    #print("tr", i, total_remainder[1])
    for i in reversed(range(n)):
        if n1 == 1 and x[-1 -i] == "1":
            print(0)
            continue
        if x[-1 -i] == "1":
            rm = (total_remainder[0] - remainders[0][i]) % sums[0]
        else:
            rm = (total_remainder[1] + remainders[1][i]) % sums[1]
        if rm == 0:
            print(1)
            continue
        ans = 1
        while rm != 0:
            #print("rm", rm)
            rm = rm % countbin(rm)
            ans += 1
        print(ans)



    return

def countbin(num):
    return sum([int(i) for i in list(bin(num)[2:])])



n = RN()
x = RS()
solve()


Measured memory_bytes: 89640
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <cmath>
#include <string>

using namespace std;

int height(int n) {
    int ret = 0;
    for(int i =1;i <= n;i++)
        ret += i;
    return ret;
}

int main(void) {
    int a,b;
    cin >> a >> b;
    cout << height(abs(a - b)) - max(a,b) << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)

Measured memory_bytes: 69228
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, a, b, l, val[800007][3], tag[800007];
int read()
{
	int num = 0;
	char c = getchar();
	while (c<'0' || c>'9')c = getchar();
	while (c >= '0' && c <= '9')num = num * 10 + c - '0', c = getchar();
	return num;
}
int add(int w, int v)
{
	for (int j = 0; j <= 2; j++)
		val[w][j] += v;
	tag[w] += v;
	return 0;
}
int down(int w)
{
	if (!tag[w])return 0;
	add(2 * w, tag[w]);
	add(2 * w + 1, tag[w]);
	tag[w] = 0;
	return 0;
}
int up(int w)
{
	for (int i = 0; i <= 2; i++)
		val[w][i] = min(val[2 * w][i], val[2 * w + 1][i]);
	return 0;
}
int change(int w, int l, int r, int x, int v)
{
	if (l == r)
	{
		val[w][0] = v;
		val[w][1] = v - x;
		val[w][2] = v + x;
		return 0;
	}
	down(w);
	int mid = (l + r) / 2;
	if (x <= mid)change(2 * w, l, mid, x, v);
	else change(2 * w + 1, mid + 1, r, x, v);
	up(w);
	return 0;
}
int ask(int p, int w, int l, int r, int x, int y)
{
	if (x <= l && r <= y)
		return val[w][p];
	down(w);
	int mid = (l + r) / 2, res = 1e18;
	if (x <= mid)res = min(res, ask(p, 2 * w, l, mid, x, y));
	if (y > mid)res = min(res, ask(p, 2 * w + 1, mid + 1, r, x, y));
	return res;
}
signed main()
{
	n = read();
	q = read();
	a = read();
	b = read();
	l = read();
	memset(val, 0x3f, sizeof val);
	change(1, 1, n, b, abs(l - a));
	change(1, 1, n, a, abs(l - b));
	for (int i = 2; i <= q; i++)
	{
		int num = read(), len = abs(num - l);
		int res1 = ask(0, 1, 1, n, num, num) + len;
		int res2 = ask(1, 1, 1, n, 1, num) + num;
		int res3 = ask(2, 1, 1, n, num + 1, n) - num;
		add(1, len);
		change(1, 1, n, l, min(res1, min(res2, res3)));
		l = num;
	}
	printf("%lld\n", val[1][0]);
	return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long int INF=1e9;

int main() {
    long long int N;
    cin >> N;
    vector<long long int> cost;
    cost.push_back(1e9);
    cost.push_back(1);
    
    long long int p6=6;
    while(p6<=N) {
        cost.push_back(p6);
        p6 *= 6;
    }
    
    long long int p9=9;
    while(p9<=N) {
        cost.push_back(p9);
        p9 *= 9;
    }
    
    sort(cost.begin(), cost.end(), greater<long long int>());
    cost[0]=0;
    
    vector<long long int> memo(N+1, INF);
    memo[0]=0;
    for(int c=1; c<cost.size(); c++) {
        // cout << cost[c] << ": ";
        for(int i=0; i<N+1; i++) {
            if(i-cost[c]>=0) {
                memo[i] = min(memo[i-cost[c]]+1, memo[i]);
            }
            // cout << memo[i] << " ";
        }
        // cout << endl;
    }
    
    cout << memo[N] << endl;

    return 0;
    
}

Measured memory_bytes: 1024
void main() {
	auto ip = readAs!(int[]).sort().array;
	(ip[2] - ip[0]).writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

int n, a[55], c;
int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
//  freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    if(a[i] != i) ++c;
  }
  if(c > 2) cout << "NO\n";
  else cout << "YES\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using M = map<int, int>;
ll INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n;
  cin >> n;
  M m;
  repI(i, 1, n) {
    ll a;
    cin >> a;
    a--;
    m[a]++;
  }

  rep(i, n) cout << m[i] << endl;;


  return 0;
}


Measured memory_bytes: 13008
#include "bits/stdc++.h"
using namespace std;

struct Node{int key; Node *right,*left,*parent;};
Node *root,*NIL;

Node * find(Node *u,int k){
	while(u!=NIL&&k!=u->key){
		if(k<u->key)u=u->left;
		else u=u->right;
	}
	return u;
}

void insert(int k){
	Node *y=NIL;//x??????
	Node *x=root;//T??????
	Node *z;
	z=(Node *)malloc(sizeof(Node));
	z->key=k;
	z->left=NIL;
	z->right=NIL;
	while(x!=NIL){
		y=x;//???????¨????
		if(z->key<x->key){
			x=x->left;
		}else{
			x=x->right;
		}
	}
	z->parent=y;
	if(y==NIL){//T???????????´???
		root=z;
	}else{
		if(z->key<y->key){
			y->left=z;//z???y?????????????????????
		}else{
			y->right=z;//z???y?????????????????????
		}
	}
}

void inorder(Node *u){
	if(u==NIL)return;
	inorder(u->left);
	printf(" %d",u->key);
	inorder(u->right);
}
void preorder(Node *u){
	if(u==NIL)return;
	printf(" %d",u->key);
	preorder(u->left);
	preorder(u->right);
}

int main(){
	int n,x;
	string com;
	scanf("%d",&n);
	for (int i = 0; i < n; ++i) {
		cin>>com;
		if(com=="insert"){
			scanf("%d",&x);
			insert(x);
		}else if(com=="print"){
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}else if(com=="find"){
			scanf("%d",&x);
			Node *t=find(root,x);
			if(t!=NIL)printf("yes\n");
			else printf("no\n");
		}
	}
	return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

ll n, q;
string str;
vector<pair<char, char>> v;

int syumi(int s){
	REP(i, q){
		if(v[i].FI == str[s]){
			if(v[i].SE == 'L')s--;
			else s++;
		}
		if(s < 0)return -1;
		if(s >= n)return 1;
	}
	return 0;
}

int seica_l(){
	int l = -1;
	int r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(syumi(mid) != -1)r = mid;
		else l = mid;
	}
	return r;
}

int seica_r(){
	int l = -1;
	int r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(syumi(mid) != 1)l = mid;
		else r = mid;
	}
	return l;
}

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

	cin >> n >> q;
	cin >> str;

	REP(i, q){
		char a, b;cin >> a >> b;
		v.EB(a, b);
	}

	int l = seica_l();
	int r = seica_r();

	//cout << l << " " << r << endl;
	cout << max(0, r - l + 1) << endl;

	return 0;
}


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

typedef long long ullong;

int main(void){
    // Your code here!
    int N;
    cin >> N;
    vector<int> A(N);
    ullong Asum = 0;
    for(int i=0;i<N;i++){
        cin >> A.at(i);
        Asum += A.at(i);
        Asum %= 1000000007;
    }
    
    ullong sum = 0;
    for(int i=0;i<N-1;i++){
        Asum -= A.at(i);
        if(Asum<0) Asum += 1000000007;
        sum += (A.at(i)*Asum);
      	sum %= 1000000007;
    }
    cout << sum%1000000007 << endl;
}


Measured memory_bytes: 4048
import java.util.Scanner;

public class Main {

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

		for (int i=0; i < K; i++) {
			if (i % 2 == 0) {
				if (A % 2 == 1) 
					A--;
				A = A/2;
				B += A;
				//System.out.println(A);
				
			}
			else {
				if (B % 2 == 1) 
					B--;
				B= B/2;	
				A += B;
				//System.out.println(B);
			}
				
		}
		System.out.println(A + " " + B);
		
	}
}	


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string str;
	cin >> str;
	if (str == "AAA" || str == "BBB")
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 100000000
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define repp(i,n,s) for (int i= (int)(n); i >= (int)(s); i--)
#define mp make_pair
ll mod = 1000000007;
ll mod2 = 998244353;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<int> a(n);
    rep(i,0,n) cin>>a[i],a[i]*=(-1);
    vector<int> nib;
    rep(i,0,n){
        auto j = upper_bound(nib.begin(),nib.end(),a[i]);
        if (j==nib.end()){
            nib.push_back(a[i]);
        }else{
            *j = a[i];
        }
    }
    cout<<nib.size()<<endl;
}

Measured memory_bytes: 4284
#include <stdio.h>
main(){
  int S[100000],T[50000];
  int n,q,i,left=0,mid=0,right=0,count=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&S[i]);
    }
  scanf("%d",&q);
  for(i=0;i<q;i++)
    {
      scanf("%d",&T[i]);
    }
  for(i=0;i<q;i++)
    {
      left=0;
      right=n;
      while(left<right)
	{
	  mid=(left+right)/2;
	  if(T[i]==S[mid]){
	    count++;
	    break;
	  }
	  if(T[i]>S[mid]){
	    left=mid+1;
	  }
	  else if(T[i]<S[mid]){
	    right=mid;
	  }
	}
    }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 1184
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define MX 10000000000
#define mod 998244353
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	if (b == 0)
		return(1);
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return sol;
}

ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
vector<int>ans;
void solve()
{
	ll n;
	cin >> n;
	ll temp = n;
	for (ll i = 2;i * i <= temp;i++)
	{
		int cnt = 0;
		while (n % i == 0)
		{
			n = n / i;
			cnt++;
		}
		ans.pb(cnt);
	}
	int sol = 0;
	for (int i = 0;i < ans.size();i++)
	{
		for (int j = 1;j < 40;j++)
		{
			if (((j * (j + 1)) / 2) <= ans[i])
			{
				sol++;
			}
		}
	}
	if (n > 1)
		sol++;
	cout << sol;
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
}


Measured memory_bytes: 7056
S = input()
N = len(S)

alp = 'BDEFHIJKLMNOPQRSUVWXYZ'

ans = []
cnt = []

for i in range(0, N):
    for j in range(i, N+1):
        tmp = S[i:j]
        flg = 1
        for a in alp:
            if a in tmp:
                flg = 0
        if flg:
            cnt.append(len(tmp))

print(max(cnt))


Measured memory_bytes: 3060
a,b,c,k=map(int,input().split())
Unfair=10**18

if k==0:
    print(a-b)
    exit()
elif k%2==0:
    k=2
else:
    k=1

for i in range(k):
    a2=b+c
    b2=a+c
    c2=a+b
    a,b,c=a2,b2,c2

if a-b>Unfair:
    print("Unfair")
else:
    print(a-b)

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	int N; cin >> N;
	ll zmax = -INF, zmin = INF, wmax = -INF, wmin = INF;
	for(int i = 0; i < N; i++) {
		ll x, y; cin >> x >> y;
		ll z = x + y, w = x - y;
		zmax = max(zmax, z); zmin = min(zmin, z);
		wmax = max(wmax, w); wmin = min(wmin, w);
	}
	int ans = max(zmax - zmin, wmax - wmin);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int sigma(int n){
    int sum=0;
    for (int i=1; i<=(n); i++){
        sum+=i;
    }
    return sum;
}
int distance(int yo,int xo,int yi,int xi){
    return (yo-yi)*(yo-yi)+(xo-xi)*(xo-xi);
}
signed main(){
    int r;
    cin >> r;
    cout << r*r << endl;;
    return 0;
}


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

using perm = vector<int>;
perm operator*(perm a, perm b){
    perm *r = new perm();
    r->resize(a.size());
    for(size_t i=0;i<a.size();i++) (*r)[i] = a[b[i]-1];
    return *r;
}
perm inv(perm a){
    perm *r = new perm();
    r->resize(a.size());
    for(size_t i=0;i<a.size();i++) (*r)[a[i]-1] = i+1;
    return *r;
}
perm pow(perm a, int n){
    perm *r = new perm();
    r->resize(a.size());
    for(size_t i=0;i<a.size();i++) (*r)[i] = i+1;
    if(n==0) return *r;
    if(n==1) return *r*a;
    delete r;
    if(n%2) return pow(a*a, n/2)*a;
    return pow(a*a, n/2);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    int n, k;
    vector<int> p, q, r, s;    
    cin >> n >> k;
    p.resize(n);
    q.resize(n);
    r.resize(n);
    s.resize(n);
    for(int i=0;i<n;i++) cin >> p[i];
    for(int i=0;i<n;i++) cin >> q[i];
    
    s = q*inv(p)*inv(q)*p;
    s = pow(s, (k-1)/6);
    if(k%6==1) copy(p.begin(), p.end(), r.begin());
    else if(k%6==2) copy(q.begin(), q.end(), r.begin());
    else{
        for(int i=3;i<=(k-1)%6+1;i++){
            r = q*inv(p);
            copy(q.begin(), q.end(), p.begin());
            copy(r.begin(), r.end(), q.begin());
        }
    }    

    r = s*r*inv(s);
    for(int i=0;i<n;i++) cout << r[i] << " \n"[i==n-1];
    
    return 0;
}

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

signed main() {
  string s; cin >> s;
  string ans;

  for(int i = 0; i < s.length(); i++) {
    switch(s[i]) {
      case '0': ans += "0"; break;
      case '1': ans += "1"; break;
      case 'B': if(ans != "") ans.erase(ans.end()-1); break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//ΔAGC033D
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 199;
void cmax(int&x,int y){
	if(x<y)
		x=y;
}
struct node{
	int n,m;
	int a[N][N][N];
}r,c,nr,nc;
void upd(node&p){
	int i,j,k;
	for(i=1;i<=p.n;i=i+1)
		for(j=1;j<=p.m;j=j+1)
			for(k=p.m;k>=j;k=k-1)
				cmax(p.a[i][j][k],max(p.a[i][j-1][k],p.a[i][j][k+1]));
}
void go(node&p,node&q){
	int i,j,k;
	for(i=1;i<=p.n;i=i+1)
		for(j=1;j<=p.m;j=j+1)
			for(k=j;k<=p.m;k=k+1)
				if(p.a[i][j][k])
					cmax(q.a[j][i][p.a[i][j][k]],k);
}
void gn(node&p){
	int i,j,k;
	for(i=1;i<=p.n;i=i+1)
		for(j=1;j<=p.m;j=j+1)
			for(k=j;k<=p.m;k=k+1)
				if(p.a[i][j][k]&&p.a[i][j][k]<p.n)
					cmax(p.a[i][j][k],p.a[p.a[i][j][k]+1][j][k]);
}
char ch[N];
int n,m,a[N][N];
int main()
{
	int i,j,k,x;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i=i+1){
		scanf("%s",ch+1);
		for(j=1;j<=m;j=j+1){
			a[i][j]=ch[j]=='#';
			r.a[i][j][j]=i,c.a[j][i][i]=j;
		}
	}
	r.n=n,r.m=m;
	c.n=m,c.m=n;
	for(i=n-1;i;i=i-1)
		for(j=1;j<=m;j=j+1)
			if(a[i][j]==a[i+1][j])
				r.a[i][j][j]=r.a[i+1][j][j];
	for(i=1;i<=n;i=i+1)
		for(j=m-1;j;j=j-1)
			if(a[i][j]==a[i][j+1])
				c.a[j][i][i]=c.a[j+1][i][i];
	for(i=1;i<=n;i=i+1){
		for(j=1;j<=m;j=j+1){
			for(k=j+1;k<=m;k=k+1){
				r.a[i][j][k]=min(r.a[i][j][k-1],r.a[i][k][k]);
				if(a[i][j]!=a[i][k])
					r.a[i][j][k]=0;
			}
		}
	}
	for(i=1;i<=m;i=i+1){
		for(j=1;j<=n;j=j+1){
			for(k=j+1;k<=n;k=k+1){
				c.a[i][j][k]=min(c.a[i][j][k-1],c.a[i][k][k]);
				if(a[j][i]!=a[k][i])
					c.a[i][j][k]=0;
			}
		}
	}
	for(x=0;1;x=x+1){
		if(r.a[1][1][m]==n){
			cout<<x;
			return 0;
		}
		gn(r),gn(c);
		upd(r),upd(c);
		go(c,r),go(r,c);
		upd(r),upd(c);
	}
	return 0;
}

Measured memory_bytes: 61824
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
int a[65][200001];
int main() {
	ll n, k, p = 1, x = 0;
	cin >> n >> k;
	rep(i, 1, n + 1)cin >> a[0][i];
	rep(i, 1, 65) {
		rep(i2, 1, n + 1)a[i][i2] = a[i - 1][a[i - 1][i2]];
	}
	while (k) {
		if (k & 1)p = a[x][p];
		k >>= 1;
		x++;
	}
	printf("%lld\n", p);
	return 0;
}


Measured memory_bytes: 54544
# 
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
a,b,c = map(str, input().split())
ans = ''
ans = a[0:1]+b[0:1]+c[0:1]
ans = ans.upper()
print(ans)

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

int h, w, a, b;

int main() {
	scanf("%d%d%d%d", &h, &w, &a, &b);
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j)
			printf("%d", (i<b)^(j<a));
		putchar('\n');
	}
}


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

using namespace std;

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> from(m);
  vector<int> to(m);
  vector<vector<int>> g(n);
  for (int i = 0; i < m; ++i) {
    cin >> from[i] >> to[i];
    --from[i]; --to[i];
    g[from[i]].push_back(to[i]);
  }
  vector<vector<bool>> reach(n, vector<bool>(n));
  for (int f = 0; f < n; ++f) {
    function<void(int)> dfs = [&](int v) {
      reach[f][v] = true;
      for (int u : g[v]) {
        if (!reach[f][u]) {
          dfs(u);
        }
      }
    };
    dfs(f);
  }
  vector<vector<bool>> another(n, vector<bool>(n));
  for (int f = 0; f < n; ++f) {
    vector<int> foo(n, -1);
    function<void(int, int)> dfs_foo = [&](int v, int w) {
      foo[v] = w;
      for (int u : g[v]) {
        if (u != f && foo[u] == -1) {
          dfs_foo(u, w);
        }
      }
    };
    for (int i = 0; i < (int) g[f].size(); ++i) {
      int v = g[f][i];
      if (foo[v] == -1) {
        dfs_foo(v, i);
      }
    }
    vector<int> bar(n, -1);
    function<void(int, int)> dfs_bar = [&](int v, int w) {
      bar[v] = w;
      for (int u : g[v]) {
        if (u != f && bar[u] == -1) {
          dfs_bar(u, w);
        }
      }
    };
    for (int i = (int) g[f].size() - 1; ~i; --i) {
      int v = g[f][i];
      if (bar[v] == -1) {
        dfs_bar(v, i);
      }
    }
    for (int t = 0; t < n; ++t) {
      if (foo[t] != bar[t]) {
        another[f][t] = true;
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << (reach[to[i]][from[i]] == another[from[i]][to[i]] ? "same" : "diff") << "\n";
  }
  return 0;
}


Measured memory_bytes: 4608
#include<stdio.h>
int main(){
  int a,b,c,d,e,f,m,i,j;
  while(scanf("%d %d %d",&a,&b,&c),a||b||c){
    if(c==0){
      if(a-1)printf("%d %d 1 0\n",a,b);
      else{
	if(b>0)printf("1 %d 1 0\n",b);
	else   printf("1 0 1 %d\n",b);
      }
      continue;
    }
    if(c<0){
      m=1;
      c=-c;
    }
    else m=0;
    for(i=1;i*i<=a;i++){
      if(a%i)continue;
      d=a/i;//printf("i%d %d\n",i,d);
      for(j=1;j*j<=c;j++){
	if(c%j)continue;
	f=j;
	e=c/j;//printf("  %d %d\n",j,e);
	if(m)f=-f;
	if(d*f+i*e==b){
	  printf("%d %d %d %d\n",d,e,i,f);
	  break;
	}
	if(d*e+i*f==b){
	  printf("%d %d %d %d\n",d,f,i,e);
	  break;
	}
	if(d*f+i*e==-b){
	  if(d-i)printf("%d %d %d %d\n",d,-e,i,-f);
	  else   printf("%d %d %d %d\n",d,-f,i,-e);
	  break;
	}
	if(d*e+i*f==-b){
	  if(d-i)printf("%d %d %d %d\n",d,-f,i,-e);
	  else   printf("%d %d %d %d\n",d,-e,i,-f);
	  break;
	}
      }
      if(j*j<=c){
	m=2;
	break;
      }
    }
    if(m-2)printf("Impossible\n");
  }
  return 0;
}

Measured memory_bytes: 612
def bin_cho(n):
    if n==1:
        return 2
    elif n<=0:
        return 1
    else:
        return bin_cho(n-2)+bin_cho(n-1)

h,w,k=map(int,input().split())
l=[[0]*w for _ in range(h+1)]
l[0][0]=1
for j in range(1,h+1):
    for i in range(w):
        l[j][i]+=l[j-1][i]*bin_cho(w-i-2)*bin_cho(i-1)
        if i-1>=0:
            l[j][i]+=l[j-1][i-1]*bin_cho(w-i-2)*bin_cho(i-2)
        if i+1<=w-1:
            l[j][i]+=l[j-1][i+1]*bin_cho(w-i-3)*bin_cho(i-1)
        l[j][i]%=10**9+7
print(l[h][k-1])

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P>IP;
typedef vector<ll> V;
typedef vector<V> V2;
typedef vector<vector<P> > G;
void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}
void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}
const ll INF = 1145141919;
const ll MOD = 1000000007;
const ll NUM = 101010;

// サイズ可変mod
class mod{
    public:
    ll N, M;
    vector<ll>fact;
    vector<ll>inv;
    vector<ll>finv;

    ll m_plus(ll a, ll b){return (a + b) % M;}
    ll m_minus(ll a, ll b){return (a + M - b) % M;}
    ll m_times(ll a, ll b){return (a * b) % M;}
    ll m_pow(ll a, ll b){
        ll ret = 1;
        while(b > 0){
            if(b & 1)(ret *= a) %= MOD;
            (a *= a) %= MOD;
            b >>= 1;
        }
        return ret;
    }

    void update(ll n){
        if(N > n)return;
        for(ll i = N; i <= n; i++){
            fact.push_back(m_times(fact[i - 1], i));
            inv.push_back(m_pow(i, M - 2));
            finv.push_back(m_times(finv[i - 1], inv[i]));
        }
        N = n + 1;
    }

    // 除算
    ll m_divs(ll a, ll b){
        if(N <= b)update(b);
        return m_times(a, inv[b]);
    }

    // N種の要素を並び替えてできる通りの数
    ll m_fact(ll a){
        if(N <= a)update(a);
        return fact[a];
    }

    // 階乗で割る
    ll m_finv(ll a){
        if(N <= a)update(a);
        return finv[a];
    }

    // N種の要素からk個取り出して並べる通りの数
    ll m_nPk(ll n, ll k){
        return m_times(m_fact(n), m_finv(n - k));
    }
    // N種の要素からk個を選ぶ通りの数
    // a個の赤い玉とb個の青い球を並び替える通りは(a+b)C(a)
    ll m_nCk(ll n, ll k){
        return m_times(m_nPk(n, k), m_finv(k));
    }
    // N種の要素からk個を選ぶ通りの数(重複して良い)
    ll m_nHk(ll n, ll k){
        return m_nCk(n + k - 1, k);
    }
    
    mod(ll m = MOD){
        M = m;
        N = 1;
        fact = vector<ll>(1, 1);
        inv = vector<ll>(1, 1);
        finv = vector<ll>(1, 1);
    }
};
mod m;

int main(){

    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    ll ans = 0;
    for(ll r = r1; r <= r2; r++){
        ll a = m.m_nCk(c2 + r + 1, c2);
        ll b = m.m_nCk(c1 - 1 + r + 1, c1 - 1);
        ll tmp = m.m_minus(a, b);
        ans = (ans + tmp) % MOD;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 49456
K, A, B = map(int, input().split())

if A + 2 >= B:
    print(1 + K)
    exit()

# ループに入るまでの操作
count = A
K -= (A - 1)
# これ以降はAを交換してBを繰り返す。２回ごとにBーA増えていく

count += (K // 2) * (B - A)
# B変換できない分のあまりは叩いて増やしておく
count += K % 2
print(count)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n, k;
		int a[];
		int sum, sum2;
		int max;
		int space;

		n = sc.nextInt();
		k = sc.nextInt();
		while (n + k != 0) {
			a = new int[n + 1];
			sum   = 0;
			sum2  = 0;
			max   = 0;
			space = 0;

			for (int i = 0; i < k; i++) {
				a[sc.nextInt()] = 1;
			}

			if (a[0] == 0) {
				for (int i = 1; i <= n; i++) {
					if (a[i] == 1) {
						sum++;
					} else {
						max = (max < sum) ? sum : max;
						sum = 0;
					}
				}
				max = (max < sum) ? sum : max;
			} else {
				for (int i = 1; i <= n; i++) {
					if (a[i] == 1) {
						sum2++;
					} else {
						if (space == 1) {
							max = (max < sum + sum2 + 1) ? sum + sum2 + 1 : max;
							sum = sum2;
							sum2 = 0;
							space = 0;
						}
						max = (max < sum2) ? sum2 : max;
						space++;
					}
				}
				if (space == 1) {
					max = (max < sum + sum2 + 1) ? sum + sum2 + 1 : max;
				}
				max = (max < sum2) ? sum2 : max;
			}
			System.out.println(max);
			n = sc.nextInt();
			k = sc.nextInt();
		}
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 405;
int dp[MAXN][MAXN],n,ma,mb,a[MAXN],b[MAXN],c[MAXN];
void init(){
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXN;j++)
            dp[i][j]=1000000;
    dp[0][0]=0;
}
int main(){
    init();
    scanf("%d%d%d",&n,&ma,&mb);
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for(int i=0;i<n;i++){
        for(int j=MAXN-1;j>=0;j--){
            for(int k=MAXN-1;k>=0;k--){
                if(j>=a[i]&&k>=b[i]){
                    dp[j][k]=min(dp[j-a[i]][k-b[i]]+c[i],dp[j][k]);
                }
            }
        }
    }
    int Ans = 1000000;
    for(int i=1;i<MAXN;i++){
        for(int j=1;j<MAXN;j++){
            if(i*mb==ma*j){
                Ans = min(Ans,dp[i][j]);
            }
        }
    }
    if(Ans!=1000000)
        cout<<Ans<<endl;
    else
        cout<<"-1"<<endl;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N,M,K;
    cin >> N >> M >> K;
    vector<ll> A(N);
    vector<ll> B(M);
    rep(i,N){
        cin >> A[i];
    }
    rep(i,M){
        cin >> B[i];
    }
    vector<ll> num_A(N);
    vector<ll> num_B(M);
    num_A[0] = A[0];
    rep(i,N - 1){
        num_A[i + 1] = num_A[i] + A[i + 1];
    }
    num_B[0] = B[0];
    rep(i,M - 1){
        num_B[i + 1] = num_B[i] + B[i + 1];
    }
    ll ans = 0;
    for (ll i = 0; i <= N; i++){
        if (i == 0){
            vector<ll>::iterator itr = upper_bound(all(num_B), K);
            if (num_B[M - 1] <= K){
                ans = M;
            }
            else{
                ans = itr - num_B.begin();
            }
        }
        else{
            if (num_A[i - 1] > K){
                break;
            }
            vector<ll>::iterator itr = upper_bound(all(num_B), K - num_A[i - 1]);
            if (num_B[M - 1] <= K - num_A[i - 1]){
                ans = M + i;
            }
            else{
                ans = max(ans, itr - num_B.begin() + i);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 9532
#![allow(non_snake_case)]

#[allow(unused_macros)]
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

fn main() {
    input!{
        N: String,
    }
    println!("{}", if N.contains("9") { "Yes" } else { "No" });
}


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

int Calc( int x )
{
    if( x == 1 )
        return 2;
    
    return x + Calc( x - 1 );
}

int main()
{
    int n;

    while( cin >> n )
    {
        cout << Calc( n ) << endl;
    }
    return 0;
}


Measured memory_bytes: 3132
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
int power2(int n){
    int ans = 1;
    rep(i, n) ans *= 2;
    return ans;
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    cout << ((N - M) * 100 + M * 1900) * power2(M)  << endl;


    return 0;
}


Measured memory_bytes: 256
// Problem : B - Product Max
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
int main()
{
	fast;
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<max({b*d, a*c, a*d, b*c});
	return 0;
}


Measured memory_bytes: 3652
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
#define ll long long

int main(){
	int n;
	vector<int> v;
	double ans=0;
	cin>>n;
	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		v.push_back(tmp);
	}
	sort(v.begin(),v.end());
	ans=v[0];
	for(int i=1;i<n;i++){
		ans+=v[i];
		ans=ans/2;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

int main() {
	string s;
	cin >> s;

	int maxLength;

	for (int i = 0; i <= s.size(); i++) {
		string tmpStr = "";
		if (s[i] == 'A') {
			for (int j = 0; j < s.size() - i; j++) {
				if (s[i + j] == 'Z') {
					tmpStr += s[i + j];
					maxLength = tmpStr.size();
					continue;
				}
				tmpStr += s[i + j];
			}
			break;
		}
	}

	cout << maxLength << endl;

	return 0;
}

Measured memory_bytes: 3852
#include <bits/stdc++.h>
using namespace std;
int main(){
  int w, h, n;
  int x, y, a;
  int r, l, b, t;
  cin >> w >> h >> n;
  l = b = 0; r = w; t = h;
  for(int i = 0; i < n; i++){
    cin >> x >> y >> a;
    if(a == 1 && l < x) l = x; 
    if(a == 2 && r > x) r = x; 
    if(a == 3 && b < y) b = y; 
    if(a == 4 && t > y) t = y; 
  }
  if (b >= t || l >= r) cout << 0 << endl;
  else cout << (r - l) * (t - b) << endl;
}


Measured memory_bytes: 256
fun main(args:Array<String>?): Unit {
    val state = readLine()!!.trim()
    var first = 0
    var second = 0
    if (state.first() == 'o') ++first else ++second
    for (i in 1 until state.length){
        if (state[i] != state[i - 1]){
            if (state[i] == 'o') ++first else ++second
        }
    }
    println(if (first >= second) "o" else "x")
}


Measured memory_bytes: 29464
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = []


for i in range(A + 1):
    for j in range(B + 1):
        for k in range(C + 1):
            ans.append(500 * i + 100 * j + 50 * k)

print(ans.count(X))

Measured memory_bytes: 8276