akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

// iterator
#define REP(i,from, to) for(lli i=from;i<to;i++)
#define REPE(i,from, to) for(lli i=from;i<=to;i++)
#define REP_R(i,from, to) for(lli i=from;i>to;i--)
#define REPE_R(i,from, to) for(lli i=from;i>=to;i--)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define cout2(x, y)      cout << #x << ": " << x << ", " << #y << ": " << y << endl;
#define cout3(x, y, z)   cout << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl;;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

#define coutp(p)         cout << #p << ":" <<  " (" << p.first << ", " << p.second << ")" << endl;

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;
typedef tuple<lli, lli, lli> tup;


// dp[i] := i個残っているときに First が勝つかどうか
bool dp[100000];

int main() {
    lli n, k;
    cin2(n, k);
    lli a[n];
    ncin1(n, a);

    REPE(i,0,k) {
        REP(j,0,n) {
            if (i-a[j] < 0)
                continue;
            if (!dp[i-a[j]]) {
                // この一手を打ったら相手は負け確定、という一手を打てるので
                dp[i] = true;
                break;
            }
        }
    }
    if (dp[k])
        cout << "First" << endl;
    else
        cout << "Second" << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
int ctoi(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    }
    return 0;
}
int main() {
    ll a, b, c, d, ans;
    string s;
    cin >> s;
    ans = 0;
    rep(i, s.size()) {
        ans += ctoi(s.at(i));
    }
    if (ans%9 == 0) {
        cout << "Yes" << endl;
    }else {
        cout << "No" << endl;
    }
    
    return 0;
}


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

int main(){
    int a[100],b[100],n,m,x,y;
    bool check=false;
    cin>>n>>m>>x>>y;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    for (int i=0;i<m;i++){
        cin >> b[i];
    }
    
    sort(a,a+n);
    sort(b,b+m);
    
    for(int i=(a[n-1]+1);i<=b[0];i++){
        if ((x<i) && (i<=y)) { check=true; break;} 
    }
    
    if (check==true) cout<<"No War"; else cout<<"War";
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
int x[9][9], n, s[10], cnt[10], p[9][9]; bool a[9][9];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		memset(x, 0, sizeof(x));
		memset(p, 0, sizeof(p));
		memset(a, false, sizeof(a));
		memset(cnt, 0, sizeof(cnt));
		if (i) { cout << endl; }
		for (int j = 0; j < 9; j++) {
			for (int k = 0; k < 9; k++) {
				cin >> x[j][k];
			}
		}
		for (int j = 0; j < 9; j++) {
			memset(s, 0, sizeof(s));
			for (int k = 0; k < 9; k++) {
				s[x[j][k]]++;
			}
			for (int k = 0; k < 9; k++) {
				if (s[x[j][k]] >= 2) {
					a[j][k] = true;
				}
			}
		}
		for (int j = 0; j < 9; j++) {
			memset(s, 0, sizeof(s));
			for (int k = 0; k < 9; k++) {
				s[x[k][j]]++;
			}
			for (int k = 0; k < 9; k++) {
				if (s[x[k][j]] >= 2) {
					a[k][j] = true;
				}
			}
		}
		for (int j = 0; j < 9; j++) {
			for (int k = 0; k < 9; k++) {
				p[(j / 3) * 3 + (k / 3)][cnt[(j / 3) * 3 + (k / 3)]] = x[j][k];
				cnt[(j / 3) * 3 + (k / 3)]++;
			}
		}
		for (int j = 0; j < 9; j++) {
			memset(s, 0, sizeof(s));
			for (int k = 0; k < 9; k++) {
				s[p[j][k]]++;
			}
			for (int k = 0; k < 10; k++) {
				if (s[p[j][k]] >= 2) {
					for (int l = 0; l < 9; l++) {
						if (x[(j / 3) * 3 + l / 3][(j % 3) * 3 + l % 3 ] == p[j][k]) {
							a[(j / 3) * 3 + l / 3][(j % 3) * 3 + l % 3 ] = true;
						}
					}
				}
			}
		}
		for (int j = 0; j < 9; j++) {
			for (int k = 0; k < 9; k++) {
				if (a[j][k] == true) {
					cout << '*';
				}
				else {
					cout << ' ';
				}
				cout << x[j][k];
			}
			cout << endl;
		}
	}
}

Measured memory_bytes: 1156
#include<cstdio>
#include<queue>
using namespace std;
queue<int>p;
struct R
{
	int v,sek,d;
}e[233333];
int cnt,kom[100010];
inline void Ins(int a,int b,int c)
{
	e[++cnt]=(R){b,kom[a],c};
	kom[a]=cnt;
}
bool viz[100010];
int deg[100010],dis[100010];
int main()
{
	int n,m,i;
	int glad=scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int a,b,c;
		int happy=scanf("%d%d%d",&a,&b,&c);
		Ins(a,b,c);
		if(c)deg[b]++;
	}
	for(i=1;i<=n;i++)dis[i]=-1;
	for(i=1;i<=n;i++)if(!viz[i]&&deg[i]==0)
	{
		p.push(i);viz[i]=1;dis[i]=0;
		for(;!p.empty();p.pop())
		{
			int u=p.front();
			for(int j=kom[u];j;j=e[j].sek)
			{
				if(viz[e[j].v])
				{
					if(dis[e[j].v]!=dis[u]+e[j].d)
					{
						puts("No");
						return 0;
					}
				}
				else
				{
					viz[e[j].v]=1;
					dis[e[j].v]=dis[u]+e[j].d;
					if(dis[e[j].v]>1000000000)
					{
						puts("No");
						return 0;
					}
					p.push(e[j].v);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)if(dis[i]==-1)
	{
		puts("No");
		return 0;
	}
	puts("Yes");
	return 0;
	return 0;
}

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

int main ()
{
    int h,w;
    cin>> h>>w ;
    char mine[h+2][w+2];
    
    for (int i=1;i<h+1;i++)
    {
        for (int j=1;j<w+1;j++)
        {
            cin>> mine[i][j];
            if (mine[i][j] == '.')
            mine[i][j] = '0';
        }
    }

    for (int i=1;i<h+1;i++)
    {
        for (int j=1;j<w+1;j++)
        {
            if (mine[i][j]== '#')
            {
                for(int k=i-1; k<i+2;k++)
                {
                    for (int l=j-1;l<j+2;l++)
                    {
                        if (mine[k][l]!='#')
                        mine[k][l]+=1;
                    }
                }
            }
        }
    }

    for (int i=1;i<h+1;i++)
    {
        for (int j=1;j<w+1;j++)
        {
            cout<<mine[i][j];
        }
        cout<<endl;
    }
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()

struct Cmp {
  bool operator()(const pll& lhs, const pll& rhs) {
    return lhs.first > rhs.first;
  }
};

int main() {
  int n;
  cin >> n;
  vi h(n);
  rep(i, n) cin >> h[i];
  bool remain = false;
  int total = 0;
  do {
    int cnt = 0;
    int start = -1;
    for (int i = 0; i < n; i++) {
      if (start >= 0 && h[i] == 0) {
        start = -1;
      } else if (start < 0 && h[i] > 0) {
        start = i;
        cnt++;
      }
    }
    total += cnt;
    remain = false;
    for (int i = 0; i < n; i++) {
      h[i] = max(0, h[i] - 1);
      if (h[i] > 0) remain = true;
    }
  } while (remain);
  cout << total << endl;
  return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
#define int long long
#define double long double
const int INF = (int)1e18 + 18;
const int maxn = (int) 1e6 + 6; 
using namespace std;
 
int n;
 
signed main() {

	string s; cin >> s;

	sort(s.begin(), s.end());

	if(s[0] == s[1] && s[2] == s[3] && s[0] != s[3]){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	return 0;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
long long n, k;
int main(){
	scanf("%lld%lld", &n, &k);
	n %= k;
	printf("%lld\n", min(n,k-n));
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var h, n int
	fmt.Scan(&h, &n)
	var sum int
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		sum += a
	}
	if sum >= h {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 5504
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,M = map(int, input().split())
X = list(map(int, input().split()))


X.sort()

ans = X[M-1] - X[0]
tmp = []

if N==1:
    print(ans)
    sys.exit()


for i in range(1,M):
    tmp2 = X[i] - X[i-1]
    if len(tmp) < N-1:
        tmp.append(tmp2)
    else:
        tmp3 = min(tmp)
        if tmp3 < tmp2:
            tmp.remove(tmp3)
            tmp.append(tmp2)

print(ans - sum(tmp))

Measured memory_bytes: 95088
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def main():
    s1 = input()
    s2 = input()
    s3 = input()

    print(s1[0] + s2[1] + s3[2])


if __name__ == '__main__':
    main()


Measured memory_bytes: 64492
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int k = sc.nextInt();
		int ans;
		if (a >= k) {
		    ans = k;
		} else if (a + b >= k) {
		    ans = a;
		} else {
		    ans = a - (k - a - b);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 35780
#include<iostream>
#include<string>
using namespace std;
int n;
string s;
int main(){
	cin>>n>>s;
	for (int i=0;i<s.length();i++){
		int x=s[i]-'A';
		x=(x+n)%26;
		s[i]='A'+x;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    
    int r, g, b;
    cin >> r >> g >> b;
    
    int N = (r * 100) + (g * 10) + b;
    
    if(N % 4 == 0){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
    
}


Measured memory_bytes: 3040
n, m = map(int, input().split())
a = list(map(int, input().split()))


a.sort(reverse=True)
limit = 1/(m*4) * sum(a)
#a = [i for i in a if i >= limit]
flag = 0

for i in range(m):
    if a[i] >= limit:
        flag += 1
    else:
        flag = -1
        break
if flag == m:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve();
        }

        public void Solve()
        {
            var cin = new MyInputStream();

            var N = cin.ReadInt();
            //var a = new int[N];
            var b = new int[100001];
            for (int i = 0; i < N; ++i)
                b[cin.ReadInt()]++;
			
            int max = 0;
          	for (int i = 0; i < 100001 - 2; ++i)
            	max = Math.Max(b[i] + b[i + 1] + b[i + 2], max);
            /*
            Array.Sort(a);
            int max = 0;
            int l = 0;
            int r = 0;
            for (; r < a.Length; ++r)
            {
                if (a[r] - a[l] > 2)
                {
                    l = r;
                }
              	max = Math.Max(r - l + 1, max);
            }
            */
            Console.WriteLine(max);
        }
    }

    public class MyInputStream
    {
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(char separator = ' ')
        {
            this.separator = separator;
            inputStream = new Queue<string>();
        }

        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = Console.ReadLine().Trim().Split(separator);
            for (int i = 0; i < tmp.Length; i++)
            {
                inputStream.Enqueue(tmp[i]);
            }
            return inputStream.Dequeue();
        }
        public string ReadLine() => Console.ReadLine();
        public int ReadInt() => int.Parse(Read());
        public long ReadLong() => long.Parse(Read());
        public double ReadDouble() => double.Parse(Read());
        public string r() => Read();
        public int ri() => ReadInt();
        public long rl() => ReadLong();
        public double rd() => ReadDouble();
    }
}


Measured memory_bytes: 22880
while True:
    a, op, b = input().split()   # 3変数ともに文字列として読み込む
    a =int(a)                   # a を整数に変換
    b = int(b)                   # b を整数に変換


    if op=="?": # opが"?"の時は終了
        break
    else:
        if op=="+":
            print(a+b)
        elif op=="-":
            print(a-b)
        elif op=="*":
            print(a*b)
        elif op=="/":
            print(a//b)



Measured memory_bytes: 5596
#include<bits/stdc++.h>
#define int long long
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
using namespace std;
int n;
void solve() {
	int a[15][7], sum = 0;
	for1(i, n)for1(j, 5) {
		cin >> a[i][j];
		sum += a[i][j];
	}
	bool b = 1;
	while (b) {
		b = 0;
		for1(i, n) {
			if (a[i][2] == a[i][3] && a[i][3] == a[i][4] && a[i][3] != 0) {
				b = 1;
				if (a[i][1] == a[i][3])a[i][1] = 0;
				if (a[i][5] == a[i][3])a[i][5] = 0;
				a[i][2] = 0;
				a[i][3] = 0;
				a[i][4] = 0;
			}
			else if (a[i][1] == a[i][2] && a[i][2] == a[i][3] && a[i][3] != 0) {
				b = 1;
				a[i][1] = 0;
				a[i][2] = 0;
				a[i][3] = 0;
			}
			else if (a[i][5] == a[i][4] && a[i][4] == a[i][3] && a[i][3] != 0) {
				b = 1;
				a[i][5] = 0;
				a[i][4] = 0;
				a[i][3] = 0;
			}
		}
		for1(j, 5) {
			vector<int>v;
			for1(i, n)if (a[i][j])v.push_back(a[i][j]);
			for1(i, n)a[i][j] = (n - v.size() >= i ? 0 : v[i - n + v.size() - 1]);
		}
	}
	for1(i, n)for1(j, 5)sum -= a[i][j];
	cout << sum << endl;
}
signed main() {
	while (cin >> n, n)solve();
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int ans[100005];
char c[100005],ch[100005];
int main()
{
    int i,now=0,num,n,m;
    bool flag;
    cin>>n>>m;
    cin>>c;
    for(i=0;i<=n;i++) ch[i]=c[n-i];
    while(1)
    {
    	flag=true;
    	for(i=m;i>=1;i--)
    	{
    		if(ch[now+i]!='1'&&i+now<=n)
			{
				ans[++num]=i;
				now+=i;
				flag=false;
				break;
			}
    	}
    	if(now==n)
    	{
    		for(i=num;i>=1;i--) cout<<ans[i]<<" ";
    		return 0;
    	}
    	if(flag)
    	{
    		cout<<-1;
    		return 0;
    	}
    }
}

Measured memory_bytes: 1024
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringBuilder sb = new StringBuilder();
		for(char c : str.toCharArray()){
			if(Character.isUpperCase(c)){
				String s = String.valueOf(c);
				sb.append(s.toLowerCase());
			}else{
				String s = String.valueOf(c);
				sb.append(s.toUpperCase());
			}
		}
		System.out.println(sb.toString());
	}
}

Measured memory_bytes: 17132
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define fore(i, init, n) for(int i = init; i < n; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MAXN = 3000;

int n;
double p[MAXN], dp[MAXN][MAXN];

double head(int i) {
    return p[i];
}
double tail(int i) {
    return 1.0-p[i];
}

double calc(int i, int j) {
    if (dp[i][j] != -1) return dp[i][j];
    double aux;
    if (i <= j && i + j == n) aux = 0.0;
    else if (i + j == n) aux = 1.0;
    else aux = head(i+j) * calc(i+1,j) + tail(i+j) * calc(i,j+1);
    dp[i][j] = aux;
    return aux;
}

int main() {
    FIN;
    cin >> n;
    fore(i,0,n) cin >> p[i];
    fore(i,0,n+1) fore(j,0,n+1) dp[i][j] = -1;

    cout << setprecision(10) << calc(0,0) << endl;

}


Measured memory_bytes: 70784
/* author: Tarek */ 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int h,a;
cin>>h>>a;
int s=0;
for(int i=0;i<a;i++){
  int x;
  cin>>x;
  s+=x;
}
if(s>=h)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
	return 0;
}



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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> C(N);
  for(int i=0; i<N; i++){
    cin >> C[i];
  }
  sort(C.begin(), C.end());
  int ans = 0;
  for(int i=0; i<K; i++){
    ans += C[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
/**
*    created: 23.06.2020 23:34:57
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcount(bit)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<int> a(n);
    vector<int> b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    sort(all(a));
    sort(all(b));
    reverse(all(a));
    if (a[0] > b[0]) {
        cout << "War" << endl;
        return 0;
    }
    else {
        for (int i = a[0]+1; i <= b[0]; i++) {
            if (x < i && i <= y) {
                cout << "No War" << endl;
                return 0;
            }
        }
    }
    cout << "War" << endl;
    return 0;
}

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

int main() {
    using namespace std;
    constexpr unsigned long size = 12800;
    unsigned long H, W;
    cin >> H >> W;
    vector<vector<unsigned long>> p(H, vector<unsigned long>(W));
    for(auto& i : p)for(auto& j : i)cin >> j;
    for(auto& i : p)for(auto& j : i){
            unsigned long b;
            cin >> b;
            j = max(j, b) - min(j, b);
        }
    vector<vector<bitset<2 * size + 1>>> dp(H, vector<bitset<2 * size + 1>>(W));
    dp[0][0][size - p[0][0]] = true;
    dp[0][0][size + p[0][0]] = true;
    for(unsigned long i = 0; i < H; ++i){
        if(i)dp[i][0] = dp[i - 1][0] << p[i][0] | dp[i - 1][0] >> p[i][0];
        for(unsigned long j = 1; j < W; ++j){
            dp[i][j] = dp[i][j - 1] << p[i][j] | dp[i][j - 1] >> p[i][j];
            if(i)dp[i][j] |= dp[i - 1][j] << p[i][j] | dp[i - 1][j] >> p[i][j];
        }
    }
    unsigned long ans{numeric_limits<unsigned long>::max()};
    for(unsigned long i = 0; i < 2 * size + 1; ++i){
        if(dp.back().back()[i])ans = min(ans, max(size, i) - min(size, i));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 20736
import socket
import sys

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'e1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


mod = 10 ** 9 + 7

N = 4 * 10 ** 5
f = [1] * (N + 1)
for i in range(N):
    f[i + 1] = ((i + 1) * f[i]) % mod

MAX = N + 2
inv = [0] * MAX
inv[1] = 1
for i in range(2, MAX):
    inv[i] = - inv[mod % i] * (mod // i)
    inv[i] %= mod


def solve():
    n, K = read_int_list()
    if K >= n:
        K = n - 1
    r = 0
    c = 1
    d = 1
    for k in range(K + 1):
        r += c * d
        r %= mod
        c = (c * (n - 1 - k) * inv[k + 1]) % mod
        d = (d * (n - k) * inv[k + 1]) % mod

    return r


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 35824
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;

int func(long long n) {
	if (n < 10)return 1;
	return func(n/10)+1;
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int A,B,C;
	bool found = false;
	scanf("%d %d %d", &A, &B, &C);
	for (int i = 1; i <= B; i++) {
		if (A * i % B == C) {
			found = true; 
			break;
		}
	}

	cout << (found?"YES":"NO") << endl;
	return 0;
}


Measured memory_bytes: 256
use std::io::Read;
use std::cmp;

struct SegTree {
  data : Vec<usize>,
  offset : usize
}
impl SegTree {
  fn new(n: usize) -> SegTree {
    let offset = n.next_power_of_two();
    let data = vec![0_usize; 2 * offset];
    SegTree{ data, offset }
  }
  fn update(&mut self, x :usize, v: usize) {
    self.data[self.offset + x] = v;
    let mut k = (self.offset + x) / 2;
    while k > 0 {
      self.data[k] = cmp::max(self.data[2 * k], self.data[2 * k + 1]);
      k /= 2;
    }
  }
  fn range_max(&self, a:usize, b:usize) -> usize {
    self.rmax(a, b, 1, 0, self.offset)
  }
  fn rmax(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> usize {
    if r <= a || b <= l {
      0
    } else if a <= l && r <= b {
      self.data[k]
    } else {
      let mid = (l + r) / 2;
      cmp::max(self.rmax(a,b,2 * k,l,mid), self.rmax(a,b,2 * k + 1, mid, r))
    }
  }
  fn max(&self) -> usize {
    self.data[1]
  }
}

fn main() {
  let mut buf = String::new();
  std::io::stdin().read_to_string(&mut buf).unwrap();
  let A : Vec<usize> = buf.split_whitespace().map(|x|x.parse().unwrap()).collect();
  let N = A[0];
  let K = A[1];
  let mut st = SegTree::new(300_100);
  for &a in &A[2 ..] {
    let s = cmp::max(0, (a as isize) - (K as isize)) as usize;
    let t = cmp::min(300_100, (a as isize) + (K as isize) + 1) as usize;
    let v = st.range_max(s, t);
    st.update(a, v + 1);
  }
  println!("{}", st.max());
}




Measured memory_bytes: 11060
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define sz(x) (int)(x.size())
#define mod 1000000007

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;
int n, m;
vi a, b;
int dp[3000][3000];
int fun(int N, int M){
    if(dp[N][M]!=-1){
        return dp[N][M];
    }
    if(N==0 || M==0){
        return dp[N][M]=1;
    }
    else{
        int ans=0;
        ans=(fun(N-1,M)+fun(N,M-1)-fun(N-1,M-1)+mod+mod+mod)%mod;
        if(a[N-1]==b[M-1]){
            ans=(ans+fun(N-1,M-1))%mod;
        }
        return dp[N][M]=ans;
    }
}


int32_t main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    a.resize(n);
    b.resize(m);
    REP(i,0,n){
        cin>>a[i];
    }
    REP(i,0,m){
        cin>>b[i];
    }
    int ans=fun(n,m);
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 70912
import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		String u, nl = System.getProperty("line.separator");
		StringBuilder 
			p = new StringBuilder(1024),
		  	d = (new StringBuilder(64)).append("."),
		  	s = (new StringBuilder(64)).append("#"),
		  	k = new StringBuilder(64);
		Scanner r = new Scanner(System.in);
		int h, w, ww = 0x10;
		while (0 != (ww >>= 1)) {
			d.append(d);
			s.append(s);
		}
		ww = d.length();
		while (0 != ((h = r.nextInt()) | (w = r.nextInt()))) {
			while (w > ww) {
				d.append(d);
				s.append(s);
				ww = d.length();
			}
			p.append(u = s.substring(0, w)).append(nl);
			k.setLength(0);
			k.append(d.substring(0, w)).append(nl)
			.replace(0, 1, "#").replace(w - 1, w, "#");
			while (2 != h--) {
				p.append(k);
			}
			p.append(u).append(nl).append(nl);
		}
		System.out.print(p);
	}
}

Measured memory_bytes: 18372
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
   	ll N;
    cin >> N;
  	ll a[N];
  	ll ans = 0;
  	ll table[110] = {0};
    for(ll i = 0; i < N; ++i){
      cin >> a[i];
    }
  	for(ll i = 0; i < N; ++i){
     	table[a[i]]++;
    }
  	for(ll i = 0; i < 110; ++i){
     	if(table[i] != 0) ans++;
    }
  	
   
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int arr[1000000];
int main(){
    int a,b,c,i,n;
    cin>>a>>b;
    c = a+b;
    if(c>=10){
        cout<<"error";
    }
    else{
        cout<<c;
    }
}


Measured memory_bytes: 256
import math
import collections
def main():
    N, M = map(int, input().split())
    mod = pow(10, 9) + 7
    if M == 1: return 1

    ps = factorize(M)
    K = max(ps.values())

    pow1 = [1, 1]
    for i in range(2, N+K+1):
        pow1.append(pow1[-1]*i % mod)

    ref = powerquick(pow1[-1], mod-2, mod) # ((N+K)!)^-1 % mod
    invpow1 = [ref]
    for i in range(N+K, 0, -1):
        invpow1.append(invpow1[-1]*i % mod)
    invpow1 = invpow1[::-1]

    # for i in range(len(pow1)):
    #     print(pow1[i]*invpow1[i] % mod)
    # print(invpow1)
    # print(pow1)

    ans = 1
    for p in ps:
        l = ps[p]
        v = pow1[l+N-1]*invpow1[N-1]*invpow1[l] % mod
        ans = (ans * v) % mod

    # print(factorize(35))
    return ans
    # if M == 1: return 1

def powerquick(x, y, mod):
    if y == 0: return 1
    if y == 1: return x % mod
    if y % 2 == 0:
        return pow(powerquick(x, y//2, mod), 2) % mod
    else:
        return pow(powerquick(x, y//2, mod), 2) * x % mod


def factorize(n):
    ps = collections.defaultdict(int)
    if n == 1: return ps
    if isPrime(n):
        ps[n] += 1
        return ps

    p = 1
    while n > 1:
        while not isPrime(p):
            p += 1
        count = 0
        while n % p == 0:
            count += 1
            n = n // p
        if count > 0:
            ps[p] = count
            if isPrime(n):
                ps[n] += 1
                return ps
        p += 1
    return ps

def isPrime(n):
    if n == 1: return False
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return True

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 12220
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll

#include <bits/stdc++.h>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
typedef std::numeric_limits< double > dbl;
using namespace std;
const long long N=200005, INF=2000000000000000000;
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }

int32_t main()
{
    IOS;
    int s,w;
    cin>>s>>w;
    if(w>=s)
    cout<<"unsafe";
    else
    cout<<"safe";
}

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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

int main(){
    string s,t;
    cin >> s >> t;

    rep(i,s.size()+10){
        char c = s[s.size()-1];
        s = c + s;
        s.erase(s.size()-1);

        if(s==t){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

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

typedef pair< long long, long long > P;
 
bool sort_cost( const P &l, const P &r )
{
	if( (__int128)l.second * r.first != (__int128)r.second * l.first ) {
		return (__int128)l.second * r.first > (__int128)r.second * l.first;
	}
	else {
		return l.second > r.second;
	}
}

long long greedy( const vector<P>& vec, const int i, long long W )
{
  long long ans = 0;
	for ( int k = i; k < vec.size() && W > 0; k++ ) {
		long long v = vec[k].second;
		long long w = vec[k].first;
		if (w <= W) {
			ans += v;
			W -= w;
		}
	}
	return ans;
}

double ubound( const vector<P>& vec, const int i, long long W )
{
	double remain_w = W;
	double ans = 0;
	for( int k = i; k < vec.size(); k++ ) {
		double v = vec[k].second;
		double w = vec[k].first;
		if( w >= remain_w ) {
			ans += v * remain_w / w;
			break;
		}
		ans += v;
		remain_w -= w;
	}
	return ans;
}
 
long long ans;
void dfs( const vector<P>& vec, const int i, const long long W, const long long total )
{
	if ( i >= vec.size() ) {
		return;
	}

	long long gans = greedy( vec, i, W );
	ans = max( ans, total + gans );

	double ub = ubound( vec, i, W );
	if( total + ub <= ans ) {
		return;
	}

	long long v = vec[i].second;
	long long w = vec[i].first;

	dfs( vec, i + 1, W, total );

	if ( W >= w ) {
		dfs( vec, i + 1, W - w, total + v );
	}
}

int main()
{
	int N;
	long long W;
	cin >> N >> W;
	vector<P> vec;
	for( int i = 0; i < N; i++ ) {
		long long v, w, m;
		cin >> v >> w >> m;
		long long k = 1;
		while( m > 0 ) {
			long long mul = min( k, m );
			k *= 2;
			m -= mul;
			vec.push_back( make_pair( w * mul, v * mul ) );
		}
	}

	sort( vec.begin(), vec.end(), sort_cost );

	dfs( vec, 0, W, 0 );

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



Measured memory_bytes: 3312
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, m, k; cin >> n >> m >> k;
	long long a[n], b[m];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if(i > 0) a[i] += a[i-1];
	}
	for (int i = 0; i < m; i++)
	{
		cin >> b[i];
		if(i > 0) b[i] += b[i-1];
	}

	int res = upper_bound(b, b + m, k) - b;
	for (int i = 0; i < n; i++)
	{
		if(a[i] > k) break;
		int id = upper_bound(b, b + m, k - a[i]) - b;
		res = max(res, i + id + 1);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 6712
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;


long long int N, M, K, H, W, L, R;



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

	cin >> N >> M;
	if (N <= M) {
		cout << N << endl;
	}
	else {
		cout << N - 1 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
ans=1
if a.count(0)==0:
  for i in range(n):
    if ans*a[i]>10**18:
      print(-1)
      break
    else:
      ans*=a[i]
  else:
    print(ans)
else:
  print(0)

Measured memory_bytes: 21648
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

struct Ballon{
  int pos,time;
  Ballon(int p,int t):pos(p),time(t){

  }
  Ballon(){}
};

const int INF=INT32_MAX/2;

void Solve(int n){
  std::vector<Ballon> ballon(n+1);
  ballon[0]=Ballon(0,0);
  for(int i=1;i<=n;i++){
    int p,t;
    cin>>p>>t;
    ballon[i]=Ballon(p,t);
  }

  int dp[41][4]={};
  for(int r=0;r<=n;r++){
    for(int c=0;c<=3;c++){
      dp[r][c]=INF;
    }
  }

  dp[0][0]=0;

  for(int bi=1;bi<=n;bi++){
    bool can_contain=false;
    for(int ci=1;ci<=3;ci++){
      if(ci==1){

        if(bi!=1){
          for(int prev_ci=1;prev_ci<=3;prev_ci++){
            if(dp[bi-1][prev_ci]==INF) continue;

            int distance=ballon[bi-1].pos+ballon[bi].pos;
            int need_time=ballon[bi-1].pos*(prev_ci+1)+ballon[bi].pos;

            if(ballon[bi-1].time+need_time>ballon[bi].time){
              continue;
            }

            dp[bi][ci]=std::min(dp[bi][ci],dp[bi-1][prev_ci]+distance);
            can_contain=true;


          }
        }else{

          int distance=ballon[bi].pos;
          int need_time=distance;
          if(need_time>ballon[bi].time) continue;
          dp[bi][ci]=distance;
          can_contain=true;
        }

      }else{

        if(dp[bi-1][ci-1]==INF) continue;
        int distance=std::abs(ballon[bi-1].pos-ballon[bi].pos);
        int need_time=distance*ci;

        if(ballon[bi-1].time+need_time>ballon[bi].time){
          continue;
        }


        dp[bi][ci]=dp[bi-1][ci-1]+distance;
        can_contain=true;

      }
    }
    if(!can_contain){
      cout<<"NG "<<bi<<endl;
      return;
    }
  }

  int result=INF;
  for(int i=1;i<=3;i++){
    result=std::min(result,dp[n][i]+ballon[n].pos);
  }
  cout<<"OK "<<result<<endl;
  return;




}

int main(void){
  cout << std::fixed << std::setprecision(16);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  while(true){
    int n;
    cin>>n;
    if(n==0) break;
    Solve(n);
  }





  return 0;
}



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

int main() {
  string S,T;
  cin >> S >> T;
  if( S.size() < T.size() ){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  bool same = true;
  string ans = "UNRESTORABLE";
  for(int i=0;i<=S.size()-T.size();i++){
//    cout << S.substr(i,T.size()) << endl;
    for(int j=0;j<T.size();j++){
      if( S.at(i+j) != T.at(j) && S.at(i+j) != '?' ){
//        cout << S.substr(i,T.size()) << endl;
        same = false;
      }
    }
    if(same){
      ans = S;
      for(int j=0;j<S.size();j++){
        if(S.at(j) == '?')  ans.at(j) = 'a';
      }
      
      for(int j=0;j<T.size();j++){
//        if(S.at(i+j) == '?')  S.at(i+j) = T.at(j);
        ans.at(i+j) = T.at(j);
      }
      
//      cout << S << endl;
//      return 0;
    }
    same = true;
  }
  cout << ans << endl;
  return 0;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;

#define sp << " " <<
#define mod 1000000007
#define PI 3.14159265358979323
#define y second
#define x first
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define pqueue priority_queue< ll >
//#define pdqueue priority_queue< ll,vector<ll> ,greater< ll > >
#define codejamDebug(x) cout<<"Case #"<<x<<": ";
#define debug(x) cout<<#x<<" :"<<x<<endl;
#define rep(i,n) for(long long i=0;i<n;i++)
#define f(i,a,b) for(long long i = a; i < b; i++)
#define fd(i,a,b) for(long long i = a; i >=b; i--)
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int           ll;
typedef long double             ld;
typedef unsigned long long int ull;
typedef vector <int>            vi;
typedef vector <ll>            vll;
typedef pair <int, int>        pii;
typedef pair <ll, ll>          pll;
typedef vector < pii >        vpii;
typedef vector < pll >        vpll;
typedef vector <string>         vs;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//Handle:cyber_rajat

int main(int argc, char const *argv[])
{
	sync;
	ll n;
	cin >> n;
	ll a[n];
	unordered_map<ll, ll> arr1, arr2;
	rep(i, n){
		cin >> a[i];
	}
	rep(i, n){
		if ((i+1)>a[i]){
			arr1[i + 1 - a[i]]++;
		}
		arr2[i + 1 + a[i]]++;
	}
	ll ans = 0;
	for (auto x : arr1){
		if (arr2.find(x.first)!=arr2.end()){
			ans += x.second * arr2[x.first];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 17496
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

long long int facctorialMethod(int k){//階乗
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

long long int tousasum(long long int n){//等差数列
    return n*(n+1)/2;
}

unsigned GetDigit(unsigned num){//桁数
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

bool IsPrime(int num)//素数判定
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

map< long long int, long long int > prime_factor(long long int n) {//素因数分解
    map< long long int, long long int > ret;
    for(long long int i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}

int main() {

    int a;
    string s;

    cin >> a >> s;

    if(a<3200){
        cout << "red" << endl;
    }else{
        cout << s << endl;
    }

}








Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<stdlib.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pr pair<ll, ll>
#define prf pair<ld,ld>
#define vct vector<ll>
#define vpt vector<pr>
#define vcf vector<ld>
#define vpf vector<prf>
#define st set<ll>
#define pq priority_queue<ll>
#define mat vector<vector<ll> >
#define all(x) x.begin(),x.end()
#define F(i, n) for(i = 0; i < (1LL*n); i++)
#define Fr(i, n) for(i = n - 1; i >= 0; i--)
 
struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umap unordered_map<long long, long long, custom_hash>
 
void prv(vct v){for (ll i=0;i<v.size();i++)cout<<v[i]<<" ";cout << "\n";}
void prn(ll n){cout<<n<<"\n";}
void prs(string n){cout<<n<<"\n";}
void deb(string s, ll n){cout<<s<<" : "<<n<<"\n";}
void prmt(mat m){for(ll i=0;i<(1LL*m.size());i++)prv(m[i]);}
 
mat getRzMat(ll m,ll n, ll ini=0){mat mt;mt.assign(m,vector<ll>(n,ini));return mt;}
 
ll poww(ll x, ll y, ll m){
    ll res = 1;
    while (y){
        if (y%2 == 0){x = (x * x) % m;y = y / 2;}
        else{res = (res * x) % m;y--;}
    }
    return res;
}
 
vct divsors(ll n){
    vct ans;//ans.push_back(1);
    for(ll i=1;i<=sqrt(n);i++){if(n%i==0){ans.push_back(i);if(i!=(n/i))ans.push_back(n/i);}}
    sort(ans.begin(),ans.end());
    return ans;
}
vct sieve(ll n){
    vct ans(n+1,-1);
    for(ll i=2;i<=n;i++){
        if(ans[i]==-1){
            for(ll j=i;j<=n;j+=i)if(ans[j]==-1)ans[j]=i;
        }
    }
    return ans;
}
ll n, k, m, x, y, z;
ll t, t1, t2;
ll q;
ll i, j;
ll a, b, c, d, w;
ll mod = 1e9+7;
ld epi = 0.00000001;
ll cas=0;

void init(){}

vct g[100001];
vct vis(100001,0);
void dfs(ll nd){
    vis[nd]=1;
    for(auto ch:g[nd])if(!vis[ch])dfs(ch);
}
void solve(){
    cin>>n>>m;
    F(i,m){
        cin>>t1>>t2;
        g[t1].pb(t2);
        g[t2].pb(t1);
    }

    ll ans=0;
    for(i=1;i<=n;i++){
        if(!vis[i]){
            ans++;
            dfs(i);
        }
    }
    prn(ans-1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout<<fixed<<setprecision(10);
    init();
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout);
    ll t = 1;
    // cin >> t;
    cas=1;
    while (t--){
        solve();
        cas++;
    }
    return 0;
}
 


Measured memory_bytes: 10568
#include <stdio.h>
int main(){
  int a,b=0,c=0;
  for(int i=0;i<3;i++){
    scanf("%d",&a);
    switch(a){
      case 5:
        b++;
        break;
      case 7:
        c++;
        break;
    }
  }
    if(b==2&&c==1)puts("YES");
    else puts("NO");
  return 0;
}

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

int main()
{
    string S;
    const string YES = "Yes", NO = "No";
    map<char, int> s_map;

    cin >> S;
    for (auto c : S)
    {
        s_map[c]++;
    }
    for (auto item : s_map)
    {
        if (item.second != 2)
        {
            cout << NO << endl;
            return 0;
        }
    }
    if (s_map.size())
    {
        cout << YES << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  int fail = 0;
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
    if (vec.at(i) != i + 1) {
      fail++;
    }
  }
  if (fail++ <= 2) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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

vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}

int main(){
  long long N,aa;
  cin >> N;
  vector<long long> A(N);
  map<long long,long long> C;
  vector<bool> same(N,false);
  int ans=0;
  for(long long i=0; i<N; i++){
    cin >> aa;
    A[i] = aa;
    if(C.count(aa)){
      same[i] = true;
      same[C.at(aa)] = true;
    }
    C[aa] = i;
  }
  vector<vector<long long>> B(N,vector<long long>());
  for(long long i=0; i<N; i++){
     B[i] = divisor(A.at(i));
  }
  for(long long i=0; i<N; i++){
    int flag=1;
    for(long long j=0; j<(B[i].size()-1); j++){
      if(C.count(B[i][j])){
		flag = 0;
        break;
      }
    }
    if(flag && !same[i]) ans++;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 112468
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	 int x,y,z,m;
	 scanf("%d %d %d",&x,&y,&z);
	 m=(x-z)/(y+z);
	 printf("%d\n",m);
}


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


int main(void){

  int n,m,i,j,max,l;
  long long sum;

  cin >> n >> m;

  priority_queue<int> que;

  for(i=0;i<n;i++){
    cin >> l;
    que.push(l);
  }

  for(i=0;i<m;i++){
    max = que.top();
    max = max/2;
    que.pop();
    que.push(max);
  }

  sum=0;

  while(!que.empty()){
    sum=sum+que.top();
    que.pop();
  }

  cout << sum <<"\n";


  return 0;

}

Measured memory_bytes: 892
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int N = sc.nextInt();
   int[] a = new int[N];
   for(int i=0;i<N;i++) a[i] = sc.nextInt();
   String ans = "APPROVED";
   for(int i =0; i<N;i++)
   {
     if(a[i] %2 == 0)
     {
       if(a[i]%3!=0&&a[i]%5!=0)
       {
         ans = "DENIED";
         break;
       }
     }
   }
   System.out.print(ans);
 }
}

Measured memory_bytes: 22612
inloop _ [] = 0
inloop c (x:xs) = inloop (f c) xs + if x == c then 0 else 1
 where
  f '0' = '1'
  f '1' = '0'

main = do
 str <-  getLine :: IO String
 print $ min (inloop '0' str) (inloop '1' str)

Measured memory_bytes: 7548
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll mod = 1e9 + 7;
    ll n, k;
    cin >> n >> k;
    ll ans = 1;
    reps(i, k, n + 1) {
        ll minv = (0 + (i - 1)) * i / 2;
        ll maxv = ((n - i + 1) + n) * i / 2;
        ans = (ans + (maxv - minv + 1)) % mod;
        // printf("%lld %lld\n", minv, maxv);
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int tmp=0;
  int ans=100;
  int anstmp=0;
  for(int i=0;i<N;i++){
    cin >> tmp;
    anstmp=0;
    while(tmp%2==0){
      tmp/=2;
      anstmp++;
    }
    if(ans>anstmp){
      ans=anstmp;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 256