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

int main(){
    int n;
    while(cin>>n,n){
        int y;cin>>y;
        double mac=0;
        int mab;

        for(int i=0;i<n;i++){
            int b,r,t;
            cin>>b>>r>>t;
            double a;
            if(t==1){
                a=1+1.0*y*r/100;

            }
            else{
                a=1;
                for(int j=0;j<y;j++)a*=(1+1.0*r/100);
            }
            if(mac<a){
                mac=a;
                mab=b;
            }
        }

        cout<<mab<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

LL n, s, a[101010];

int main() {
	cin >> n >> s;
	REP(i, n) {
		cin >> a[i];
	}
	int l = 0, r = 0;
	int ans = INF<int>();
	LL sum = 0;
	while (true) {
		while (r < n&&sum < s)sum += a[r++];
		if (sum < s)break;
		ans = min(ans, r - l);
		sum -= a[l++];
	}
	cout << (ans == INF<int>() ? 0 : ans) << endl;
}


Measured memory_bytes: 3892
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define IN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////

//AtCoder Beginner Contest 101

int main(){
	string s;
	int sum = 0;
	
	getline(cin,s);
	
	REP(i,4){
		if (s[i] == '+'){
			sum++;
		}else{
			sum--;
		}
	}
	
	PRINTD(sum);
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,sum,ans;
int a[105];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    int res=10005;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i];
        int t=abs(sum-2*ans);
        res=min(res,t);
    }
    printf("%d\n",res);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100 + 7;

int dp[N][N];

int main()
{
	ios::sync_with_stdio(false);

	ll n, m;
	cin >> n >> m;
	/*for (int i=0; i<=20; i++)
		for (int j=0; j<=i; j++)
		{
			int a = j;
			int b = i - j;
			bool ok = false;
			for (int x=2; x<=a; x+=2)
				if (!dp[a-x][b+x/2])
					ok = true;
			for (int x=2; x<=b; x+=2)
				if (!dp[a+x/2][b-x])
					ok = true;
			if (ok)
				dp[a][b] = true;
		}
	for (int i=0; i<=10; i++)
		for (int j=i; j<=10; j++)
			cout << i << " " << j << " " << dp[i][j] << "\n";*/
	if (abs(n-m) >= 2)
		cout << "Alice\n";
	else
		cout << "Brown\n";
	return 0;
}

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

int gcd(int a,int b)
{
  if(a < b){
    a^=b;
    b^=a;
    a^=b;
  }
  if(b==0)
    return a;

  return gcd(a%b,b);
}

int main()
{
  int n,x;
  int ans=-1;
  cin >> n >> x;
  for(int i=0;i<n;i++){
    int buf;
    cin >> buf;

    buf=x-buf;
    if(buf<0)
      buf=-buf;
    if(ans==-1)
      ans=buf;

    ans=gcd(ans,buf);
  }

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

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int A[100];   //Array
  int minj, N, temp;
  int i, j, count=0;   //Loop counter variable

  scanf("%d", &N);

  for( i = 0 ; i < N ; i++ ) scanf("%d", &A[i]);

  for( i = 0 ; i < N ; i++ ){
    minj = i;
    for( j = i ; j < N ; j++ ){
      if( A[j] < A[minj] ){
	minj = j;
      }
    }
    if( i != minj ){
      temp = A[i];
      A[i] = A[minj];
      A[minj] = temp;
      count++;
    }
  }

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

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

  return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
int main(void)
{
	int x,y,temp,X,xx,yy,sb;
	while(scanf("%d %d",&x,&y)!=EOF){
		xx=x; yy=y;
		if(x<=y){
			temp=x;
			x=y;
			y=temp;
		}
		while(1){
			if(y==0)break;
			X=x%y;
			x=y;
			y=X;
		}
		sb=(xx/x)*(yy/x)*x;
		printf("%d %d\n",x,sb);
	}
	return 0;
}	

Measured memory_bytes: 1024
# coding: utf-8
# Your code here!

yoko_1 = [int(i) for i in input().split()]
yoko_2 = [int(i) for i in input().split()]
yoko_3 = [int(i) for i in input().split()]
tate_1 = [yoko_1[0], yoko_2[0], yoko_3[0]]
tate_2 = [yoko_1[1], yoko_2[1], yoko_3[1]]
tate_3 = [yoko_1[2], yoko_2[2], yoko_3[2]]
naname_1 = [yoko_1[0], yoko_2[1], yoko_3[2]]
naname_2 = [yoko_1[2], yoko_2[1], yoko_3[0]]

n = int(input())
bs = [int(input()) for i in range(n)]

def bingo(card, call):
    cnt = 0
    for i in card:
        for j in call:
            if i == j:
                cnt += 1
                break
    if cnt == 3:
        return 1
    else:
        return 0

if bingo(yoko_1, bs) + \
bingo(yoko_2, bs) + \
bingo(yoko_3, bs) + \
bingo(tate_1, bs) + \
bingo(tate_2, bs) + \
bingo(tate_3, bs) + \
bingo(naname_1, bs) + \
bingo(naname_2, bs) > 0:
    print("Yes")
else:
    print("No")

# print(bingo(yoko_1, bs))
    



Measured memory_bytes: 3064
def main():
    n = int(input())
    primes = get_primes_less_than(55556)
    out = []
    num = 0
    for prime in primes:
        if prime%5 == 1:
           out.append(prime)
           num += 1
        if n == num:
            print(*out)
            return

def get_primes_less_than(x):
    ans = []
    if x < 3:
        return ans
    if x == 3:
        ans.append(2)
        return ans
    else:
        for i in range(3, x, 2):
            for j in ans:
                if not i%j:
                    break
            else:
                ans.append(i)
    return ans
        
if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define MAXN 200000
typedef long long ll;

using namespace std;

int main(){
    int N;
    cin >> N;
    int c[510]={0},s[510]={0},f[510]={0};
    for (int i=1;i<N;i++){
	cin >> c[i] >> s[i] >> f[i];
    }

    for (int i=1;i<=N;i++){
	int res=s[i]+c[i];
	for (int j=i+1;j<N;j++){
	    if (res < s[j]){
		res=s[j]+c[j];
	    } else if ((res-s[j])%f[j] == 0){
		res+=c[j];
	    } else {
		res+=(f[j]-(res-s[j])%f[j]+c[j]);
	    }
	}
	cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N = map(int, input())
A = list(map(int, input().split()))

while len(A) >= 2:
    idx = A.index(min(A))
    x = A.pop(idx)
    B = list()
    for i in range(len(A)):
        if A[i] % x != 0:
            B.append(A[i] % x)
    B.append(x)
    A = B[:]

print(A[0])


Measured memory_bytes: 14248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
	ll n;
	cin >> n;
	int len = log2(n);
	ll ans = 1;
	for(int i = 1; i <= len+1; i++){
	    ans *= 2;
	}
	cout<<ans-1<<endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
#a = gets.chomp.split().map(&:to_i)
s=[]
t=[]
n.times do
  ss, tt = gets.chomp.split()
  s.push ss
  t.push tt.to_i
end
x = gets.chomp
i = s.index(x)

if i == n-1
  puts 0
else
  puts t.slice(i+1,10000).inject(:+)

end




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

int main(){
    int n, q;
    cin >> n >> q;
    vector<queue<int>> Q(1100);
    for(int i=0; i<q; i++){
        int a, t;
        cin >> a >> t;
        if(a == 0){
            int x;
            cin >> x;
            Q[t].push(x);
        }else{
            if(a == 1){
                if(!(Q[t].empty())){
                    cout << Q[t].front() << endl;
                }
            }else{
                if(!(Q[t].empty())){
                    Q[t].pop();
                }
            }
        }
    }
    return 0;
}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<long long> w(n);
  vector<long long> v(n);
  for(int i=0;i<n;++i){
    cin>>w[i]>>v[i];
  }
  vector<long long> last(m+1,0);
  vector<long long> curr(m+1,0);
  
  for(int i=0;i<n;++i){
    for(int j=m;j>0;--j){
      if(j>=w[i] && curr[j-w[i]]+v[i] > last[j]){
        curr[j] = curr[j-w[i]]+v[i];
      }
    }
    /*
    for(auto i:curr){
      cout<<i<<" ";
    }cout<<endl;
    */
    last = curr;
  }
  cout<<curr[m]<<endl;
  return 0;
}

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

int main(){
  long long n,q;
  cin >> n >> q;
  long long s[n],t[n],x[n],d[q];
  pair<long long, int> p[n];
  for(int i=0;i<n;i++){
    cin >> s[i] >> t[i] >> x[i];
    p[i]=make_pair(x[i], i);
  }
  sort(p, p+n);
  vector<pair<long long, int> > vec;
  bool active[n];
  for(int i=0;i<n;i++){
    vec.push_back(make_pair(s[p[i].second]-x[p[i].second]-1, i));
    vec.push_back(make_pair(t[p[i].second]-x[p[i].second]-1, i));
    active[i]=false;
  }
  for(int i=0;i<q;i++){
    cin >> d[i];
    vec.push_back(make_pair(d[i], -1));
  }
  sort(vec.begin(), vec.end());
  priority_queue<int, vector<int>, greater<int> > que;
  for(size_t i=0;i<vec.size();i++){
    if(vec[i].second == -1){
      if(!que.empty()){
        cout << p[que.top()].first << endl;
      }else{
        cout << -1 << endl;
      }
    }else{
      long long idx = vec[i].second;
      if(active[idx]){ //工事終了
        active[idx] = false;
        if(idx == que.top()){
          que.pop();
          while(!que.empty()){
            if(active[que.top()]){
              break;
            }else{
              que.pop();
            }
          }
        }
      }else{ //工事開始
        active[idx] = true;
        que.push(idx);
      }
    }
  }
  return 0;
}


Measured memory_bytes: 28264
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  if(n==1)cout<<0<<endl;
  else{
    vector<int>h(n),m(n);
    for(int i=0;i<n;i++){
      cin>>h.at(i);
      m.at(i)=1;
    }
    int i=0;
    while(i<n){
      if(i<n-1){
        for(int j=i;j<n-1;j++){
          if(h.at(j)>=h.at(j+1))m.at(i)++;
          else break;
        }
      }
      i+=max(m.at(i)-1,1);
    }
    sort(m.begin(),m.end());
    cout<<m.at(n-1)-1<<endl;
  }
}


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

int main(){
  int n,x;cin >> n >> x;
  int l[n];rep(i,n)cin >> l[i];
  int sum = 0,ans = 0;
  rep(i,n){
    sum += l[i];
    if(sum <= x){ans += 1;}
  }
  cout << ans+1 << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>
#include <deque>
#include <set>

typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;
Graph G;
const int AMAX = 100000;
//四方向への移動ベクトル
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

//入力
int H, W;
vector<string> field;

//探索
bool seen[510][510];	// seen[h][w] := マス(h,w)が検知済みかどうか

void dfs(int h, int w)
{
	seen[h][w] = true;

	//四方向を検索
	for (int dir = 0; dir < 4; dir++)
	{
		int nh = h + dx[dir];
		int nw = w + dy[dir];

		//場外アウトしたり、移動先が壁の場合はスルー
		if (nh < 0 || nh >= H || nw < 0 || nw <= W)continue;
		if (field[nh][nw] == '#')continue;

		//移動先が探索済みの場合
		if (seen[nh][nw])continue;

		//再帰的に探索
		dfs(nh, nw);
	}
}

/*int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}




int n;
vll a;

ll solve(bool isp)
{
	ll sum = 0ll;
	ll ret = 0ll;

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (isp and sum <= 0)
		{
			ret += -sum + 1;
			sum = 1ll;
		}
		if (not isp and sum >= 0)
		{
			ret += sum + 1;
			sum = -1ll;
		}
		isp ^= 1;
	}
	return ret;
}

*/
/*
vector<bool> seen;
void dfs(const Graph & G, int v)
{
	seen[v] = true;	//v を訪問済みにする

	// vから行ける各頂点 next_vについて
	for (auto next_v : G[v])
	{
		if (seen[next_v])continue;	//next_vが探索済みだったらスルー
		dfs(G, next_v);//再帰的に探索
	}
}
*/
/*
 * 最大公約数計算
 */
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


void init(int n)
{
	for (int i = 0; i < n; i++) par[i] = i;
	for (int i = 0; i < n; i++) r[i] = 0;
}

int find(int x)
{
	if (par[x] == x)return x;
	else return find(par[x]);
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);

	if (r[x] < r[y])
	{
		par[x] = y;
	}
	else
	{
		par[y] = x;
		if (r[x] == r[y])
		{
			r[x]++;
		}
	}
}

bool same(int x, int y)
{
	return find(x) == find(y);
}

};


string SS, T;
string solve()
{
	
	int N = SS.length();
	int M = T.length();
	set<string> ans;
	for (int R = N; R >= M; R--)
	{
		int L = R - M;

		int ok = 1;
		for (int j = 0; j < M; j++)
		{
			if (SS[L + j] != '?' && SS[L + j] != T[j])
			{
				ok = 0;
			}

			if (ok)
			{
				string S;
				for (int i = 0; i < N;i++) S += SS[i];
				for (int i = 0; i < M; i++) S[L+i] = T[i];
				for (int i = 0; i < N; i++) if (S[i] == '?')S[i] = 'a';
				ans.insert(S);
			}
		}
		
	}
	if (ans.size() == 0)return "UNRESTORABLE";
	return *(ans.begin());

}

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

	ll ans = sqrt(N);
	cout << ans*ans << endl;
	/*for (ll i = 0; i < N ; i++)
	{
		ll ans = i * i;
		if (ans > N)
		{
			cout << (i - 1ll) * (i - 1ll) << endl;
			break;
		}
	}*/

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int32_t main(){
	int a, b;
	cin >> a >> b;
	if(a == b)
		cout << "Yes";
	else
		cout << "No";

	return 0;
}



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

using namespace std;

const int MAX = 100;

class DFS
{
    vector< vector<int> > adj;
    int num, d[MAX], f[MAX], parent[MAX], status[MAX], tt;

public:
    DFS()
    {
        cin >> num;
        for (int i = 0; i < num; i++)
        {
            d[i] = status[i] = 0;
            parent[i] = -1;
        }

        load(num);
        tt = 0;
    }

    void load(int n)
    {
        int r, c, n_c;
        adj.assign(n, vector<int>());
        for (int i = 0; i < n; i++)
        {
            cin >> r >> n_c;
            adj[r - 1].assign(n_c, int());
            for (int j = n_c - 1; j >= 0; j--)
            {
                cin >> c;
                adj[r - 1].at(j) = c-1;
            }
        }
    }

    int next(int node)
    {
        if (!adj[node].empty())
        {
            int v = adj[node].back();
            adj[node].pop_back();
            return v;
        }
        return -1;
    }

    void run(int node)
    {
        int next_node;
        while (node != -1)
        {
            if (status[node] == 0)
            {
                status[node] = 1;
                d[node] = ++tt;
            }
            next_node = next(node);
            if (next_node == -1)
            {
                status[node] = 2;
                f[node] = ++tt;
                node = parent[node];
                continue;
            }
            if (status[next_node] == 0)
            {
                parent[next_node] = node;
                node = next_node;
            }
        }
    }

    void dfs(){
        for(int node=0;node<num;node++){
            if(status[node] == 0) run(node);
        }
    }

    int dd(int n)
    {
        return d[n];
    }

    int ff(int n)
    {
        return f[n];
    }

    int number()
    {
        return num;
    }
};

int main()
{
    DFS dfs;

    dfs.dfs();
    for (int i = 0; i < dfs.number(); i++)
    {
        cout << i + 1 << " " << dfs.dd(i) << " " << dfs.ff(i) << endl;
    }
}


Measured memory_bytes: 3120
function main(input) {
    var n = input[0]-0;
    var list = [0].concat(input[1].split(" ").map(v=>v-0), [0]);
    var llist = []; llist[0] = 0;
    var rlist = []; rlist[n] = 0;
    for(var i=1;i<=n;i++){
        llist[i] = llist[i-1] + Math.abs(list[i]-list[i-1]);
        rlist[n-i] = rlist[n-i+1] + Math.abs(list[n-i+1]-list[n-i+2]);
    }
    for(var i=1;i<=n;i++){
        var ans = 0;
        ans += llist[i-1];
        ans += rlist[i]||0;
        ans += Math.abs(list[i-1]-list[i+1]);
        console.log(ans);
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


Measured memory_bytes: 64224
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Iterator;

class Graph {
	private int totalVertex;
	private LinkedList<LinkedList<Integer>> adjList;
	//adjacency list of edges
	public Graph() { totalVertex = 0; }
	public int getTotalVertex() { return totalVertex; }
	public void loadAdjList() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjList = new LinkedList<LinkedList<Integer>>();
		for(int i = 0; i < totalVertex; i ++) {
			LinkedList<Integer> tmp = new LinkedList<Integer>();
			int idx1 = in.nextInt() - 1; //-1, index
			int degree = in.nextInt();
			//System.out.println("mark idx1 = " + idx1 + " degree = " + degree);
			for(int j = 0; j < degree; j ++) {
				int idx2 = in.nextInt() - 1; //-1, index
				tmp.add(idx2);
			}	
			adjList.add(tmp);
		}
		in.close();
	}
	
	public int[] computeDistDFS(int s) {
		LinkedList<Integer> q = new LinkedList<Integer>();
		q.add(s);
		int[] visited = new int[totalVertex];
		int[] dist = new int[totalVertex];
		int v, u;
		for(v = 0; v < totalVertex; v ++) {
			visited[v] = 0; 
			dist[v] = -1; 
		}
		dist[s] = 0;
		visited[s] = 1;
		while(!q.isEmpty()) {
			u = q.remove(0); //remove the first item from the list/queue
			Iterator<Integer> it = adjList.get(u).iterator();
			while(it.hasNext()) {
				v = it.next();
				if(visited[v] == 0) {
					q.add(v); //add to the end of the list/queue
					dist[v] = dist[u] + 1;
					visited[v] = 1;
				}
			}
		}
		return dist;
	}
}

public class Main {
	public static void main(String[] args) {
		Graph g = new Graph();
		g.loadAdjList();
		int[] dist = g.computeDistDFS(0);
		for(int i = 0; i < g.getTotalVertex(); i ++) {
			System.out.println((i+1) + " " + dist[i]);
		}
	}
}


Measured memory_bytes: 28360
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 入力値を文字の配列で返却する
def gets_nsp_list()
  gets.chomp.split("")
end

w_list = gets_nsp_list

w_count_h = w_list.group_by(&:itself).map{|k,v| [k, v.count]}.to_h

dpp w_count_h

w_count_h.each do |k, v|
  if v.odd?
    puts "No"
    exit
  end
end

puts "Yes"

Measured memory_bytes: 14544
#include <iostream>
#include <math.h>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const long C_10PW9 = 1000000000;
const int ULCODE = 32;

int main()
{
	int N;
	string c;
	cin >> N;
	cin >> c;
	int last = N;
	int count = 0;
	for (int i = 0; i < N; i++) {
		if (c[i] == 'W') {
			last = c.find_last_of('R', last - 1);
			if (last != c.npos && last > i) {
				count++;
			}
			else
			{
				break;
			}
		}
	}
	cout << count;
	return 0;
}

Measured memory_bytes: 3716
// C - Forbidden List
#include <bits/stdc++.h>
using namespace std;

int main(){
    int x, n;
    cin >> x >> n;
    int ans, mx = 0;
    if(n == 0) ans = x;
    else{
        ans = 1000;
        vector<bool>p(102, false);
        for(int i=0; i<n; i++){
            int in;
            cin >> in;
            p[in] = true;
        }
        mx = x;
        for(int i=0; i<102; i++){
            if(p[i] == false){
                if(abs(x-i) < abs(x-ans)) ans = i;
                if(abs(x-i) == abs(x-ans)) ans = min(ans, i);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

int main(){
	int H,W;
	int x,y;
	while(1){
		scanf("%d%d",&H,&W);
		if(H==0 && W==0){break;}
		for(x=0;x<H;x++){
			for(y=0;y<W;y++){
				if(x>0 && x<H-1 && y>0 && y<W-1){
					printf(".");
				}
				else{
					printf("#");
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1000
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <bitset>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < (n); i++)

using namespace std;

long c[10][10] = { 0 };

void solve() {
  vector<long> change(10);
  change[0] = 10000000l;
  change[1] = 0;
  change[2] = 10000000l;
  change[3] = 10000000l;
  change[4] = 10000000l;
  change[5] = 10000000l;
  change[6] = 10000000l;
  change[7] = 10000000l;
  change[8] = 10000000l;
  change[9] = 10000000l;

  long H, W;
  cin >> H >> W;
  rep (i, 10) rep(j, 10) cin >> c[i][j];

  queue<long> q;
  q.push(1);

  while (q.size()) {
    long current = q.front();
    q.pop();
    rep (i, 10) {
      long tmp = change[current] + c[i][current];
      if (tmp < change[i]) {
        change[i] = tmp;
        q.push(i);
      }
    }
  }

  long ans = 0;
  rep (i, H) rep (j, W) {
    long A;
    cin >> A;
    if (A == -1) continue;
    ans += change[A];
  }

  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int w,a,b;
    while(~scanf("%d %d %d",&w,&a,&b))
    {
        if((a+w)<=b)
        printf("%d",b-(a+w));
        else if(a>(b+w))
            printf("%d",a-(b+w));
        else
            printf("0");
    }
    return 0;
}

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

#define rep(i, x, y) for(int i = (x), _ = (y); i <= _; ++ i)

typedef long long LL;

const int maxN = 2e5 + 5;

char s[maxN];
LL fib[100];
int fail[maxN];
int lens, lent;
LL ansl[26], ansr[26], L; 
int sums[26], sumt[26];

void getans(LL Bnd, LL ans[])
{
	if(Bnd < lens)
	{
		rep(i, 1, Bnd) ans[s[i] - 'a']++;
		return;
	}
	rep(i, 0, 90) if(fib[i] * lent + fib[i + 1] * lens > Bnd)
	{
		rep(j, 0, 25) ans[j] += fib[i - 1] * sumt[j] + fib[i] * sums[j];
		getans(Bnd - fib[i - 1] * lent - fib[i] * lens, ans);
		return;
	}
}

int main()
{
	fib[0] = 0; fib[1] = 1;
	rep(i, 2, 90) fib[i] = fib[i - 1] + fib[i - 2];
	scanf("%s", s + 1);
	lens = strlen(s + 1) >> 1;
	fail[0] = fail[1] = 0;
	rep(i, 2, lens)
	{
		int tmp = fail[i - 1];
		while(tmp && s[tmp + 1] != s[i]) tmp = fail[tmp];
		fail[i] = s[tmp + 1] == s[i] ? tmp + 1 : 0;
	}
	lent = lens - fail[lens];
	rep(i, 1, lent) sumt[s[i] - 'a']++;
	rep(i, 1, lens) sums[s[i] - 'a']++;
	scanf("%lld", &L), getans(L-1, ansl);
	scanf("%lld", &L), getans(L, ansr);
	rep(i, 0, 25) printf("%lld ", ansr[i] - ansl[i]);

	return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;
typedef unsigned long ulong;

void solve() {
	vector<int> res;
	while (true) {
		int n;
		cin >> n;
		if (n == 0)break;

		vector<int> vec;
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			vec.push_back(x);
		}
		sort(vec.begin(), vec.end());
		int sum = 0;
		for (int i = 1; i < n - 1; i++)sum += vec[i];
		res.push_back(sum / (n - 2));
	}
	for (int i = 0; i < res.size(); i++)cout << res[i] << endl;
}

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


Measured memory_bytes: 3128
N = int(input())

k = 1

while 2*N >= k*(k-1):
    if 2*N == k*(k-1):
        print('Yes')
        print(k)

        S = [[0 for i in range(k-1)] for j in range(k)]

        for lis in range(k-1):
            S[0][lis] = lis + 1

        num_max = k - 1
        for history in range(1, k):
            num_max += k - 1 - history
            for bef_list in range(history):
                S[history][bef_list] = S[bef_list][history - 1]
            for new_list in range(k - history - 1):
                S[history][new_list + history] = num_max - new_list
            S[history].sort()

        for i in range(k):
            print(k-1, end=' ')
            for j in range(k-1):
                print(S[i][j], end=' ')
            print('')

        exit()

    k += 1

print('No')



Measured memory_bytes: 9256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const int n_max = 1e5+10;
#define int ll

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x; cin >> x;
    auto c = [&](ll a,ll b){
        ll l = a - b;
        ll r = a*a*a*a + a*a*a*b + a*a*b*b + a*b*b*b + b*b*b*b;
        return l * r == x;
    };
    auto pow5 = [&](ll i){
        return i*i*i*i*i;
    };
    rep(i,2e3){
        ll temp = pow5(i) - x;
        ll ab = abs(temp);
        ll ok = 2e3, ng = 0;
        while(abs(ok - ng) > 1){
            ll b = (ok + ng) / 2;
            if(pow5(b) >= ab)ok = b;
            else ng = b;
        }
        if(pow5(ok) == ab){
            cout << i << " " << ok * (temp / ab) << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3652
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
using namespace std;
#define INF 10000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;

int C[60];

P s[3000];

void reset(){
    for(int i=0;i<60;i++) C[i]=0;
}

int main(){
    ll x[60],y[60],temp=0,ans=0;
    int N,count=0;
    cin>>N;

    for(int i=0;i<N;i++) cin>>x[i]>>y[i];

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            s[count].first=x[j]-x[i]; s[count].second=y[j]-y[i];
            count++;
        }
    }

    for(int i=0;i<count;i++,temp=0){
        for(int j=0;j<count;j++){
            if(s[i].first==s[j].first && s[i].second==s[j].second || s[i].first==-s[j].first && s[i].second==-s[j].second){
                temp++;
            }
        }
        ans=max(ans,temp);
    }
    cout<<N-ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

long long n, k;
const long long M = 1e9 + 7;
long long cnt;
long long a[2005];

int main()
{
    scanf("%lld%lld", &n, &k);
    for(long long i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        for(long long j = 0; j < i; j++)
        {
            if(a[j] > a[i]) cnt += k * (k + 1) / 2;
            else if(a[j] < a[i]) cnt += k * (k - 1) / 2;
            cnt %= M;
        }
    }
    printf("%lld", cnt);
    return 0;
}


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

int main()
{
    int N; cin >> N;
    vector<int> a(N);

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

    sort(a.begin(), a.end(), greater<int>());

    int alice = 0;
    int bob = 0;
    for(int i = 0; i < N; i++) {
        if(i % 2 == 0)
            alice += a[i];
        else
            bob += a[i];
    }

    cout << alice - bob << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N ;
  
  long int L[87];	// L[86]まで
  L[0] = 2;
  L[1] = 1;
  
  for(int i=2; i<87; i++){
  	L[i] = L[i-2] + L[i-1];
  }
  
  cout << L[N] << endl;
}

Measured memory_bytes: 256
open System

module Util =
    
    /// 正の整数の2bit分解(逆順)
    let _2bitSeq x :seq<bool> =
        Seq.unfold (fun before ->
            if before = 0L then 
                None
            else
                Some(before % 2L |> Convert.ToBoolean , before / 2L) ) 
            x


    /// x^y(mod m)
    let power x y m =
        _2bitSeq y
        |> Seq.fold (fun (p, total) bit ->
            if bit then
                (p * p % m, total * p % m)
            else
                (p * p % m, total))
            (x, 1L)
        |> snd


    /// x^(-1) (mod m) (x,mは互いに素)
    let rev x m =
        // フェルマーの小定理を用いる
        power x (m-2L) m


    /// xCy(mod m)
    let combination x y m =
        let nomalSeq = 
            seq{ x .. -1L .. (x - y + 1L)}
        
        let revSeq =
            seq{1L .. y}
            |> Seq.map (fun x -> rev x m)
        
        let nomalTotal =
            nomalSeq
            |> Seq.fold (fun total x -> total * x % m) 1L

        let revTotal =
            revSeq
            |> Seq.fold (fun total x -> total * x % m) 1L

        nomalTotal * revTotal % m


    /// x - y (mod m)
    let minus x y m =
        let mutable ans = (x - y) % m
        while ans < 0L do
            ans <- ans + m
        ans


module Program =

    let main =
        let p = 1000000007L
        
        let n, a, b =
            stdin.ReadLine().Split() |> Array.map int64 |>fun array -> array.[0], array.[1], array.[2]
        
        Util.power 2L n p - 1L
        |> fun x -> Util.minus x (Util.combination n a p) p
        |> fun x -> Util.minus x (Util.combination n b p) p
        |> stdout.WriteLine


Measured memory_bytes: 17544
import java.util.*;
public class Main{
	public static void main(String[] args){
		//10000<=A<=B<=99999
		//
		//回文数とは逆から読んでも同じ数のこと
		//AからBまでを配列に入れていく
		//AからBまでは0から数えてB-A個ある
		//
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int acopy = a;
		String ba[] = new String[b-a+1];//b-a個に1をプラスしたのは０の時1個配列作られないから(324個配列がある)	 
		String mozireverse;
		int count = 0;
		for(int i = 0;i < b-a+1;i++){

			ba[i] = String.valueOf(acopy);
			//System.out.println(acopy);
			acopy++;

		}
		//System.out.println(ba.length);

		//５桁だから中身を逆にして比較
		for(int i = 0;i < b-a+1;i++){
	
			 StringBuffer sb = new StringBuffer(ba[i]);
       			 mozireverse = sb.reverse().toString();
			 //System.out.println(ba[i]);
			 //System.out.println(mozireverse);
			 if(ba[i].equals(mozireverse)){//カウント
				 
				count++;

			 }
	
		}

		System.out.println(count);
		//System.out.println(ba[323]);
				


		
		
	
	}
}


Measured memory_bytes: 46932
n, k = map(int, input().split())
p = list(map(int, input().split()))

cnt = 0
for i in range(n):
    if i <= k - 1:
        cnt += p[i]
        tmp = cnt
        end = i + 1
    else:
        cnt = cnt - p[i - k] + p[i]
        if cnt >= tmp:
            tmp = cnt
            end = i + 1

ans = 0
L = p[end - k: end]
for i in L:
    ans += sum(range(1, i + 1)) / i

print(ans)


Measured memory_bytes: 71792
n, x = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i + 1] + a[i] for i in range(n - 1)]
ans = 0
for i in range(n - 1):
    if a[i + 1] + a[i] > x:
        reduce = a[i + 1] + a[i] - x
        ans += reduce
        if a[i + 1] > 0:
            if reduce > a[i + 1]:
                reduce -= a[i + 1]
                a[i + 1] = 0
            else:
                a[i + 1] -= reduce
                reduce = 0
        if reduce > 0:
            a[i] -= reduce
print(ans)

Measured memory_bytes: 14132
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
typedef long long ll;
const int N=0;
int n,k,x,t,a,b;
string s;
vector<int>v;
int main(){

	cin >> n;
	printf("%0.9f",pow(n/3.0,3));	
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    if(n%2==0){
        cout << n/2 - 1;
    }else{
        cout << n/2;
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int N, i, sum=0, x;
    scanf("%d", &N);
    for(i=0; i<N; i++){
        scanf("%d", &x);
        if(x % 2 == 0){
            sum++;
        }
    }
    printf("%d\n", sum);
    return 0;
}

 


Measured memory_bytes: 2104
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {

	var s string
	fmt.Scan(&s)

	date := strings.Split(s, "/")
	year, _ := strconv.Atoi(date[0])
	month, _ := strconv.Atoi(date[1])
	day, _ := strconv.Atoi(date[2])

	if year > 2019 {
		fmt.Println("TBD")
		return
	} else {
		if month > 4 {
			fmt.Println("TBD")
			return
		} else {
			if day > 30 {
				fmt.Println("TBD")
				return
			}
		}
	}
	fmt.Println("Heisei")

}


Measured memory_bytes: 640
N = int(input())
h = [int(i) for i in input().split()]
ans = 0
i = 0
while True:
    if max(h)==0:
        break
    i = 0
    while i < N:
        if h[i]==0:
            i += 1
        else:
            ans += 1
            j = i
            while j<N and h[j]>0:
                h[j] -= 1
                j += 1
print(ans)

Measured memory_bytes: 3064
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
Q = dq([0])
d = [1, 0]
dp = [float("inf")] * (H * W)
dp[0] = int(S[0][0] == "#")
while len(Q):
  p = Q.popleft()
  for k in range(2):
    y = p // W + d[k]
    x = p % W + d[-1 - k]
    if y in range(H) and (x in range(W)):
      f = (S[p // W][p % W] == ".") and (S[y][x] == "#")
      if dp[y * W + x] > dp[p] + f:
        dp[y * W + x] = dp[p] + f
        if f: Q.append(y * W + x)
        else: Q.appendleft(y * W + x)
print(dp[-1])

Measured memory_bytes: 43760
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

#define for1(n) for (int i = 0 ; i < n ; i++)
#define for2(n) for (int j = 0 ; j < n ; j++)
#define for3(n) for (int k = 0 ; k < n ; k++)
#define for4(n) for (int l = 0 ; l < n ; l++)
#define forl(n) for (ll i = 0 ; i < n ; i++)

int main() {
    ios::sync_with_stdio(false);
    int n, k;
    ll z = 10000000000ll;
    cin >> n >> k;
    int x[n]; 
    for1(n) cin >> x[i];
    for1(n - k + 1) {
    	ll a;
    	if (x[i] >= 0) a = x[i + k - 1];
    	else if (x[i + k - 1] < 0) a = abs(x[i]);
    	else if (x[i] <= 0 && x[i + k - 1] >= 0) a = min(abs(x[i]), x[i + k - 1]) + abs(x[i] - x[i + k -1]);
    	z = min(z, a);
	}
	if (z == 10000000000ll) cout << 0;
	else cout << z;
}

Measured memory_bytes: 3944
#include<bits/stdc++.h>
using namespace std;
int main() {
	int A, B, K;
	cin >> A >> B >> K;
	bool flg=true;

	for (int i = K; i > 0; i--) {
		if (flg) {
			if (A % 2 == 0) {
				B += A / 2;
				A /= 2;
			}
			else {
				A -= 1;
				B += A / 2;
				A /= 2;
			}
			flg = !flg;
		}
		 else if (!flg) {
			if (B % 2 == 0) {
				A += B / 2;
				B /= 2;
			}
			else {
				B -= 1;
				A += B / 2;
				B /= 2;
			}
			flg = !flg;
		}
	}

	cout << A <<" "<< B << endl;
}

Measured memory_bytes: 256
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 210000;

ll x[MAXN];
ll y[MAXN];
int n;

int cnk(ll a, ll b) {
	if (b < 0 || b > a)
		return 0;
	return (a & b) == b;
}

int get(ll t) {
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (y[i] > 0) {
			if (x[i] <= t && t <= x[i] + y[i]) {
				ans ^= cnk(y[i] - 1, t - x[i]);
			}
		}
		else if (y[i] == 0) {
			if (x[i] <= t)
				ans ^= 1;
		}
		else {
			if (t >= x[i]) {
				ans ^= cnk(-y[i] - 1 + (t - x[i]) + 1, t - x[i]);
			}
		}
	}
	return ans;
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
	}
	ll lb = -1e18;
	ll rb = 1e18;
	while (rb - lb > 1) {
		ll mid = (lb + rb) >> 1;
		//if (rb == 7629394531250)
		//	int a = 0;
		if (get(mid) == 1)
			rb = mid;
		else
			lb = mid;
	}
//	for (int i = -10; i <= 10; ++i)
//		cerr << i << " " << get(i) << "\n";
	cout << rb << "\n";
	return 0;
}




Measured memory_bytes: 1792
#include <iostream>
#define _GLIBCXX_DEBUG
using namespace std;

int main(){
    string S, T;
    cin >> S >> T;
    
    int x,i;
    int ans = 0;

    x = S.size();
    for( i = 0; i < x; i++ ){
        if( S[i] != T[i] ) ans += 1;
    }

    cout << ans << endl;

}


Measured memory_bytes: 3860
package main

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

const (
	initialBufSize = 1024
	maxBufSize     = 1e6
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	// writer  = bufio.NewWriterSize(os.Stdout, 1000000)
)

func main() {
	scanner.Split(bufio.ScanWords)
	// scanner.Buffer(make([]byte, initialBufSize), maxBufSize)
	// defer writer.Flush()
	n := scanInt()
	h := scanInts(n)

	tmp, ans := 0, 0
	for i := 0; i < n-1; i++ {
		if h[i] >= h[i+1] {
			tmp++
		} else {
			if tmp > ans {
				ans = tmp
			}
			tmp = 0
		}
	}
	if tmp > ans {
		ans = tmp
	}

	fmt.Println(ans)
}

func scanInt() int {
	i, _ := strconv.Atoi(scanString())
	return i
}

func scanInts(size int) []int {
	ints := make([]int, size)
	for i := 0; i < size; i++ {
		ints[i] = scanInt()
	}
	return ints
}

func scanFloat64() float64 {
	f, _ := strconv.ParseFloat(scanString(), 64)
	return f
}

func scanFloat64s(size int) []float64 {
	f := make([]float64, size)
	for i := 0; i < size; i++ {
		f[i] = scanFloat64()
	}
	return f
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func scanStrings(size int) []string {
	s := make([]string, size)
	for i := 0; i < size; i++ {
		s[i] = scanString()
	}
	return s
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

// greatest common divisor(最大公約数)
func gcd(a, b int) int {
	for {
		mod := a % b
		if mod == 0 {
			return b
		}
		a, b = b, mod
	}
}

// latest common multiple(最小公倍数)
func lcm(a, b int) int {
	return (a / gcd(a, b)) * b
}

func fact(n int) int {
	ret := 1
	for i := 1; i <= n; i++ {
		ret *= i
	}
	return ret
}

func perm(n, r int) int {
	ret := 1
	for i := 0; i < r; i++ {
		ret *= n
		n--
	}
	return ret
}

func isPrimeNum(n int) bool {

	if n <= 1 {
		return false
	}

	l := int(math.Sqrt(float64(n)) + 1.)
	for i := 2; i < l; i++ {
		if n%i == 0 {
			return false
		}
	}

	return true
}


Measured memory_bytes: 3072
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
#include<deque>
const double PI = acos(-1);
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
using ll =long long;
const int mod = 1000000007;

//map<string>a
class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% mod + mod) % mod) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint & a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint & operator-=(const mint & a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint & operator*=(const  mint & a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint & a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint & a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint & a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint & a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint & a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream & os, const mint & m) {
		os << m.x;
		return os;
	}
};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
//組み合わせ
void recursive_comb(vector<int> indexes, int s, int rest, std::function<void(vector<int>)> f) {
	if (rest == 0) {
		f(indexes);
	}
	else {
		if (s < 0) return;
		recursive_comb(indexes, s - 1, rest, f);
		indexes[rest - 1] = s;
		recursive_comb(indexes, s - 1, rest - 1, f);
	}
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(vector<int>)> f) {
	vector<int>indexes(k);
	recursive_comb(indexes, n - 1, k, f);
}

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


int main() {
	int N;

	cin >> N;
	vector<ll>h(N);
	map<ll, ll>m;
	rep(i, N) {
		cin >> h[i];
	}
	ll ans = 0;
	ll check=0;
	while (1) {
		check = 0;
		for (int i = 0; i < N; i++) {
			if (h[i] != 0) {

				h[i] --;
				for (int j = i + 1; j < N; j++) {
					if (h[j] != 0) {
						h[j]--;

					}
					else {

						break;
					}

				}
				ans++;
				break;
			}

		check++;
		}
		if (check == N) {
			break;

		}
	}

	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 1000010
#define inf 0x3f3f3f3f
#define LL long long
#define pi acos(-1)
#define MOD 1000000007
using namespace std;

char s[MAXN];
int a[MAXN],ss[MAXN];
int n,k,nn,ans=0;

int main()
{
	cin >> n >> k;
	cin >> s+1;
	int tmp=0;
	char ti;
	if (s[1]=='0') a[++nn]=0;
	for (int i = 1; i <= n; i++){
		if (tmp==0){
			ti=s[i];
			tmp++;
		} else if (s[i]!=ti){
			a[++nn]=tmp;
			tmp=1;
			ti=s[i];
		} else tmp++;
	}
	if (tmp) a[++nn]=tmp;
	if (s[n]=='0') a[++nn]=0;
	//cout << nn << endl;
	for (int i = 1; i <= nn; i++) ss[i]=ss[i-1]+a[i];//,cout<<ss[i]<<endl;
	if (nn<=2*k+1) ans=ss[nn];
	else {
		for (int i = 1; i <= nn-2*k; i++) if (i%2)ans=max(ss[i+2*k]-ss[i-1],ans);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6784
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(w):
    t=s[i]
    b+=a^t
    dp[i]=b
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    q+=p^t
    dp[i]=b=q
    a=p=t
    k=i-x
    for j in range(i+1,i+w):
      sj=s[j]
      b+=a^sj
      k+=1
      t=dp[k]+(s[k]^sj)
      if b>t:b=t
      dp[j]=b
      a=sj
  print(b+1>>1)
main()

Measured memory_bytes: 3188
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define MAX 1000



int solve(string x, string y) {
  int xl = x.size();
  int yl = y.size();
  int lcs[MAX + 1][MAX + 1];

  int i, j;
  for (i = 0; i < xl; i++)
    lcs[i][0] = 0;
  for (j = 0; j < yl; j++)
    lcs[0][j] = 0;

  // shift
  x = " " + x;
  y = " " + y;

  int maxlcs = 0;
  for (i = 1; i <= xl; i++) {
    for (j = 1; j <= yl; j++) {
      if (x[i] == y[j]) {
        lcs[i][j] = lcs[i - 1][j - 1] + 1;
      } else {
        int a = lcs[i][j - 1];
        int b = lcs[i - 1][j];
        lcs[i][j] = max(a, b);
      }
      maxlcs = max(maxlcs, lcs[i][j]);
    }
  }
  return maxlcs;
}

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

Measured memory_bytes: 7008
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(30);
#define ll long long
#define pi 3.14159265359
using namespace std;

int main()
{
    IOS;
    char a;
    cin>>a;
    if(isupper(a)) cout<<'A';
    else cout<<'a';
    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;
int divr[maxn];
/*ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}*/
void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
 
 
 
 
 



















int main()
{
     ll a,b,x;
     cin>>a>>b>>x;
     if(a==0)
     {
          cout<<(b/x+1LL);
     }
     else
     {
          ll res=b/x-(a-1)/x;
          cout<<res;
     }
     


}




 
 
 
 
 

















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
ll pow1(ll a, ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b=b>>1;
	}
	return ans;
}
int main()
{
	int n,i,j;
	cin>>n;
	string s;
	set<string> st;
	char ch;
	for(i=0;i<n;i++)
	{
		cin>>s;
		if(i == 0)
		{
			ch = s[s.size()-1];
			st.insert(s);
			continue;
		}
		if(ch == (s[0]) && st.find(s)==st.end())
		{
			st.insert(s);
			ch = s[s.size()-1];
		}
		else
		{
			cout<<"No\n";
			return 0;
		}
	}
	cout<<"Yes\n";
	return 0;
}

Measured memory_bytes: 256