akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <ctime>
#include <list>
#include <numeric>
#include <fstream>

using namespace std;
static const double EPS = 1e-8;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PI;
#ifndef M_PI
const double M_PI=acos(-1.0);
#endif
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FORR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int((a).size()))
#define F first
#define S second
void pkuassert(bool b){if(!b){int a=0;cout << 1/a << endl;}};
int dx[]={0,-1,0,1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1};

int n,m;

string in[100];

void solve(){
  vector<string> app;  
  rep(i,n) cin >> in[i];
  rep(i,n)rep(j,m){
    rep(k,8){
      int cx=i,cy=j;
      string str;
      do{
        str += in[cx][cy];
        cx += dx[k];
        cy += dy[k];
        if(cx<0) cx += n;
        if(cy<0) cy += m;
        if(cx>=n) cx -= n;
        if(cy>=m) cy -= m;
      }while(cx!=i || cy!=j);
      app.pb(str);
    }
  }
  sort(ALL(app));

  string ans;
  rep(i,SZ(app)-1){
    int le=0;
    while(le<SZ(app[i]) && le<SZ(app[i+1]) &&
          app[i][le]==app[i+1][le])
      ++le;
    if(SZ(ans)<le) ans = app[i].substr(0,le);
  }
  
  if(SZ(ans)>1) cout << ans << endl;
  else cout << 0 << endl;
}

int main(){
  while(cin >> n >> m && n&&m) solve();
}

Measured memory_bytes: 1520
// 問題名:　Square Route
// URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2015&lang=jp
// 所要時間: 20分
// --感想--
// intの配列は今までfor文を用いて1個ずつ0を代入して初期化していたので、今後は"= {}"などを用いて簡略化するようにしたい。

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

int main(){
    int T;
    cin >> T;
    for (; T > 0; T--){
        int n[11];
        char c[11];
        for (int i = 0; i < 9;i++)
            cin >> n[i];
        for (int i = 0; i < 9; i++)
            cin >> c[i];
        pair<int,char> card[11];
        for (int i = 0; i < 9;i++)
            card[i] = make_pair(n[i], c[i]);
        sort(card, card + 9);
        int ans = 0;
        // 勝てる手札なら、左から綺麗に3セット並ぶような並べ方が存在する
        do{
            bool flag = true;
            for (int i = 0; i < 3;i++){
                // カードの色が違う
                if (card[i * 3].second != card[i * 3 + 1].second || card[i * 3 + 1].second != card[i * 3 + 2].second)
                    flag = false;
                // 連番や同じ数字でない
                if (!((card[i * 3].first == card[i * 3 + 1].first && card[i * 3 + 1].first == card[i * 3 + 2].first)
                    ||(card[i * 3].first + 1 == card[i * 3 + 1].first && card[i * 3 + 1].first + 1 == card[i * 3 + 2].first)))
                    flag = false;
            }
            if(flag)
                ans = 1;
        } while (next_permutation(card, card + 9));
        cout << ans << endl;
    }
}


Measured memory_bytes: 3004
# -*- coding: utf-8 -*-

def main():
    N  = int(input())
    if N > 81:
        print("No")
        exit()
    for i in range(1,10,1):
        if N % i ==0 and N // i < 10:
            print("Yes")
            exit()
    print("No")

        
if __name__ == '__main__':
    main()

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

int main() {
  int n, k, q; cin >> n >> k >> q;
  vector<int> a(n);
  rep(i,q) {
    int ai; cin >> ai;
    a[--ai]++;
  }
  rep(i,n) {
    //cout << k - q + a[i] << endl;
    if (k - q + a[i]  > 0) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3744
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Main{
	static BufferedReader br;
	static int in() throws Exception
	{
		return Integer.valueOf(br.readLine());
	}
	static int[] split() throws Exception
	{
		String[] cmd=br.readLine().split(" ");
		int[] ans=new int[cmd.length];
		for(int i=0;i<cmd.length;i++)
		{
			ans[i]=Integer.valueOf(cmd[i]);
		}
		return ans;
	}
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n=in();
        int ans=0;
        if(n>=400 && n<=599)
        	ans=8;
        else if(n>=600 && n<=799)
        	ans=7;
        else if(n>=800 && n<=999)
        	ans=6;
        else if(n>=1000 && n<=1199)
        	ans=5;
        else if(n>=1200 && n<=1399)
        	ans=4;
        else if(n>=1400 && n<=1599)
        	ans=3;
        else if(n>=1600 && n<=1799)
        	ans=2;
        else if(n>=1800 && n<=1999)
        	ans=1;
        System.out.println(ans);
    }
}


Measured memory_bytes: 32456
import itertools
def main():
    n = int(input())
    A = [0 for i in range(5)]
    for _ in range(n):
        s = input()
        if s[0] in "MARCH":
            A["MARCH".index(s[0])] += 1
    ans = 0
    for i, j, k in itertools.combinations(range(5), 3):
        ans += A[i] * A[j] * A[k]
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static MyIO;


public class B
{
	public static void Main()	
	{
		int N = GetInt();
		int K = GetInt();
		List<int> l = new List<int>(N);
		for(int i = 0; i < N; i++)
			l.Add(GetInt());
		l.Sort((x,y) => y-x);
		int ans = 0;
		for(int i = 0; i < K; i++)
			ans += l[i];
		Console.WriteLine(ans);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


Measured memory_bytes: 11220
def mod(n,p):
    return n % p
#ある数をAで割ったとき，その数をpで割ったときの余りを求めるのにかけるべき数を返す
def bunbo(A, p): 
    # p-2を2進数にする
    pp = p-2
    pb = list(str(format(pp, 'b')))
    # ひっくりかえす
    pb.reverse()
    # pbの要素の数lとして，A^1, A^2, A^4, A^8, ..., A^(2^l)をpで割った余りを求める
    lpp = [mod(A,p)]
    for _ in range(len(pb)-1):
        lpp.append(mod((lpp[-1] ** 2), p))
    # 必要なやつだけ足して，x=(A^(p-2)をpで割った余り)を求める
    x = 1
    for i in range(len(pb)):
        if pb[i] == '1':
            x *= lpp[i]
    return mod(x, p)

def nckp(n, k, p):
    # 0!, 1!, 2!, 3!, ..., n!をリストに入れる
    nk = [1]
    for i in range(1,n+1):
        nk.append(mod((nk[-1] * i), p))
    return mod((nk[n] * bunbo(nk[k], p) * bunbo(nk[n-k], p)),p)

X, Y = map(int,input().split())
if (2*X-Y) % 3 != 0 or (2*Y-X) % 3 != 0:
    print(0)
elif 2*X-Y < 0 or 2*Y-X < 0:
    print(0)
else:
    a = (2*Y-X) // 3
    b = (2*X-Y) // 3
    n = a + b
    k = a
    p = 1000000007
    print(nckp(n, k, p))

Measured memory_bytes: 29484
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<Int, Int> P;

int main(){
    int N; cin >> N;
    vector<int> P(10), Q(10);
    rep(i,N) cin >> P[i];
    rep(i,N) cin >> Q[i];

    vector<int> perm(10);
    rep(i,N) perm[i] = i+1;

    int a, b, cnt = 0;
    do {
        bool flag1 = true, flag2 = true;
        rep(i,N){
            if (P[i] != perm[i]) flag1 = false;
            if (Q[i] != perm[i]) flag2 = false;
        }

        if(flag1) a = cnt;
        if(flag2) b = cnt;

        cnt++;
    } while (next_permutation(perm.begin(),perm.begin()+N));

    cout << abs(a-b) << endl;
    
}


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

int main(){
	int a,b,c;
	string str;
	stringstream ss;
	while(cin>>a>>b){
		c=a+b;
		ss<<c;
		str=ss.str();
		ss.str("");
		c=str.length();
		cout<<c<<endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>


int merge(long int a1[], long int a2[], int a1_size, int a2_size, long int a[]);
int merge2(long int b1[], long int b2[], long int c1[], long int c2[], int b1_size, int b2_size, long int b[], long int c[]);
int mergeSort(long int a[], int number);
int mergeSort2(long int a[], long int b[], int number);

int main(void)
{
	int n, m;
	long int sum = 0;
	int i, j, index = 0;;
	long int work;
	long int a[100000], b[100000], c[100000];
	
	scanf("%d%d", &n, &m);
	
	for(i = 0; i < n; i++) {
		scanf("%ld", &a[i]);
		sum += a[i];
	}
	for(i = 0; i < m; i++) {
		scanf("%ld%ld", &b[i], &c[i]);
	}
	
	mergeSort(a, n);
	mergeSort2(b, c, m);
		
	for(i = 0; i < m; i++) {
		if(a[index] > c[i]) {
			break;
		}
		for(j = 0; j < b[i]; j++) {
			if(index + j >= n) {
				break;
			}
			if(a[index + j] < c[i]) {
				sum += c[i] - a[index + j];
			}
		}
		index += b[i];
		if(index >= n) {
			break;
		}
	}
	/*
	for(i = 0; i < n; i++) {
		printf("%ld\n", a[i]);
	}
	
	for(i = 0; i < m; i++) {
		printf("%ld %ld\n", b[i], c[i]);
	}
	*/
	printf("%ld\n", sum);
	
	return 0;
}

int merge(long int a1[], long int a2[], int a1_size, int a2_size, long int a[])
{
	int i = 0, j = 0;
	
	while( (i < a1_size ) || (j < a2_size) ){
		if( (j >= a2_size ) || ( (i < a1_size) && (a1[i] < a2[j]) ) ) {
			a[i + j] = a1[i];
			i++;
		} else {
			a[i + j] = a2[j];
			j++;
		}
	}
	
	return 0;
}

int merge2(long int b1[], long int b2[], long int c1[], long int c2[], int b1_size, int b2_size, long int b[], long int c[])
{
	int i = 0, j = 0;
	
	
	while( (i < b1_size ) || (j < b2_size ) ) {
		if( (j >= b2_size ) || ( (i < b1_size) && (c1[i] > c2[j]) ) ) {
			b[i + j] = b1[i];
			c[i + j] = c1[i];
			i++;
		} else {
			b[i + j] = b2[j];
			c[i + j] = c2[j];
			j++;
		}
	}
	
	return 0;
}

int mergeSort(long int a[], int number)
{
	int m = number / 2, n = number - m;
	long int a1[m];
	long int a2[n];
	int i, j;
	
	if(number > 1) {
		for(i = 0; i < m; i++) {
			a1[i] = a[i];
		}
		for(i = 0; i < n; i++) {
			a2[i] = a[m + i];
		}
		mergeSort(a1, m);
		mergeSort(a2, n);
		merge(a1, a2, m, n, a);
	}
	
	return 0;
}

int mergeSort2(long int b[], long int c[], int number)
{
	int m = number / 2, n = number - m;
	long int b1[m];
	long int b2[n];
	long int c1[m];
	long int c2[n];
	int i, j;
	
	if(number > 1) {
		for(i = 0; i < m; i++) {
			b1[i] = b[i];
		}
		for(i = 0; i < n; i++) {
			b2[i] = b[m + i];
		}
		
		for(i = 0; i < m; i++) {
			c1[i] = c[i];
		}
		for(i = 0; i < n; i++) {
			c2[i] = c[m + i];
		}
		
		mergeSort2(b1, c1, m);
		mergeSort2(b2, c2, n);
		merge2(b1, b2, c1, c2, m, n, b, c);
	}
	
	return 0;
}

Measured memory_bytes: 5632
#include<iostream>
	using namespace std;
	
	int main()
	{
			int a,b,c;
			cin >> a;
			cin >> b;
			cin >> c;
			
			if((c>=a&&c<=b)||(c<=a&&c>=b))
			{
				cout << "Yes"<< endl;
			}
			else
			{
				cout << "No"<< endl;
			}
	}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#include<atcoder/all>
#include<iostream>
#include<cstdint>
#include<cstddef>
#include<set>
#include<vector>
using namespace std;
//using namespace atcoder;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using usize = uint_fast64_t;
#define rep(i, n) for (usize i = 0; i < (usize)(n); i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using P = pair<i64,i64>;
vector<vector<i64>> edges;
i64 cnt,n;
void dfs(set<i64> st, i64 now){
    if(st.count(now))return ;
    st.insert(now);
    set<i64> nst = st;
    if(nst.size() == n){
        cnt++;
        return ;
    }
    for(auto v:edges[now])dfs(nst,v);
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 m;
cin >> n >> m;
edges.resize(n);
rep(i,m){
    i64 a,b;
    cin >> a >> b;
    edges[a - 1].emplace_back(b - 1);
    edges[b - 1].emplace_back(a - 1);
}
set<i64> st;
dfs(st,0);
cout << cnt << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define lowbit(x) (x&-x)
using namespace std;
const int mod=1e9+7;
inline int read()
{
	int kkk=0,x=1;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-')
		c=getchar();
	if(c=='-')
		c=getchar(),x=-1;
	while(c>='0' && c<='9')
		kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
	return kkk*x;
}
int n,m,x[100001],y[100001],liml,limr,tree[200001],dp[100001],ans,tot,num[200001];
struct sb
{
	int l,r;
}a[100001];
inline int cmp(sb x,sb y)
{
	return x.l<y.l || (x.l==y.l && x.r<y.r);
}
inline int cx(int zone)
{
	int bck=0;
	while(zone)
	{
		bck=(bck+tree[zone])%mod;
		zone-=lowbit(zone);
	}
	return bck;
}
inline void xg(int zone,int v)
{
	while(zone<=tot)
	{
		tree[zone]=(tree[zone]+v)%mod;
		zone+=lowbit(zone);
	}
}
inline int find(int v)
{
	int l=1,r=tot,bck;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(num[mid]<=v)
			bck=mid,l=mid+1;
		else
			r=mid-1;
	}
	return bck;
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
		x[i]=read();
	for(register int i=1;i<=m;++i)
		y[i]=read();
	for(liml=1;liml<=n && x[liml]<y[1];++liml);
	for(limr=n;limr>=1 && x[limr]>y[m];--limr);
	if(liml>limr)
	{
		puts("1");
		return 0;
	}
	int bj=1;
	for(register int i=liml;i<=limr;++i)
	{
		while(x[i]>y[bj+1])
			++bj;
		a[++tot].l=x[i]-y[bj];
		a[tot].r=y[bj+1]-x[i];
	}
	sort(a+1,a+tot+1,cmp);
	n=1;
	for(register int i=2;i<=tot;++i)
		if(a[i].l!=a[n].l || a[i].r!=a[n].r)
			a[++n].l=a[i].l,a[n].r=a[i].r;
	//cout<<n<<endl;
	//for(register int i=1;i<=n;++i)
	//	cout<<a[i].l<<" "<<a[i].r<<endl;
	tot=0;
	for(register int i=1;i<=n;++i)
	{
		num[++tot]=a[i].r;
		num[++tot]=a[i].r-1;
	}
	sort(num+1,num+tot+1);
	tot=unique(num+1,num+tot+1)-num-1;
	for(register int i=1;i<=n;)
	{
		int mem=i;
		while(a[i].l==a[mem].l && i<=n)
		{
			dp[i]=(cx(find(a[i].r-1))+1)%mod;
			ans=(ans+dp[i])%mod;
			++i;
		}
		for(register int j=mem;j<i;++j)
			xg(find(a[j].r),dp[j]);
	}
	printf("%d\n",(ans+1)%mod);
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(int,a,b,c);
	OUT(min(c,b/a))BR;
  
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

class Main {
    public static void main(final String[] args) throws Exception {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
            List<String> inputNumberString = Arrays.asList(br.readLine().split(" "));
            int N = Integer.parseInt(inputNumberString.get(0));
            int A = Integer.parseInt(inputNumberString.get(1));
            int B = Integer.parseInt(inputNumberString.get(2));

            int ans = 0;
            for (int i = 1; i <= N; i++) {
                List<String> tmpStringList = Arrays.asList(String.valueOf(i).split(""));
                int tmpSum = 0;
                for (String str : tmpStringList) {
                    tmpSum += Integer.parseInt(str);
                }

                if (tmpSum >= A && tmpSum <= B) {
                    ans += i;
                }
            }

            System.out.println(ans);
        } catch (IOException | NumberFormatException e) {
            e.printStackTrace();
            System.exit(0);
        } catch (final Exception e) {
            e.printStackTrace();
            System.exit(0);
        }
    }
}

Measured memory_bytes: 34132
o=998244353
r=2500100
f=[1]
for i in range(1,r):
 f.append(f[-1]*i%o)
def v(x):
 return pow(x,o-2,o)
def c(n,k):
 return f[n]*v(f[n-k])*v(f[k])%o
n,m=map(int,input().split())
w=3*m
a=(c(n+w-1,n-1)-n*c(n+m-2,n-1))%o
if n>m+1:
 for i in range(m+1,min(w,n)+1):
  if (w-i)%2:continue
  x=(w-i)//2
  a=(a-c(n,i)*c(x+n-1,n-1))%o
print(a)

Measured memory_bytes: 107144
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
int main()
{
	string s1="";
  	string s2="";
  	cin>>s1;
  	for(int i=0;i<s1.length();i++)
    {
      s2=s2+"x";
    }
  cout<<s2;
}


Measured memory_bytes: 256
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
amax = max(d.keys())
t = 1
valids = []
while t < 2 * amax:
  t *= 2
  valids.append(t)
result = 0
keys = list(sorted(d.keys(), reverse = True))
for a in keys:
  if a not in d:
    continue
  t = valids[bisect_right(valids, a)] - a
  while True:
    if t not in d:
      break
    if a == t and d[a] == 1:
      break
    result += 1
    if d[a] == 1:
      del d[a]
    else:
      d[a] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    if a not in d:
      break
print(result)


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

using namespace std;
int main() {
	
  int N, K;
  vector<int> x;
  
  cin >> N >> K;
  x.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> x[i];
  }
  
  int sum = 0;
  for (int i = 0; i < N; ++i) {
    sum += min(x[i], K - x[i]) * 2;
  }
  
  cout << sum << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main(){
    int n,q,a,b,p,x;
    cin>>n>>q;
    vector<int>g[n],ans(n,0);
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }
    for(int i=0;i<q;i++){
        cin>>p>>x;
        ans[--p]+=x;
    }
    vector<bool>visited(n);
    stack<int>s;
    s.push(0);
    visited[0]=true;
    while(!s.empty()){
        int n=s.top();s.pop();
        for(auto x:g[n])if(!visited[x])s.push(x),visited[x]=true,ans[x]+=ans[n];
    }
    for(auto x:ans)cout<<x<<" ";
    return 0;
}

Measured memory_bytes: 15604
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c,x,y,z;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN2(a,b);
  Yay(a<=8&&b<=8);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
vector<pair<char, int>> runLength(string x)
{
	char now = x[0];
	int count = 1;
	vector<pair<char, int>> ret;
	for (int i = 1; i < x.size(); ++i)
	{
		if(x[i] != now)
		{
			ret.push_back(make_pair(now, count));
			now = x[i];
			count = 1;
		}
		else
		{
			++count;
		}
	}
	ret.push_back(make_pair(now, count));
	return ret;
}
 
int main()
{
	string in;
	cin >> in;
	auto re = runLength(in);
	int res[100001] = {};
	int count = 0;
	for (int i = 0; i < re.size() - 1; i += 2)
	{
		res[count + re[i].second-1] = 1 + (re[i].second-1) / 2 + re[i+1].second / 2;
		res[count + re[i].second] = 1 + re[i].second / 2 + (re[i+1].second-1)/2;
		count += re[i].second + re[i + 1].second;
	}
	for (int i = 0; i < in.size(); ++i)
	{
		cout << res[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1908
import static java.lang.Double.parseDouble;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	private static final long MOD = 1000000007;
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	void solve() throws Exception {

		long res = solution(nextInt());
//		Helper.tr(freq);
		out.println(res);
	}

	private long solution(int N) {
		
		return (N+1)/2*(N/2);
	}

	private long f(long cnt) {
		if (cnt <= 0)
			return 0;
		return cnt * cnt;
	}

	private int[][] nextInts(int r, int c) throws IOException {
		int[] a[];
		a = new int[r][c];
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				a[i][j] = nextInt();
		return a;
	}

	private int[] nextTuple(int n) throws IOException {
		int[] a;
		a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	private int[] nextInts(int n) throws IOException {
		return nextTuple(n);
	}

	static int nextInt() throws IOException {
		return parseInt(next());
	}

	static long nextLong() throws IOException {
		return parseLong(next());
	}

	static double nextDouble() throws IOException {
		return parseDouble(next());
	}

	static String next() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public static void main(String[] args) {
		new Thread(null, null, "Main", 0x4000000) {
			public void run() {
				try {
					in = new BufferedReader(new InputStreamReader(System.in));
					out = new PrintWriter(new OutputStreamWriter(System.out));
					new Main().solve();
					in.close();
					out.close();
				} catch (Throwable e) {
					e.printStackTrace();
					exit(1);
				}
			}
		}.start();
	}
}


Measured memory_bytes: 24276
#include <bits/stdc++.h>
using namespace std;
string s, t;
vector<vector<int>> dp(3010, vector<int>(3010, 0));

int main() {
    cin >> s >> t;
    int slen = s.length();
    int tlen = t.length();

    for(int i = 1; i < slen+1; ++i) {
        for(int j = 1; j < tlen+1; ++j) {
            if(s.at(i-1) == t.at(j-1)) {
                dp.at(i).at(j) = dp.at(i-1).at(j-1)+1;
            }else {
                dp.at(i).at(j) = max(dp.at(i-1).at(j), dp.at(i).at(j-1));
            }
        }
    }

    int len = dp.at(slen).at(tlen);
    int si = slen;
    int ti = tlen;
    string ans;
    while(len > 0) {
        if(s.at(si-1) == t.at(ti-1)) {
            ans.push_back(s.at(si-1));
            si--;
            ti--;
            len--;
        }else if(dp.at(si).at(ti) == dp.at(si-1).at(ti)) {
            si--;
        }else {
            ti--;
        }
    }

    reverse(ans.begin(), ans.end());

    cout << ans << endl;
}

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

typedef long long ll;
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define memset(v, h) memset((v), h, sizeof(v))
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll m[20][20];

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

struct node
{
    public: ll x;
    public: ll y;

    node(ll xx, ll yy)
    {
        x = xx;
        y = yy;
    }
};

int main(){
    ll h, n;
    cin >> h >> n;

    ll d[n];
    ll c[n];

    rep(i,n)cin >> d[i] >> c[i];


    ll dp[h+1];

    rep(i, h+1)
    {
        dp[i] = 0;
    }

    ll min = 0;
    rep(i, h+1){
        if(i > 0 && dp[i] == 0)
        {
            continue;
        }

        rep(j, n)
        {
            ll damage = i + d[j];
            ll cost = dp[i] + c[j];

            if(damage > h)
            {
                damage = h;
            }

            if(dp[damage] == 0 || dp[damage] > cost)
            {
                dp[damage] = cost;

                if(damage == h && (min == 0 || min > cost))
                {
                    min = cost;
                }
            }   
        }
    }

    cout << min << endl;
    return 0;
}

Measured memory_bytes: 384
#define KAKUSUKO
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N;
string S;

int main() {

    cin >> N;
    cin >> S;

    S.erase(unique(all(S)), S.end());

    cerr << S << endl;

    cout << len(S) << endl;

    return 0;
}


Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> >vvi;
typedef pair<int,int> P;
const ll MOD=1000000007LL;
int main(){
  int n,q;
  cin>>n>>q;
  string s;cin>>s;
  vi count(n);
  count[0]=0;
  for(int i=1;i<n;i++){
    if(s[i-1]=='A' && s[i]=='C')count[i]=count[i-1]+1;
    else count[i]=count[i-1];
  }
  rep(i,q){
    int l,r;
    cin>>l>>r;
    cout<<count[r-1]-count[l-1]<<endl;
  }
}
   
  
  

Measured memory_bytes: 1408
// template
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<long long, long long> LP;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define REP_AB(i, a, b) for (ll i = ll(a); i <= ll(b); ++i)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)), v.end());
#define SIZE(x) ((ll)(x).size())
#define REVERSE(v) reverse(ALL(v))
// true / false
#define BIN_SEARCH(v, a) binary_search(ALL(v), a)
// index
#define BIN_LEFT(v, a) (lower_bound(ALL(v), a) - v.begin())
#define BIN_RIGHT(v, a) (upper_bound(ALL(v), a) - v.begin())
#define BIN_INSERT(v, a) (v.insert(v.begin() + BIN_LEFT(v, a), a))
#define DEL(v, i) v.erase(v.begin() + i)
#define INSERT(v, i, a) v.insert(v.begin() + i, a)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a / gcd(a, b)) * b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define out cout
#define in cin
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
// template end

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

    ll n;
    in >> n;
    vector<ll> h(n);
    REP(i, n) in >> h[i];
    ll dp[n] = {};
    dp[2] = abs(h[1] - h[0]);
    if(n > 2){
        REP_AB(i, 3, n){
            dp[i] = min(dp[i-1] + abs(h[i-1] - h[i-2]), dp[i-2] + abs(h[i-1] - h[i-3]));
        }
    }
    out << dp[n] << endl;
}


Measured memory_bytes: 1792
a = input()
b = input()
f = abs(len(a) - len(b))
if f== 0 :
  pass
else :
  if len(a)<len(b):
    a+=" "
  else :
    b += " "
s = ""
for i,j in zip(a,b):
  s+= i+j
print(s.replace(' ', ''))
  

Measured memory_bytes: 3060
N = int(input())
A = [0]*(N)
H = list(map(int, input().split()))
ans = int(0)
count = int(0)
ansc = []


for i in range(N-1):
    if H[i]>=H[i+1]:
        count += 1
    else:
        ansc.append(count)
        count =  int(0)

ansc.append(count)
ans = max(ansc)

print(ans)

Measured memory_bytes: 15120
#include <stdio.h>

int main(void)
{
	int i,a,m[100];
    
	scanf("%d",&a);
    
	for(i=0;i<a;i++)
	{
        scanf("%d",&m[i]);
    }
    
	for(i=a-1;i>-1;i--)
	{
        printf("%d",m[i]);
        if(i!=0)
		{
			printf(" ");
		}
    }
    
	printf("\n");
    
	return 0;
}

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

int main(){
int a;
  cin >> a;
  cout << (a+2-1)/2 << endl;
}

Measured memory_bytes: 3600
#include<iostream>

using namespace std;

int main(){

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


  while(cin >> sx >> sy){

    if(sx==0 && sy==0) break;

    int live[11][9]={{0}};
    int x[11][9],y[11][9];

    live[0][4]=1;
    x[0][4]=sx;
    y[0][4]=sy;

    int n;
    cin >> n;

    bool dead=false;

    for(int i=1;i<=n;i++){// ジャンプ回数
      
      cin >> sx >> sy;
      if(dead) continue;
      dead = true;

      for(int j=0;j<9;j++){// 新スプリンクラーの周囲の位置j
	x[i][j]=sx+dx[j];
	y[i][j]=sy+dy[j];
	
	// 範囲外
	if(x[i][j]<0 || x[i][j]>9 || y[i][j]<0 || y[i][j]>9) continue;

	for(int k=0;k<9;k++){// 旧スプリンクラーの周囲の位置k
	  if(live[i-1][k]){
 	    int d_x = x[i][j] - x[i-1][k];
	    int d_y = y[i][j] - y[i-1][k];
	    int d2 = d_x * d_x + d_y * d_y;
	    
	    if(d2 == 4 || d2 == 5){
	      live[i][j] = 1;
	      dead = false;
	      break;
	    }
	  }
	}
      }

      // cout << "i = " << i << endl;
      // for(int j=0;j<9;j++){
      // 	cout << new_l[j] << " ";
      // 	if (j%3==2) cout << endl;
      // }

    }

    if(dead) cout << "NA" << endl;
    else cout << "OK" << endl;
    
  }
  return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>

int main() {
    int n, a;
    scanf("%d", &n);
    a = (n+1)/2;
    float n2, a2, final;
    n2 = n;
    a2 = a;
    final = a/n2;
    //printf("%.9lf %.9lf\n", a2, n2);
    printf("%.9lf\n", final);


    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
using Graph = vector<vector<int>>;
//#define pi 3.1415926535

vector<bool> seen;
void dfs(const Graph &G, int v){
 
  seen[v] = true;
  for(auto next_v : G[v]){
    if(seen[next_v]){
      continue;
    }
 
    dfs(G, next_v);
  }
}
 
int main()
{
  int n, m;
  cin >> n >> m;
 
  Graph G(n);
  for (int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;
    G[a - 1].push_back(b - 1);
    G[b - 1].push_back(a - 1);
  }

  seen.assign(n, false);
 
  int c = 0;
  for(int v = 0; v < n; v++){
    if(seen[v]){
      continue;
    } 
    
    dfs(G, v);
    c++;
  }
 
  cout << c - 1 << endl;
 
  return 0; 
}

Measured memory_bytes: 9596
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = 99999999;
const ll linf = 999999999999999999;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////



int main(){
	double N;
	cin >> N;
    
	rep(h,1,3501){
        rep(n,1,3501){
            
            double w = (h*n*N) / (4*h*n - h*N - n*N);
                
                 
            if(1 <= w && w <= 3500 && w == (ll)w){
                cout << h << " " << n << " " << (ll)w << endl;
                ret 0;         
            }           
        }
	}


	return  0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
int main() {
   int a1,a2,a3;cin>>a1>>a2>>a3;
   if(a1+a2+a3>=22){
       cout<<"bust"<<endl;
   }else{
       cout<<"win"<<endl;
   }
}

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

#define M 1046527
#define L 14

char H[M][L];

int getChar(char ch){
    if(ch == 'A') return 1;
    else if(ch == 'C') return 2;
    else if(ch == 'G') return 3;
    else if(ch == 'T') return 4;
}

// 文字列から数値へ変換してkeyを生成
long long getKey(char str[]){
    long long sum=0, p=1;
    for(long long i=0; i<strlen(str); i++){
        sum += p*(getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return (1 + (key % (M-1))); }

int find(char str[]){
    long long key, i, h;
    key = getKey(str);
    for(i=0;; i++){
        h = (h1(key) + i*h2(key)) % M;
        if(strcmp(H[h], str) == 0) return 1;
        else if(strlen(H[h]) == 0) return 0;
    }
    return 0;
}

int insert(char str[]){
    long long key, i, h;
    key = getKey(str);
    for(i=0;; i++){
        h = (h1(key) + i*h2(key)) % M;
        if(strcmp(H[h], str) == 0) return 1;
        else if(strlen(H[h]) == 0){
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int n, h;
    char str[L], com[9];  
    for(int i=0; i<M; i++) H[i][0] = '\0';  
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> com >> str;
        if(com[0] == 'i'){
            insert(str);
        }else{
            if(find(str)){
                cout << "yes" << endl; 
            }else{
                cout << "no" << endl;
            }
        } 
    }
    return 0;
}


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

struct UnionFind {
  vector<int> ps, ss;

  UnionFind(){};

  UnionFind(int n) {
    ps.resize(n, 0);
    ss.resize(n, 1);
    for (int i = 0; i < n; ++i) {
      ps[i] = i;
    }
  }

  int find(int x) {
    if (ps[x] != x) {
      ps[x] = find(ps[x]);
    }
    return ps[x];
  }

  int size(int x) {
    return ss[find(x)];
  }

  void unite(int x, int y) {
    int x_root = find(x);
    int y_root = find(y);
    if (x_root == y_root) {
      return;
    }
    if (ss[x_root] < ss[y_root]) {
      swap(x_root, y_root);
    }
    ps[y_root] = x_root;
    ss[x_root] += ss[y_root];
  }
};

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

  vector<pair<int, int>> ab;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    ab.emplace_back(a - 1, b - 1);
  }

  UnionFind u(n);

  vector<long long> ans(m + 1);
  ans[m] = n * (n - 1) / 2;
  for (int i = m - 1; i >= 0; --i) {
    int a = ab[i].first;
    int b = ab[i].second;
    if (u.find(a) == u.find(b)) {
      ans[i] = ans[i + 1];
      continue;
    }
    long long an = u.size(a);
    long long bn = u.size(b);
    u.unite(a, b);
    ans[i] = ans[i + 1] - an * bn;
  }

  for (int i = 0; i < m; ++i) {
    cout << ans[i + 1] << endl;
  }
}

Measured memory_bytes: 5548
#include<bits/stdc++.h>
using namespace std;
#define int long long

bool compare(int a,int b){
  return a<b;//ascending
} 

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);


    int n;
    cin>>n;
    cout<<!n<<endl;


  return 0;
}

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

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") { 
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}
                     
int main()
{                                  
  # ifdef Local
    //localInput();
  # endif
  Read_rap();
  string s;
  int cnt = 0;
  cin >> s;
           
  for (int i = 0; i + 1 < sz(s); i++)
    if (s[i] != s[i + 1])
      cnt++;
  cout << cnt;


  return 0;
}






// Coded by Z..



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

#define DIV 1000000007

int main(void) {
	long long n,m,temp=1,min,max;

	scanf("%lld %lld", &n, &m);
	if (n >= m)max = n, min = m;
	else max = m, min = n;

	for (long long i = 1; i <= min; i++) {
		temp = temp * i %DIV;

	}

	if (min == max - 1)printf("%lld", (temp * temp%DIV) * max % DIV);
	else if (min == max)printf("%lld", 2 * temp * temp % DIV);
	else printf("0");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT64_MAX;
const long long int Mod = 1000000007;
const long long int INF_dp = 1<<29; 
using ll = long long int; using ci = const int;
using vi = vector<int>;
using Vi = vector<long long int>;
typedef pair<int, int> P; typedef pair<ll, ll> PLL;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
typedef vector<vector<ll> > matrix;
void princ(auto x){cout<<x<<" ";}; void print(auto x){cout<<x<<"\n";};
///////////////////////////////////////////////////////////////////////////////////

struct edge{/*重み付き,有向*/
    int to , cost;/*toは接続先*/
    edge(ll to_ ,ll cost_ = 1){ to=to_; cost=cost_; };/*全てのcost=1 <=> 無向グラフ*/
};
bool operator<(edge e1 ,edge e2){return e1.cost < e2.cost; }
bool operator>(edge e1 ,edge e2){return e1.cost > e2.cost; }
using graph =  vector< vector<edge> >;

graph g;
ll n,q;
Vi su;
vector<bool> seen;
void dfs(int v,int num){
    if(seen[v])return;
    seen[v]=true;
    num += su[v];
    su[v] = num;
    rep(i,g[v].size()){
        dfs(g[v][i].to,num);
    }
}


int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>n>>q; ll a,b,p,x;
    g.resize(n+1);
    seen.resize(n+1,false);
    rep(i,n-1){
        cin>>a>>b;
        g[a].pb(edge(b));
        g[b].pb(edge(a));
    }
    su.resize(n+1);
    rep(i,n+1)su[i]=0;
    rep(i,q){
        cin>>p>>x;
        su[p] += x;
    }
    dfs(1,0);
    rep(i,n)princ(su[i+1]);
    print("");
    return 0;
}

Measured memory_bytes: 21248
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);v++)
#define FOR(v,a,n) for(int v=a;v<(int)(n);v++)
#define FORE(x,arr) for(auto &x:arr)
#define REP(v,n) FOR(v,0,n)
#define ALL(c) begin(c),end(c)
const int DX[4]={0,1,0,-1}, DY[4]={-1,0,1,0};
const int INF = 1e9;
template<class T,class U>ostream&operator<<(ostream &os,const pair<T,U> &p){
    os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T>ostream&operator<<(ostream &os,const vector<T> &v){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":" ");return os;}
//-----------------------------------------------------------

int main(int argc, char const *argv[]) {
    int n,l;
    cin>>n>>l;
    vector<int> a(n);
    REP(i,n) cin>>a[i];

    int last=-1;
    REP(i,n-1) {
        if(a[i]+a[i+1]>=l) {
            last=i;
            break;
        }
    }
    if(last==-1) {
        cout<<"Impossible"<<endl;
        return 0;
    }
    cout<<"Possible"<<endl;
    REP(i,last) cout<<i+1<<endl;
    for(int i=n-1;i>last;i--) cout<<i<<endl;
    return 0;
}


Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		String t = sc.next();

		int matchMax = 0;
		for (int i=0; i+t.length() <= s.length(); i++){
			int match = 0;
			for (int j=0; j<t.length();j++){
				if (s.charAt(i+j) == t.charAt(j)){
					match++;
				}
			}
			matchMax = Math.max(matchMax, match);
		}
		System.out.println(t.length() - matchMax);
	}


}

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

int main()
{
  int64_t N, X;
  cin >> N >> X;
  vector<int64_t> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  for (int i = 0; i < N; i++)
  {
    if (A.at(i) > X)
    {
      cout << i << endl;
      return 0;
    }
    X -= A.at(i);
  }
  cout << (X == 0 ? N : N - 1) << endl;
}


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

public class MainClass
{
	public const long Giri = 1000000007;

	public static void Main(string[] args)
	{
		var o = Input().ToInt();
		var n = o[0];
		var k = o[1];
		o = Input().ToInt();
		var r = o[0];
		var s = o[1];
		var p = o[2];
		var t = Console.ReadLine();
		var map = new Dictionary<char, int>(){{'r',r}, {'s', s}, {'p', p}};
		var dp = new int[n];
		long wa = 0;
		for(int i = 0; i < n; i++)
		{
			char tea = t[i];
			char kati = t[i] == 'r' ? 'p' : (t[i] == 's' ? 'r' : 's');
			int q = kati == 'r' ? 0 : (kati == 's' ? 1 : 2);
			
			if(i - k >= 0 && tea == t[i-k] && dp[i-k] == 1)
			{
				
			}
			else
			{
				wa += map[kati];
				dp[i] = 1;
			}
		}
		Console.WriteLine(wa);
	}

	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(' '); }
	public static int Clamp(int val, int max, int min = 0) { return Math.Min(max, Math.Max(min, val)); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt();
		return r;
	 }
}


Measured memory_bytes: 13920
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<list>
#include<set>
using namespace std;
int main(){
int N,M;
int n[1011],m[1011];
int p[1011];
for(int i=0;i<1011;i++){
p[i]=0;
}
int i,j,ans=0;
cin >> N >> M;
for(i=0;i<N;i++){
cin >> n[i];
}
for(i=0;i<M;i++){
cin >> m[i];
}
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(m[i]>=n[j]){
p[j]++;
break;
}
}
}
for(i=0;i<N;i++){
if(p[ans]<p[i])ans=i;
}
cout << ans+1 << endl;
return 0;
}


Measured memory_bytes: 3092