akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n, m;
	while (cin >> n >> m) {
		if (n + m == 0)break;
		vector<int> v(n);
		for (int i = 0; i < n; i++)cin >> v[i];
		int ans = -1;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (v[i] + v[j] <= m)ans = max(ans, v[i] + v[j]);
			}

		}
		if (ans == -1)cout << "NONE" << endl;
		else cout << ans << endl;
	}

}


Measured memory_bytes: 3084
#include<stdio.h>
#include<string.h>
int main ()
{
    int i;
    char st[6];
    gets(st);
    for(i=0;st[i]!='\0';i++)
    {

        if(st[i]=='A' && st[i+1]=='C')
        {
           printf("Yes\n");
            return 0; 
            
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 128
//#include<iostream>
//#include<algorithm>
//#include<string>
//#include <cmath>
//#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

//vector//
#define vei vector<int> 
#define velli vector<long long int> 
#define pb(x) push_back(x) // 末尾にxを加える
#define pb2 pop_back() // 末尾削除
#define all(x) (x).begin(),(x).end() //イテレーター
#define be(x) (x).begin()
//auto  auto begin = v.begin()とか

typedef pair<int,int> P;  //q(p.first,p.second)

int main (){
    string s; cin >> s;
    int size = s.size();
    if(s[size-1] == 's') s += "es";
    else s += "s";

    cout << s;
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int count = 0;
		for(int i = n - 1; i > 0; i--) {
			int j = 0;
			while(j < i) {
				if(arr[j] > arr[j + 1]) {
					int v = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = v;
					count++;
				}
				j++;
			}
		}
		for(int i = 0; i < n; i++) {
			if(i == n - 1) {
				System.out.println(arr[i]);
			} else {
				System.out.print(arr[i] + " ");
			}
		}
		System.out.println(count);
	}
}



Measured memory_bytes: 26428
#include <iostream>
#include <string>
#include <set>

using namespace std;

void solve()
{
	int n, h;
	while(cin >> n >> h, n || h)
	{
		set<int> Set;
		string str;
		int a, b;
		int n2 = n * n;
		for(int i = 0; i < h; ++i)
		{
			int sum = 0;
			cin >> str >> a >> b;
			--a; --b;
			if(str == "xy")
			{
				sum = a + n * b;
				for(int j = 0; j < n; ++j)
				{
					Set.insert(sum);
					sum += n2;
				}
			}
			else if(str == "xz")
			{
				sum = a + n2 * b;
				for(int j = 0; j < n; ++j)
				{
					Set.insert(sum);
					sum += n;
				}
			}
			else
			{
				sum = n * a + n2 * b;
				for(int j = 0; j < n; ++j)
				{
					Set.insert(sum);
					sum++;
				}
			}
		}
		cout << n2 * n - Set.size() << endl;
	}
}

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

Measured memory_bytes: 1984
N = int(input())
A = list(map(int,input().split()))
B = [A[k]*2 for k in range(N)]

lo = 0
hi = max(2*A[0],2*A[-1])+1

while hi-lo > 0:
    mid = (hi+lo)//2
    t = mid
    for k in range(N):
        t = B[k]-t
    if t == mid:
        break
    elif t > mid:
        lo = mid
    else:
        hi = mid
C = [0 for k in range(N)]
C[0] = mid
for k in range(1,N):
    C[k] = B[k-1] - C[k-1]
print(*C)


Measured memory_bytes: 66532
s = gets.chomp
n = s.size

def check(s)
    (s.size/2).times do |i|
        return false if s[i] != s[-1-i]
    end
    true
end

puts check(s) && check(s[0..(n/2-1)]) && check(s[(n/2+1)..-1]) ? "Yes" : "No"

Measured memory_bytes: 1788
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    map<long long int, long long int> mp;
    for(int n=0; n<N; n++) {
        long long int a;
        cin >> a;
        mp[a]++;
    }
    
    long long int ans=0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        if(itr->second-itr->first>=0) {
            ans += min(itr->second-itr->first, itr->second);
        } else {
            ans += itr->second;
        }
    }
    
    cout << ans << endl;


    return 0;
    
}

Measured memory_bytes: 6272
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		//String t = sc.next();
		//String g = sc.next();
		//long n = sc.nextLong();
		//long m = sc.nextLong();
		//long k = sc.nextLong();
		//long l = sc.nextLong();
		//String buff="Christmas";
		long count=0;
		long[] array=new long[3];

		/*for(long i=n;i<25;i++) {
			buff+=" Eve";
		}*/
		Arrays.sort(array);
		int buff = Integer.parseInt(s.substring(0,4));
		int buff1 = Integer.parseInt(s.substring(5,7));
		if(buff>2019||buff1>4) {
			System.out.println("TBD");
		}else {
			System.out.println("Heisei");
		}
		//System.out.println(buff+" "+buff1);
		//System.out.println(Math.abs(array[2]-array[1])+Math.abs(array[1]-array[0]));
	}
}




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

using namespace std;

#define ll long long
#define mod 1000000007

void solve(){

    int n; cin >> n;
    int dp[3] = {0, 0, 0};
    while(n--){
        int a, b, c; cin >> a >> b >> c;
        int newdp[3];
        newdp[0] = a + max(dp[1], dp[2]);
        newdp[1] = b + max(dp[0], dp[2]);
        newdp[2] = c + max(dp[0], dp[1]);

        dp[0] = newdp[0], dp[1] = newdp[1], dp[2] = newdp[2];
    }
    cout << max(dp[0], max(dp[1], dp[2])) << endl;
    
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
	return 0;
}

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

int main() {
    char c;
    cin >> c;
    c += 1;
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Data.Char
import Data.List


-- space delimited integers
getVals::IO [Int]
getVals = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

-- space delimited strings
getStrings::IO [String]
getStrings = (map BS.unpack . BS.words) <$> BS.getLine


solver:: Int->Int->Bool
solver x y = (mod y 2 == 0) && 2*x <= y && 4*x >= y  

main::IO()
main = do
    val <- getVals
    let x:y:_ = val
    putStrLn $ if solver x y then "Yes" else "No" 



Measured memory_bytes: 3776
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define ll long long
const int INF=1e9+7;

int main(){
#ifndef ONLINE_JUDGE
	freopen("C:\\Users\\User\\Documents\\input.txt","r",stdin);
#endif
	int T,i,j;
	
	int n;
	cin>>n;
	vector<int> dp(n+1,INF),a(n+1);

	for(i=1;i<=n;++i){
	    scanf("%d",&a[i]);
	}
	dp[1]=0;
	for(i=1;i<n;i++){
		dp[i+1]=min(dp[i+1],dp[i]+abs(a[i+1]-a[i]));
		if(i+2<=n) dp[i+2]=min(dp[i+2],dp[i]+abs(a[i+2]-a[i]));
	}
	printf("%d\n",dp[n]);



	return 0;
}

Measured memory_bytes: 3960
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int N; cin >> N;
	int ans = -1;

	for(int i=40000;;--i){
		if(i*i <= N){
			cout << i*i << endl;
			break;
		}

	}

	return 0;

}


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

int main(){
    int n,m,k;
    cin >> n >> m >> k;
    vll a(n),b(m),a_(n+1,0),b_(m+1,0);

    for(int ix=0;ix<n;ix++){
        cin >> a.at(ix);
        a_.at(ix+1) = a.at(ix) + a_.at(ix);
    }
    for(int ix=0;ix<m;ix++){
        cin >> b.at(ix);
        b_.at(ix+1) = b.at(ix) + b_.at(ix);
    }
    int cnt = 0,ixx = m;
    for(int ix=0;ix<=n;ix++){
        if(a_.at(ix) > k) break;
        while(ixx >= 0 && b_.at(ixx) + a_.at(ix) > k){
            ixx--;
        }
        cnt = max(cnt, ix+ixx);
    }
    cout << cnt << endl;
}


Measured memory_bytes: 9572
#include<bits/stdc++.h>
using namespace std;
bool sol(int n)
{
	for(int i=1;i<=9;i++)
	{
		int k=n/i;
		if(n%i==0 && k>=1 && k<=9)
		{
			return true;
		}
	}
	return false;
}
main()
{
	int n;
	cin>>n;
	if(sol(n))
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
a_even = [i for i in a if i % 2 == 0]
if a_even == [i for i in a_even if i % 3 == 0 or i % 5 == 0]:
    print('APPROVED')
else:
    print('DENIED')


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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        bool can = true;
        can &= (vec[i] + vec[j] > vec[k]);
        can &= (vec[i] + vec[k] > vec[j]);
        can &= (vec[j] + vec[k] > vec[i]);
        can &= (vec[i] != vec[j] && vec[j] != vec[k] && vec[i] != vec[k]);
        if (can) {
          ++ans;
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int R, G, B, N;
    cin >> R >> G >> B >>N;

    int cnt = 0;

    for (int i = 0; i <= N / R; i++){
        for (int j = 0; j <= N / G; j++){
            int k = N - R * i - G * j;
            if (k >= 0 && k % B == 0){
                cnt++;
            }
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 2147483647
#define lli long long int
#define MOD 1000000007
#define pb push_back

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;

bool C(vvi check, int nx, int ny){
	if (0 <= nx and nx < check.front().size() and 0 <= ny and ny < check.size()) {
		if (check[ny][nx] == 0) {
			return true;	
		}
	}
	return false;	
}

bool UB(vvi ub, int nx, int ny) {
	if (0 <= nx and nx < ub.front().size() and 0 <= ny and ny < ub.size()){
		if (ub[ny][nx] == 0) {
		//cout << "ub : " << ny << " " << nx << endl;
			//cout << ub[ny][nx] << endl;
			return true;
		}	
	}
	return false;
}

bool LR(vvi lr, int nx, int ny) {
	if (0 <= nx and nx < lr.front().size() and 0 <= ny and ny < lr.size()){
		if (lr[ny][nx] == 0) {
		//cout <<"lr : " <<  ny << " " << nx << endl;
			return true;
		}
	}
	return false;
}

int bfs(vvi ub, vvi lr) {

	int w = ub.front().size();
	int h = lr.size();
	vvi check(lr.size(),vi(ub.front().size(),0));
	check[0][0] = 1;
	queue<pii> q;
	q.push(make_pair(0,0));
	
	vi cx = {1,-1,0,0};	
	vi cy = {0,0,1,-1};	
	vi dx = {0,-1,0,0};	
	vi dy = {0,0,0,-1};	
	int ret = 0;
	while(!q.empty()) {
		pii now = q.front();
		//cout << "x = " << now.second << " y = " << now.first << endl;
		q.pop();
		if (now.first == ub.size() and now.second == lr.front().size()) {
			return check[now.first][now.second];
		}
		
		for (int i = 0; i < 4; i++) {
			int ccx = now.second + cx[i];	
			int ccy = now.first + cy[i];
			int ddx = now.second + dx[i];
			int ddy = now.first + dy[i];
			if (C(check,ccx,ccy) and UB(ub,ddx,ddy) and (i == 2 or i == 3)) {
				//cout << "UB" << endl;
				q.push(make_pair(ccy,ccx));
				check[ccy][ccx] += check[now.first][now.second] + 1;
				//cout << ccy << ":" << ccx << "???????????§" << check[ccy][ccx] <<"??§???"<< endl;
			}else if(C(check,ccx,ccy) and LR(lr,ddx,ddy) and  (i == 0 or i == 1)) {
				//cout << "LR" << endl;
				q.push(make_pair(ccy,ccx));
				check[ccy][ccx] += check[now.first][now.second] + 1;
				//cout << ccy << ":" << ccx << "???????????§" << check[ccy][ccx] <<"??§???"<< endl;
			//	cout << ccx << " " << ccy << endl;
			}
			
			//cout << C(check,ccx,ccy) << " " << UB(ub,ddx,ddy) << " " <<  LR(lr,ddx,ddy) << endl;
		}

	}
	//cout << "empty" << endl;
	return 0;
}

int main() {
	while(1) {
		int w,h; cin >> w >> h;

		if (w + h == 0) break;

		vvi lr(h,vi(w-1,0));
		vvi ub(h-1,vi(w,0));

		for (int i = 0; i < h-1; i++) {
			for (int j = 0; j < w - 1; j++) {
				cin >> lr[i][j];	
			}
			for (int j = 0; j < w; j++) {
				cin >> ub[i][j];	
			}
		}
		for (int j = 0; j < w - 1; j++) {
				cin >> lr[h-1][j];	
		}

		cout << bfs(ub,lr) << endl;
	}
	return 0;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int X, ans = 0; cin >> X;
    rrep (i, 1, 100) {
        rrep (j, 2, 100) {
            int val = pow(i, j);
            if (val > X) break;
            ans = max(ans, val);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
//const ll MOD=(ll)998244353;
const ll INF=(ll)1e18+10;
const double PI = 2.0*acos(0);
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
const int D=365;
const int beam = 175;
int c[26];
int s[D][26];
int ans[D];

struct State{
    ll val = 0;
    int out[D]={0};
    int cnt[26]={0};
};

bool operator< (const State &a, const State &b){
    return a.val<b.val;
}
bool operator> (const State &a, const State &b){
    return a.val>b.val;
}

void itr(){
    priority_queue<State> pq[2];
    pq[0].push(State());
    for (int i = 0; i < D; ++i) {
        int prev=i&1,next = prev^1;
        //cout<<prev<<" "<<next<<endl;
        for (int j = 0; !pq[prev].empty()&&j < beam; ++j) {
            auto state = pq[prev].top();
            pq[prev].pop();
            ll dec=0;
            for (int k = 0; k < 26; ++k) { //開催しなかったときのへる値
                //cout<< state.cnt[k]<<endl;
                state.cnt[k]++;
                dec+=(ll)c[k]*state.cnt[k];
            }
            for (int k = 0; k < 26; ++k) {
                const ll inc = (ll)c[k]*state.cnt[k];
                const int tmp = state.cnt[k];
                const int tmp_val = state.val;
                state.val = state.val-dec+inc+s[i][k];
                state.cnt[k]=0;
                state.out[i]=k;
                pq[next].push(state);
                //cout<<"called"<<endl;
                state.cnt[k]=tmp;
                state.val = tmp_val;
                //if(i==0)cout<<state.val
            }
        }
        pq[prev]=priority_queue<State>();
    }
    auto best = pq[D&1].top().out;
    for (int i = 0; i < D; ++i) {
        ans[i]=best[i]+1;
    }
}

void solve(int ca){
    int waste;
    scanf("%d",&waste);
    for (int i = 0; i < 26; ++i) {
        scanf("%d",c+i);
    }
    for (auto & i : s) {
        for (int & j : i) {
            scanf("%d",&j);
        }
    }

    itr();
    for (int i = 0; i < D; ++i) {
        printf("%d\n",ans[i]);
    }

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


struct dat {
    int w,s; ll val;
    void read() {
	cin>>w>>s>>val;
    }
    //if s-o.w > o.s-w, then we should come before o. (box o should go on top of us)
    bool operator<(dat o) {
	return w+s>o.w+o.s;
    }
};


int n;
vector<dat> v;

ll dp[1001][10001];



ll solve(int i, int have) {
    assert(have>=0);
    if (i==n) {
	return 0;
    }

    if (~dp[i][have]) return dp[i][have];

    ll &res = dp[i][have] = 0;

    res = solve(i+1, have);

    if (have >= v[i].w) {
	res = max(res, v[i].val + solve(i+1, min(have-v[i].w, v[i].s)));
    }

    return res;
}

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

    memset(dp,-1,sizeof(dp));

    cin>>n;
    v.resize(n);
    for (int i=0; i<n; i++) {
	v[i].read();
    }

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


    ll res = 0;
    for (int i=0; i<n; i++) {
	dp[i][v[i].s] = v[i].val+solve(i+1, v[i].s);
	res = max(res, dp[i][v[i].s]);
    }


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


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

int main(){
  int N,K;
  cin >> N >> K;
  int multiplier = 0;
  double result = 0;
  int temp = 0;
  
  for(int i = 1; i <= N; ++i){
    temp = i;
    while(temp < K){
      temp <<= 1;
      ++multiplier;
    }
    result += (double)1 / (N * pow(2,multiplier));
    multiplier = 0;
  }
  
  printf("%.12f",result);
  
}

Measured memory_bytes: 384
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn vec<T, F: FnMut(usize) -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|i| f(i)).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let mut neighbors: Vec<Vec<usize>> = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let a: usize = scan(tokens);
        let b: usize = scan(tokens);
        neighbors[a - 1].push(b - 1);
        neighbors[b - 1].push(a - 1);
    }
    let mut parent: Vec<usize> = (0..n).collect();
    let mut children: Vec<usize> = vec![0; n];
    fn dfs(
        i: usize,
        p: usize,
        neighbors: &Vec<Vec<usize>>,
        parent: &mut Vec<usize>,
        children: &mut Vec<usize>,
    ) {
        parent[i] = p;
        children[i] = 1 << i;
        for &j in &neighbors[i] {
            if j != p {
                dfs(j, i, neighbors, parent, children);
                children[i] |= children[j];
            }
        }
    }
    dfs(0, 0, &neighbors, &mut parent, &mut children);
    let m: usize = scan(tokens);
    let paths: Vec<usize> = vec(m, |_| {
        let u: usize = scan(tokens);
        let v: usize = scan(tokens);
        let mut u = u - 1;
        let mut v = v - 1;
        let mut p = 0;
        while children[u] & (1 << v) == 0 {
            p |= 1 << u;
            u = parent[u];
        }
        while u != v {
            p |= 1 << v;
            v = parent[v];
        }
        p
    });
    fn rec(paths: &[usize], set: usize, all: usize) -> i64 {
        if paths.is_empty() {
            1 << (all ^ set).count_ones()
        } else {
            rec(&paths[1..], set, all) - rec(&paths[1..], set | paths[0], all)
        }
    }
    println!("{}", rec(&paths, 0, (1 << n) - 2));
}


Measured memory_bytes: 4352
package main

import "fmt"

func main() {
	var D int

	fmt.Scan(&D)
	switch D {
	case 22:
		fmt.Println("Christmas Eve Eve Eve")
	case 23:
		fmt.Println("Christmas Eve Eve")
	case 24:
		fmt.Println("Christmas Eve")
	case 25:
		fmt.Println("Christmas")
	}
}


Measured memory_bytes: 512
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int frd(){
	int x=0,f=1; char ch=gc();
	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
inline void print(int x){
	if (x<0)	putchar('-'),x=-x;
	if (x>9)	print(x/10);
	putchar(x%10+'0');
}
const int N=5e2,inf=1e9;
int V[N+10][N+10];
int main(){
	int n=read(),m=read(),h=read(),w=read();
	int v=3999,mv=-(h*w-1)*v-1,sum=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			sum+=V[i][j]=(i%h==0&&j%w==0)?mv:v;
	if (sum<=0)	printf("No\n");
	else{
		printf("Yes\n");
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++)	printf("%d ",V[i][j]);
			putchar('\n');
		}
	}
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <complex>
#include <string>
#define x real() 
#define y imag() 
using namespace std;
typedef complex <double> point;
typedef complex<double> vectol;

string ccw(point a,point b,point c) {
  vectol ab=b-a, ac =c-a;
  vectol d =ac*conj(ab); 
  if(d.y > 0) return "COUNTER_CLOCKWISE";
  if(d.y < 0) return "CLOCKWISE";
  ab = ab*conj(ab);
  if(ab.x<d.x) return "ONLINE_FRONT";
  if(0>d.x) return "ONLINE_BACK";
  return "ON_SEGMENT";
}

int main() {
  double x0,y0,x1,y1;
  cin>>x0>>y0>>x1>>y1;
  point a = point( x0, y0);
  point b = point( x1, y1);
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> x0 >> y0;
    cout << ccw(a,b,point(x0,y0)) <<endl;
  }

  return 0;
}

Measured memory_bytes: 1244
import bisect
x,n=map(int,input().split())
p = sorted(map(int,input().split()))
i = 0
judge = 0

while judge != 1:
    if x-i not in p:
        ans = x-i
        judge = 1
        break
    if x+i not in p:
        ans = x+i
        judge = 1
    i += 1

print(ans)

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

using namespace std;


int my_max(int a, int b) {
    return a > b ? a : b;
}

int my_abs(int x) {
    return x < 0 ? -x : x;
}

template <typename T>
map<T, T> prime_factor(T n) {
    map<T, T> ret;
    for(T i = 2; i * i <= n; i++) {
        T tmp = 0;
        while(n % i == 0) {
            tmp++;
            n /= i;
        }
        ret[i] = tmp;
    }
    if(n != 1) ret[n] = 1;
    return ret;
}

template <typename T>
T divisor_num(T n) {
    map<T, T> pf = prime_factor(n);
    T ret = 1;
    for(auto p : pf) {
        ret *= (p.second + 1);
    }
    return ret;
}

int main() {

    int n;
    cin >> n;

    int result = 0;
    for(int i=1; i<=n; i++) {
        if(i%2!=0 && divisor_num(i) == 8) {
            result++;
        }
    }

    cout << result << endl;


    return 0;
}


Measured memory_bytes: 256
from scipy.sparse.csgraph import dijkstra

h, w = map(int, input().split())
n = 10
dist = dijkstra([list(map(int, input().split())) for _ in range(n)])

res = 0
for i in range(h):
    for j in map(int, input().split()):
        if j != -1:
            res += dist[j][1]
print(int(res))


Measured memory_bytes: 22852
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(lint (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
 
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
  
  int main(){      
   lint n,m;
   cin>>n>>m;
   lint h[n];
   Graph g(n);
   rep(i,n)cin>>h[i];
   rep(i,m){
       lint a,b;
       cin>>a>>b;
       --a;--b;
       g[a].push_back(b);
       g[b].push_back(a);
   }
   lint ans=0;
   rep(i,n){
       bool p=true;
       rep(j,g[i].size()){
           if(h[i]<=h[g[i][j]])p=false;
       }
       if(p)ans++;
   }
   cout<<ans<<endl;
  }
          
  

Measured memory_bytes: 9920
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int N = int.Parse(str[0]);
		int K = int.Parse(str[1]);
		int[]A = new int[N];
		for(var i=0;i<N;i++){
			A[i] = int.Parse(Console.ReadLine());
		}
		Array.Sort(A);
		long min = A[K-1]-A[0];
		for(var i=1;i<N-K+1;i++){
			int a1 = A[i+K-1]-A[i];
			if(a1<min){
				min = a1;
			}
		}
		Console.WriteLine(min);
	}
}

Measured memory_bytes: 15452
#include<iostream>
using namespace std;
int main()
{
    int X;
    cin >> X;
    if(400 <= X && X <= 599){
        cout << 8;
    }
    else if(600 <= X && X <= 799){
        cout << 7;
    }
    else if(800 <= X && X <= 999){
        cout << 6;
    }
    else if(1000 <= X && X <= 1199){
        cout << 5;
    }
    else if(1200 <= X && X <= 1399){
        cout << 4;
    }
    else if(1400 <= X && X <= 1599){
        cout << 3;
    }
    else if(1600 <= X && X <= 1799){
        cout << 2;
    }
    else if(1800 <= X && X <= 1999){
        cout << 1;
    }
}

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

int main(){
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++) cout << "x";
    cout << endl;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  
  int t=0;
  int s=1;
  
  for(int i=0;i < 10000;i++){
    if(s >= b){
      break;
    }
    t++;
    s += a-1;
    
  }
  
  cout << t << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;
    if (v <= w){
        cout << "NO" << endl;
        return 0;
    }

    int dis = abs(a - b);
    int k = ceil((double)dis / (v - w));
    if (k <= t){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#define S 540
#define T 720 //1260 - 540
using namespace std;

int main()
{
	int n, m, r;
	while (cin >> n >> m, n) {
		vector<vector<int> > v(m, vector<int>(T, 0));
		cin >> r;
		while (r--) {
			int t, pc, st, s;
			cin >> t >> pc >> st >> s;
			v[st-1][t-S] += s?1:-1;
		}

		for (int i = 0; i < m; i++) {
			int sum = 0, state = 0;
			for (int j = 0; j < T; j++) {
				sum += !!state;
				state += v[i][j];
				v[i][j] = sum;
			}
		}
		int q, ts, te, st;
		cin >> q;
		while (q--) {
			cin >> ts >> te >> st;
			cout << v[st-1][te-S] - v[st-1][ts-S] << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 28784
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


template<typename T>
struct SegmentTree{
private:
    int n;
    T E;
    vector<T> node;
    inline void updatef(T& x,T& y){
        x = y;
        //x += y;
        //x = max(x,y);
        //x = min(x,y);
    }
    inline T queryf(T& x,T& y){
        //return x*y;
        //return x+y;
        //return max(x,y);
        return min(x,y);
    }

public:
    SegmentTree(int sz,T E_):E(E_){
        n=1;
        while(n<sz)n<<=1;
        node.resize(2*n-1,E);
    }

    SegmentTree(vector<T>& A,T E_):E(E_){
        int sz=A.size();
        n=1;
        while(n<sz)n<<=1;
        node.resize(2*n-1,E);
        rep(i,sz)node[i+n-1]=A[i];
        for(int i=n-2;i>=0;--i){
            node[i]=queryf(node[2*i+1], node[2*i+2]);
        }
    }
    void update(int k,T x){
        k+=n-1;
        updatef(node[k],x);
        while(k>0){
            k=(k-1)/2;
            node[k]=queryf(node[2*k+1], node[2*k+2]);
        }
    }
       //[a,b)での和を返す
    T get(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l)return E;
        if(a<=l&&r<=b)return node[k];
        T xl=get(a,b,2*k+1,l,(l+r)/2);
        T xr=get(a,b,2*k+2,(l+r)/2,r);
        return queryf(xl, xr);
    }
};


struct UnionFind{
   vector<int> par;
   UnionFind(int n):par(n,-1){}
   int find(int x){
       if(par[x]<0)return x;
       return par[x]=find(par[x]);
   }
   bool unite(int x,int y){
       x=find(x);
       y=find(y);
       if(x==y)return false;
        par[x]+=par[y];
        par[y]=x;
       return true;
   }

   bool same(int x,int y){
       return find(x)==find(y);
   }
   int size(int x){
       return -par[find(x)];
   }
};
int main(){
    int n,k;
    cin>>n>>k;
    SegmentTree<int> sg(2*n, inf),sg2(2*n,inf);
    int a[n];
    rep(i,n){
        cin>>a[i];
        sg.update(i,a[i]);
        sg2.update(i,-a[i]);
    }
    UnionFind uf(n+1);
    REP(i,1,n-k+1){
        if(sg.get(i-1,i+k-1)==a[i-1]&&sg2.get(i,i+k)==-a[k+i-1]){
            uf.unite(i-1,i);
        }
    }
    vector<int> sum(n);
    rep(i,n-1){
        sum[i+1]=(a[i]>a[i+1]);
    }
    rep(i,n)sum[i+1]+=sum[i];
    rep(i,n-k+1){
        if(sum[i]==sum[i+k-1])uf.unite(i,n);
    }
    int ans = 0;
    rep(i,n-k+1){
        if(uf.find(i)==i)++ans;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 11136
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

int n, q;

struct MyStruct
{
	int ne;
	vector<int>eda;
	int x;
	ll sum = 0;
};

vector<MyStruct>list(200005);
vector<ll>ans(200005, 0);

int func(int no, ll sum) {

	ll x = list[no].x + sum;
	ans[no] = x;

	for (int i = 0; i < list[no].eda.size(); i++) {
		
		func(list[no].eda[i], x);
	}


	return 0;
}

signed main() {
	
	cin >> n >> q;


	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		list[a].eda.push_back(b);
		list[b].ne = a;
	}

	for (int i = 0; i < q; i++) {
		int p, x;
		cin >> p >> x;
		list[p].x += x;
	}

	func(1, 0);

	for (int i = 1; i <= n; i++) {
		cout << ans[i];
		if (i != n ) {
			cout << " ";
		}
	}
	cout << endl;


	return 0;
}

Measured memory_bytes: 25856
inf = float('inf')

n, m = map(int, input().split())

e = []
for _ in range(m):
    s, t, c = map(int, input().split())
    s -= 1
    t -= 1
    c *= -1
    e.append((s, t, c))

dist = [inf] * n
dist[0] = 0
ans = None
for cnt in range(n * 2):
    for s, t, c in e:
        if dist[s] != inf and dist[t] > dist[s] + c:
            dist[t] = dist[s] + c
            update = True
    if cnt == n - 1:
        ans = -dist[n - 1]
if ans != -dist[n - 1]:
    print('inf')
else:
    print(ans)

# 「ベルマンフォード法」の pythonのコード
# (https://juppy.hatenablog.com/entry/2018/10/30/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E9%96%A2%E9%80%A3_python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)
#
# Bellman Fordは負辺があってもかまわない場合の単一始点全点間最短距離を求め，同時に負閉路の存在を検出するアルゴリズムである．
#
# これは動的計画法に基づくアルゴリズムで，k 回目の更新によって始点から k ステップ以下で進む場合の最短距離が計算される．
# もし n 回目にもまだ更新があるのならば，経路はどこかに負の閉路を含んでいるので，
# その頂点への経路には負閉路が存在するとして距離を負の無限大に設定する．
# (http://www.prefield.com/algorithm/graph/bellman_ford.html)
#
# 通常の Bellman-Ford 法における負閉路検出は、後者の負閉路に対して「負閉路あり」と判定してしまうことに注意。それを防ぐためには、
# 本来 Bellman-Ford は N-1 回のイテレーションで終わるので N 回目以降にも更新が行われたら負閉路ありとしていたところを
# N 回目以降にも頂点 N への最短路が更新されたら、「1 から N までの間に負閉路あり」
# と判定すればいい。この場合、ループは 2N 回程度回せば確実。
# (http://drken1215.hatenablog.com/entry/2019/02/16/075900)


Measured memory_bytes: 3316
using System.Linq;
using System.Collections.Generic;
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = new List<int>();
        for (int i = 0; i < n; i++)
            a.Add(int.Parse(line[i]));
        getAns(a);
    }
    static void getAns(List<int> a)
    {
        var ans = new List<int>();
        while (a.Count() > 0)
        {
            var ac = a.Count();
            var find = false;
            for (int i = ac - 1; i >= 0; i--)
            {
                if (a[i] == i + 1)
                {
                    ans.Add(a[i]);
                    a.RemoveAt(i);
                    find = true;
                    break;
                }
            }
            if (!find) { Console.WriteLine(-1); return; }
        }
        ans.Reverse();
        foreach (var x in ans) Console.WriteLine(x);
    }
}

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

//container util
//------------------------------------------
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).begin(),(c).end(),greater<int>())

#define PB(a) push_back(a)

#define FS first
#define SE second

#define ALL(x) (x).begin(),(x).end()
#define MAX_EL(c) *max_element((c).begin(),(c).end())
#define MIN_EL(c) *min_element((c).begin(),(c).end())
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef string str;
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal var
//------------------------------------------
int N,M;
bool visited[100];
bool world[100][100];


int main(){
// magic spell------------------------------
  cin.tie(0);
  ios::sync_with_stdio(false);
//------------------------------------------

  int N;
  cin >> N;
  VI H(N);
  int cur=0;
  int ans=0;
  REP(i,N){
    cin >> H[i];
  }
  EACH(i,H){
     cur=0;
    REP(j,i-H.begin()){
      if(*i>=H[j]) cur++;
    }
    if(cur==i-H.begin()) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
X = input()

def popcount(n):
    return bin(n).count('1')

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt != 1:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)


Measured memory_bytes: 94660
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

template <typename T>
bool chmax(T &a, const T& b) {
    if (a < b) {
      a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T& b) {
    if (a > b) {
      a = b;
      return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    cout << max(0,min(D,B)-max(A,C)) << endl;
}

Measured memory_bytes: 3556
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int A,B;
  cin>>A>>B;
  REP(i,100000){
    if(((i*8)/100 == A) and ((i*10)/100 == B)){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
const ll INF = 1LL<<60;



int main(){
  ll N,M;
  cin>>N>>M;
  vector<vector<ll>> A(N+1,vector<ll>(0,0));
  ll a,b;
  rep(i,M){
    cin>>a>>b;
    A[a].push_back(b);
    A[b].push_back(a);
  }
  
  vector<ll> dist(N+1,-1);
  queue<ll> que;
  ll ans=0;
  for(ll i=1;i<N+1;i++){
    if(dist[i]!=-1){continue;}
   if(dist[i]==-1){ans++;}
    que.push(i);
    dist[i]=ans;
    while(!que.empty()){
      ll v=que.front();
      que.pop();
      
      for(ll j=0;j<(ll)A[v].size();j++){
        if(dist[A[v][j]]!=-1){continue;}
        que.push(A[v][j]);
        dist[A[v][j]]=ans;
      }
    }
  }
  
  
  cout<<ans-1<<endl;
  
}


Measured memory_bytes: 10172
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

bool good(string S)
{
    VEC(int) Counts(3);
    FOR(i, 0, 3)
        Counts[i] = count(ALL(S), (char)('a' + i));

    if (SZ(S) == 1)
        return true;
    if (SZ(S) == 2)
        return S[0] != S[1];

    FOR(i, 0, 3)
        FOR(j, 0, 3)
            if (i != j) {
                FOR(k, 0, 3)
                    Counts[k] = count(ALL(S), (char)('a' + k));
                if (Counts[i] == 0 || Counts[j] == 0)
                    continue;

                Counts[i]--;Counts[j]--;
                int good = 1, a = i, b = j;
                FOR(k, 0, SZ(S) - 2) {
                    int c = 3 - a - b;
                    if (Counts[c] == 0) {
                        good = 0;
                        break;
                    }
                    Counts[c]--;
                    a = b;b = c;
                }

                if (good)
                    return true;
            }

    return false;
};

void solveSingleCase(int caseNo)
{
    string S;
    cin >> S;

    cout << (good(S) ? "YES" : "NO") << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 512
n, x = gets.split.map(&:to_i)
l = gets.split.map(&:to_i)

def dn(i, l)
  if i == 1
    0
  else
    dn(i - 1, l) + l[i - 2]
  end
end


ans = 0
1.upto(n + 1) do |i|
  d = dn(i, l)
  if d <= x
    ans  = i
  end
end
puts ans

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define inc( i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec( i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(i, v) for(auto i =  v.begin(); i !=  v.end(); ++i)
#define RFOR(i, v) for(auto i = v.rbegin(); i != v.rend(); ++i)

template<typename T> bool setmin(T & a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T & a, T b) { if(b <= a) { return false; } else { a = b; return true; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T> ostream & operator<<(ostream & os, const vector<T> & v) {
	os << "[";
	FOR(it, v) {
		if(it != v.begin()) { os << ", "; }
		os << *it;
	}
	os << "]";
	return os;
}
template<typename F, typename S> ostream & operator<<(ostream & os, const pair<F, S> & p) {
	os << "<" << p.FI << ", " << p.SE << ">";
	return os;
}

// ---- ----

int n, m;
vector<pair<int, int>> vec[100001];

const int BS = 1 << 17;
template<typename T> T BIT(T t[], int p, T v, bool f = false) {
	if(! f) { return BIT(t, p + BS, v, ! f); }
	
	if(p == 0) { return 0; }
	
	if(p % 2 == 0) { t[p / 2] += v; }
	T w = BIT(t, p / 2, v, f);
	if(p % 2 != 0) { w += t[p / 2]; }
	return w;
}
int L[BS], R[BS];

int main() {
	cin >> n >> m;
	inc(i, n) {
		int l, r;
		cin >> l >> r;
		vec[r - l + 1].EB(l, r + 1);
	}
	
	int a = n;
	inc1(d, m) {
		int k = d, b = 0;
		while(k <= m) {
			b += BIT(L, k + 1, 0) - BIT(R, k + 1, 0);
			k += d;
		}
		
		cout << a + b << "\n";
		
		inc(i, vec[d].size()) {
			BIT(L, vec[d][i].FI, 1);
			BIT(R, vec[d][i].SE, 1);
			a--;
		}
	}
	
	return 0;
}


Measured memory_bytes: 8448
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    int M, D;
    cin >> M >> D;
    int ans = 0;
    REP(m, 1, M + 1) {
        REP(d, 1, D + 1) {
            int d1 = d % 10;
            int d2 = d / 10;
            if (d1 >= 2 && d2 >= 2) {
                if (d1 * d2 == m)
                    ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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


int main(){
  int n,a[1000];
  int count=0;
  cin>>n;
  for(int i=0;i<n;i++){cin>>a[i];}

  for(int i=n;i>=0;i--){
    for(int k=0;k<n;k++){
      if(a[k]>=i){count++;}
    }
    if(count>=i){count=i; break;}
    else{count=0;}
  }

  cout<<count<<endl;
  
  return 0;
}



Measured memory_bytes: 3096
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramA
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var result = true;
            result = result && s.Contains("a");
            result = result && s.Contains("b");
            result = result && s.Contains("c");
            Console.WriteLine(result ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 25828
MOD = 10**9 + 7
N,A,B,C = map(int,input().split(' '))

fact = [1] * (2*N)
inv = [0] * (2*N)
inv[1] = 1
ifact = [1] * (2*N)
for i in range(2,2*N):
	fact[i] = (fact[i-1] * i) % MOD
	inv[i] = (inv[MOD % i] * (MOD - MOD//i) % MOD)
	ifact[i] = ifact[i-1] * inv[i] % MOD

INV = [0] * 101
INV[1] = 1
for i in range(2,101):
	INV[i] = (INV[MOD % i] * (MOD - MOD//i) % MOD)

ap = [1] * (N+1)
bp = [1] * (N+1)
for i in range(1,N+1):
	ap[i] = ap[i-1] * A % MOD
	bp[i] = bp[i-1] * B % MOD

icp = [1] * (2*N+1)
for i in range(1,2*N+1):
	icp[i] = icp[i-1] * INV[100-C] % MOD

a = [0] * (2*N)

j = 1
a[N] =(ap[N] + bp[N]) % MOD
for i in range(N+1,2*N):
	f = fact[i-1] * ifact[j] * ifact[i-1-j] % MOD
	a[i] = fact[i-1] * ifact[j] * ifact[i-1-j] % MOD
	a[i] *= (ap[N] * bp[j] + ap[j] * bp[N]) % MOD
	j = j + 1

p = [0] * (2*N)
for i in range(N,2*N):
	p[i] = a[i] * i * icp[i+1] % MOD

print(sum(p)*100 % MOD)



Measured memory_bytes: 52004