akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
long INF = 2147483647;

int main() {
    int N;
    int W;

    scanf("%d", &N);
    scanf("%d", &W);

    int w[N + 1];
    int v[N + 1];

    int max_v = 0;
    for (int i = 1; i < N + 1; i++) {
        scanf("%d", &w[i]);
        scanf("%d", &v[i]);
        max_v += v[i];
    }

    long DP[N + 1][max_v + 1];
    // initialize
    for (int j = 0; j <= max_v; j++) {
        if(j <= v[1]) {
            DP[1][j] = w[1];
        } else {
            DP[1][j] = INF;
        }
        //printf("DP[1][%d]: %ld\n", j, DP[1][j]);
    }

    for (int i = 2; i < N + 1; i++) {
        for (int j = 0; j <= max_v; j++) {
            if (j - v[i] <= 0) {
                DP[i][j] = (DP[i-1][j] < w[i]) ? DP[i-1][j] : w[i];
            } else {
                DP[i][j] = (DP[i-1][j - v[i]] + w[i] < DP[i-1][j]) ? (DP[i-1][j - v[i]] + w[i]) : (DP[i-1][j]);
            }
            //printf("DP[%d][%d]: %ld\n", i, j, DP[i][j]);
        }
    }

    int ans = 0;
    for (int i = 0; i < max_v + 1; i++) {
        if (DP[N][i] <= W && DP[N][i] != INF) {
            ans = i;
        }
    }

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

    return 0;
}


Measured memory_bytes: 78336
from bisect import bisect_right

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N + 1)
for i in range(1, N + 1):
    a[i] = A[i-1] + a[i-1]

b = [0] * (M + 1)
for i in range(1, M + 1):
    b[i] = B[i-1] + b[i-1]

ans = 0
for i in range(N + 1):
    if a[i] > K:
        break
    ans = max(ans, bisect_right(b, K - a[i]) - 1 + i)

print(ans)

Measured memory_bytes: 118580
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
ll a[maxn], b[maxn];
int main()
{
	ios::sync_with_stdio(false);
	ll n, m, k, ans = 0;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for (int j = 1; j <= m; j++)
	{
		cin >> b[j];
		b[j] += b[j - 1];
	}
	for (ll i = 0; i <= n; i++)
	{
		if (k >= a[i])
		{
			ans = max(ans, upper_bound(b + 1, b + m + 1, k - a[i]) - b - 1 + i);
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 6768
s=input().split()
money,num=int(s[0]),int(s[1])
no_list=input().split()
for i in range(money,100000):
    flag=0
    for money_element in list(str(i)):
        if money_element in no_list:
            flag=1
            break
    if flag==0:
        print(i)
        break












Measured memory_bytes: 2940
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    static void solve(String s1,String s2,int n,int m){
        
        int t[][]=new int[n+1][m+1];
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    t[i][j]=1+t[i-1][j-1];
                }
                
                else{
                    t[i][j]=Math.max(t[i-1][j],t[i][j-1]);
                }
                
            }
        }
        
        
    int a=n;
    int b=m;
    String str="";
    while(a!=0&&b!=0){
        if(s1.charAt(a-1)==s2.charAt(b-1)){
            str+=s1.charAt(a-1);
            a--;
            b--;
        }
        
        else{
            if(t[a-1][b]>t[a][b-1]){
                a--;
            }
            else{
                b--;
            }
            
            
        }
        
    }
        
      
      System.out.println(reverse(str));
        
      
        }
        
  public static String reverse(String str)
	{
		return new StringBuilder(str).reverse().toString();
	}

    
    
    
	public static void main (String[] args) throws java.lang.Exception
	{
	
	Scanner s=new Scanner(System.in);
String s1=s.next();
   String t=s.next();
   
solve(s1,t,s1.length(),t.length());
   
	}
}


Measured memory_bytes: 101580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

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> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9+5;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

vector<int> z_algorighm(string s) {
  vector<int> z(s.size());
  z[0] = s.size();
  int i = 1, j = 0;
  while (i < s.size()) {
    while (i + j < s.size() && s[j] == s[i + j]) j++;
    z[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (k < j && k + z[k] < j) {
      z[i + k] = z[k];
      k++;
    }
    i += k;
    j -= k;
  }
  return z;
}


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

  int n;
  cin >> n;
  string s;
  cin >> s;

  int ans = 0;

  for (int l1 = 0; l1 < s.size() - 1; l1++) {
    auto z = z_algorighm(s.substr(l1));
    for (int i = 1; i < z.size(); i++) {
      chmax(ans, min(z[i], i));
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
    public static final int BIG_NUM  = 2000000000;
    public static final int MOD  = 1000000007;
 
    public static void main(String[] args) {
 
        Scanner scanner = new Scanner(System.in);
        double a = scanner.nextDouble();
        double b = scanner.nextDouble();
        double degree = scanner.nextDouble();
 
        double S = 0.5*a*b*Math.sin(Math.PI*degree/180.0);
        double c = Math.sqrt(a*a+b*b-2*a*b*Math.cos(Math.PI*degree/180.0));
 
        System.out.printf("%.10f\n",S);
        System.out.printf("%.10f\n", a+b+c);
        System.out.printf("%.10f\n", 2*S/a);
    }
}


Measured memory_bytes: 28280
#include<bits/stdc++.h>
using namespace  std;
int main()
{
    long long int n,m,sum=0,temp=0;
    cin>>n>>m;
    long long int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    sort(arr,arr+n,greater<int>());
    temp=sum%(4*m);
    if(temp==0)
    {
    if(arr[m-1]<sum/(4*m) )
    cout<<"No";
    else
    {
        cout<<"Yes";
    }
    }
    else if(temp!=0)
    {
        if(arr[m-1]<=sum/(4*m))
        cout<<"No";
        else
        {
            cout<<"Yes";
        }
        
    }
    
    
}

Measured memory_bytes: 256
from math import sqrt

N=int(input())
XY=[]
for i in range(N):
    x,y=map(int,input().split())
    XY.append([x,y])

distance=0
for i in range(N):
    for j in range(i+1,N):
        distance+=sqrt( pow( (XY[i][0])-(XY[j][0]) ,2 ) + pow(XY[i][1] - XY[j][1],2) )

print(2*distance/N)

Measured memory_bytes: 3064
import sys

S=str(input())

for a in range(len(S)):
    if a%2==0:
        if S[a]=='R' or S[a]=='U' or S[a]=='D':
            continue
    elif a%2==1:
        if S[a]=='L' or S[a]=='U' or S[a]=='D':
            continue
    
    print('No')
    sys.exit()

print('Yes')

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i <= (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
 
int main()
{
	long long N; //ここをintにするとWAになる！！！！！
	cin >> N;
	long long A[N], dA[N];
	long long sum = 0;//Aの和
	long long x = 0;//取った回数
	REP(i,N){
		cin >> A[i];
		sum+=A[i];
	}
	if(sum % (N*(N+1)/2) != 0){
		cout << "NO" << endl;
	}else{
		x = sum/(N*(N+1)/2);
		REP(i,N){
			dA[i] = A[(i+1)%N]-A[i];
			if((x-dA[i])%N != 0 || (x-dA[i])<0){
				cout << "NO" << endl;
				return 0;
			}
		}
		cout << "YES" << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
int dp[10010];
int main() {
  int N,M; cin >> N >> M;
  int A[10];
  int B[10]={0,2,5,5,4,5,6,3,7,6};
  for ( int i = 0; i < M; i++ ) cin >> A[i];
  sort(A,A+M,greater<int>());
  for ( int i = 0; i < M; i++ ) {
    for (int j = 0; j <= N; j++ ) {
      if ( (j-B[A[i]] >= 0 && dp[j-B[A[i]]] >= 1) || B[A[i]] == j ) {
	dp[j] = max(dp[j],dp[j-B[A[i]]]+1);
      }
    }
  }
  //for ( int i= 0; i <= N; i++ ) cout << dp[i] << " ";
  // cout << endl;

  vector<int>cost;
  int num = N;
  for ( int j = dp[N]; j >= 1; j-- ) {
    for ( int i = 0; i < M; i++ ) {
      //cout <<"j " << j << " " << "num " <<  num << " B[A[i]]" << " " <<
      //	B[A[i]] << endl;
      if ( j == 1 ){
	cost.push_back(num);
	break;
      } else {     
      if (num-B[A[i]] >= 0 &&  dp[num] - 1 == dp[num-B[A[i]]] ) {
	cost.push_back(B[A[i]]);
	num -= B[A[i]];
	break;
      }
      }
    }
  }
  // for ( int i = 0; i < cost.size(); i++ ) {
  // cout << cost[i] << " ";
  // }
  //cout << endl;
  vector<char>ans;

  for ( int i = 0; i < cost.size(); i++ ) {
    for ( int j = 0; j < M; j++ ) {
      if ( cost[i] == B[A[j]] ) {
	ans.push_back(A[j]+'0');
	break;
      }
    }
  }
  sort(ans.begin(),ans.end(),greater<char>());
  for ( int i = 0; i < ans.size(); i++ ) cout << ans[i];
  cout << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    cout << (a == b ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
N,T=map(int,input().split(' '))
t=input().split(' ')
X=0
for i in range(len(t)-1):
  if int(t[i+1])-int(t[i])<T:
    X+=int(t[i+1])-int(t[i])
  else:
    X+=T
X+=T
print(X)

Measured memory_bytes: 20856
#include <bits/stdc++.h>
#define LL long long

int read() {
    int x = 0, f = 0, ch;
    while(!isdigit(ch = getchar())) f |= ch == '-';
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

int main() {
    int n = read(), m = read();
    printf("%d", n * (n - 1) / 2 + m * (m - 1) / 2);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
x = list(map(float, input().split()))
y = list(map(float, input().split()))

for p in range(1, 4):
    
    result = 0
    for i in range(n):
        result += pow(abs(x[i] - y[i]), p)
    result = pow(result, 1/p)
    print(result)

result = 0
for i in range(n):
    result = max(result, abs(x[i] - y[i]))
print(result)



Measured memory_bytes: 5664
#include <stdio.h>
int main(void){
    int n;
    int s;
    int S=0;
    int m=100;
    int i=0;
    
    for(;~scanf("%d",&s);){
        i&&s%10&&(m=fmin(m,s));
        i++&&(S+=s);
    }
    
    m>=100&&(S=m);
    printf("%d",S%10?S:S-m);
}


Measured memory_bytes: 2144
s = input() + "R"

rcnt = 0
lcnt = 0
tmp = "R"
ans = []

for c in s:
    if tmp == "R" and c == "R":
        rcnt += 1
    elif tmp == "R" and c == "L":
        tmp = "L"
        lcnt = 1

    elif tmp == "L" and c == "L":
        lcnt += 1

    elif tmp == "L" and c == "R":
        cnt = lcnt + rcnt
        for _ in range(rcnt - 1):
            ans.append(0)
        if (lcnt + rcnt) % 2 == 0:
            ans.append(cnt // 2)
            ans.append(cnt // 2)
        else:
            if rcnt % 2 == 0:
                ans.append(cnt // 2)
                ans.append(cnt // 2 + 1)
            else:
                ans.append(cnt // 2 + 1)
                ans.append(cnt // 2)
        for _ in range(lcnt - 1):
            ans.append(0)
        lcnt = 0
        rcnt = 1
        tmp = "R"
print(*ans)


Measured memory_bytes: 10804
import math

while True:
    n = int(input())
    tot = 0
    ave = 0
    moto = 0
    if n == 0:
        break
    s = list(map(int,input().split()))
    for i in range(n):
        tot += s[i]
    ave = tot/n
    for i in range(n):
        moto += (s[i]-ave)**2
    bunsan = moto/n
    hh = math.sqrt(bunsan)
    print('{:.8f}'.format(hh))
        


Measured memory_bytes: 5704
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const ll inf=1e9;
const int MAX = 510000;
const ll MOD = 998244353;

ll gcd(ll a,ll b){
   if (a%b == 0){
        return(b);
    }
   else{
       return(gcd(b, a%b));
    }
}
ll lcm(ll a,ll b){
   return (a / gcd(a, b))*b;
}
int main(){
  ll n,m;cin>>n>>m;
  string s,t;cin>>s>>t;
  ll ans=lcm(n,m);
  ll a=ans/n,b=ans/m;
  rep(i,0,gcd(n,m)){
    if(s[i*b]!=t[i*a]){
      cout<<-1<<endl;return 0;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3760
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<utility>
#include<algorithm>
#include<functional>
#include<deque>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<iomanip>
using namespace std;

int main(){
   int d, n;
   cin >> d >> n;
   switch (d){
      case 0: if (n == 100) cout << 101 << endl; else cout << n << endl; break;
      case 1: if (n == 100) cout << 101*100 << endl; else cout << n * 100 << endl; break;
      case 2: if (n == 100) cout << 101*100*100 << endl; else cout << n * 10000 << endl;
   }
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<set>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<iomanip>
#include<cmath>
#include<stack>
#define endl '\n'
#define Bedoazim ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const long long mod = 1e9 + 7, N = 1e3 + 5;
long long fact[N], inv[N];

long long ncr(long long n, long long r) {

	return ((fact[n] * inv[n - r]) % mod * inv[r]) % mod;

}


int fastpower(int base, int power) {

	if (power == 0)
		return 1;

	long long halfpower = fastpower(base, power / 2) % mod;

	long long ret = (halfpower * halfpower) % mod;

	if (power % 2) {

		ret = (ret * base) % mod;
	}
	return ret;


}



void pre() {

	fact[0] = 1;

	inv[0] = 1;

	for (long long i = 1; i < N; i++) {

		fact[i] = ((i)*fact[i - 1]) % mod;

		inv[i] = fastpower(fact[i], mod - 2) % mod;

	}

}


int main() {

	Bedoazim

		pre();

	long long n, m;

	cin >> n >> m;


	cout << ncr(n, 2) + ncr(m, 2);




}

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

#define int		long long

using namespace std;

int ans=1000,yen=0,n,j;
bool ok=true;

void anss(vector<int> v){

	for(int i=j;i<n;i++){
		if(v[i]<v[i+1]){
			yen=ans/v[i];
			ans%=v[i];
			ok=false;
			j=i;
			break;
		}
	}
}

void yenn(vector<int> v){
	
	for(int i=j;i<n;i++){
		if(i==n-1){
			ans+=(v[i]*yen);
			yen=0;
		}

		if(v[i]>v[i+1]){
			ans+=(yen*v[i]);
			yen=0;
			ok=true;
			j=i;
			break;
		} 
	}
}
void solve()
{
	int mn=INT_MAX,mx=INT_MIN;
	cin>>n;
	std::vector<int> v(n);
	for(int i =0;i<n;i++)
		cin >> v[i];
	for(int i =0;i<n;i++){
		if(ok){
			anss(v);
		}
		else
			yenn(v); 
	}
	cout<<ans<<endl;
}

int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	//int t;cin >> t;while(t--)
		solve();;
	
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n-1;i>=0;i--)
#define Pool(i, m, n) for(ll i=n-1;i>=m;i--)
#define MAX 999999999ll
#define MIN -999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(x) cout<<x<<endl
#define Gput(a,b) G[a].push_back(b)
int main() {
  cout << fixed << setprecision(16);
  ll n,m;
  cin>>n>>m;
  Graph G(n);
  loop(i,m){
    ll a,b;
    cin>>a>>b;
    Gput(a-1,b-1);
    Gput(b-1,a-1);
  }
  vec v(n);
  loop(i,n){
    v[i]=i;
  }
  loop(i,n){
    sort(all(G[i]));
  }
  ll ans=0;
  bool z=true;
  do {
    z=true;
    loop(i,n-1){
      if(!(binary_search(all(G[v[i]]), v[i+1]))){
        z=false;
      }
    }
    if(z)ans++;
  } while (next_permutation(v.begin()+1, v.end()));
  
  
  putout(ans);
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N,K;
    N = sc.nextInt();
    K = sc.nextInt();
    int ans = 1000000007;
    int tmp;
    Integer x[] = new Integer[N];
    for(int i=0; i<N; i++) x[i] = sc.nextInt();
    for(int i=0; i<N-K+1; i++){
      int a = Math.abs(x[i]) + Math.abs(x[i+K-1] - x[i]);
      int b = Math.abs(x[i+K-1]) + Math.abs(x[i+K-1] - x[i]);
      tmp = Math.min(a,b);
      ans = Math.min(ans, tmp);
    }
    System.out.println(ans);
  }
  
  public static int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
  }
}

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

struct UnionFind
{
  // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
  vector<int> par;
  // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
  vector<int> sizes;

  UnionFind(int n) : par(n), sizes(n, 1) {
    // 最初は全てのデータiがグループiに存在するものとして初期化
    rep(i,n) par[i] = i;
  }

  // データxが属する木の根を得る
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // データの根ノードを得る
    x = find(x);
    y = find(y);

    // 既に同じ木に属しているならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるように連結する
    par[y] = x;
    sizes[x] += sizes[y];
    // sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
  }

  // 2つのデータx, yが属する木が同じならtrueを返す
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // データxが含まれる木の大きさを返す
  int size(int x) {
    return sizes[find(x)];
  }
};

int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  UnionFind un = UnionFind(n);
  vector<int> frbr(n, 0);

  rep(i, m)
  {
    int a, b;
    cin >> a >> b;
    a--; b--;
    frbr[a]++;
    frbr[b]++;
    un.unite(a, b);
  }
  rep(i, k)
  {
    int c, d;
    cin >> c >> d;
    c--; d--;
    if (un.same(c, d))
    {
      frbr[c]++;
      frbr[d]++;
    }
  }
  cout << un.size(0) - frbr[0] - 1;
  for (int i=1; i<n; i++)
  {
    printf(" %d", un.size(i) - frbr[i] - 1);
  }
  cout << endl;
}

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

int main(){
	int N;
	cin>>N;
	
	int p[5000];
	for(int i=0;i<N;i++){
		cin>>p[i];
	}
	
	int min_sum=20000;

	for(int I=0;I<=p[0];I++){
		int q[5000];
		for(int i=0;i<N;i++){
			q[i]=p[i];
		}
		
		int sum=I;
		q[0]-=I;
			
		for(int i=0;i<=N-2;i++){
			if(q[i]<=0)
				continue;
		
			sum+=q[i]*2;
			q[i+1]-=q[i];
		}

		if(q[N-1]>0){
			sum+=q[N-1];
		}
		
		min_sum=min(min_sum,sum);
	}

	cout<<min_sum<<endl;
				
	return 0;
}
	

Measured memory_bytes: 3136
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
const int MAX = 1e5 + 5;
const int Mod = 1e9 + 7;
#define PP pair<int, P>

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n)
        cin >> a[i];
    sort(a.begin(), a.end());
    int i = 0;
    int l = inf, r = 0;
    while(i < n)
    {
        i++;
        while(i < n && a[i-1] == a[i])
            i++;
        if(i * 2 == n)
        {
            l = min(a[i-1], l);
            r = max(a[i], r);
        }
    }
    cout << max(0, r-l) << endl;
    return 0;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define rep(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define rrep(i, b, a) for(int (i) = (b); (i) > (a); (i)--)
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, pair<int, int>> iii;

int arr[200'005];

int main() {
	FASTIO;
	int n; cin >> n;
	int ans;
	rep(i, 0, n) {
		int a; cin >> a;
		if (i == 0) ans = a;
		else ans ^= a;
		arr[i] = a;
	}

	rep(i, 0, n) {
		cout << (ans ^ arr[i]) << " ";
	}
	return 0;
}




Measured memory_bytes: 4292
/*
 _____ _             _              _           _ 
|_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|                                                

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll,ll>
#define msi         map<string,ll>
#define mis         map<ll, string>
#define rep(i,a,b)    for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) 	for(auto& a : x)
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define max(a,b)	(a>b?a:b)
#define min(a,b)	(a<b?a:b)

/*	For Debugging	*/
#define DEBUG 		cerr<<"\n>>>I'm Here<<<\n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace __gnu_pbds;
using namespace std;
#define PI 3.141592653589793
#define N  1000005
ll a[N];
void solve()
{
	ll n;
	cin>>n;
	rep(i,0,n+1)
	{
		a[i]=i;
		if(i%3==0 || i%5==0)
			a[i]=0;
	}
	rep(i,1,n+1)
	a[i]+=a[i-1];
	cout<<a[n]<<endl;
	return;
}
int main()
{
	FAST
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	TIME
	return 0;
}

Measured memory_bytes: 11524
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef long long LL;
typedef pair<LL, LL> P;
 
int main() {
    LL a, c;
    LL b;
    cin >> a >> b >> c;
 
    P m[100005];
    P q[1010];
    vector<LL>st;
 
    for (LL i = 0;i < a;i++)cin >> m[i].first >> m[i].second;
    
    for (LL i = 0;i < c;i++) {
        LL d;
        cin >> d;
        q[i] = m[d - 1];
    }
 
    for (LL i = 0;i < a - 1;i++) {
        if (m[i].second == 1 && m[i + 1].second == 2)st.push_back((m[i].first + m[i+1].first) / 2);
    }
 
 
    for (LL i = 0;i < c;i++) {
 
        if (q[i].second == 1) {
 
            long long e = q[i].first+b;
 
            for (int j = 0;j < st.size();j++) {
 
                if (q[i].first < st[j]) {
                    if (e>= st[j])e = st[j];
                }
 
            }
            cout << e << endl;
        }
 
        else {
 
            long long e=q[i].first-b;
 
            LL f = st.size();
            for (LL j = f - 1;j > -1;j--) {
 
                if (q[i].first > st[j]) {
                    if (e <= st[j])e = st[j];
                }
                 
            }
            cout << e << endl;
        }
        
    }
   
    return 0;
}

Measured memory_bytes: 4720
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
  int A, B, H, M;
  cin >> A >> B >> H >> M;
  
  long double h_angle, m_angle;
  
  h_angle = 360.0 * (long double)H / 12.0 + 30.0 * (long double)M / 60.0;
  m_angle = 360.0 * (long double)M / 60.0;
  
  long double angle;
  if(h_angle > m_angle) {
    angle = h_angle - m_angle;
  }
  else {
    angle = m_angle - h_angle;
  }
  if(angle > 180.0) {
    angle = 360.0 - angle;
  }
  
  long double unit = 2.0 * asin(1.0) / 180.0;
  
  long double ans;
  ans = (long double)(A * A + B * B) - 2.0 * (long double)(A * B) * cos(angle*unit);
  
  cout << fixed << setprecision(20) << sqrt(ans) << endl;
}

Measured memory_bytes: 4168
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll a,b,c,d,n,maxi=0,f=0,mini=INF,sum=0;
    cin>>n;
    ll la=0,lb=0,lc=0;
    rep(i,n){
        cin>>a>>b>>c;
        if(a-la>=abs(b-lb)+abs(c-lc)&&(a-la)%2==(abs(b-lb)+abs(c-lc))%2){

        }else{
            f=1;
        }
        la=a;lb=b;lc=c;
    }
    if(f==1) No;
    else Yes;
    
    return 0;
}


Measured memory_bytes: 3644
/// @file

#include <algorithm>
#include <iostream>
#include <string>

namespace {

bool run(std::istream& is, std::ostream& os);
}  // unnamed namespace

/// @brief エントリポイント
#ifdef _TEST
static int run()
#else
int main()
#endif
{
  try {
    if (run(std::cin, std::cout) == false) {
      std::cerr << "main funciton error.\n";
      return EXIT_FAILURE;
    }
  } catch (const std::exception& e) {
    std::cerr << "catch exception\n";
    std::cerr << e.what() << "\n";
    return EXIT_FAILURE;
  }

  return EXIT_SUCCESS;
}

namespace {

/// @brief 実行処理
bool run(std::istream& is, std::ostream& os)
{
  std::string s;
  is >> s;

  if (s.length() == 3) std::reverse(s.begin(), s.end());

  os << s << "\n";

  return true;
}
}  // unnamed namespace


Measured memory_bytes: 888
#!/usr/bin/env python3
#ABC132 D
import sys
sys.setrecursionlimit(1000000)
from collections import deque

inf = 10**9+7
N,K = map(int,input().split())

fact = [1]*10000
for i in range(1,10000):
    fact[i] = fact[i-1]*i

for i in range(1,K+1):
    if N - K + 1 < i:
        print(0)
    else:
        ans = (fact[N-K+1]//fact[i]//fact[N-K-i+1])
        ans *= (fact[K-1]//fact[i-1]//fact[K-i])
        print(ans%inf)


Measured memory_bytes: 76532
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin>>n>>m;
	FORR(i, 1, m/n+1){
		if(m%i==0){
			cout<<i<<'\n';
			return 0;
		}
	}
	return 0;
}


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

void printSort(int A[], int N){
    cout << A[0];
    for(int i=1; i<N; i++){
        cout << " " << A[i];
    }
    cout << "" << endl;
}

void insertionSort(int A[], int N){
    int v, i, j;
    for(i=1; i<N; i++){
        v = A[i];
        j = i - 1;
        while(j>=0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        A[j+1] = v;
        }
        printSort(A, N);
    }
}

int main(void){
    int N;
    cin >> N;
    int A[N];
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    printSort(A, N);
    insertionSort(A,N);
    return 0;
}

Measured memory_bytes: 3108
// inputに入力データ全体が入る
function Main(input) {
	//出力
	console.log(Number(input)*2*Math.PI);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 30128
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
int INF = 1e9+7;
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for(auto i = (c).begin(); i != (c).end(); i++)
#define rep(i,b) for(auto i=0;i<(b);i++)
#define pb push_back
#define sz(c) int((c).size())

int total(vi& unit, vi& sellnr)
{
  int res = 0;
  for (int i = 0; i < sz(unit); i++) {
    res += unit[i] * sellnr[i];
  }
  return res;
}

int avg(vi& sellnr)
{
  int total = 0;
  for (int i = 0; i < sz(sellnr); i++) {
    total += sellnr[i];
  }
  return round((double)total/sz(sellnr));
}

int main(int argc, char **argv)
{
  int u, s;
  char c;
  vi unit, sellnr;
  while (cin >> u >> c >> s) {
    unit.pb(u);
    sellnr.pb(s);
  }
  cout << total(unit, sellnr) << endl;
  cout << avg(sellnr) << endl;
  return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))

#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef vector<int>		vi;
typedef vector<pii>		vpii;
typedef vector<vi>		vvi;
//=======================
const int MOD = 1'000'000'007;
const int N = 2e6+13, M = N;
//=======================
bool check(vector<int>v,int key){
    int i=0;
    int m=v.size();
    for(i=0;i<m;i++){
        if(v[i]==key){return false;}
    }
    return true;
}
void solve() {
   // int i,j;
    int n;
    cin>>n;
    if(n==0){cout<<1;return;}
    else  if(n==1){cout<<0;return;}


}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
   // cin >> t;
    while(t--) {
      solve();
      //solve()?  cout << "Yes" : cout << "No "; 
      cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 3644
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

namespace Q4
{
    class Program
    {
        static void Main(string[] args)
        {
            var strInput = Console.ReadLine().Split(' ');
            long A = Int64.Parse(strInput[0]);
            long B = Int64.Parse(strInput[1]);
            long gcd = Gcd(A, B);
            var factors = PrimeFactors(gcd);
            long ans = factors.Distinct().Count() + 1;
            Console.WriteLine(ans);

            //Console.ReadKey();
        }
        // ユークリッドの互除法 
        public static long Gcd(long a, long b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }

        public static IEnumerable<long> PrimeFactors(long n)
        {
            long i = 2;
            long tmp = n;

            while (i * i <= n) //※1
            {
                if (tmp % i == 0)
                {
                    tmp /= i;
                    yield return i;
                }
                else
                {
                    i++;
                }
            }
            if (tmp != 1) yield return tmp;//最後の素数も返す
        }
    }
}


Measured memory_bytes: 13152
fun main(args: Array<String>) = ripPro0408e()

fun ripPro0408e() {
    val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    val s = readLine()!!.map { it == '1' }.toBooleanArray()

    var left = 0
    var right = 0
    var stand = 0
    var answer = 0
    while (left <= s.lastIndex) {
        while (stand < k) {
            while (right <= s.lastIndex && stand <= k && s[right]) right++
            while (right <= s.lastIndex && stand <= k && !s[right]) right++
            while (right <= s.lastIndex && stand <= k && s[right]) right++
            stand++
        }
        answer = Math.max(answer, right - left)

        while (left <= s.lastIndex && s[left]) left++
        while (left <= s.lastIndex && !s[left]) left++
        stand--

    }

    println(answer)
}


Measured memory_bytes: 43060
import sys
import itertools

INF = 1001001001

def resolve():
  a, b = map(int, input().split())
  for i in range(10, 10100):
    if int(i * 0.08) == a and int(i * 0.10) == b:
      print(i)
      return
  print('-1')
  return

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

void solve(){
    int n;
    cin>>n;
    vector<double>a(n);
    double sum=0;
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    sum/=n;
    int ans;
    double minv=1000;
    rep(i,n){
        if(chmin(minv,abs(sum-a[i]))){
            ans=i;
        }
    }
    cout<<ans<<"\n";
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


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


void solve(long long N, long long K){
    printf("%lld\n",min(N%K,K-N%K));

}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 256
/*input
17
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define eb emplace_back
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define EL cout<<'\n'
#define BS(a,x) binary_search(ALL(a),x)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
	REP(i,SZ(V)) out<<V[i]<<((i!=SZ(V)-1)?" ":"");
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=20;
const ll INF64=1e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

string four[]={
	"aabc",
	"ddbc",
	"efgg",
	"efhh"
};

string five[]={
	"abbaa",
	"acc.b",
	"c..cb",
	"c..ca",
	"aabba"
};
string seven[]={
	"aa..aab",
	".bb..cb",
	"ac...c.",
	"ac.aa..",
	"..cbb.a",
	"a.c...a",
	"a.bb.bb"
};

string ans[1005];

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

	if(n==2){
		cout<<"-1\n";
		return 0;
	}
	if(n==3){
		cout<<"aab\nb.b\nbaa\n";
		return 0;
	}
	if(n==6){
		cout<<"aab...\nb.b...\nbaa...\n...aab\n...b.b\n...baa\n";
		return 0;
	}
	REP(i,n) ans[i].resize(n);
	REP(i,n) REP(j,n) ans[i][j]='.';
	if(n%4==3){
		int pt=0;
		REP(i,7) REP(j,7) ans[pt+i][pt+j]=seven[i][j];
		pt=7;
		while(pt<n){
			REP(i,4) REP(j,4) ans[pt+i][pt+j]=four[i][j];
			pt+=4;
		}
	}
	else{
		int pt=0;
		while((n-pt)%4){
			REP(i,5) REP(j,5) ans[pt+i][pt+j]=five[i][j];
			pt+=5;
		}
		while(pt<n){
			REP(i,4) REP(j,4) ans[pt+i][pt+j]=four[i][j];
			pt+=4;
		}
	}
	REP(i,n) cout<<ans[i]<<'\n';
	return 0;
}


Measured memory_bytes: 2304
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  return (n-1)*n//2

# main()
print(main())


Measured memory_bytes: 6864
//temprates
#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

using ll = long long;
using namespace std;

#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define LFOR(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define FORR(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define LFORR(i,a,b) for(ll i = (int)(a); i >= (ll)(b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define LREP(i,n) LFOR(i,0,(ll)(n)-1)
#define REPR(i,n) FORR(i,(int)(n)-1,0)
#define LREPR(i,n) LFORR(i,(ll)(n)-1,0)

#define SIZ(v) int(v.size())
const int INF = 1e8;
const ll LINF = 1e15;
const ll MOD = 1e9+7;

vector<vector<ll> > cmemo;

ll combbi(int n, int k){
  if (k==0||n==k) return cmemo[n][k]=1;
  if (cmemo[n][k])return cmemo[n][k];
  if (n<k) return 0;
  return cmemo[n][k]=((combbi(n-1,k-1)+combbi(n-1,k)) % MOD);
  }

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k;
  ll tmp;
  cin >> n >> k;
  cmemo.assign(n+1,vector<ll>(n+1,0));
  FOR(i,1,k){
    if(i-1>n-k)tmp=0;
    else tmp = (combbi(n-k+1,n-k-i+1)*combbi(k-1,i-1))%MOD;
    cout << tmp << endl;
  }
}


Measured memory_bytes: 31744
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		String[] sa = br.readLine().split(" ");
		int x = Integer.parseInt(sa[0]);
		int y = Integer.parseInt(sa[1]);
		br.close();

		String[] f = s.split("T", -1);
		int[] cnt = new int[f.length];
		for (int i = 0; i < cnt.length; i++) {
			cnt[i] = f[i].length();
		}

		Set<Integer> set = new HashSet<>();
		set.add(cnt[0]);
		for (int i = 2; i < cnt.length; i+=2) {
			Integer[] arr = set.toArray(new Integer[0]);
			set = new HashSet<>();
			for (int j = 0; j < arr.length; j++) {
				set.add(arr[j] + cnt[i]);
				set.add(arr[j] - cnt[i]);
			}
		}
		if (!set.contains(x)) {
			System.out.println("No");
			return;
		}

		set = new HashSet<>();
		set.add(0);
		for (int i = 1; i < cnt.length; i+=2) {
			Integer[] arr = set.toArray(new Integer[0]);
			set = new HashSet<>();
			for (int j = 0; j < arr.length; j++) {
				set.add(arr[j] + cnt[i]);
				set.add(arr[j] - cnt[i]);
			}
		}
		if (!set.contains(y)) {
			System.out.println("No");
			return;
		}
		System.out.println("Yes");
	}
}


Measured memory_bytes: 118624
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] D = new int[K];
        for(int i=0;i<K;i++) D[i]=sc.nextInt();
        HashSet<Integer> dic = new HashSet<>();
        for(int w:D) dic.add(w);
        int cur = N;
        while(cur<=99999){
            if(valid(cur,dic)) break;
            cur++;
        }
        System.out.println(cur);
    }
    static boolean valid(int N, HashSet<Integer> dic){
        String cur = Integer.toString(N);
        for(int i=0;i<cur.length();i++){
            int w = cur.charAt(i)-'0';
            if(dic.contains(w)) return false;
        }
        return true;
    }
}


Measured memory_bytes: 26324
#include <iostream>
#include<string>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<map>
using namespace std;


int main() {
	int A, B, C, K;
	int i;
	cin >> A >> B >> C >> K;
	for (i = 0; i <= K; i++) {
		if (A < B * pow(2, i) && B * pow(2, i) < C * pow(2, K - i)) {
			cout << "Yes" << endl;
			break;
		}
		if (i == K)cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 4008
#include <iostream>
#include <cmath>
using namespace std;
static const int MAX=100;

int main(void){
    int n;
    int W[MAX];
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> W[i];
    }
    int ans = 10000000;
    for(int t=0; t<n; t++){
        int S_1=0, S_2=0;
        for(int i=0; i<=t; i++){
            S_1 += W[i];
        }
        for(int i=t+1; i<n; i++){
            S_2 += W[i];
        }
        int sa = abs(S_1 - S_2);
        ans = min(sa,ans);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool q[1000009];

ll gcd(ll x, ll y){ll r; while((r= x % y)!=0){x=y; y=r;} return y;}

int main(){
  ll A,B;
  cin >> A >> B;
  ll C=gcd(A,B);
  int cnt=1;
  vector<int> pr;
  for(int i=1;i<=1000000;i++)q[i]=true;
  for(int i=2;i<=1000000;i++){
    if(q[i]){
      pr.push_back(i);
      for(int j=2*i;j<=1000000;j+=i){q[j]=false;}
    }
  }
  for(int i=0;i<pr.size();i++){
    if(C%pr[i]==0)cnt++;
    while(C%pr[i]==0){C/=pr[i];}
  }
  if(C>1)cnt++;
  cout << cnt << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll a,b,c,d,e,f;
  cin>>a>>b>>c>>d>>e>>f;

  vector<bool> isx(f+10,false);
  vector<bool> isy(f+10,false);
  for(ll i=0; i*a*100<=f; i++){
    for(ll j=0; i*a*100+j*b*100<=f; j++){
      ll now=i*a*100+j*b*100;
      isx[now]=true;
    }
  }

  isx[0]=false;

  for(ll i=0; i*c<=f; i++){
    for(ll j=0; i*c+j*d<=f; j++){
      ll now=i*c+j*d;
      isy[now]=true;
    }
  }


  ld maxn=-1;
  ll ans_all,ans_sugar;
  for(ll x=0; x<=f; x++){
    for(ll y=0; x+y<=f; y++){
      if(isx[x]&&isy[y]){
        if(y<=x/100*e){
          ld p=100.0*y/(x+y);
          if(maxn<p){
            maxn=p;
            ans_all=x+y;
            ans_sugar=y;
          }
        }
      }
    }
  }


  cout<<ans_all<<" "<<ans_sugar<<endl;
}



Measured memory_bytes: 3564
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>

using namespace std;

int main() {
    
    const long long mod = 1e9 + 7;
    
    string l;
    cin >> l;
    
    vector<long long> p(l.size(), 0);
    vector<long long> dp(l.size(), 0);
    p[0] = 1;
    dp[0] = 1;
    
    for (int i = 1; i < l.size(); ++i)
    {
        p[i] = (3 * p[i - 1]) % mod;
    }
    
    long long ret = 0;
    
    for (int i = 1; i < l.size(); ++i)
    {
        if (l[i] == '1')
        {
            dp[i] = (dp[i - 1] * 2) % mod;
        }
        else
        {
            dp[i] = dp[i - 1];
        }
    }
    
    for (int i = 0; i < l.size(); ++i)
    {
        if (l[i] == '1')
        {
            ret += (dp[i] * p[l.size() - 1 - i]) % mod;
            ret %= mod;
        }
    }
    
    ret += ((dp[l.size() - 1] * 2) % mod);
    ret %= mod;
    
    cout << ret << endl;
    
    return 0;
}

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

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

int main(){
	int n;
	cin >> n;
	int c = 0;
	for(int i =1; i<=n; i++){
		int x;
		cin >> x;
		if(i%2 == 1 && x%2 == 1) c++;
	}
	cout << c << endl;
}


Measured memory_bytes: 3588
#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; i++){
        cin >> a[i];
    }
    int min = 1000;
    int P;
    for (int i = 0; i < N; i++){
        P = a[i];
        int count = 0;
        while((P % 2) == 0){
            P = P/2;
            count += 1;
        }
        if ( min > count){
            min = count;
        }
    }
    cout << min << endl;
    return 0;
}

Measured memory_bytes: 256