akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

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; }

#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
//#define vvector(name,typ,m,n)vector<vector<typ> > name(m,vector<typ> (n))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
ll ceil(ll a,ll b){
    return ((a+b-1)/b);
}
const int INF = 2000000000;
//const ll INF64 = 9223372036854775807ll;
const ll INF64 = 9223372036854775ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//mapは、if関数などで覗いただけで構成されるので注意しよう！
//std::vector<vector<int>> g;
int main(){
    int n;std::cin >> n;
    VEC(int,a,n);
    rep(i,n){
        a[i]--;
    }
    int ans=0;
    rep(i,n){
        if(a[i]<i)continue;
        if(a[a[i]]==i)ans++;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int L;
  int R;
  int d;
  cin>>L>>R>>d;
  int count=0;
  for(int i=L;i<=R;i++)
  {
    if((i%d)==0)
      count++;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 3560
N, Y = list(map(int, input().split()))
result = '-1 -1 -1'

for x in range(N + 1):
    for y in range(N + 1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y and z >= 0:
            result = '{} {} {}'.format(x, y, z)
            break

print(result)
        

Measured memory_bytes: 2940
import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp = np.zeros(N,dtype = int)

for i in range(1,N):
    s = max(i-K,0)
    dp[i] = np.min(dp[s:i] + np.abs(h[s:i]-h[i]))

print(dp[N-1])


Measured memory_bytes: 22836
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <string>

#define ll long long
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<double> x(n);
	vector<string> u(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> u[i];
	}
	double total = 0;
	for (int i = 0; i < n; i++) {
		if (u[i] == "JPY") {
			total += x[i];
		}
		else {
			total += 380000 * x[i];
		}
	}
	cout << total;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
 int a,b;
 cin>>a>>b;
 if((a==1&&b==2)||(a==2&&b==1))
    cout<<'3';
 if((a==2&&b==3)||(a==3&&b==2))
    cout<<'1';
 if((a==3&&b==1)||(a==1&&b==3))
    cout<<'2';
 }


Measured memory_bytes: 3632
N,K=map(int,input().split())

A=list(map(int,input().split()))
two=[2**i for i in range(44)][::-1]

sums=[0]
for a in A:
    sums.append(sums[-1]+a)

log=[]

for i in range(N):
    for j in range(i,N+1):
        if sums[j]-sums[i]!=0:
            log.append(sums[j]-sums[i])
log.sort()

ans=0
for t in two:
    count=0
    for item in log:
        if item>=t:
            count+=1
    if count>=K:
        ans+=t
        log=list(filter(lambda x: x>=t, log))
    log=list(map(lambda x: x%t, log))
    

print(ans)

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

L = [0]*n
for i in range(n):
    L[i] = chr(i+ord('a'))
#print(L)_

ans = []
def dfs(A):
    if len(A) == n:
        ans.append(''.join(A))
        return
    for v in L[0:len(set(A))+1]:
        A.append(v)
        dfs(A)
        A.pop()

dfs([])
ans.sort()
for i in range(len(ans)):
    print(ans[i])


Measured memory_bytes: 61020
// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll cnt[50][50];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	str v;
	ll x, ans = 0;
	for(int i = 1; i <= n; i++){
		cin >> v;
		x = 0;
		int rq = 9;
		int flg = 0;
		for(auto c : v){
			if(flg == 1) rq --;
			if(c == '.'){
				flg = 1;
				continue;
			}
			x = 10 * x + (c - '0');
		}
		for(int j = 0; j < rq; j++) x *= 10;

		ll c5 = 0, c2 = 0;

		//cerr << "! " << x << '\n';
		if(x == 0){
			c2 = 18;
			c5 = 18;
			x = 1;
		}
		while(x % 5 == 0) x /= 5, c5 ++;
		while(x % 2 == 0) x /= 2, c2 ++;
		c2 = min(c2, 18ll);
		c2 = min(c2, 18ll);
		//cerr << c2 << ' ' << c5 << '\n';
		for(int i1 = max(0ll, 18 - c2); i1 <= 18; i1 ++)
		for(int i2 = max(0ll, 18 - c5); i2 <= 18; i2 ++)
			ans += cnt[i1][i2];

		cnt[c2][c5] ++;
	}
	cout << ans << '\n';
	return 0;
}


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

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

    double dice = 1.0 / N;

    vector<int> A; //何乗するかの配列
    for(int i = 1; i <= N; i++)
    {
        int tmp = 0;
        int tmp2 = 0;

        if(i < K)
        {
            tmp = i;
            
            while(tmp < K)
            {
                tmp *= 2;
                tmp2++;
            }
            A.push_back(tmp2);
        }
    }

    double ans = 0;
    for(int i = 1; i <= N; i++)
    {
        if(i < K)
        {
            int m = A.at(i - 1);
            
            double tmp = 1;
            for(int j = 0; j < m; j++)
            {
                tmp *= 0.5;
            }
            ans += dice * tmp;
        }
        else
        {
            ans += dice;
        }
    }

    cout << fixed << setprecision(12);
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> P;
int h,w,k;
int m[55][55];
int d[55][55];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(void){
    scanf("%d%d",&h,&w);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            scanf(" %c",&c);
            if(c=='#'){
                m[i][j]=1;
                k++;
            }
            d[i][j]=-1;
        }
    }
    queue<P>bfs;
    bfs.push(P(0,0));
    d[0][0]=0;
    while(!bfs.empty()){
        int x=bfs.front().first,y=bfs.front().second;
        bfs.pop();
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(0<=a&&a<w&&0<=b&&b<h&&m[b][a]==0&&d[b][a]==-1){
                d[b][a]=d[y][x]+1;
                bfs.push(P(a,b));
            }
        }
    }
    if(d[h-1][w-1]==-1)printf("-1\n");
    else printf("%d\n",h*w-k-d[h-1][w-1]-1);
    
}


Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val a = sc.nextInt()
  val b = sc.nextInt()
  val c = sc.nextInt()
  val d = sc.nextInt()
  val e = sc.nextInt()
  val k = sc.nextInt()

  val array = IntArray(5) { 0 }
  array[0] = a
  array[1] = b
  array[2] = c
  array[3] = d
  array[4] = e
  

  val dist = mutableListOf<Int>()
  for (i in 0..3) {
    for (j in i+1..4) {
      val tmp = array[j] - array[i]
      dist.add(tmp)
    }
  }

  val has = dist.any { it > k }
  if (has) {
    println(":(")
    return
  }
  println("Yay!")
}


Measured memory_bytes: 36460
def maxHeapify(i):
    l = 2*i
    r = 2*i+1

    if l<= H and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if  r <= H and a[r]> a[largest]:
        largest = r

    if largest != i:
        a[i],a[largest] = a[largest],a[i]
        maxHeapify(largest)

def buildMaxHeap(a):
    i = H//2 
    while i>=1:
        maxHeapify(i)
        i -= 1
    
    

H = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
buildMaxHeap(a)
del a[0]
print(' ',end = "")
print(*a)




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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var << endl;
#else
#define debug(var)
#endif

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void solve() {
	int n, k; scanf("%d%d", &n, &k);
	int ans = 1;
	for (int i = 0; i < n; ++i) {
		if (ans*2 < ans+k) ans<<=1;
		else ans += k;
	}
	printf("%d", ans);
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
N = int(input())
heights = tuple(map(int, input().split()))

times = [0 for _ in range(N)]
for i in range(N-1):
  if heights[i+1] <= heights[i]:
    times[i+1] = times[i] + 1 
  else:
    times[i+1] = 0

print(max(times))

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

const int maxn = 2e5 + 5;
const long long p = 1e9 + 7;
int n;
int arr[maxn], val[maxn];
long long ans = 1;

int main(){
	scanf("%d\n",&n);
	for(int i=1;i<=2*n;i++){
		char a;
		scanf("%c",&a);
		if(a == 'B') arr[i] = 1;
		else arr[i] = 0;
	}
	int stat = 0;
	for(int i=1;i<=2*n;i++){
		arr[i] ^= stat;
		if(arr[i]) val[i] = 1, stat ^= 1;
		else val[i] = 0, stat ^= 1;
	}
	long long cur = 0;
	for(int i=1;i<=2*n && ans > 0;i++){
		if(val[i] == 0 && cur == 0) ans = 0;
		else if(val[i]) cur ++;
		else ans = (ans * cur) % p, cur --;
	}
	if(cur != 0) ans = 0;
	for(int i=1;i<=n;i++) ans = (ans * i) % p;
	printf("%lld",ans);
	return 0;
} 

Measured memory_bytes: 1792
n=int(input())
a=[]
for i in range(n):
  a.append(sorted(input()))
a.sort()
p=1
q=0
for i in range(n-1):
  if a[i]==a[i+1]:
    p+=1
  else:
    q+=p*(p-1)//2
    p=1
q+=p*(p-1)//2
print(q)

Measured memory_bytes: 24652
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)x.size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int N;
pair<ll,ll> p[300010];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>N;
	rep(i,N)cin>>p[i].sec>>p[i].fir;
	sort(p,p+N);
	reverse(p,p+N);
	ll lo=-1,hi=N+1;
	while(lo+1<hi){
		ll M=(lo+hi)/2;
		priority_queue<ll> Q;
		ll sum=0;
		rep(i,M){
			Q.push(p[i].sec);
			sum+=p[i].sec;
		}
		int ok=0;
		rep(i,N-M+1){
			if(sum<=p[i+M-1].fir*M){
				ok=1;break;
			}
			if(i==N-M)break;
			Q.push(p[i+M].sec);
			sum+=p[i+M].sec;
			sum-=Q.top();
			Q.pop();
		}
		if(ok)lo=M;
		else hi=M;
	}
	cout<<lo<<endl;
}

Measured memory_bytes: 13980
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N)
  {
    cin >> a[i];
  }
  int Alice = 0;
  int Bob = 0;
  sort(a.begin(), a.end(), greater<int>());
  int ret = 0;
  rep(i, N)
  {
    ret += a[i] * (i & 1 ? -1 : 1);
  }
  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long int LL;
int main(){
	LL n,s;
	LL i,j,k;
	LL a,b,c;
	cin>>n>>s;
	if(s==n){
		cout<<n+1<<endl;
		return 0;
	}
	if(s>n){
		cout<<-1<<endl;
		return 0;
	}
	for(i=0,c=0;i<1e6;i++){
		a=i+1;
		if(s<a)break;
		b=n-(s-a);
		if(b%a==0 && s-a<b/a && a<b/a && (c>b/a || c==0))c=b/a;
	}
	for(i=2;i<1e6;i++){
		a=n,b=0;
		while(a>=i){b+=a%i,a/=i;}
		b+=a;
		if(b==s && c>i){c=i;break;}
	}
	if(c!=0)cout<<c<<endl;
	else cout<<-1<<endl;
	return 0;
}
	


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  string s;
  cin >> s;
  
  int state = 0;
  for (int i = 0; i < s.size(); i++){
    if (state == 0){
      if (s[i] == 'C')
        state++;
    }
    else if (state == 1)
      if (s[i] == 'F')
        state++;
  }

  if (state == 2)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
    
  

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if (abs(a-c) <= d) {
        cout << "Yes" << endl;
    } else if (abs(a-b) <= d && abs(b-c) <= d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main(){
  char s[1024];
  fgets(s, 1024, stdin);

  for(int i=0;i<strlen(s);i++)
    if('a' <= s[i] && s[i] <= 'z')
      s[i] += 'A'-'a';

  printf("%s", s);
}

Measured memory_bytes: 0
#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>
#include<limits.h>


#define eps 1e-8
#define PI 3.141592653589793
#define bsize 512

#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define bs 1000000007
const long INF = 1e15 + 5;

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false) ;
    cin.tie(NULL) ;
    cout.tie(NULL) ;
    
    int n, W;
    scanf("%d%d", &n, &W);
    vector<int> weight(n), value(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    
    const int MAX_VALUE = 100 * 1000 + 1; // n * max_value + 1
    vector<long> dp(MAX_VALUE, INF);
    dp[0] = 0;

    int answer = 0;
    for (int i = 0; i < n; i++) 
    {
        for (int j = MAX_VALUE - 1; j >= value[i]; j--) 
        {
            if (dp[j - value[i]] + weight[i] <= W) 
            {
                dp[j] = min(dp[j], dp[j - value[i]] + weight[i]);
                answer = max(answer, j);
            }
        }
    }
    printf("%d\n", answer);

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;

#define PI acos(-1)
typedef long long ll;
#define INF 0x3f3f3f3f
int mod = 1000000007;
int rec[10][10];
int mp[202][202];
int main()
{
	// freopen("in.txt", "r", stdin);
	 int n, m;
	 while (~scanf("%d%d", &n, &m))
	 {
	 	memset(rec, INF, sizeof(rec));
	 	for (int i = 0; i < 10; i++)
	 		for (int j = 0; j < 10; j++)
	 			scanf("%d", rec[i] + j);
	 	for (int k = 0; k < 10; k++)
	 		for (int i = 0; i < 10; i++)
	 			for (int j = 0; j < 10; j++)
	 				if (rec[i][j] > (rec[i][k] + rec[k][j]))
	 				{
	 					rec[i][j] = rec[i][k] + rec[k][j];
	 				}
	 	int ans = 0;
	 	for (int i = 0; i < n; i++)
	 		for (int j = 0; j < m; j++)
	 		{
	 			int x;
	 			scanf("%d", &x);
	 			if (~x)
	 			{
	 				ans += rec[x][1];
	 			}
	 		}
	 	printf("%d\n", ans);
	 }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(rng(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
//const ll INF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
//inline int in() { int x; scanf("%d",&x); return x;}
template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
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; }

int main () {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  sort(a.begin(), a.end());
  uni(a);
  int k = a.size();
  if (k%2 == 1) cout << k << endl;
  else cout << k-1 << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
 
int main(){
	int n,k;
	cin>>n>>k;
	int a[n+5];
	for(int i=1; i<=n; i++) cin>>a[i];
	int dp[n+5][k+5]; //nth element k used
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=1; i<=n; i++){
		int sm=0;
		for(int j=0; j<=k; j++){
			if(j<=a[i]) sm+=dp[i-1][j];
			else {
				sm-=dp[i-1][j-a[i]-1];
				sm+=dp[i-1][j];
			}
			sm %= MOD;
			if(sm < 0) sm+=MOD;
			dp[i][j] = sm;
		}
	}
	cout<<dp[n][k];
}

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

int main() {
  int N;
  cin >> N;
  if (N<1 || N>100){
    return 0;
  }
  bool peach = false;
  bool white = false;
  bool green = false;
  bool yellow = false;
  for(int i=0; i<N; ++i){
    char color;
    cin >> color;
    switch(color){
      case 'P':
        peach = true; break;
      case 'W':
        white = true; break;
      case 'G':
        green = true; break;
      case 'Y':
        yellow = true; break;
    }
  }
  if(peach && white && green && yellow){
    cout << "Four";
  }
  else{
    cout << "Three";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string N;
    cin >> N;
    if ((N[0] == N[1] and N[1] == N[2]) or (N[1] == N[2] and N[2] == N[3])) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
using namespace std;
int n, Time;
int main(){
  cin >> n >> Time;
  int c, t;
  int cost = 1001;
  for(int i = 0; i < n; i++){
    cin >> c >> t;
    if(t <= Time){
      if(c < cost) cost = c;
    }
  }
  if(cost == 1001) cout << "TLE" << endl;
  else cout << cost << endl;
}

Measured memory_bytes: 256
def cmb(n,r,mod):
    x=1
    y=1
    if n/2<r:
        r=n-r
    for i in range(r):
        x*=n-i
        if x>mod:
            x%=mod
        y*=r-i
        if y>mod:
            y%=mod
    val=x*pow(y,mod-2,mod)%mod #pow(y,mod-2,mod)モジュラ逆数
    return val

def bouquet():
    mod=10**9+7
    n,a,b=map(int,input().split(" "))
    ans=int(pow(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))
    print(ans%mod)

bouquet()

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

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

  if(b/a>=c){
    cout << c << endl;
  }else{
    cout <<  b/a<< endl;
  }
  return 0;
}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())
to = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i + 100*j + 50*k == X:
                to += 1
print(to)

Measured memory_bytes: 39536
#include<iostream>
#include <cstdio>
#include<cctype>
#include <algorithm>
#include<string>

using namespace std;

int main(){
	int match, p_taro = 0, p_hana = 0;
	string taro, hana;
	
	cin >> match;
	
	for(int i = 0; i < match; i++){
		cin >> taro >> hana;
		if(taro > hana)
			p_taro += 3;
		else if(taro < hana)
			p_hana += 3;
		else{
			p_taro ++;
			p_hana ++;
		}
	}
	cout << p_taro <<" " << p_hana << endl;
	
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl
int main() {
  int n;
  cin >> n;
  vector<int> L(n);
  rep(i, n) cin >> L[i];
  sort(all(L));
  int maxL = L[n - 1];
  int sum = 0;
  rep(i, n - 1) sum += L[i];
  if(sum > maxL) {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}

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

vector<int> par;
vector<int> RA;
int root(int a){
  if(a==par.at(a)){
    return a;
  }
  else{
    return par.at(a)=root(par.at(a));
  }
}
void UN(int a,int b){
  a=root(a);
  b=root(b);
  if(a==b){
    return;
  }
  else if(RA.at(a)<RA.at(b)){
    par.at(a)=b;
  }
  else{
    par.at(b)=a;
  }
  if(RA.at(a)==RA.at(b)){
    RA.at(a)++;
  }
}



int main() {
  int N,M;
  cin>>N>>M;
  int Z=M;
  vector<vector<int>> p(M,vector<int>(2));
  for(int i=0;i<M;i++){
    cin>>p.at(i).at(0)>>p.at(i).at(1);
    p.at(i).at(0)--;
    p.at(i).at(1)--;
  }
  for(int i=0;i<M;i++){
    par.resize(N);
    RA.resize(N);
    for(int j=0;j<N;j++){
      par.at(j)=j;
      RA.at(j)=0;
    }
    for(int k=0;k<M;k++){
      if(k!=i){
        UN(p.at(k).at(0),p.at(k).at(1));
      }
    }
    if(root(p.at(i).at(0))==root(p.at(i).at(1))){
      Z--;
    }
  }
  cout<<Z<<endl;
    
}

Measured memory_bytes: 256
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<utility>
#include<functional>
#include<cassert>
#include<cmath>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<vint> vvint;
#define PI 3.1415926535;
#define MOD 1000000007;
#define rep(i, n) for(int i=0;i<(n);i++)


int main(void) {
	int a[3];
	for (int i=0; i < 3; i++) {
		cin >> a[i];
	}
	if (a[0] + a[1] + a[2]<=21) {
		cout << "win" << endl;
	}
	else {
		cout << "bust" << endl;
	}
}

Measured memory_bytes: 256
object Main {
  def count_days(years: Int, months: Int, days: Int): Int = {
    val monthsToDays = {
      val m = months - 1
      if (years % 3 == 0) m * 20
      else (m - m / 2) * 20 + (m / 2) * 19
    }
    val yearsToDays = { val y = years - 1; (y - y / 3) * 195 + (y / 3) * 200 }
    666 * 195 + 333 * 200 - yearsToDays - monthsToDays - days + 1
  }
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    var n = sc.nextInt
    for(_ <- 1 to n) {
      var y, m, d = sc.nextInt
      println(count_days(y, m, d))
    }
  }
}

Measured memory_bytes: 45204
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
  int n,f=-1;
  long num;
  cin >> n;
  while(n!=0){
  vector<long> ar;
  f=-1;
  for(int i=0;i<n;i++){
  cin >> num;
    ar.push_back(num);
  }
  sort(ar.begin(),ar.end());
  int i=0;
  while(i<n){
    num=ar[i];
    int j=i+1;
    while(num==ar[j]&&j<n){
      j++;
    }
    if(2*(j-i)>n){
      f=num;
      break;
    }
    i=j;
  }
    if(f==-1) cout<<"NO COLOR"<<endl;
    else cout << f<<endl;
    cin >> n;
  }
}



Measured memory_bytes: 18984
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(), v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 1;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> idx1, idx2;
        for(int i = 0; i < n; i++){
            if(s[i] == 'W'){
                idx1.push_back(i);
            }else{
                idx2.push_back(i);
            }
        }
        int i = 0, j = idx2.size() - 1;
        int ans1 = 0;
        while(i < idx1.size() and j >= 0 and idx1[i] < idx2[j]){
            i++;
            j--;
            ans1++;
        }
        ans1 = min(ans1, n - (int)idx1.size());
        ans1 = min(ans1, n - (int)idx2.size());
        cout << ans1 << '\n';
    }
}

Measured memory_bytes: 37076
#include <bits/stdc++.h>
using namespace std ;
template < class R > inline void Readin( R &K ) {
	K = 0 ; bool F = false ; char C = getchar() ; while( C < '0' or C > '9' ) { if( C == '-' ) F = true ; C = getchar() ; }
	while( C <= '9' and C >= '0' ) K = ( K << 1 ) + ( K << 3 ) + C - '0' , C = getchar() ; if( F ) K = -K ;
}
template < class R > inline void Checkmax( R &A , R B ) {
	if( A < B ) A = B ;
}
template < class R > inline void Checkmin( R &A , R B ) {
	if( A > B ) A = B ;
}
int main() {
	long long S , T = 1e9 ;
	Readin( S ) ;
	return not printf( "%lld 0 %lld %lld 0 %lld\n" , S / T , S / T + (bool)( S % T ) , T , S % T ) ;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, X: "List[int]"):
    if N >= M:
        print(0)
        return
    X.sort()
    dist = []
    for i in range(1, len(X)):
        dist.append(abs(X[i] - X[i - 1]))
    distIndices = [(dist[i], i) for i in range(len(dist))]
    distIndices.sort(reverse=True)
    splitIndex = []
    for i in range(N-1):
        splitIndex.append(distIndices[i][1])
    splitIndex.sort()
    ranges = []
    begin = 0
    for next in splitIndex:
        ranges.append(X[begin:next+1])
        begin = next+1
    ranges.append(X[begin:])
    cost = 0
    for R in ranges:
        if len(R) == 1:
            continue
        cost += R[-1] - R[0]
    print(cost)
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X)


if __name__ == '__main__':
    main()


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

const int N = 2e5+35;
const int INF = 0x3f3f3f3f;

char s[N];
int dp[N], nxt[N], f[30], p[30];

int main() {
    memset(dp, INF, sizeof(dp));
    scanf("%s", s);
    int l = strlen(s);
    for(int i = 0; i < 26; i++) {
        dp[l+i] = f[i] = 0;
        p[i] = l+i;
        nxt[l+i] = -1;
        s[l+i] = i+'a';
    }
    for(int i = l-1; i >= 0; i--) {
        int c = s[i]-'a';
        for(int j = 0; j < 26; j++) {
            if(dp[p[j]]+1 < dp[i]) {
                dp[i] = dp[p[j]]+1;
                nxt[i] = p[j];
                f[c] = dp[i];
            }
        }
        p[c] = i;
    }
    int j = 0;
    for(int i = 0; i < 26; i++)
        if(f[i] < f[j]) j = i;
    int x = p[j];
    while(x != -1) {
        printf("%c", s[x]);
        x = nxt[x];
    }
    return 0;
}


Measured memory_bytes: 2048
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskE {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			char[] s = in.next().toCharArray();
			char[] t = in.next().toCharArray();
			int[][] sumsS = partialSums(s);
			int[][] sumsT = partialSums(t);
			int numQueries = in.nextInt();
			for (int query = 0; query < numQueries; query++) {
				int a = in.nextInt() - 1;
				int b = in.nextInt() - 1;
				int c = in.nextInt() - 1;
				int d = in.nextInt() - 1;
				int is = getInvariant(sumsS, a, b);
				int it = getInvariant(sumsT, c, d);
				out.println(is == it ? "YES" : "NO");
			}
		}

		private int getInvariant(int[][] sums, int l, int r) {
			int na = sums[0][r + 1] - sums[0][l];
			int nb = sums[1][r + 1] - sums[1][l];
			return (na + 2 * nb) % 3;
		}

		private int[][] partialSums(char[] s) {
			int[][] sums = new int[2][s.length + 1];
			for (int i = 0; i < s.length; i++) {
				for (int j = 0; j < 2; j++) {
					sums[j][i + 1] = sums[j][i];
					if (s[i] == (char) (j + 'A')) {
						++sums[j][i + 1];
					}
				}
			}
			return sums;
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}



Measured memory_bytes: 48240
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using bint = boost::multiprecision::cpp_int;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
#define rrepSE(i,s,e) for (int i = (s); i > (e); i--)
#define ssort(v) sort(v.begin(), v.end())
#define gsort(v) sort(v.rbegin(), v.rend())
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }

int main()
{
    int n, k, r, s, p;
    cin >> n >> k;
    vector<int> rsp(3);
    cin >> rsp[0] >> rsp[1] >> rsp[2];
    string t;
    cin >> t;
    vector<int> pnt(n);
    rep(i,n) {
        if (t[i] == 'r') pnt[i] = 2;
        else if (t[i] == 's') pnt[i] = 0;
        else if (t[i] == 'p') pnt[i] = 1;
    }
    auto count = [&](int i) {
        int now = pnt[i], cnt = 0, res = 0;
        for (int id = i; id < n; id += k) {
            if (pnt[id] == now) {
                cnt ++;
            }
            else {
                res += ((cnt + 1) / 2) * rsp[now];
                now = pnt[id];
                cnt = 1;
            }
        }
        res += ((cnt + 1) / 2) * rsp[now];
        return res;
    };
    int ans = 0;
    rep(i,k) {
        ans += count(i);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 896
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int ll;

ll GCD(ll x, ll y)
{
    return !y ? x : GCD(y, x % y);
}

ll LCM(ll x, ll y)
{
    return x * y / GCD(x, y);
}

int main()
{
    ll a, b;
    while (cin >> a >> b)
    {
        cout << GCD(a, b) << ' ' << LCM(a, b) << endl;
    }
    return 0;
}

Measured memory_bytes: 3096
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int min = (int)Math.pow(10, 9);
		int max = 0;
		for(int i = 0; i < n; i++) {
		int a = scanner.nextInt();
		if(a > max) max = a;
		if(a < min) min = a;
		}
		System.out.println(max-min);
	}

}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ull = unsigned long long;

int main(){
    int N = 0;
    cin >> N;
    vector<ull> v;
    for(int i = 0; i < N; ++i){
        ull a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    ull ans = 1;
    int count = 0;
    for(int i = N; i >= 0; --i){
        if(v[i] == v[i-1]){
            ans *= v[i];
            i--;
            count++;
        }
        if(count >= 2) break;
    }
    if(!count) ans = 0;

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


Measured memory_bytes: 1400
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int N=in();
	auto R=vecin(N);
	int num=0;
	REP(i,N){
		auto res = min_element(R.begin()+i,R.end());
		if((R.begin()+i)!=res){
			iter_swap(R.begin()+i,res);
			num++;
		}
	}
	REP(i,N-1){
		cout << R[i] << ' ';
	}
	out(R[N-1]);
	out(num);

	return 0;
}



Measured memory_bytes: 3160
S = input()
n = S.count('N')
w = S.count('W')
s = S.count('S')
e = S.count('E')

ans = 'Yes'
if n > 0 and s == 0 or n == 0 and s > 0:
    ans = 'No'
if w > 0 and e == 0 or w == 0 and e > 0:
    ans = 'No'

print(ans)

Measured memory_bytes: 3064
import java.util.*;
import static java.lang.System.*;
import static java.lang.Math.*;

public class Main {

	Scanner sc = new Scanner(in);
	
	int x, y;
	int extgcd(int a, int b) {
		int d = a;
		if (b != 0) {
			d = extgcd(b, a%b);
			int temp = y;
			y = x - (a/b)*y;
			x = temp;
		} else {
			x = 1; y = 0;
		}
		return d;
	}
	
	void run() {
		while (true) {
			int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
			if (a == 0 && b == 0 && c == 0) break;
			int d = extgcd(a, b);
			x *= c/d;
			y *= c/d;
			int resx = x, resy = y;
			int p = b/d, q = -a/d;
			for (int k = 1; abs(p*(k-1)+x)>abs(p*k+x) || abs(q*(k-1)+y)>abs(q*k+y); k++) {
				if (abs(p*k+x)+abs(q*k+y) < abs(resx)+abs(resy) || (abs(p*k+x)+abs(q*k+y) == abs(resx)+abs(resy) && a*abs(p*k+x)+b*abs(q*k+y) < a*abs(resx)+b*abs(resy))) {
					resx = p*k+x;
					resy = q*k+y;
				}
			}
			for (int k = -1; abs(p*(k+1)+x)>abs(p*k+x) || abs(q*(k+1)+y)>abs(q*k+y); k--) {
				if (abs(p*k+x)+abs(q*k+y) < abs(resx)+abs(resy) || (abs(p*k+x)+abs(q*k+y) == abs(resx)+abs(resy) && a*abs(p*k+x)+b*abs(q*k+y) < a*abs(resx)+b*abs(resy))) {
					resx = p*k+x;
					resy = q*k+y;
				}
			}
			
			
			out.printf("%d %d\n", abs(resx), abs(resy));
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 21276
s = int(input())

numList = [s]
count = 0
ans = 2
while(True):
    nextNum = numList[count] / 2 if numList[count] % 2 == 0 else numList[count] * 3 + 1

    if nextNum in numList:
        print(ans)
        break
    numList.append(nextNum)
    count += 1
    ans += 1


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

int main(void){
    int N,ans;
    cin>>N;
    if(N%1000 == 0)cout<<0<<endl;
    else{
        ans = (N/1000+1)*1000-N;
        cout<<ans<<endl;
    }
    return 0;
}

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

using namespace std;

vector<int> blue;
vector<int> red;
vector<int> redpair;
vector<int> v;
vector<vector<int> > c;
int m = 0;
int n = 0;


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

bool match(int x){
    if(x == -1){
        return 1;
    }
    for(int i = 0;i < n;i++){
        if(c[x][i] == 1 && v[i] == 0){
            v[i] = 1;
            if(match(redpair[i])){
                redpair[i] = x;
                return 1;
            }
        }
    }
    return 0;
}


int main(){

    while(cin >> m >> n){
        if(m == 0 && n == 0){
            break;
        }
        blue.clear();
        red.clear();
        redpair.clear();
        v.clear();
        c.clear();
        for(int i = 0;i < m;i++){
            int tmp;
            cin >> tmp;
            blue.push_back(tmp);
        }
        for(int i = 0;i < n;i++){
            int tmp;
            cin >> tmp;
            red.push_back(tmp);
            redpair.push_back(-1);
            v.push_back(0);
        }
        for(int i = 0;i < m;i++){
            c.push_back(vector<int>());
            for(int j = 0;j < n;j++){
                c[i].push_back(gcd(blue[i],red[j]) != 1);
            }
        }
        int ans = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                v[j] = 0;
            }
            if(match(i)){
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 2156
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c1 = 0;
        int c2 = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            if (a % 4 == 0) {
                c1++; 
            } else if (a % 2 == 0) {
                c2++;
            }
        }

        if (c1 >= n / 2) {
            System.out.println("Yes");
        } else {
            if (c2 == n - 2 * c1) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        sc.close();
    }
}

Measured memory_bytes: 58920
N,M=map(int,input().split())
H=list(map(int,input().split()))
B=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  B[a-1].append(b-1)
  B[b-1].append(a-1)
ans=0
for i in range(N):
  if B[i]==[]:
    ans+=1
  else:
    flag=1
    for b in B[i]:
      if H[b]>=H[i]:
        flag=0;break
    if flag:
      ans+=1
print(ans)
      

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

using namespace std;

char cake[300][300];
int ans[300][300];

int main() {
	int h, w, k; cin >> h >> w >> k;
	for (int i = 0; i < h; ++i)
		for (int j = 0; j < w; ++j)
			cin >> cake[i][j];
	vector<int> cutr;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (cake[i][j] == '#') {
				cutr.push_back(i);
				break;
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < cutr.size(); ++i) {
		int u = (i > 0 ? cutr[i - 1] + 1 : 0);
		int d = (i < cutr.size() - 1 ? cutr[i] : h - 1);
		vector<int> cutl;
		for (int j = u; j <= d; ++j)
			for (int k = 0; k < w; ++k)
				if (cake[j][k] == '#')
					cutl.push_back(k);
		sort(cutl.begin(), cutl.end());
		for (int j = 0; j < cutl.size(); ++j) {
			int l = (j > 0 ? cutl[j - 1] + 1 : 0);
			int r = (j < cutl.size() - 1 ? cutl[j] : w - 1);
			cnt++;
			for (int k = u; k <= d; ++k)
				for (int m = l; m <= r; ++m)
					ans[k][m] = cnt;
		}
	}
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (j) cout << " ";
			cout << ans[i][j];
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1152
// ITP1_4_D: Min, Max and Sum 
#include <stdio.h>
#include <stdlib.h> 
int main() {
	int n; int d, min, max;
	long long sum;
	scanf("%d%d", &n, &d);
	sum = min = max = d;
	while (--n > 0) {
		scanf("%d", &d);
		if (d < min) min = d;
		if (d > max) max = d;
		sum += d; 
	} 
	printf("%d %d %lld\n", min, max, sum);
	return 0;
}
 


Measured memory_bytes: 2104
import java.util.InputMismatchException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try {
			Scanner scan = new Scanner(System.in);
			int sec = scan.nextInt();
			int h = sec / 3600;
			int m = (sec / 60) % 60;
			int s = sec % 60;
			System.out.println(h + ":" + m + ":" + s);
			scan.close();
		} catch (InputMismatchException e) {
			System.out.println("Maybe Inputdata contains some characters");
		}
	}
}

Measured memory_bytes: 17300
n = int(input())
a = list(map(int, input().split()))
p = 10**9 + 7

acmlator = sum(a[1:]) % p
ans = (a[0] * acmlator) % p
if n == 2:
    print(ans)
else:
    for i in range(1, n - 1):
        acmlator = (acmlator - a[i]) % p
        ans = (ans + a[i] * acmlator) % p
    print(ans)


Measured memory_bytes: 31612
#include<stdio.h>
#include<string.h>
int main()
{
    int i;
    char str[100000];
    while(scanf("%s",str)!=EOF)
    {
    for(i=1;i<=strlen(str);i++)
    {
        if(i%2==1)
        {
            printf("%c",str[i-1]);
        }
    }
    }
    return 0;
}


Measured memory_bytes: 256
s=input()
a=s[0]
b=0
ac=1
bc=1
for i in range(1,4):
    if s[i]!=a:
        if s[i]!=b:
            if b==0:
                b=s[i]
            else:
                break
        else:
            bc-=1
    else:
        ac-=1
if ac==0 and bc==0:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 3060
"use strict";
// inputに入力データ全体が入る
const main = (input) => {
  //分割代入,1行目がq,2行目がb,3行目がcに代入される
  const array = input
    .trim()
    .split("")
    .map((e) => Number(e));
  // ここに処理を書く
  let count = 0;
  for (let i = 0; i <= 2; i++) {
    if (array[i] === 1) {
      count++;
    }
  }

  // console.logは標準出力に1行出力します (自動的に最後に改行が入ります)
  console.log(count);
};

// ※この行以降は編集しない (標準入力から一度に読み込みMainを呼び出します)
main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29588
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define sortrev(x)       sort(all(x), greater<int>())
#define debug(x)         cout << '>' << #x << ':' << x << endl;
#define int              long long
#define ld               long double
#define endl "\n";
#define lb lower_bound
#define ub upper_bound
const int mod = 1000000007;
using namespace std;
// const int N = 1e5 + 5; 
// int n;
// int a[N];

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = 1;
// cin >>t;
while(t--){

int n,k;
cin >>n>>k;
vi v;
for(int i = 0; i<n; i++){
	int a;cin >>a;
	v.pb(a);
}
sort(all(v));
int sum = 0;
for(int i = 0; i<k; i++){
	sum+=v[i];
}
cout <<sum <<endl;








}
return 0;
}

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

int main()
{
	int n;
	while(cin >> n){
		int ans = 0;
		for(int i = 1; i < n; i++)
			ans += i * (n - i);
		int sum = n + ans * 6;
		cout << sum << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>
#include <set>
#include <iomanip>

using namespace std;

typedef long long ll;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int c[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++)
      cin >> c[i][j];
  }
  vector<int> v(3);
  v[0]=0; v[1]=1; v[2]=2;
  // repeat 3! times
  int ans = c[0][v[0]]+c[1][v[1]]+c[2][v[2]];
  for(int i=1;i<6;i++){
    next_permutation(v.begin(), v.end());
    if(c[0][v[0]]+c[1][v[1]]+c[2][v[2]] == ans){
      // do nothing
    }else{
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

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

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

s_list = gets_nsp_list
az = ("a".."z").to_a

diff = az - s_list.uniq.sort

if diff.empty?
  puts "None"
else
  puts diff.first
end


Measured memory_bytes: 7164
using System;

public class Test
{
	public static void Main()
	{
		var line = Console.ReadLine().Split(' ');
		int n = int.Parse(line[0]);
		int k = int.Parse(line[1]);
		string s = Console.ReadLine();
		
		string a = "";
		
		for(int i = 0; i < n; i++)
		{
			if(k == i + 1) a += s[i].ToString().ToLower();
			else a += s[i];
		}
		
		Console.WriteLine(a);
	}
}

Measured memory_bytes: 13140