akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

struct job {
	int A, B;
	bool operator < (const job& b) {
		return A == b.A ? B > b.B:A < b.A;
	}
};
job J[100010];
int main()
{
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> J[i].A >> J[i].B;
	}
	J[N].A = mod; J[N].B = -mod;
	sort(J, J + N);
	priority_queue<int> que;
	int j = 0;
	ll ans = 0;
	for (int i = 1; i <= M; i++) {
		while (J[j].A <= i) {
			que.push(J[j++].B);
		}
		if (que.empty()) continue;
		ans += que.top();
		que.pop();
	}
	cout << ans << endl;
}

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

struct node {
	int key;
	struct node *car;
	struct node * cdr;
};

void
record(struct node *r, struct node *p)
{
	if (p->key == r->key)
		return;
	else if (p->key < r->key) {
		if (r->car == NULL)
			r->car = p;
		else
			record(r->car, p);
	} else {
		if (r->cdr == NULL)
			r->cdr = p;
		else
			record(r->cdr, p);
	}
}

int
find(struct node *r, int key)
{
	if (key == r->key)
		return 1;
	else if (key < r->key) {
		if (r->car == NULL)
			return 0;
		else
			return find(r->car, key);
	} else {
		if (r->cdr == NULL)
			return 0;
		else
			return find(r->cdr, key);
	}
}

void
preorder(struct node *a)
{
	if (a == NULL)
		return;

	printf(" %d", a->key);
	preorder(a->car);
	preorder(a->cdr);
}

void
inorder(struct node *a)
{
	if (a == NULL)
		return;

	inorder(a->car);
	printf(" %d", a->key);
	inorder(a->cdr);
}

int
main(void)
{
	int i, n, p;
	struct node *a;

	scanf("%d", &n);

	a = (struct node *)malloc(sizeof(struct node) * n);
	if (a == NULL)
		return 1;

	for (i = p = 0; i < n; i++) {
		char cmd[16];
		int key;

		scanf("%s", cmd);
		if (cmd[0] == 'i') {
			scanf("%d", &key);
			a[p].key = key;
			a[p].car = NULL;
			a[p].cdr = NULL;
			record(a, a + p++);
		} else if (cmd[0] == 'f') {
			scanf("%d", &key);
			printf("%s\n", find(a, key) ? "yes" : "no");
		} else if (cmd[0] == 'p') {
			inorder(a);
			printf("\n");
			preorder(a);
			printf("\n");
		}
	}

	return 0;
}



Measured memory_bytes: 11092
#include<iostream>
using namespace std;
#define NUL -1
const int N_MAX = 45;
int root;
struct Node{
    int parent, left, right;
};
Node tree[N_MAX];
int pre[N_MAX], in[N_MAX];

void reConstruct(int parent, int * preP, int * inP, int n, bool isLeft){
    if(n==0) return;
    int nowRoot = preP[0];
    tree[nowRoot].parent = parent;
    //getchar();
    //cout<<"-- nowRoot: "<<nowRoot<<endl;
    if(parent==NUL){
        root=nowRoot;
    }else if(isLeft){
        tree[parent].left=nowRoot;
    }else{
        tree[parent].right=nowRoot;
    }
    if(n==1)return;
    int flag = 0;
    for(;flag<n;flag++){
        if(inP[flag]==nowRoot) break;
    }
    //cout<<"nowRoot: "<<nowRoot<<" flag: "<<flag<<endl;
    reConstruct(nowRoot, preP+1, inP, flag, true);
    reConstruct(nowRoot, preP+1+flag, inP+1+flag, n-flag-1, false);
}

void post(int id){
    if(id==NUL) return;
    if(tree[id].left==NUL&&tree[id].right==NUL&&id!=root){
        cout<<id<<" ";
        return;
    }
    post(tree[id].left);
    post(tree[id].right);
    if(id==root){
        cout<<id<<endl;
    }else{
        cout<<id<<" ";
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>pre[i];
        tree[i].parent=tree[i].left=tree[i].right=NUL;
    }
    tree[n].parent=tree[n].left=tree[n].right=NUL;
    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    reConstruct(NUL, pre, in, n, true);
    /*//Debugging/
    for(int i=1;i<=n;i++){
        cout<<"node"<<i<<": p: "<<tree[i].parent<<"  l: "<<tree[i].left<<"  r: "<<tree[i].right<<endl;
    }
    ///Debugging*/
    post(root);
    //cout<<"root: "<<root<<endl;
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector <char> slime(n);
  for (int i = 0; i < n; i++) {
    cin >> slime.at(i);
  }
  int ans = 1;
  if (n == 1){
    cout << 1 << endl;
  }
  else {
    for (int i = 0; i < n - 1; i++){
      if (slime.at(i) != slime.at(i + 1)) {
        ans++;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 384
main :: IO ()
main = do
  n <- readLn
  print $ g n

f :: Int -> [(Int,Int)]
f n = [(x, n-x) | x <- [1..((n+1) `div` 2)]]

sod
  :: Int -> Int
sod n
  | q == 0 = r 
  | otherwise = r + sod q
  where
    (q,r) = quotRem n 10

sod2
  :: Int -> Int -> Int
sod2 x y = sod x + sod y

g :: Int -> Int
g = minimum . map (uncurry sod2) . f

Measured memory_bytes: 892
#include<iostream>
using namespace std;
int main(){
  int a;
  int b;
  cin >> a >>  b;
  if(a < b){
    cout << "a < b" << endl;
  }
  else if(a == b){
    cout << "a == b" << endl;
  }
  else if(a > b){
    cout << "a > b" << endl;
  }
}

Measured memory_bytes: 1160
n = int(input())
h = list(map(int, input().split()))

cnt = 0
ret = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    cnt = cnt+1
  else:
    ret = max(cnt,ret)
    cnt = 0
  if i == n-2:
    ret = max(cnt,ret)
print(ret)

Measured memory_bytes: 15560
#include <iostream>
#include <cstring>
using namespace std;
int main(){
	string S, T; cin >> S >> T;
	
	int kotae = 10000000;
	for(int i=0; i<S.size() - T.size() + 1; i++){
		int cnt = 0;
		for(int j=0; j<T.size(); j++){
			if(S[i+j] != T[j]) cnt++;
		}
		kotae = min(cnt, kotae);
	}  	
  
  	cout << kotae << endl;
  
  return 0;
}


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

int main(){
  int N; cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<int> l(N), r(N);
  for(int i = 0; i < N; i++){
    if(i == 0) l[i] = A[i];
    else{
      l[i] = __gcd(A[i], l[i - 1]);
    }
  }
  for(int i = N - 1; i >= 0; i--){
    if(i == N - 1) r[i] = A[i];
    else r[i] = __gcd(r[i + 1], A[i]);
  }
  vector<int> num(N);
  for(int i = 1; i < N - 1; i++){
    num[i] = __gcd(l[i - 1], r[i + 1]);
  }
  num[0] = r[1]; num[N - 1] = l[N - 2];
  cout << *max_element(num.begin(), num.end()) << endl;
}

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

// change maximum
// aよりbが大きかったら、aの値をbの値に置き換えて、trueを返す
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

// dp[i][sum_w]:i-1番目までの品物から重さsum_wを超えないように選んだときの、価値の総和の最大値
long long int dp[110][110000] = {0};

int main()
{
    long long int N, W;
    cin >> N >> W;
    long long int w[110], v[110];
    rep(i, N) cin >> w[i] >> v[i];

    for (long long int i = 0; i < N; i++)
    {
        for (long long int sum_w = 0; sum_w <= W; ++sum_w)
        {
            // i番目の品物を選ぶ場合
            if (sum_w - w[i] >= 0)
            {
                chmax(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]);
            }

            // i番目の品物を選ばない場合
            chmax(dp[i + 1][sum_w], dp[i][sum_w]);
        }
    }

    // for (long long int i = 0; i < N; i++)
    // {
    //     for (long long int sum_w = 0; sum_w <= W; ++sum_w)
    //     {
    //         cout << i << " " << sum_w << " " << dp[i][sum_w] << endl;
    //     }
    // }

    cout << dp[N][W] << endl;
}

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

int main()
{
    int S,h,m,s;
   while(cin>>S)
   {
    h=S/3600;
    m=(S-h*3600)/60;
    s=S-h*3600-m*60;
    printf("%d:%d:%d\n",h,m,s);
   }
    return 0;
}




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

int main(){
    int H,W;
    while(1){
     cin >> H >> W;
     if(H == 0 && W == 0)break;
     for(int s = 0; s < H; s++){
        
        for(int i = 0; i < W; i++){
            if(i%2 == 0){
                if(s%2 == 0){
                    printf("#");
                }
                else{
                    printf(".");
                }
            }
            
            else{
                if(s%2 == 0){
                    printf(".");
                }
                else{
                    printf("#");
            }
           }
        }
       printf("\n");
      }
     printf("\n");
    }
    return 0;
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int a, p;
    cin >> a >> p;
    cout << (a*3+p)/2;
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int remaining_operations;
    cin >> remaining_operations;

    while (b <= a && remaining_operations) {
        b *= 2;
        remaining_operations--;
    }

    while (c <= b && remaining_operations) {
        c *= 2;
        remaining_operations--;
    }

    cout << (c > b && b > a ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
using namespace std;
long long m[100010];
int main()
{
    int u;
    cin>>u;
    for(int p = 0;p < u;p++){
        cin>>m[p];
    }
    int c = 0;
    for(int p = 0;p < u;p++){
            if (m[p] == 0){
                c += 1;
            }
    }
    if (c > 0){
        cout<<0<<"\n";
        return 0;
    }
    long long i = 1;
    for(int p = 0;p < u;p++){
        if (m[p] <= 1000000000000000000 / i){
            i *= m[p];
        }
        else{
            cout<<-1<<"\n";
            return 0;
        }
    }
    cout<<i<<"\n";
}

Measured memory_bytes: 4360
/*
 * atcoder/abc114/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
#include <map>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * N!の約数のうち、約数を75個もつ約数の数を求める問題.
 * 10! = 3628800 = 2^8 * 3^4 * 5^2 * 7*1 を素因数分解できる.
 * よって約数は9 * 5 * 3 * 2 = 270通り
 */
int N, M;
map<int, int> npf;
vector<int> keys;
int dp[100][80];

int rec(int n = 0, int rem = 75) {
  int &cc = dp[n][rem];
  if (~cc) return cc;
  if (n==M) return cc = rem == 1;
  int num = 0;
  for (int i=0; i<=npf[keys[n]]; i++) {
    if (rem % (i+1) != 0) continue;
    num += rec(n + 1, rem / (i+1));
  }
  return cc = num;
}

void solve() {
  cin >> N;
  for (int n=1; n<=N; n++) {
    int a = n;
    for (int pf=2; pf<=97; pf++) {
      while (a % pf == 0) {
        npf[pf]++;
        a /= pf;
      }
    }
  }
  for (auto&& a: npf) keys.push_back(a.first);
  M = keys.size();
  memset(dp, -1, sizeof(dp));
  cout << rec() << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;

}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main(void){
    int i,n,a=0,b=0,c=0,d=0;

    scanf("%d",&n);

    char s[n][4];

    for(i=0;i<n;i++)
        scanf("%s",&s[i]);

    for(i=0;i<n;i++){
        if(strcmp(s[i],"AC")==0) a++;
        if(strcmp(s[i],"WA")==0) b++;
        if(strcmp(s[i],"TLE")==0) c++;
        if(strcmp(s[i],"RE")==0) d++;
    }

    printf("AC x %d\n",a);
    printf("WA x %d\n",b);
    printf("TLE x %d\n",c);
    printf("RE x %d",d);

    return 0;
}

Measured memory_bytes: 2112
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<tuple<string, int, int>> restMap(N);

    for(int i=0;i<N;i++){
        string tmp_str;
        cin >> tmp_str;
        int tmp;
        cin >> tmp;

        get<0>(restMap[i]) = tmp_str;
        get<1>(restMap[i]) = tmp;
        get<2>(restMap[i]) = i+1;
    }

    sort( begin(restMap), end(restMap), [](const auto &x, const auto &y){
        return get<0>( x ) == get<0>( y ) ? get<1>( x ) > get<1>( y ) : get<0>( x ) < get<0>( y );
    });

    for(int i=0;i<N;i++){
        cout << get<2>(restMap[i]) << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main { 
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       long o=0;
     
       int n=sc.nextInt(); 
      int k=sc.nextInt(); 
      int r=sc.nextInt(); 
      int s=sc.nextInt(); 
      int p=sc.nextInt(); 
      String t=sc.next(); 
       boolean[] b=new boolean[n]; //連続になっている
      for(int i=0;i<k;i++){
      	if(t.charAt(i)=='r'){
        	o+=p;
        }else if(t.charAt(i)=='s'){
        	o+=r;
        }else if(t.charAt(i)=='p'){
        	o+=s;
        }
      }
      for(int i=k;i<n;i++){
        if(t.charAt(i)==t.charAt(i-k)&&b[i-k]){	//3bannme
          b[i]=false;
        }else if(t.charAt(i)==t.charAt(i-k)){	//2bannme
          b[i]=true;
          o+=0;
          continue;
        }
        if(t.charAt(i)=='r'){
        	o+=p;
        }else if(t.charAt(i)=='s'){
        	o+=r;
        }else if(t.charAt(i)=='p'){
        	o+=s;
        }
      }
      System.out.println(o);
    }
}

Measured memory_bytes: 27192
n,k,q = [int(i) for i in str(input()).split(' ')]
a = [int(input()) for i in range(q)]

b = [k - q] * n
for i in range(q):
  #b = list(map(lambda x: x - 1, b))
  b[a[i] - 1] += 1

for i in range(n):
  if b[i] > 0:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 10448
N = int(input())
A = list(map(int, input().split()))
from collections import Counter
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    c = Counter(fct)
    return c

def solve(N,A):
    ans = 0
    mod = 10**9+7
    fcts = [0]*10**6
    for a in A:
        c = factorize(a)
        for k,v in c.items():
            fcts[k] = max(fcts[k],v)
    prod = 1
    for i,f in enumerate(fcts):
        if f==0:
            continue
        prod *= pow(i,f)
        prod %= mod
    for a in A:
        ans += prod*pow(a,mod-2,mod)
        ans %= mod
    return ans
print(solve(N,A))

Measured memory_bytes: 60504
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int Max=1e5;
struct node{
    int xi,yi,ci,sum;
}ti[Max+10];
int a[Max+10];
int b[Max+10];
int main()
{
    int A,B,M;
    int Min=0x3f3f3f3f;
    int Min1=0x3f3f3f3f;
    int Min2=0x3f3f3f3f;
    scanf("%d%d%d",&A,&B,&M);
    for(int i=1;i<=A;++i){
        scanf("%d",&a[i]);
        Min1=min(Min1,a[i]);
    }
    for(int i=1;i<=B;++i){
        scanf("%d",&b[i]);
        Min2=min(Min2,b[i]);
    }
    for(int i=1;i<=M;++i){
        scanf("%d%d%d",&ti[i].xi,&ti[i].yi,&ti[i].ci);
        ti[i].sum=a[ti[i].xi]+b[ti[i].yi]-ti[i].ci;
        Min=min(Min,ti[i].sum);
    }
    Min=min(Min,Min1+Min2);
    printf("%d\n",Min);
    return 0;
}


Measured memory_bytes: 2560
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int n;
int a , b , c;
vector < pair < int , int > > v[N];
long long dist1[N];
int root;
int subtree[N];
void dfs1(int node , int parent , long long level , long long dist[] , bool weights){
	dist[node] = level;
	for(auto next : v[node]){
		if(next.first != parent){
			dfs1(next.first , node , level + (weights ? next.second : 1) , dist , weights);
		}
	}
}
void dfs2(int node , int parent){
	subtree[node] = 1;
	for(auto next : v[node]){
		if(next.first != parent){
			dfs2(next.first , node);
			subtree[node] += subtree[next.first];
		}
	}
}
int find(int node , int parent , int val){
	for(auto next : v[node]){
		if(next.first != parent){
			if(subtree[next.first] > val){
				return find(next.first , node , val);
			}
		}
	}
	return node;
}
void centre(){
	dfs2(1 , 0);
	root = find(1 , 0 , n >> 1);
}
int main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		v[i].clear();
	}
	for(int i = 1 ; i < n ; ++i){
		scanf("%d %d %d" , &a , &b , &c);
		v[a].emplace_back(make_pair(b , c));
		v[b].emplace_back(make_pair(a , c));
	}
	centre();
	dfs1(root , 0 , 0 , dist1 , 1);
	/*cout << root << endl;
	for(int i = 1 ; i <= n ; ++i){
		cout << dist1[i] << " ";
	}
	cout << endl;*/
	long long ans = 0;
	long long mnval = 1LL << 60;
	for(int i = 1 ; i <= n ; ++i){
		ans += 2LL * dist1[i];
	}
	bool done = 0;
	for(auto next : v[root]){
		if(subtree[next.first] * 2 == n){
			done = 1;
			mnval = next.second;
		}
	}
	if(!done){
		for(auto next : v[root]){
			mnval = min(mnval , 1LL * next.second);
		}
	}
	ans -= mnval;
	printf("%lld\n" , ans);
}

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

#define ll long long

int main() {
    int al[5];
    int k;
    scanf("%d", &al[0]);
    scanf("%d", &al[1]);
    scanf("%d", &al[2]);
    scanf("%d", &al[3]);
    scanf("%d", &al[4]);
    scanf("%d", &k);

    int max = 0;
    for(int i = 0;i < 5;i++) {
        for(int j = i;j < 5;j++) {
            max = max < al[j] - al[i] ? al[j] - al[i] : max;
        }
    }

    if(max <= k) {
        printf("Yay!\n");
    }else{
        printf(":(\n");
    }
    return 0;
}


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

using namespace std;

const int MAX_N = 1000000;

int cnt1[MAX_N+1],cnt2[MAX_N+1];

int main()
{
    rep(i,MAX_N){
        cnt1[i] = cnt2[i] = 10*MAX_N;
    }
    cnt1[0] = cnt2[0] = 0;
    for(int j=1;;j++){
        int val = j*(j+1)*(j+2)/6;
        if(val > MAX_N){
            break;
        }
        for(int i=0;i+val<=MAX_N;i++){
            cnt1[i+val] = min(cnt1[i+val],cnt1[i]+1);
        }
        if(val%2){
            for(int i=0;i+val<=MAX_N;i++){
                cnt2[i+val] = min(cnt2[i+val],cnt2[i]+1);
            }
        }
    }
    while(1){
        int n;
        cin >> n;
        if(n == 0){
            break;
        }
        cout << cnt1[n] << " " << cnt2[n] << "\n";
    }
}



Measured memory_bytes: 10888
#include <bits/stdc++.h>
#define TAM 3020

using namespace std;

int main(){
	
	string s1, s2;

	getline(cin,s1);
	getline(cin,s2);

	int M[TAM][TAM] = {0};

	for(int i=1; i<=s1.size(); i++){
		for(int j=1; j<=s2.size(); j++){
			if(s1[i-1]==s2[j-1]){
				M[i][j] = M[i-1][j-1]+1;
			} else {
				M[i][j] = max(M[i-1][j],M[i][j-1]);
			}
			//printf("%d ", M[i][j]);
		}
		//printf("\n");
	}

	int i=s1.size();
	int j=s2.size();
	string s="";

	while(i>0 && j>0){
		if(s1[i-1]==s2[j-1]){
			s += s1[i-1];
			i--;
			j--;
		} else if(M[i-1][j]>M[i][j-1]){
			i--;
		} else {
			j--;
		}
	}

	for(i=s.size()-1; i>=0; i--){
		printf("%c", s[i]);
	}
	printf("\n");

	return 0;
}

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

using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;

const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;

#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = ll(b) - 1; i >= (a); i--)
#define TR(X)                                                  \
    ({                                                         \
        if (1) cerr << "TR: " << (#X) << " = " << (X) << endl; \
    })
#define LL(name) \
    ll name;           \
    cin >> name;
#define VL(name, num) \
    vl name(num);           \
    FOR(INPUT_VL_I, 0, num) { cin >> name[INPUT_VL_I]; }

int main() { cin.sync_with_stdio(0);
    LL(N); LL(A); LL(B); LL(C);

    vector<string> ss(N);
    FOR(i, 0, N) cin >> ss[i];

    vl score = {A,B,C};
    vector<char> ans;
    FOR(i, 0, N) {
        ll id1 = ss[i][0] - 'A';
        ll id2 = ss[i][1] - 'A';

        if (score[id1] == 1 && score[id2] == 1) {
            if (i < N-1) {
                string next_s = ss[i+1];
                if (next_s.find(char(id2+'A')) != string::npos) {
                    swap(id1, id2);
                }
            }
        } else if (score[id2] < score[id1]) {
            swap(id1, id2);
        }

        score[id1] ++;
        score[id2] --;

        if (score[id1] < 0 || score[id2] < 0) {
            break;
        }

        ans.pb('A' + id1);
    }

    if (sz(ans) == N) {
        cout << "Yes" << endl;
        for (char c : ans) cout << c << endl;
    } else {
        cout << "No" << endl;
    }
}  // cin.tie(0) bei schnellem Wechseln


Measured memory_bytes: 6692
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    string S;
    cin >> S;
    if(S[0]==S[1] && S[1]==S[2]) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
mod = 10**9 + 7

ans = 1
comb = 1
H = 1
for i in range(1,min(n, k+1)):
	tmp = 1
	comb *= (n-i+1)
	comb %= mod
	comb *= pow(i, mod-2, mod)
	comb %= mod

	tmp *= comb
	tmp %= mod

	H *= n-i
	H %= mod
	H *= pow(i, mod-2, mod)
	H %= mod

	tmp *= H
	tmp %= mod

	ans += tmp
	ans %= mod

print(ans)



Measured memory_bytes: 3064
#include <cmath>
#include <iostream>
#include <string>
using namespace std;
int main() {
  int N;
  double T, A;
  cin >> N >> T >> A;
  double H;
  int res;
  double diff = 1000;
  for (int i = 1; i <= N; ++i) {
    cin >> H;
    double diff_tmp = fabs(T - H * 0.006 - A);
    if (diff_tmp < diff) {
      diff = diff_tmp;
      res = i;
    }
  }
  cout << res << endl;

  return 0;
}


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

//省略形
#define rep(i,n) for(auto i=0; i<n ; ++i)
#define REP(i,a,b) for(auto i=a; i<b; ++i)
#define all(v) (v).begin() , (v).end()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using pii = pair<int , int>;
using pll = pair<long long , long long>;

//よく使う定数
const int INF = 1e9;
const int MOD = 1e9+7;
//逆元
const int INV = 1e9+5;

//UnionFindTree
struct union_find{
  vector<int> data;
  union_find(int size) : data(size , -1) { }

  void merge(int x , int y){
    x = root(x); y = root(y);
    if(x == y) return;
    if(data[y] < data[x]) swap(x , y);
    data[x] += data[y];
    data[y] = x;
    return; 
  }

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

  int root(int x){
    return data[x] < 0 ? x : (data[x] = root(data[x]));
  }

  int size(int x){
    return -data[root(x)];
  }
};

//プロトタイプ宣言
void faster(void);
template <class T>
T get_digent(T);
template <class T>
T POW(T , T);
template <class T>
T modpow(T , T , T);

//メモ
//最大公約数:__gcd　|　最小公倍数:__lcm


int main(){
  int l;
  cin >> l;
  double cube = (double)(l*l*l)/27.0;
  cout << setprecision(10) << cube;
}


























//同期解除
void faster(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}

//桁数取得
template <class T>
T get_digent(auto x){
  string s;
  s = to_string(x);
  ll digent = s.size();
  return digent;
} 

//繰り返し自乗法
template <class T>
T POW(T x, T y){
  if(y==0) return 1;
  if(y%2 == 1){
    ll temp = POW(x,y-1);
    return (temp*x);
  }
  else{
    ll temp = POW(x,y/2);
    return temp*temp;
  }
} 

//繰り返し自乗法(剰余)
template <class T>
T modpow(T x , T y , T mod){
  if(y == 0) return 1;
  if(y%2 == 1){
    ll temp = modpow(x,y-1,mod);
    return temp*x%mod;
  }
  else{
    ll temp = pow_mod(x,y/2,mod);
    return temp*temp%mod;
  }
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#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 <unordered_set>
#include <unordered_map>
using namespace std;

using LL = long long;
const LL MAX_V = 12345 * 2;
const LL INF = 1234567890123456;
struct edge { LL to, cap, rev; };
vector<edge>G[MAX_V];
LL level[MAX_V];
LL iter[MAX_V];
void add_edge(LL from, LL to, LL cap)
{
	G[from].push_back({ to,cap,(LL)G[to].size() });
	G[to].push_back({ from,0,(LL)G[from].size() - 1ll });
}
void bfs(LL s)
{
	memset(level, -1, sizeof(level));
	queue<LL>que;
	level[s] = 0;
	que.push(s);
	while (!que.empty())
	{
		LL v = que.front(); que.pop();
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge &e = G[v][i];
			if (e.cap > 0 && level[e.to] < 0)
			{
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}
LL dfs(LL v, LL t, LL f)
{
	if (v == t)return f;
	for (LL &i = iter[v]; i < G[v].size(); ++i)
	{
		edge & e = G[v][i];
		if (e.cap > 0 && level[v] < level[e.to])
		{
			LL d = dfs(e.to, t, min(f, e.cap));
			if (d > 0)
			{
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
LL max_flow(LL s, LL t)
{
	LL flow = 0;
	for (;;)
	{
		bfs(s);
		if (level[t] < 0)return flow;
		memset(iter, 0, sizeof(iter));
		LL f;
		while ((f = dfs(s, t, INF)) > 0)
		{
			flow += f;
		}
	}
	return flow;
}

LL h, w;
vector<string>vec;
map<pair<int, int>, int>id;
int main(void)
{
	cin >> h >> w;
	for (int i = 0; i < h; ++i)
	{
		string s; cin >> s;
		vec.push_back(s);
	}
	LL sx, sy, tx, ty;
	int nid = 1;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			char c = vec[i][j];
			switch (c)
			{
			case 'S':
				sx = i; sy = j;
				id[{i, j}] = 0;
				break;
			case 'T':
				tx = i; ty = j;
				break;
			case 'o':
				id[{i, j}] = nid;
				++nid;
				break;
			}
		}
	}
	id[{tx, ty}] = nid;
	if (sx == tx || sy == ty)
	{
		cout << -1 << endl;
		return 0;
	}
	for (auto par : id)
	{
		if (par.second == nid)continue;
		auto ind = par.first;
		auto val = par.second;
		if (val != 0)add_edge(val * 2 - 1, val * 2, 1);
		for (int x = 0; x < h; ++x)
		{
			if (ind.first == x)continue;
			if (vec[x][ind.second] == 'o' || vec[x][ind.second] == 'T')
			{
				int from = val * 2;
				int to = id[{x, ind.second}] * 2 - 1;
				if (to < 0)continue;
				add_edge(from, to, 1);
			}
		}
		for (int y = 0; y < w; ++y)
		{
			if (ind.second == y)continue;
			if (vec[ind.first][y] == 'o' || vec[ind.first][y] == 'T')
			{
				int from = val * 2;
				int to = id[{ind.first, y}] * 2 - 1;
				if (to < 0)continue;
				add_edge(from, to, 1);
			}
		}
	}
	LL maybe_answer_but_maybe_not = max_flow(0, nid * 2 - 1);
	//if (nid - 1 < maybe_answer_but_maybe_not)maybe_answer_but_maybe_not = -1;
	cout << maybe_answer_but_maybe_not << endl;
	return 0;
}


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

#define int long long
#define str string
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
#define vint vector<int>
#define vchar vector<char>
#define vstr vector<string>
#define pb(n) push_back(n)

signed main(){
  int A,B,N,M,count=0,count2=0,count3=0;
  str S,W,T;
  int C='A'-'a';
  cin>>S;
  if(S.at(0)=='A')rep(1,S.size()){
    if(S.at(i)=='C'&&i!=1&&i!=S.size()-1)count+=1;
    if(isupper(S.at(i)))count2+=1;
  }
  if(count==1&&count2==1)cout<<"AC"<<endl;
  else cout<<"WA"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

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

  h=min(h,2*q);
  s=min(s,2*h);

  ll ans;
  if(2*s<=d){
    ans=n*s;
  }
  else{
    if(n%2) ans=s+(n-1)*d/2;
    else ans=n*d/2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300;
double dp[N][N][N];
int n;
double f(int a,int b,int c){
 if(a==n) return 0;
 if(dp[a][b][c]!=-1) return dp[a][b][c];
 double ans=1;
 if(b>0) ans+=b*f(a+1,b-1,c)/n;
 if(c>0) ans+=c*f(a,b+1,c-1)/n;
 if(n>a+b+c) ans+=(n-(a+b+c))*f(a,b,c+1)/n;
 ans=ans*n/(n-a);
 return dp[a][b][c]=ans;
}
int main(){
 for(int i=0;i<N;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) dp[i][j][k]=-1;
 cin>>n;
 int a=0,b=0,c=0;
 for(int i=0;i<n;i++) {
  int x;
  cin>>x;
  if(x==1) b++;
  if(x==2) c++;
 }
 cout.precision(15);
 cout<<fixed;
 cout<<f(a,b,c)<<endl;
 return 0;
}

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

string nexts[9] = {
	"BD",
	"ACE",
	"BF",
	"AEG",
	"BDFH",
	"CEI",
	"DH",
	"EGI",
	"FH"
};

bool isok(string s) {
	int cur = 0, len = (int)s.size();
	
	while (cur < len-1) {
		if (nexts[s[cur] - 'A'].find(s.substr(cur + 1, 1)) == s.npos) return 0;
		++cur;
	}
	
	return 1;
}

int main() {
	vector< string > ans;
	
	for (int i=0; i<1000; ++i) {
		string s;
		cin >> s;
		if (isok(s)) ans.push_back(s);
	}
	
	int size = (int)ans.size();
	for (int i=0; i<size; ++i) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 1256
#include <stdio.h>

int main(){
	int N;
	int i=0;
	int count=0;
	scanf("%d",&N);
	while (i < 4){
		if (N%10 == 2) count++;
		N /= 10;
		i++;
	}
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 128
#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 long long ll;
typedef pair<ll, int>Pair;


int main() {
    int K,N;
 	cin >>N>>K;
  	vector<int>num(N);
  	rep(i,N){
    	int p; cin >>p;
      	num[i]=p+1;//期待値×２
    }
  	vector<int> maxsum(N);
  	int sumk=0;
  	rep(i,K){
    	sumk+=num[i];
    }
  	maxsum[K-1]=sumk;
  	for(int i=K;i<N;i++){
    	int memo,next;
      	memo=maxsum[i-1];
      	next=memo-num[i-K]+num[i];
      	maxsum[i]=next;
    }
  	sort(maxsum.begin(),maxsum.end());
  	reverse(maxsum.begin(),maxsum.end());
  	double ans=(double)maxsum[0]/2;
  	cout<<setprecision(12)<<ans<<endl;
}


Measured memory_bytes: 1792
#include <stdio.h>
 
int main()
{
	int h[10000],w[10000],i,j,k,m;
	
	for(i=0;i<10000;i++){
		scanf("%d %d",&h[i],&w[i]);
		if((h[i]==0)&&(w[i]==0)){
			break;
			}
		}
	
	for(j=0;j<i;j++){
		for(k=0;k<h[j];k++){
			if(k%2==0){
				for(m=0;m<w[j];m++){
					if(m%2==0){
						printf("#");
						}
					else{
						printf(".");
						}	
					}
				printf("\n");
				}
			else{
				for(m=0;m<w[j];m++){
					if(m%2==1){
						printf("#");
						}
					else{
						printf(".");
						}	
					}
				printf("\n");
				}
			}
			printf("\n");
		}
	
	return 0;
}
 



Measured memory_bytes: 2100
#include<bits/stdc++.h>
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>());
  long ans = 0;
  for(int i = 0; i < N - 1;i++){
    ans += A[(i + 1)/2];
  }
  cout << ans << endl;
}

Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int main()
{
	SPEED
	int n;
	string s, t;
	cin >> n;
	cin >> s >> t;
	std::vector<char> v;
	for (int i = 0; i < n; ++i)
	{
		v.push_back(s[i]);
		v.push_back(t[i]);
	}
	int N = n+n;
	for (int i = 0; i < N; ++i)
	{
		cout << v[i];
	}
}


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

const int MOD = 1000000007;

int main() {
    int N;
    string S;
    cin >> N >> S;

    vector<long long> cnt(26);
    for (char c : S) {
        cnt[c - 'a']++;
    }

    long long res = 1;
    for (int i = 0; i < 26; i++) {
        if (cnt[i]) {
            res *= (cnt[i] + 1);
            res %= MOD;
        }
    }

    cout << res - 1 << endl;
    return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		ArrayList<String> list = new ArrayList<String>();
		ArrayList<String> listFirst = new ArrayList<String>();
		ArrayList<String> listLast = new ArrayList<String>();
		boolean ng = false;
		
		for (int i = 0; i < N; i++) {
			String w = sc.next();
			if (!ng){
				ng = list.contains(w);				
			}
			list.add(w);
			listFirst.add(w.substring(0,1));
			listLast.add(w.substring(w.length()-1));
		}
		if (ng) {
			System.out.println("No");									
			return;
		}
		for (int i = 1; i < N; i++) {
			String f = listLast.get(i-1);
			String l = listFirst.get(i);
			if (!f.equals(l)) {
				ng = true;
				break;
			}
		}
		if(ng){
			System.out.println("No");						
		} else {
			System.out.println("Yes");						
		}
		
		
		// 入力
		/*
		String S = sc.next();                
		String T = sc.next();                
		
		for (int i = 0; i < S.length(); i++) {
			if (!S.substring(i,i+1).equals(T.substring(i,i+1))) {
				if (S.indexOf(T.substring(i,i+1)) == -1) {
					S = S.replace(S.substring(i,i+1), T.substring(i,i+1));
				} else {
					String s = S.substring(0, S.length());
					StringBuilder sb = new StringBuilder("");
					for (int j = 0; j < s.length(); j++) {
						if (s.substring(j, j+1).equals(S.substring(i, i+1))) {
							sb.append(T.substring(i, i+1));
						} else if (s.substring(j, j+1).equals(T.substring(i, i+1))) {
							sb.append(S.substring(i, i+1));							
						} else {
							sb.append(s.substring(j, j+1)); 
						}
					}
					S = sb.toString();
				}
			}
		}
		if(S.equals(T)){
			System.out.println("Yes");			
		} else {
			System.out.println("No");			
		}
	*/
	}	
}


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


int main()
{
    // 整数の入力
    string N;
    cin >> N;
    unsigned long maxSum = 0;
    for (int i=0;i< N.length();i++){
        maxSum += N[i] - '0';
    }
    maxSum = max(maxSum,(N.length() - 1) * 9 + (N[0] - '1')) ;

    cout << maxSum << endl;
    return 0;
}

Measured memory_bytes: 256
while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    count = 0
    
    for a in range(1, x // 3):
        for b in range(a + 1, x // 2):
            c = x - a - b
            if b < c <= n:
                count += 1

    print(count)


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

long long calc(bitset<30> k, int A[], int B[], int N) {
	long long r = 0;
	for (int i = 0; i < N; i++) {
		bitset<30> orbits = k | bitset<30>(A[i]);
		if (orbits == k) { r += B[i]; }
	}
	return r;
}

int main() {
	int N, K;
	cin >> N >> K;

	int A[100000], B[100000];
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}

	bitset<30> k(K);
	long long ans = calc(k, A, B, N);
	for (int i = 29; i >= 0; i--) {
		if (k[i]) {
			bitset<30> tmp(K);
			tmp[i] = false;
			for (int j = i - 1; j >= 0; j--) {
				tmp[j] = true;
			}
			long long r = calc(tmp, A, B, N);
			ans = max(r, ans);
		}
	}

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


Measured memory_bytes: 1024
#include<iostream>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    int n;cin>>n;
    int a[3];
    a[2]=1<<30;
    rep(i,n) cin>>a[i];
    loop(i,1,1+min(a[0],min(a[1],a[2]))){
        bool ok=true;
        rep(j,n) if(a[j]%i!=0) ok=false;
        if(ok) cout<<i<<endl;
    }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    map<string,int>m;
    map<string,int>::iterator it;

    cin>>n;
    int mx=-1;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;

        m[s]++;
        mx=max(mx,m[s]);
    }
    for(it=m.begin();it!=m.end(); it++)
    {
        if(it->second==mx){
            cout<<it->first<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 27008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << - 1 << endl;}
void unhap() {cout << ":(" << endl;}

int main() {
  string s;
  ll k;
  cin >> s >> k;
  int cnt1 = 0, x = 0;
  while (s.at(x) == '1') {
    cnt1++;
    x++;
    if (x == s.size()) break;
  }
  if (k <= cnt1) cout << 1 << endl;
  else cout << s.at(cnt1) << endl;
}

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

struct Edge {
    int to, id;
};

vector<vector<Edge>> g;
vector<int> ans;

void dfs(int v, int p = -1, int pc = -1) {
    int color = 1;
    rep(i, g[v].size()) {
        int to = g[v][i].to, id = g[v][i].id;
        if(to == p) continue;
        if(color == pc) color++;
        ans[id] = color; color++;
        dfs(to, v, ans[id]);
    }
}

int main() {
    int n;
    cin >> n;
    g.resize(n);
    ans.resize(n - 1);
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back((Edge){b, i});
        g[b].push_back((Edge){a, i});
    }
    
    dfs(0);

    int mx = 0;
    rep(i, n) mx = max(mx, int(g[i].size()));
    cout << mx << endl;
    rep(i, n - 1) cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 10112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))


int main(){
    int h, w;   cin >> h >> w;
    vector<vector<int>> L(h, vector<int>(w, 0)), 
        R(h, vector<int>(w, 0)), D(h, vector<int>(w, 0)), U(h, vector<int>(w, 0)); 

    vector<vector<char>> g(h, vector<char>(w));
    REP(i, h)   REP(j, w)   cin >> g[i][j];

    REP(i, h){
        REP(j, w){
            if(g[i][j]=='#') continue;
            
            if(0<j)
                L[i][j] = L[i][j-1]+1;
            else L[i][j] = 1;
        }
        REPD(j, w){
            if(g[i][j]=='#') continue;
            if(j<w-1)
                R[i][j] = R[i][j+1]+1;
            else R[i][j] = 1;
        }
    }
    REP(j, w){
        REP(i, h){
            if(g[i][j]=='#') continue;
            if(0<i)
                D[i][j] = D[i-1][j]+1;
            else D[i][j] = 1;
        }
        REPD(i, h){
            if(g[i][j]=='#') continue;
            if(i<h-1)
                U[i][j] = U[i+1][j]+1;
            else U[i][j] = 1;
        }
    }
    int ans=0;
    REP(i, h)   REP(j,w) ans = max(ans, L[i][j]+U[i][j]+D[i][j]+R[i][j]-3);
    cout << ans << endl;
}

Measured memory_bytes: 67072
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int num[3],n;
cin>>n;
for(int i=0;i<n;i++){
cin>>num[0]>>num[1]>>num[2];
sort(num,num+3);
  if(num[0]*num[0]+num[1]*num[1]==num[2]*num[2]){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}
 
 
return 0;
}

Measured memory_bytes: 1168
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
	int x,a,b;
	scanf("%d%d%d",&x,&a,&b);
	if(abs(x-a)>=abs(x-b)) cout<<"B";
	else cout<<"A";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,a,b) for (int i = (a); i < (b); i++ )
typedef pair<int,int> P;
typedef long long ll;
const int INF = 100000000;

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

    rep(i,0,3*N) {
        cin >> a[i];
    }

    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());

    ll ans = 0;

    rep(i,0,N) {
        ans += a[2*i+1];
    }
    cout << ans << endl;
}




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

int gcd(int x, int y)
{
  if(y == 0)
    return x;
  return gcd(y, x%y);
}

int main()
{
  int n;
  cin >> n;
  
  int v[n];
  for(auto i = 0; i < n; i++)
    cin >> v[i];
  
  int l[n],r[n];
  for(auto i = 0; i < n; i++)
  {
    if(i == 0)
    {
      l[i] = 0;
      r[i] = 0;
    }
    
    else if(i == 1)
    {
      l[i] = v[i-1];
      r[i] = v[n-1-(i-1)];
    }
    
    else{
      l[i] = gcd(l[i-1],v[i-1]);
      r[i] = gcd(r[i-1],v[n-1-(i-1)]);
    }
      
  }
  
  int max = -1, tmp;
  for(auto i = 0; i < n; i++)
  {
    tmp = gcd(l[i],r[n-i-1]);
    if(tmp > max)
      max = tmp;
  }
  
  cout << max << endl;
  return 0;
  
}

Measured memory_bytes: 1408
#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> ;
const int INF = 1e9;
const int MOD = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    int A = 0,B = 0;
    int AB = 0;
    bool ok = false;
    rep(i,n){
        rep(j,s[i].size()-1){
            if(s[i][j] == 'A' && s[i][j+1] == 'B'){
                ++AB;
            }
        }

        if(s[i][0] == 'B' && s[i].back() == 'A'){
            ++A;++B;
        }else if(s[i][0] == 'B'){
            ++B;ok = true;
        }else if(s[i].back() == 'A'){
            ++A;ok = true;
        }
    }
    if(ok) cout << AB + min(A,B) << endl;
    else cout << AB + (min(A,B)==0 ? 0 : min(A,B)-1) << endl;
    return 0;
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 9;
ll a[N];
vector<int> T[N];
vector<ll> cur;
int ans[N];

void dfs(int u, int par){
  int it = lower_bound(cur.begin(), cur.end(), a[u]) - cur.begin();
  int id;
  int pv;
  id = it;
  if(it == cur.size()){
    cur.push_back(a[u]);
    pv=-1;
  }
  else{
    pv=cur[it];
    cur[it]=a[u];
  }
  ans[u]=(int)cur.size();
  for(auto x : T[u]) if(x != par) dfs(x,u);
  if(pv == -1)
    cur.pop_back();
  else
    cur[id]=pv;
}

int main(){
  fastIO;
  //cur.push_back(0);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i ++ ){
    cin >> a[i];
  }
  int u, v;
  for(int i = 1; i < n; i ++ ){
    cin >> u >> v;
    T[u].push_back(v);
    T[v].push_back(u);
  }
  dfs(1,-1);
  for(int i = 1; i <= n; i ++ )
    cout << ans[i] << "\n";
  return 0;
}


Measured memory_bytes: 28380
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws Exception {
		int n = sc.nextInt();
		int k =sc.nextInt();
		long[]a = input(n);
		long[] dp = new long[n];
		for(int i =1 ; i < n ;i++) {
			long max = Integer.MAX_VALUE ;
			for(int j =1  ; j<=k && i-j>=0;j++ ) {
				long temp = Math.abs(a[i]-a[i-j]) + dp[i-j];
				max = Math.min(temp, max);
			}
			dp[i]=max  ;
		}
		System.out.println(dp[n-1]);
	}
	public static long[] input(int n) throws Exception {

		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextLong();
		}
		return arr;
	}

}


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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<pll> shops;
    for (int i = 0; i < N; i++)
    {
        ll A, B;
        cin >> A >> B;
        shops.emplace_back(A, B);
    }
    sort(shops.begin(), shops.end());
    ll answer = 0;
    ll needsNum = M;
    for (auto shop : shops)
    {
        ll price, num;
        tie(price, num) = shop;
        ll buyNum = min(num, needsNum);
        answer += buyNum * price;
        needsNum -= buyNum;
        if (needsNum == 0)
        {
            break;
        }
    }
    cout << answer << endl;
    return 0;
}


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

dp = [float('inf')] * (N+1)
dp[0] = 0

for n in range(1, N+1):
    power = 1
    while (power <= n):
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 6
    power = 1
    while (power <= n):
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 9

print(dp[N])


Measured memory_bytes: 44880
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
const ll INF = 1e9;
template<class T=ll> using V = vector<T>;
template<class T=ll> using PQ = priority_queue<T>;
template<class T=ll> using PQG = priority_queue<T, V<T>, greater<T>>;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
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 (a>b) {a=b; return 1;} return 0;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

void solve()
{
    IN(n, m);
    vector<vector<ll>> g(n);
    rep(i, m) {
        IN(a, b); --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    queue<ll> s;
    s.push(0);
    vector<bool> checked(n);
    vector<ll> to(n);
    while (!s.empty()) {
        ll p = s.front();
        s.pop();
        for (ll q : g[p]) {
            if (checked[q]) continue;
            checked[q] = true;
            to[q] = p;
            s.push(q);
        }
    }
    cout << "Yes" << endl;
    reps(i, 1, n) {
        cout << to[i]+1 << endl;
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

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

#define ll long long
#define ld long double
#define COIN const int
#define ite iterator
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define REPD(i,n) for((i)=(n)-1;(i)>=0;(i)--)

#define ALL(c) (c).begin(), (c).end()
#define sz(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/
const ll mod=1e9+7;
const ll INF=1e18;
/*****************************************************************************/

using namespace std;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n;
	cin >>n;
	for (int i=0;i<n;i++) cout <<"ACL";
	return 0;
}
/******************************************************************************
******************************************************************************/


Measured memory_bytes: 3568