akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		int N = reader.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = reader.nextInt();
		}
		Arrays.sort(A);
		long ans = 1;
		int mod = 1000_000_007;
		for (int i = N-1; i > 0; i-=2) {
			if (A[i] != i || A[i-1] != i) {
				ans *= 0;
			} else {
				ans *= 2;
				ans %= mod;
			}
		}
		if (N % 2 == 1 && A[0] != 0) {
			ans *= 0;
		}
		System.out.print(ans);
		reader.close();
	}
}





Measured memory_bytes: 50852
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main()
{
	int n;
	ll m;
	vector<ll> a;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		ll atmp;
		cin >> atmp;
		atmp %= m;
		a.push_back(atmp);
	}
	ll sum = 0;
	unordered_map<ll, ll> map;
	map.insert(make_pair(0, 1));
	for (int i = 0; i < n; i++)
	{
		sum = (sum + a[i]) % m;
		if (map.find(sum) != map.end()) //key ga sonzai 
		{
			map[sum] ++;
		}
		else
		{
			map.insert(make_pair(sum, 1));
		}
	}
	ll ans = 0;
	for (auto p : map)
	{
		ans += p.second * (p.second - 1) / 2;
	}

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

Measured memory_bytes: 4468
/*
 * Note: This template uses some c++11 functions , so you have to compile it with c++11 flag.
 *       Example:-   $ g++ -std=c++11 c++Template.cpp
 *
 * Author : Denzil Bernard  / Edgar Monis
 * Handle: 1_mn_RMY / the_king_in_the_north
 *
 */

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
//#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define read(type) readInt<type>()
#define ll long long
typedef pair< ll, ll> PII;
typedef vector<ll> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<ll,ll> MPII;
typedef set<ll> SETI;
typedef multiset<ll> MSETI;

ll SI(){
    ll x;
    cin>>x;
    return x;
}


ll mod(ll a){
	return a<0?-a:a;
}


/********** Main()  function **********/
int main()
{
    ll a = SI();
    string x;
    cin>>x;
    ll num = 0;
    for(auto y:x){
    	if(y=='.')
    		continue;
    	num*=10;
    	num+= y-'0';
    }
    cout<<(a*num)/100;
    // cout<<x;
    
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main 
{
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String f = sc.nextLine();
		boolean ans = false;

		for(int i = 0; i < s.length(); i++)
		{
			if(i <= s.length() - f.length())
			{
				if(s.substring(i, i+f.length()).equals(f))
				{
					ans = true;
					break;
				}
			}
			else
			{
				int l1 = s.length() - i;
				int l = f.length() - l1;
				String comp = s.substring(i) + s.substring(0, l);
				
				if(comp.equals(f))
				{
					ans = true;
					break;
				}
			}
		}
		
		if(ans)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
	}

}



Measured memory_bytes: 26360
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) b.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  ll n;
  cin >> n;
  cout << n*(n-1)/2 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(), T = in.nextInt();
        int cost = Integer.MAX_VALUE;
        for(int i = 0; i < N; i++){
            int c = in.nextInt(), t = in.nextInt();
            if(t <= T){
                cost = Math.min(cost, c);
            }
        }
        if(cost == Integer.MAX_VALUE){
            System.out.println("TLE");
        }
        else{
            System.out.println(cost);
        }
    }
}


Measured memory_bytes: 22868
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[20202],b[20202];
int main()
{
	int n,p;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		a[i]=i*20001;
	for(int i=1;i<=n;i++)
		b[i]=(n-i+1)*20001;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p);
		a[p]+=i;
	}
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	printf("\n");
	for(int i=1;i<=n;i++)
		printf("%d ",b[i]);
	return 0;
}

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

using namespace std;

char s[4][4];

int main()
{
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++) cin >> s[i][j];
	for (int i = 1; i <= 3; i++) cout << s[i][i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#define ll long long
using namespace std;
const int N=1e6+10;
string s1,s2,s;
int n;


int main(){
    cin>>n;
  cin>>s1;
  cin>>s2;
    for(int i=0;i<n;i++){
        s=s+s1[i]+s2[i];
    }
  cout<<s<<endl;

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y)
{
return x>y;
}
int n,k,a[55],s;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<k;i++)s+=a[i];
cout<<s;
return 0;	
} 

Measured memory_bytes: 256
n = int(input())


def prime_factorize_n(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


a_list = prime_factorize_n(n)
# print(a_list)

tmp = 1
used_list = []
for i in range(len(a_list)):
    if a_list[i] not in used_list:
        used_list.append(a_list[i])

    else:
        if tmp == 1:
            tmp = a_list[i]

        else:
            # print(i, tmp)
            if tmp % a_list[i] == 0:
                tmp *= a_list[i]
                if tmp not in used_list:
                    used_list.append(tmp)
                    tmp = 1
            else:
                tmp = a_list[i]

# print(used_list)
print(len(used_list))


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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    station_count = int(input())
    c, s, f = list(), list(), list()

    # HACK: More smarter.
    for _ in range(station_count - 1):
        line = list(map(int, input().split()))
        c.append(line[0])
        s.append(line[1])
        f.append(line[2])

    for i in range(station_count):
        elapsed_time = 0

        for j in range(i, station_count - 1):
            if elapsed_time < s[j]:
                elapsed_time = s[j]
            elif (elapsed_time % f[j]) == 0:
                pass
            else:
                elapsed_time = elapsed_time + f[j] - (elapsed_time % f[j])

            elapsed_time += c[j]

        print(elapsed_time)

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



struct Si{
    int a[6];
    void move(char c) {
    int b;
     if (c=='N'){
         b=a[0];
         a[0]=a[1];
         a[1]=a[5];
         a[5]=a[4];
         a[4]=b;
      }
      if (c=='E'){
         b=a[0];
         a[0]=a[3];
         a[3]=a[5];
         a[5]=a[2];
         a[2]=b;
      }
      if(c=='S'){
         b=a[0];
         a[0]=a[4];
         a[4]=a[5];
         a[5]=a[1];
         a[1]=b;
      }
      if(c=='W'){
         b=a[0];
         a[0]=a[2];
         a[2]=a[5];
         a[5]=a[3];
         a[3]=b;
      }
      if (c=='R'){
         b=a[1];
         a[1]=a[2];
         a[2]=a[4];
         a[4]=a[3];
         a[3]=b;
      }
    }
int up(){return a[0];}
int front(){return a[1];}
int right(){return a[2];}
int left(){return a[3];}
};
bool same(Si k,Si j){
    for(int i=0;i<6;i++) if(k.a[i]!=j.a[i]) return false;
    return true;
}
int main()
{  Si r[2];
     for (int j=0;j<2;j++){
         for(int i=0;i<6;i++){
         cin>>r[j].a[i];
         }
     }
     bool f=false;
     
     for(int i=0;i<4;i++){
         r[1].move('R');
         for(int j=0;j<4;j++){
             r[1].move('N');
             if(same(r[0],r[1])) f=true;
         }
     }
     r[1].move('E');
     for(int j=0;j<4;j++){
         r[1].move('N');
         if(same(r[0],r[1])) f=true;
     }
     r[1].move('W');
     r[1].move('W');
     for(int j=0;j<4;j++){
         r[1].move('N');
         if(same(r[0],r[1])) f=true;
     }
     cout <<(f?"Yes":"No") <<endl;
    
    return 0;
}


Measured memory_bytes: 3100
//abc152_c.cpp
//Sun Jan 19 20:45:41 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int p[n];
	int acc[n];
	for (int i=0;i<n;i++){
		cin >> p[i];
		if (i==0){
			acc[i] = p[i];
		}else {
			acc[i] = min(acc[i-1],p[i]);
		}
	}


	int ans = 0;
	for (int i=0;i<n;i++){
		if (p[i]<=acc[i]){
			ans++;
		}
	}


	cout << ans << endl;
//	printf("%.4f\n",ans);
}

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

int w, h;
int field[60][60];

void dfs(int x, int y) {
    field[x][y] = 0;

    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            int dx = x + i, dy = y + j;
            if (dx < 0 || dx >= h || dy < 0 || dy >= w) continue;
            if (field[dx][dy] == 0) continue;
            dfs(dx, dy);
        }
    }
}

int main() {
    while (1) {
        cin >> w >> h;
        if (w == 0 && h == 0) break;

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> field[i][j];
            }
        }

        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (field[i][j] == 0) continue;
                dfs(i, j);
                cnt++;
            }
        }

        cout << cnt << endl;
    }

    return 0;
}


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

int GCD(int a, int b) {
  if ( a%b==0 ) return b;
  return GCD(b, a%b);
}

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

  int ans = 0;
  for( int i=1; i<=K; ++i ) 
    for( int j=1; j<=K; ++j ) 
      for( int k=1; k<=K; ++k ) {
        ans += GCD(i, GCD(j,k));
      }
  cout << ans << endl;

}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=105;
int B[MAX_N],A[MAX_N][MAX_N];
int n,m,C;
int main()
{
	cin>>n>>m>>C;
	for(int i=1;i<=m;i++)cin>>B[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)cin>>A[i][j];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int ret=C;
		for(int j=1;j<=m;j++)ret+=A[i][j]*B[j];
		if(ret>0)ans++;
	}
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 256
n = int(raw_input())
 
def makeHash(letter):
    if letter == 'A':
        return 1
    elif letter == 'C':
        return 2
    elif letter == 'G':
        return 3
    elif letter == 'T':
        return 4
    return 0
 
dict = {}
for i in range(n):
    command, word = raw_input().split()
    key = 0
    if command == 'insert':
         dict[word] = 1
    elif command == 'find':
        if word in dict: 
            print 'yes'
        else:
            print 'no'


Measured memory_bytes: 63204
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

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

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int main()
{
	#ifndef ONLINE_JUDGE
	freopen(".in.txt", "r", stdin);
	freopen(".out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << setprecision(20);
	ld a, b; cin >> a >> b;
	cout << floor(a * b);

	return 0;
}

Measured memory_bytes: 3808
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
	int n;
	cin>>n;
	vector<int>v(n);
	rep(i,n)cin>>v[i];
	int map[100001];
	int cnt=0,max1=0,max2=0,argmax,rslt1,rslt2;
	rep(i,100001) map[i]=0;
	rep(j,n/2){
		map[v[2*j+1]]+=1;
		if (map[v[2*j+1]]>max1) {max1=map[v[2*j+1]];argmax=v[2*j+1];}
	}
	rep(i,100001) map[i]=0;
	rep(j,n/2){
		map[v[2*j]]+=1;
		if (map[v[2*j]]>max2&&argmax!=v[2*j]) max2=map[v[2*j]];
	}
	rslt1=n-(max2+max1);

max1=0;max2=0;
	rep(i,100001) map[i]=0;
	rep(j,n/2){
		map[v[2*j]]+=1;
		if (map[v[2*j]]>max1) {max1=map[v[2*j]];argmax=v[2*j];}
	}
	rep(i,100001) map[i]=0;
	rep(j,n/2){
		map[v[2*j+1]]+=1;
		if (map[v[2*j+1]]>max2&&argmax!=v[2*j+1]) max2=map[v[2*j+1]];
	}
	rslt2=n-(max2+max1);




	if (rslt1<rslt2) rslt2=rslt1;
	cout<<rslt2<<endl;




	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(void){
        int i,j,k,n,m,l,a[101][101]={},b[101][101]={};
        long long int c[101][101]={};

        scanf("%d %d %d",&n,&m,&l);

        for(i=1; i<=n; i++)
                for(j=1; j<=m; j++)
                        scanf(" %d",&a[i][j]);

        for(i=1; i<=m; i++)
                for(j=1; j<=l; j++)
                        scanf(" %d",&b[i][j]);

        for(i=1; i<=n; i++){
                for(j=1; j<=l; j++){
                        for(k=1; k<=m; k++)
                                c[i][j] += a[i][k] * b[k][j];
                        printf("%lld",c[i][j]);
                        if(j != l) putchar(' ');
                }
                putchar('\n');
        }
        return 0;

}

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

int main() {
  int N,A;
  
  cin >> N >> A;
  
  int X = N % 500;

  if (X<=A) {
    cout << "Yes" << endl;
  }
  else{
    cout << "No" <<endl;
  }
  
}


Measured memory_bytes: 256
function makeOpenCards(str) {
    var cards = str.split(' ');
    return {
        A: parseInt(cards[0]),
        B: parseInt(cards[1])
    };
}
var Record = (function () {
    function Record(name) {
        if (typeof name === "undefined") { name = ''; }
        this.getScore = function () {
            var sum = 0;
            this.cards.forEach(function (card, i) {
                sum += card;
            });
            return sum;
        };
        this.name = name;
        this.cards = [];
    }
    return Record;
})();
(function (input) {
    var inputs = input.replace(/\r/g, '').split("\n"), index = 0, n, i, openCard, a, b;
    while(inputs[index] !== '0') {
        n = parseInt(inputs[index++]);
        a = new Record();
        b = new Record();
        for(i = index; i < n + index; i++) {
            openCard = makeOpenCards(inputs[i]);
            if(openCard.A === openCard.B) {
                a.cards.push(openCard.A);
                b.cards.push(openCard.B);
            } else if(openCard.A > openCard.B) {
                a.cards.push(openCard.A);
                a.cards.push(openCard.B);
            } else {
                b.cards.push(openCard.A);
                b.cards.push(openCard.B);
            }
        }
        console.log(a.getScore() + ' ' + b.getScore());
        index += n;
    }
})(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 11740
#include <iostream>
using namespace std;
int main()
{
	int H,W,r,x,y;
	cin>>W>>H>>x>>y>>r;
	if(x>0&&y>0)
	{
		if((x+r<=W)&&(y+r)<=H)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	else
		cout<<"No\n";
	return 0;
}


Measured memory_bytes: 3108
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
typedef unsigned long long ull;
typedef   signed long long sll;


#define N_MAX 100000
#define M_MAX 100

ull n;
ull h[N_MAX];
ull a, b;

void swap_adj(ull *a, ull *b){
	ull tmp = *b;
	*b = *a;
	*a = tmp;
	return;
}

int comp(const void *a, const void *b){
	if (*(ull*)a > *(ull*)b) {
		return -1;
	} else if (*(ull*)a < *(ull*)b) {
		return +1;
	} else {
		return 0;
	}
}

int ispossible(int x){
	int i;
	int f = 0;
	for (i = 0; i < n; i++) {
		if (h[i] <= x * b) break;
		f += (h[i] - x * b - 1) / a + 1;
	}
	if (f > x) {
		return 0;
	} else {
		return 1;
	}
}

int solve(){
	
	if ((a * 2 + b) & 3) {
		puts("NO");
	} else {
		puts("YES");
	}

	return 0;
}

int main(void){
	int i;

	scanf("%llu%llu%llu", &n, &a, &b);

	solve();

	return 0;
}


Measured memory_bytes: 128
num=[i for i in range(1,14)]
pat=["S","H","C","D"]
pat_num=[]
for i in range(4):
    for j in range(13):
        card=[pat[i],str(num[j])]
        pat_num.append(card)
        
n=int(input())
l= [input().split() for i in range(n)]
pat_num = [x for x in pat_num if x not in l]            
for a in pat_num:
    print(*a)


Measured memory_bytes: 5604
s=input()
a=int(s[0])*10+int(s[1])
b=int(s[2])*10+int(s[3])
if 1<=a<=12 and 1<=b<=12:
    print("AMBIGUOUS")
elif 1<=b<=12:
    print("YYMM")
elif 1<=a<=12:
    print("MMYY")
else:
    print("NA")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

mat G(1e+5, vec(0));//子の方へ向かう有向グラフ
vec depth(1e+5, 0);
void dfs(int v, int k){
    depth[v] = k;
    for(int to : G[v]) dfs(to, k + 1);
}

vector<bool> used(1e+5, false);
void dfs2(int v){
    used[v] = true;
    for(int to : G[v]) if(!used[to]) dfs2(to);
}

int main() {
    cin>>N>>K;
    vec a(N), ord(N);
    ll ans = 0;
    rep(i,N){
        cin>>a[i];
        --a[i];
        if(i == 0) {
            ans += a[i] != 0;
            a[i] = 0;
        }else {
            G[a[i]].push_back(i);
        }
        ord[i] = i;
    }
    dfs(0, 0);
    sort(ALL(ord), [&](int x, int y){
        return depth[x] > depth[y];
    });
    rep(i,N){
        int id = ord[i];
        //cout<<id<<endl;
        if(!used[id]) {
            bool ng = false;
            rep(j, K - 1) {
                id = a[id];
                if(a[id] == 0) {
                    ng = true;
                    break;
                }
            }
            if(ng || a[id] == 0) break;
            ++ans;
            dfs2(id);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 11264
#include <stdio.h>

int main(int argc, const char * argv[]) {
    double r,S,R;    //S:??¢??????R:?????¨
    scanf("%lf",&r);
    
    S=r*r*3.141592653589;
    R=2*r*3.141592653589;
    
    printf("%f %f\n",S,R);
    
    return 0;
}

Measured memory_bytes: 648
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int main() {
  string str; cin >> str;
  int ans = 0, cnt = 0;
  for (int i = 0; i != str.size(); ++i) {
    if (str[i] == 'A' || str[i] == 'C' || str[i] == 'G' || str[i] == 'T') cnt++;
    else cnt = 0;
    ans = max(ans, cnt);
  }
  cout << ans << endl;
  return 0;
}


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

#define LL long long
#define MOD 1000000007

using namespace std;

LL gcd(LL C, LL D) {
	if (C < D) gcd(D, C);

	if (C%D == 0)return D;
	else gcd(D, C%D);
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {
	int N;
	cin >> N;
	vector<pair<int, int> >work(N);

	for (int i = 0; i < N; i++) {
		cin >> work[i].first >> work[i].second;
	}

	sort(work.begin(), work.end(), compare_by_b);

	LL sum = 0;
	for (int i = 0; i < N; i++) {
		sum += work[i].first;
		if (work[i].second < sum) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	cin >> N;

}





Measured memory_bytes: 1792
import itertools
n = int(input())
a = [int(m) for m in input().split()]
a.sort()
acculi = list(itertools.accumulate(a))
sym = -1
for i in range(n - 1):
    if 2 * acculi[i] < a[i + 1]:
        sym = i
print(n - sym - 1)

Measured memory_bytes: 14428
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define ran 111111
int n,q;
vector<int> e[ran];
int vert[ran],query_dis[ran],query_col[ran];
int col[ran];
int dis[ran];

int que[ran],op,cl;
int inq[ran],T;

int main(){
	int m;
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	scanf("%d",&q);
	for(int i=0; i<q; i++)
		scanf("%d%d%d",&vert[i],&query_dis[i],&query_col[i]);
	memset(dis,-1,sizeof(dis));
	while(q--){
		int V = vert[q], D = query_dis[q], C = query_col[q];

		if(dis[V] >= D)continue;

		++T;
		op=cl=0;
		que[op++] = V;
		if(dis[V] == -1)
			col[V] = C;
		dis[V] = D;
		inq[V] = T;

		while(cl<op){
			V = que[cl++];
			D = dis[V];
			if(D == 0)continue;
			--D;
			for(vector<int>::iterator it = e[V].begin(); it!=e[V].end(); it++){
				int y = *it;
				if(inq[y] == T)continue;
				if(dis[y] >= D)continue;
				if(dis[y] == -1)
					col[y] = C;
				dis[y] = D;
				inq[y] = T;
				que[op++] = y;
			}
		}
	}
	for(int i=1; i<=n; i++)
		printf("%d\n",col[i]);
	return 0;
}

Measured memory_bytes: 9720
a,b,c,d = map(int,input().split())
alice = [int(x) for x in range(a,b)]
bob = [int(y) for y in range(c,d)]
s = set()
for i in alice:
	s.add(i)
for j in bob:
	s.add(j)
print((len(alice)+len(bob))-len(s))




Measured memory_bytes: 3064
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        n: usize,
        s: [Bytes; n],
    }
    let mut set = std::collections::BTreeSet::new();
    for s in s {
        set.insert(s);
    }
    println!("{}", set.len());
}


Measured memory_bytes: 23080
from sys import stdin
from math import ceil, floor
n=int(stdin.readline().rstrip())
min_ = n/1.08
max_ = (n+1)/1.08
if float(max_).is_integer():
    if ceil(min_) == floor(max_)-1:
        print(ceil(min_))
    else:
        print(":(")
else:
    if ceil(min_) == floor(max_):
        print(ceil(min_))
    else:
        print(":(")

Measured memory_bytes: 9148
def judge(a,b,c)
  if a == b && b == c && a != 's'
    return a
  else
    return nil
  end
end

while gets
  s = $_.chomp.chars
  res = nil
  0.upto(3) do |i|
    res = judge(s[i], s[i+3], s[i+6])
    break if res
    res = judge(s[3*i], s[3*i+1], s[3*i+2])
    break if res
  end
  if s[4] != 's' and (judge(s[0], s[4], s[8]) or judge(s[2], s[4], s[6]))
    puts s[4]
  elsif res.nil?
    puts 'd'
  else
    puts res
  end
end

Measured memory_bytes: 6096
#include "bits/stdc++.h"
#define _USE_MATH_DEFINES
#include <math.h>
 
using namespace std;
 
using LL = long long;
using VLL = std::vector<LL>;
using VVLL = std::vector<VLL>;
using VVVLL = std::vector<VVLL>;
using LD = long double;
using VLD = std::vector<LD>;
using VVLD = std::vector<VLD>;
using VVVLD = std::vector<VVLD>;
 
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; }

//template<class T=LL> inline vector<T> cinv(LL N){ vector<T> v(N); REP(i, N)cin>>v[i]; return move(v);}
//template<class T=LL> inline vector<T> cinv(LL N){ vector<T> v(N); REP(i, N)cin>>v[i]; return move(v);}
#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) {LL i=0; for(auto (a): v ){   cerr <<i << " : "<<  a << endl; i++;}}
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl
#define cmax(a,b) {if(a<b){a=b;}}
#define cmin(a,b) {if(a>b){a=b;}}
#define EACH(a,A) for(auto a: A)
//#define cmax(a,b) a = (a>b ? a:b)
//#define cmin(a,b) a = (a<b ? a:b) 
//cin,cout高速化のおまじない＋桁数指定
inline VLL cinvll(LL N){
  VLL A(N);
  REP(i,N){
    cin >> A[i];
  }
  return move(A);
}
struct Fast{
	Fast(){
		cin.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
	}
} fast;



void func(){
  string S;
  cin >> S;
  string T = "AKIHABARA";
  string U;


  bool ok = true;
  LL j=0;
  for(LL i=0;i<T.length();++i){
    //cerr << T[i]<< " " << S[j]<< endl;
    if(T[i] ==  S[j]){
      j++;

    }
    else if (T[i]=='A'){
    }
    else{
      ok=false;
    }
  }
  if(j!=S.length()){
     ok=false;
  }
  if(ok){
    cout << "YES";
  }
  else{
    cout << "NO";
  }



} 

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

Measured memory_bytes: 256
//
//  supercon.cpp
//
//
//  Created by Fourier Shuzaei on 2018/06/02.
//

#include "bits/stdc++.h"
using namespace std;
#define ri(a,b,c) for(int a=(b);a<(c);++a)
#define ll long long
#define rll(a,b,c) for(ll a=(b);a<(c);++a)

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

    int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;
  cin>>n>>k;

    cout<<(n+k-3)/(k-1)<<"\n";
}



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.Comparator;
import java.util.PriorityQueue;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmpArray = br.readLine().split(" ");
		
		int a[] = new int[3];
		
		a[0] = Integer.parseInt(tmpArray[0]);
		a[1] = Integer.parseInt(tmpArray[1]);
		a[2] = Integer.parseInt(tmpArray[2]);
		
		Arrays.sort(a);

		int result = 0;
		
		while(!(a[0] == a[1] && a[0] == a[2])){
			if(a[0] <= a[2] - 2){
				a[0] += 2;
			}
			else {
				a[0]++;
				a[1]++;
			}
			
			result++;
			Arrays.sort(a);
		}
		
		System.out.println(result);
	}

}

Measured memory_bytes: 23252
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAX 2010
using namespace std;
int nums[MAX]={0};
int main(){
	int n,x,y;
	scanf("%d %d %d",&n,&x,&y);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int dis= abs(x-i)+abs(y-j)+1;
			dis=min(dis,j-i);
			nums[dis]+=1;
		}
	}
	for(int i=1;i<=n-1;i++){
		printf("%d\n",nums[i]);
	}
	return 0;
}

Measured memory_bytes: 384
#include<iostream>

using namespace std;

int main(){
	int n;
	cin>>n;
	long long int A[n];
	for (int i=0; i<n; i++){
		cin>>A[i];
	}
	long long int sum = 0;
	for (int i=1; i<n; i++){
		if(A[i - 1] > A[i]){
			sum += (A[i - 1] - A[i]);
			A[i] = A[i - 1];
		}
	}
	cout<<sum;
}

Measured memory_bytes: 5196
import math
N, D = map(int, input().split())

X = []
for _ in range(N):
    X.append(list(map(int,input().split())))

def dist(l,m):
    sum = 0
    for i in range(D):
        sum += (X[l][i] - X[m][i])**2
    return math.sqrt(sum)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        #print("{} {}".format(i,j))
        d = dist(i,j)
        if d.is_integer():
            ans += 1

print(ans)

Measured memory_bytes: 38384
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [n,k] <- getIntList
    as <- getIntList
    let ans = (solve k as) VU.! k 
    putStrLn $ if ans == 1 then "First" else "Second"

solve k as = VU.create $ do
    vec <- VUM.replicate (k+1) (0 :: Int)
    forM_ [1..k] $ \i -> do
        forM_ as $ \a -> do
            when (i-a >= 0) $ do
                b <- VUM.read vec (i-a)
                when (b == 0) $ VUM.write vec i 1
    return vec

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int n,a,b; cin>>n>>a>>b;
	cout<<min(a*n,b)<<endl;
	
	return 0;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())
if A+B+C==17:
  if A==5:
    if abs(B-C)==2:
      print("YES")
    else:
      print("NO")
  elif A==7:
    if B==C:
      print("YES")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")

Measured memory_bytes: 3064
if __name__ == '__main__':
	N, Y = map(int, input().split())

	yukichi = Y // 10000

	ans = [-1,-1,-1]

	for i in range(yukichi+1):
		n = N - i
		y = Y - 10000 * i
		if n == 0 and y == 0:
			ans = [i,0,0]
			break
		for p in range(n+1):
			q = n-p
			if 5000 * p + 1000 * q == y:
				ans = [i,p,q]
				break
				break

	print("{} {} {}".format(ans[0],ans[1],ans[2]))

Measured memory_bytes: 3064
C=[[0]*3 for i in range(3)]
D=[[0]*3 for i in range(3)]
for i in range(3):
    d=list(map(int,input().split()))
    C[i][0]=d[0]
    C[i][1]=d[1]
    C[i][2]=d[2]
N=int(input())
for i in range(N):
    b=int(input())
    for s in range(3):
        for t in range(3):
            if(b==C[s][t]):
                D[s][t]=1

ans="No"
for i in range(3):
    c=0
    for j in range(3):
        c+=D[i][j]
    if(c==3):
        ans="Yes"

for i in range(3):
    c=0
    for j in range(3):
        c+=D[j][i]
    if(c==3):
        ans="Yes"

c=0
c=D[0][0]+D[1][1]+D[2][2]
if(c==3):
    ans="Yes"

c=0
c=D[0][2]+D[1][1]+D[2][0]
if(c==3):
    ans="Yes"
print(ans)


Measured memory_bytes: 3064
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef vector<vector<long long> > arr;
int n, m;
char p[1010][1010];
long long K, Mod = 1000000007;
void Make(arr &a, int W, int H){
    int i;
    a.resize(W);
    for(i=0;i<W;i++){
        a[i].resize(H);
    }
}
arr Mul(arr &a, arr &b){
    arr tp;
    Make(tp,2,2);
    int i, j, k;
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            for(k=0;k<2;k++){
                tp[i][j] = (tp[i][j] + a[i][k]*b[k][j])%Mod;
            }
        }
    }
    return tp;
}
int main(){
    int i, cx = 0, cy = 0, j;
    scanf("%d%d%lld",&n,&m,&K);
    for(i=1;i<=n;i++){
        scanf("%s",p[i] + 1);
    }
    for(i=1;i<=n;i++){
        if(p[i][1] == '#' && p[i][m] == '#')cx = 1;
    }
    for(i=1;i<=m;i++){
        if(p[1][i] == '#' && p[n][i] == '#')cy = 1;
    }
    if(cx&&cy){
        printf("1\n");
        return 0;
    }
    if(cy){
        for(i=1;i<=max(n,m);i++){
            for(j=1;j<=max(n,m);j++){
                if(i<j)swap(p[i][j],p[j][i]);
            }
        }
        swap(n,m);
    }
    int c = 0, c1 = 0, c2 = 0;
    for(i=1;i<=n;i++){
        if(p[i][1]=='#' && p[i][m]=='#')c2++;
        for(j=1;j<=m;j++){
            if(j<m && p[i][j]=='#' && p[i][j+1]=='#')c1++;
            if(p[i][j]=='#')c++;
        }
    }
    arr w, R;
    Make(w,2,2);
    Make(R,2,2);
    w[0][0] = c;
    if(c2){
        w[0][1] = Mod-c1, w[1][1] = c2;
    }
    R[0][0]=R[1][1]=1;
    K--;
    while(K){
        if(K%2){
            R = Mul(R, w);
        }
        K/=2;
        w = Mul(w, w);
    }
    printf("%lld\n",(R[0][0]+R[0][1])%Mod);
}

Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int main()
{
	long long i, j, k, A, B, C;

	cin >> A; cin >> B; cin >> C;
	k = A%B; j = k;

	for (i = 0; i <= B; i++) {
		if (j == C) {
			cout << "YES" << endl;
			return 0;
		}

		if (j + k >= B)
			j = j + k - B;
		else
			j += k;
	}

	cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);

	int flag = 0;
	for(int i=1;i<4;i++)
	{
		if((a*b*i)%2 == 1)
		{
			printf("Yes\n");
			return 0;
		}
	}
printf("No\n");


return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int dfs(vector<set<int> > &G, int v, vector<int> &deg, vector<bool> &del){
  if(deg[v] == 1) del[v] = true;
  else return 0;
  deg[v] = 0;
  int num = 1;
  for(const int& u : G[v]){
    G[u].erase(v);
    --deg[u];
    num += dfs(G, u, deg, del);
  }
  return num;
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N,M;cin >> N >> M;
  vector<set<int> >G(N);
  vector<int> deg(N,0);
  vector<bool> del(N,false);
  rep(j,M){
    int x,y;cin >> x >> y;
    --x;--y;
    G[x].insert(y);
    G[y].insert(x);
  }
  rep(i,N) deg[i] = G[i].size();
  int num = 0;
  rep(i,N) num += dfs(G,i,deg,del);

  cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int n;
int main()
{
	cin >> n;
  	cout << a[n - 1];
  	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;

int main()
{
    int K, S;
    if (scanf("%d%d", &K, &S) < 2) return 0;

    int cnt = 0;
    for (int i = 0; i <= K; i++)
    {
        for (int j = 0; j <= K; j++)
        {
            int Z = S - i - j;
            if (0 <= Z && Z <= K) cnt++;
        }
    }

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


Measured memory_bytes: 128
n, m = map(int, tuple(input().split(' ')))
a = [[int(s) for s in input().split(' ')] for _ in range(n)]
b = [int(input()) for i in range(m)]
for i in range(n):
	ci = 0
	for j in range(m): ci += a[i][j] * b[j]
	print(ci)


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


int main()
{
	int H,W;
	cin>>H>>W;
	vector<string> s(H);
	rep(i,H)
	{
		cin>>s[i];
	}
	vector<vector<int>> l(H,vector<int>(W+1));
	vector<vector<int>> r(H,vector<int>(W+1));
	vector<vector<int>> t(H+1,vector<int>(W));
	vector<vector<int>> b(H+1,vector<int>(W));
	rep(i,H)
	{
		l[i][0]=0;
		r[i][0]=0;
		rep(j,W)
		{
			if(s[i][j]=='#')
			{
				l[i][j+1]=0;
			}
			else
			{
				l[i][j+1]=l[i][j]+1;
			}

			if(s[i][W-1-j]=='#')
			{
				r[i][j+1]=0;
			}
			else
			{
				r[i][j+1]=r[i][j]+1;
			}
		}
	}	
	rep(j,W)
	{
		t[0][j]=0;
		b[0][j]=0;
		rep(i,H)
		{
			if(s[i][j]=='#')
			{
				t[i+1][j]=0;
			}
			else
			{
				t[i+1][j]=t[i][j]+1;
			}
			if(s[H-1-i][j]=='#')
			{
				b[i+1][j]=0;
			}
			else
			{
				b[i+1][j]=b[i][j]+1;
			}
		}
	}
	int ans=0;
	rep(i,H)
	{
		rep(j,W)
		{
			ans=max(ans,l[i][j+1]+r[i][W-j]+t[i+1][j]+b[H-i][j]-3);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 73696
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=b-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 200005;
int h,w,a,b;
int n,k;
ll fac[N],inv[N];

inline ll mod_pow(ll x,ll p){
	if(p == 0)return 1;	
	ll y = 1;
	while(p > 1){
		if(p&1)y= y * x % MOD;	
		p/=2;
		x= x * x % MOD;
	}
	return x * y % MOD;
}

ll comb(ll n, ll k){
	ll res = fac[n] * inv[k] % MOD;
	res = res * inv[n-k] % MOD;
	return res;
}

int main(){
	fast_io();
	cin >> h >> w >> a >> b;;
	--h;--w;--a;--b;
	fac[0] = inv[0] = 1;
	cu(i,1,N){
		fac[i] = fac[i-1] * i % MOD;
		inv[i] = mod_pow(fac[i], MOD - 2);
	}
	ll ans = comb(h + w, w);
	fu(i,h - a,h){
		ans -= comb(i + b, b) * comb(h - i + w - b - 1 , w - b - 1) % MOD;
		ans += MOD;
		ans %= MOD;
	}
	cout << ans << '\n';
}


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

int n;
string a, b, c;
int cnt = 0;

int main() {
    cin >> n >> a >> b >> c;
    if( (a==b)&&(b==c) ) {
        cout << "0" << endl;
        return 0;
    }
    for(int i=0; i<n; i++) {
        if((a[i]==b[i])&&(b[i]==c[i]))  continue;
        else if((a[i]!=b[i])&&(b[i]!=c[i])&&(a[i]!=c[i]))
            cnt += 2;
        else cnt += 1;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<algorithm>
#include<list>
#include<cmath>
#include<iomanip>
#include<queue>
#include<functional>
#include<climits>
#include<iterator>
#include<unordered_map>

using namespace std;

const double pi=4*atan(1.0);

int mod=1000000007;

int dfs(int index,int rest,vector<vector<int>>& dp,const vector<pair<int,int>>& Items){
	if(index>dp.size()-1)return 0;
	if(dp[index][rest]>=0)return dp[index][rest];

	int tmp1=dfs(index+1,rest,dp,Items);
	int tmp2=-1;
	if(rest>=Items[index].second)tmp2=dfs(index+1,rest-Items[index].second,dp,Items)+Items[index].first;
	dp[index][rest]=max(tmp1,tmp2);
	return dp[index][rest];
}

int main() {
	int N,W;
	cin>>N>>W;
	vector<pair<int,int>> Items(N);
	for(auto& val:Items){
		cin>>val.first>>val.second;
	}

	vector<vector<int>> dp(N,vector<int>(W+1,-1));

	int ans=dfs(0,W,dp,Items);

	cout<<ans<<endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 6844
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <iomanip>
#include <stdio.h>
#include <bitset>
#include <queue>

constexpr long long INFLL = 1e18;

using namespace std;
using ll = long long;
using P = pair<int, int>;

ll solve(vector<P> p)
{
    int s = p.size();
    for (int i = 0; i < s; i++)
    {
        p.at(i).first = min(s, p.at(i).first);
    }
    priority_queue<int> pq;

    vector<vector<int>> vv(s + 1);
    ll ans = 0;
    for (int i = 0; i < s; i++)
    {
        vv.at(p.at(i).first).push_back(p.at(i).second);
    }
    for (int i = s; i >= 1; i--)
    {
        for (int k : vv.at(i))
        {
            pq.push(k);
        }
        if (pq.size() > 0)
        {
            ans += pq.top();
            // cout << "check" << endl;
            pq.pop();
        }
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while (t > 0)
    {
        int n;
        cin >> n;
        vector<int> k(n);
        vector<P> l, r;

        int left, right;
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> k.at(i) >> left >> right;
            int temp = min(left, right);
            left -= temp;
            right -= temp;
            ans += temp;
            // cout << "a:" << temp << endl;
            if (left == 0)
            {
                // cout << "right:" << i << endl;
                r.emplace_back(n - k.at(i), right);
            }
            else
            {
                // cout << "left:" << i << endl;
                l.emplace_back(k.at(i), left);
            }
        }

        ans += solve(r);
        //cout << ans << endl;
        ans += solve(l);
        cout << ans << endl;

        t--;
    }

    return 0;
}

Measured memory_bytes: 10696
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    #
    up.sort(key=lambda t: t[1], reverse=True)
    down.sort(key=lambda t: t[0]-t[1], reverse=True)
    H = 0
    for h, b in up:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()



Measured memory_bytes: 84900
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
template <class T>
void inputV(vector<T> &x, int n){
  for(int i=0; i<n; i++) cin >> x[i];
}
int gcd(int a, int b){
  if( a == 0 || b == 0 ) return 0;
  int c;
  while( a != 0 ){
    c = a; a = b%a; b = c;
  }
  return b;
}
int main() {

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  bool f = false;
  for(int i=0; i<n; i++){
    cin >> a[i];
    if( a[i] >= k ){
      f = true;
    }
  }
  if (!f) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  int d = a[0];
  for(int i=1; i<n; i++){
    d = gcd(d, a[i]);
  }
  cout << (k%d == 0 ? "POSSIBLE" : "IMPOSSIBLE") << endl;

  return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		int n = s.length();
		StringBuilder sb = new StringBuilder();
		
		sb.append(s);
		
		for(int i = n-1; i >= 0 ;i--) {
			if(sb.charAt(i) == 'x') {
				sb.deleteCharAt(i);
			}
		}
		
		char []c = sb.toString().toCharArray();
		int m = c.length;
		
		for(int i = 0 ; i < m ;i++) {
			if(c[i] != c[m - 1 -i]) {
				System.out.println(-1);
				return;
			}
		}
		
		int []x = new int [m+1];
		int cnt = 0;
		for(int i = 0 ; i < n ;i++) {
			if(s.charAt(i) != 'x') {
				cnt++;
			}
			else {
				x[cnt]++;
			}
		}
		
		int ans = 0;
		
		for(int i = 0 ; i <= m ;i++) {
			ans += Math.abs(x[m-i] - x[i]);
		}
		
		System.out.println(ans/2);
		
		
		
	}
}


Measured memory_bytes: 27912