akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(void) {
    /*cout << std::fixed << std::setprecision(10);
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    */
    int64_t n, k;
    int64_t result = 0;
    cin >> n >> k;
    int64_t secnum, length;
    for (int i = 1; i <= n; i++) {
        if (i % k == 0) {
            secnum = k;
            length = n - secnum;
            result += (length / k + 1) * (length / k + 1);
        } else if (k != 2 && k % 2 == 0 && i % k == k / 2) {
            secnum = k / 2;
            length = n - secnum;
            result += (length / k + 1) * (length / k + 1);
        } else {
            secnum  = k - (i % k);
            int mod = secnum % k;
            if ((mod * 2) % k == 0) {
                length = n - secnum;
                result += (length / k + 1) * (length / k + 1);
            }
        }
        // cout << result << endl;
    }

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

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

    int n;
    cin >> n;
    vector<ll> a(n);
    ll mx = -1;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx,a[i]);
    }

    int loga = 0;

    while((1ll << loga) < mx) loga++;

    vector<int> bit(loga,0);
    for(int j = 0; j < n; j++){
        for(int i = 0; i < loga; i++){
            if(a[j] & (1ll << i)) bit[i]++;
        }
    }

    ll ans = 0;
    for(int i = 0; i < n; i++){
        ll now = 1;
        for(int j = 0; j < loga; j++){
            if(a[i] & (1ll << j)){
                bit[j]--;
                ans += now*(n-i-1-bit[j])%mod;
                ans %= mod;
            } else ans += now*bit[j]%mod;
            now *= 2;
            now %= mod;
        }
    }

    cout << (ans+mod)%mod << endl;

    return 0;
}

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


def solve(N: int, K: int, h: "List[int]"):
    h.sort()

    ans = 1000000000000
    for i in range(N-K+1):
        ans = min(ans, h[i+K-1]-h[i])
    
    print(ans)

    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 7392
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    int N;
    cin >> N;
    vector<int> d;
    for(int i=0;i<N;i++){
        int tmp;
        cin >> tmp;
        d.push_back(tmp);
    }
    sort(d.begin(),d.end());
    cout << d[N/2]-d[N/2-1] << endl;
    
    return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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 (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define MAX_N 1000
#define INF 1152921504606846976
using T = tuple<i64, i64, i64>;
vector<i64> stog[MAX_N];
vector<i64> gtos[MAX_N];
vector<bool> r(MAX_N, false);
vector<bool> rr(MAX_N, false);

void dfs(i64 u) {
    for (i64 v : stog[u]) {
        if (r[v]) continue;
        r[v] = true;
        dfs(v);
    }
}
void rdfs(i64 u) {
    for (i64 v : gtos[u]) {
        if (rr[v]) continue;
        rr[v] = true;
        rdfs(v);
    }
}

int main() {
    i64 N, M; cin >> N >> M;

    vector<T> edge;
    REP(i, M) {
        i64 u, v, c; cin >> u >> v >> c;
        u--, v--;
        edge.emplace_back(u, v, -c);
        stog[u].pb(v);
        gtos[v].pb(u);
    }

    r[0] = true;
    rr[N - 1] = true;
    dfs(0);
    rdfs(N - 1);

    vector<i64> d(N, INF);
    d[0] = 0;
    i64 step = 0;
    bool update = true;
    while (update) {
        update = false;
        for (auto [from, to, cost] : edge) {
            if (!r[from] || !rr[from]) continue;
            if (!r[to] || !rr[to]) continue;

            if (chmin(d[to], d[from] + cost)) update = true;
        }

        step++;
        if (step > N) {
            cout << "inf" << endl;
            return 0;
        }
    }

    i64 ans = -d[N - 1];
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3844
#include<bits/stdc++.h>
using namespace std;
string a,b;
int la,lb;
char ma='{',mb='A'; 
int c(){
	for(int i=0;i<la;i++)
		for(int j=0;j<lb;j++)
			if(a[i]!=b[j])return 0;
	return 1;
}
int main()
{
	cin>>a>>b;
	la=a.length();
	lb=b.length();
	for(int i=0;i<la;i++)if(a[i]<ma)ma=a[i];
	for(int j=0;j<lb;j++)if(b[j]>mb)mb=b[j];
	if(ma<mb)cout<<"Yes";
	else if(ma<mb)cout<<"Yes";
	else if(la<lb){
		if(c()==1)cout<<"Yes";
		else cout<<"No";
	}
	else cout<<"No";
	return 0;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    a = list(map(int,input().split()))
    f,s = {},{}
    for i in range(n):
        if i+1-a[i] not in f.keys():
            f[i+1-a[i]] = 1
        else:
            f[i+1-a[i]]+=1
        if i+1+a[i] not in s.keys():
            s[i+1+a[i]] = 1
        else:
            s[i+1+a[i]] += 1
    ans = 0
    for k in f.keys():
        if k in s.keys():
            ans += f[k] * s[k]
    print(ans)

if __name__ == "__main__":
    main()


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

int main() {
    string s;
    cin >> s;
    int ans = 0;
    rep(i, 3) if (s[i] == 'R') ans++;
    if(ans == 2 && s[1] == 'S') cout << 1 << endl;
    else cout << ans << endl;
}


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

char str[4];

int main()
{
    int i;
    int n, m;
    scanf("%d%d", &n, &m);
    str[n] = 0;
    for(int i=1; i<=m; ++i){
        int s, x;
        scanf("%d%d", &s, &x);
        if(str[s-1] != 0){
            if(str[s-1] != x+'0'){
                printf("-1\n"); return 0;
            }
        }
        str[s-1] = x + '0';
    }
    if(n>1 && (str[0]==0 || str[0]=='1')) str[0] = '1';
    if(n>1 && str[0]=='0'){ printf("-1\n"); return 0; }
    for(int i=(n==1?0:1); i<n; ++i) str[i] = (str[i]==0)?'0':str[i];
    printf("%s\n", str);
}


Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	tmp = input[0].split(" ");
    var a = tmp[0];
    var b = tmp[1];
    var c = tmp[2];
    if(a[a.length-1] === b[0] && b[b.length-1] === c[0]) {
      console.log("YES");
    } else {
      console.log("NO");
    }
    
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define pb push_back
#define fi first
#define se second
typedef long long ll;

ll gcd(ll a, ll b)
{
	return (b == 0 ? a : gcd(b, a % b));
}

ll lcm(ll a, ll b)
{
	return (a * b) / gcd(a, b);
}

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

	int n;
	cin >> n;

	ll A[n], numerator = 1, denominator = 0;
	for (int i = 0; i < n; ++i) {
		cin >> A[i];
		numerator = lcm(numerator, A[i]);
	}
	for (int i = 0; i < n; ++i)
		denominator += (numerator / A[i]);

	cout << setprecision(12) << (double)numerator / denominator << '\n';
}


Measured memory_bytes: 384
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

long long int INF = 1000000000000000000LL; // 10^18
using namespace std;

typedef pair<long long int, long long int> P;

int main(){
	
	int N;
	cin >> N;
	
	int A[200000];
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	
	int ans = 1;
	int is_up = 0;
	for(int i = 0; i < N - 1; i++){
		if(A[i + 1] > A[i]){
			if(is_up == -1){
				is_up = 0;
				ans++;
			}else{
				is_up = 1;
			}
		}else if(A[i + 1] < A[i]){
			if(is_up == 1){
				is_up = 0;
				ans++;
			}else{
				is_up = -1;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 768
#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>;

struct Edge{
    int to, id;
    Edge(int to, int id): to(to), id(id) {}
};

vector<Edge> g[55];

vector<int> es;
bool dfs(int v, int tv, int p=-1){
    if(v == tv) return true;
    for(Edge e : g[v]){
        if(e.to == p) continue;
        if(dfs(e.to, tv, v)){
            es.push_back(e.id);
            return true;
        }
    }
    return false;
}

int main(){
    int n, m;
    cin >> n;
    rep(i,n-1){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    
    cin >> m;
    vector<ll> eset(m);
    rep(i,m){
        int a, b;
        cin >> a >> b;
        a--, b--;
        es = vector<int>();
        dfs(a, b);
        for(int e : es){
            eset[i] |= 1ll<<e;
        }
    }

    ll ans = 0;
    rep(i,1<<m){
        ll mask = 0;
        rep(j,m){
            if(i>>j&1) mask |= eset[j];
        }
        int white = __builtin_popcountll(mask);
        ll now = 1ll<<(n-1-white);
        if(__builtin_popcountll(i)%2 == 0) ans += now;
        else ans -= now;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
int main(){
  int N;
  cin>>N;
  string c;
  cin>>c;
  int white=0;
  int red=0;
  int siro[200000],aka[200000];
  for(int i=0;i<N;i++){
   if(c[i]=='W'){
     siro[white]=i;
     white++;
   }
  }
  for(int i=N-1;i>=0;i--){
    if(c[i]=='R'){
      aka[red]=i;
      red++;
    }
    }
  if(red==0||white==0) cout<<0<<endl;
  else{
    int i=0;
    int answer=0;
    while(i<white&&i<red&&siro[i]<aka[i]){
      answer++;
      i++;
    }
    cout<<answer<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 4100
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if (i+1) % 2 == 1 and a[i] % 2 == 1:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 21868
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

int main(void){
	int n,a,b,c,d;
	cin>>n>>a>>b>>c>>d;
	a--;b--;c--;d--;
	string s;
	cin>>s;
	int a_ = a, b_ = b;
	while(true){
		if(a+1 <= c && s[a+1] == '.'){
			a++;
			continue;
		}
		if(a+2 <= c && s[a+2] == '.'){
			a++;a++;
			continue;
		}
		break;
	}

	while(true){
		if(b+1 <= d && s[b+1] == '.'){
			b++;
			continue;
		}
		if(b+2 <= d && s[b+2] == '.'){
			b++;b++;
			continue;
		}
		break;
	}


	if(a < c || b < d){
		cout<<"No"<<endl;
		return 0;
	}
	a = a_;
	b = b_;

	if(c < d){
		cout<<"Yes"<<endl;
		return 0;
	}

	if(a > b){
		int tmp = a;
		a = b;
		b = tmp;
		tmp = c;
		c = d;
		d = tmp;
	}

	//a<b, d<c
	while(true){
		if(c <= a+1 || n <= a+2 || d < a+1){
			break;
		}
		if(a+1 >= b && s[a] == '.' && s[a+1] == '.' && s[a+2] == '.'){
			cout<<"Yes"<<endl;
			return 0;
		}
		a++;
	}
	cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		boolean found[] = new boolean[27];
		for(int i = 0; i < 27; i++) found[i] = false;
		boolean result = true;
		for(int i = 0; i < s.length(); i++) {
			if(found[(int)s.charAt(i) - 97]) {
				result = false;
				break;
			}
			found[(int)s.charAt(i) - 97] = true;
		}
		if(result) System.out.println("yes");
		else System.out.println("no");
	}

}


Measured memory_bytes: 23764
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class C
{
	public static void Main()
	{
		int N = GetInt();
		int M = GetInt();
		int[] csum = new int[N+2];
		for(int i = 0; i < M; i++)
		{
			int L = GetInt();
			int R = GetInt();
			csum[L]++;
			csum[R+1]--;
		}
		for(int i = 1; i <= N; i++)
			csum[i] += csum[i-1];

		int ans = 0;
		for(int i = 1; i <= N; i++)
			if(csum[i] == M)
				ans++;
		Console.WriteLine(ans);
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}


Measured memory_bytes: 15328
#include"bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
	int A, B, K;
	cin >> A >> B >> K;
	rep(i, K) {
		if (i % 2 == 0) {
			if (A % 2 != 0) {
				A--;
			}
			B += A / 2;
			A /= 2;
		}
		else {
			if (B % 2 != 0) {
				B--;
			}
			A += B / 2;
			B /= 2;
		}
	}
	cout << A << " " << B << endl;
	return 0;
}

Measured memory_bytes: 256
#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<memory.h>
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)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int n;
  cin >> n;
  ll a[n]={};
  rep(i,n)cin >> a[i];
  sort(a,a+n);
  int left=-1;
  int right=n;
  while(right-left>1){
    int mid=(right+left)/2;
    bool flag=false;
    ll sum=0;
    ll pos=0;
    while(pos<n && (2*sum>=a[pos] || pos<=mid) ){
      sum+=a[pos];
      pos++;
    }
    if(pos>=n){
      right=mid;
    }else left=mid;
  }
  ll ans=0;
  rep(i,n)if(i>=right)ans++;
  cout << ans << endl;
return 0;}

Measured memory_bytes: 1024
A, B, C, X, Y = map(int, input().split())
num = float("inf")
for i in range(0, (10 ** 5) * 2 + 1, 2):
    num = min(num, max(0, X - i // 2) * A + max(0, Y - i // 2) * B + C * i)
print(num)

Measured memory_bytes: 3060
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "damage", long, "cost");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    auto n = lread();
    auto h = aryread();
    auto dp = new long[](n + 5);
    dp[] = INF;
    dp[0] = 0;
    foreach (i; iota(n))
    {
        if (i + 1 < n)
            dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i + 1]);
        if (i + 2 < n)
            dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 2]);
    }
    dp[n - 1].writeln();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


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

#define REP(i,n) for(int i=0; i<(n); i++)

int n;
int a[252521];

int main(){
	scanf("%d",&n);
	REP(i,n)scanf("%d",a+i);
	int cnt = 0;
	REP(i,n)if(a[i]%2==0)cnt++;
	if(cnt==0 || cnt==n){
		puts("0");
		return 0;
	}else{
		int o = n-cnt;
		int e = cnt;
		int ans = 0;
		while(o>=3){
			o-=2;
			e++;
			ans++;
		}
		while(o>=1 && e>=1){
			e--;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 3924
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*":
        c=0
      elif x[j]==".":
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=max(M[k],j-C[k])
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=max(M[k],w-C[k])
    a=b[:]
  s=0
  for i in range(h+1):
    s=max(s,M[i]*i)
  print s

Measured memory_bytes: 4300
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
using namespace std;

int main(){
  long long N = 0,K = 0,Q = 0;
  cin >> N >> K >> Q;
  vector<long long> person(N);
  for(int i = 0;i < N;i++){
    person.at(i) = K - Q;
  }
  int x;
  for(int i = 0;i < Q;i++){
    cin >> x;
    person.at(x - 1) += 1;
  }
  for(int i = 0;i < N;i++){
    if(person.at(i) > 0){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
}


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

a = []
b = []
c = []
d = []
for i in range(n):
    aa, bb = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
for i in range(m):
    aa, bb = list(map(int, input().split()))
    c.append(aa)
    d.append(bb)

for i in range(n):
    min = 200000001
    p = 1
    for j in range(m):
        z = abs(a[i] - c[j]) + abs(b[i] - d[j])
        if z < min:
            min = z
            p = j + 1

    print(p)

Measured memory_bytes: 3064
#!/usr/bin/env python
# coding: utf-8

def main():
	a, b = [int(x) for x in raw_input().split(" ")]
	if a < b:
		print "a < b"
	elif a == b:
		print "a == b"
	else:
		print "a > b"


if __name__ == '__main__':
	main()

Measured memory_bytes: 4208
import math

x,y = map(int,input().split())
n = 0
mod = 10**9 + 7
mx = 700000
fac = [0]*mx
fin = [0]*mx
inv = [0]*mx

if ((x+y) % 3 != 0):
    print("0")
    exit()
n = (2*y-x)//3
m = (2*x-y)//3

if (n<0)|(m<0):
    print("0")
    exit()

# nCr mod p を求めるのに必要な前処理
fac[0] = fac[1] = 1
fin[0] = fin[1] = 1
inv[1] = 1
for i in range(2,mx):
    fac[i] = fac[i-1]*i % mod
    inv[i] = mod - inv[mod%i] * (mod // i) % mod
    fin[i] = fin[i-1] * inv[i] % mod

print(fac[n+m]*((fin[n]* fin[m])%mod) % mod)

Measured memory_bytes: 86132
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,n,s) for(int i=s;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  int n;
  cin >> n;
  if(n%2 != 0) {
    cout << 0 << endl;
    return 0;
  }

  vector<int> d(n);
  REP(i, n) {
    cin >> d[i];
  }

  SORT(d);

  cout << d[n/2] - d[n/2-1] << endl;
  return 0;
}


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

int main()
{
    int c[3][3];
    bool ans = 1;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            cin >> c[i][j];
    }

    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (c[i][j] + c[i + 1][j + 1] != c[i + 1][j] + c[i][j + 1])
            {
                ans = 0;
                break;
            }
        }
    }
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define int long long
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;
constexpr long long inf = 1e17;
constexpr int mod = 998244353;
int dp[302][302][302];
int a[305];
signed main() {
	string s; cin >> s;
	int N = s.size();
	if(s[N-1]=='1')s.push_back('0');
	int k; cin >> k;
	int cnt = 0, now = 0;
	rep(i, s.size()) {
		if (s[i] == '0') {
			a[now] = cnt;
			now++;
		}
		else cnt++;
	}
	for (int i = N - 1; i > 0; i--)a[i] -= a[i - 1];
	k = min(k, cnt);
	dp[0][0][0] = 1;
	N = now;


	rep(i, N) {
		for(int j=0;j<=k;j++) {
			for(int l=0;l<=j;l++) {
				if (!dp[i][j][l])continue;
				for (int m = j; m <= k; m++) {
					dp[i + 1][m][l] += dp[i][j][l]; dp[i + 1][m][l] %= mod;
				}
				for (int m = l + 1; m <= min(l + a[i], j); m++) {
					dp[i + 1][j][m] += dp[i][j][l]; dp[i + 1][j][m] %= mod;
				}
			}
		}
	}
	int ans = 0;
	rep(i, k + 1) {
		ans += dp[N][i][i]; ans %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 57400
#include<stdio.h>
int main(){
int n,m,a[1010],b[1010],i,k=0,l;
for(i=0;i<1005;i++){
    a[i]=0,b[0]=0;
}
while(1){
scanf("%d %d\n",&n,&m);
if(n==0 && m==0){
break;
}
for(i=0;i<n;i++){
scanf("%d\n",&a[i]);
}
for(i=0;i<m;i++){
scanf("%d\n",&b[i]);
}
for(i=0;i<m;i++){
k=k+b[i];
l=a[k];
k=k+l;
if(k>=n-1){
printf("%d\n",i+1);
k=0;
break;
}
}
}
return 0;
}


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

typedef struct 
{
	char name;
	int number;
}Card;

void bubble_sort(Card *a, int n);
void selection_sort(Card *a, int n);
int isstable(Card *a, Card *b, int n);

int main(void)
{
	
	
int n, i, j, flag, result, min;
	
scanf("%d", &n);

Card card1[100];
Card card2[100];
Card card3[100];
Card temp;


for(i=0; i<n ; i++)
{
	scanf(" %c%d", &card1[i].name, &card1[i].number);
}
	
for(i=0; i<n ; i++)
{
	card2[i] = card1[i];
	
}
	
bubble_sort(card1, n);
	

printf("Stable\n");
	
	
selection_sort(card2,n);
	
	result = isstable(card1, card2, n); //0の時not stable , 1の時stable
	
	if(result==0)
	{
		printf("Not stable\n");
	}
	else if(result==1)
	{
		printf("Stable\n");
	}
	

	return 0;
	
	
}
void bubble_sort(Card *a, int n)
{
	int j, i;
	Card temp;
	
	for(int i=0; i<n ; i++) //バブルソート
	{
		for(j=n-1; j>=i+1; j--)
		{
			if(a[j].number < a[j-1].number)
			{
				temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
			}
		}
	}
	
	
	for(i=0; i<n-1; i++)
	{
		printf("%c%d ", a[i].name, a[i].number);
	}
	
	printf("%c%d\n", a[n-1].name, a[n-1].number);
	
}
void selection_sort(Card *a, int n)
{
	int i, j, min;
	Card temp;

	for( i=0; i<n ; i++) //選択ソート
	{
		min = i;
		
		for(j=i; j<n; j++)
		{
			if(a[j].number < a[min].number)
			{
				min = j;
				
			}
		}
		
		temp = a[i];
		a[i] = a[min];
		a[min] = temp;
		
	}
	
	for(i=0; i<n-1; i++)
	{
		printf("%c%d ", a[i].name, a[i].number);
	
	}
	
	printf("%c%d\n", a[n-1].name, a[n-1].number);
	
}


int isstable(Card *a, Card *b, int n)
{
	int i, j, k, l;
	
	for(i=0; i<n; i++)
	{
		if(a[i].name != b[i].name)
		{
			return 0;
		}
	
	}
	
	return 1;

}



Measured memory_bytes: 2092
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();

		X-=A;
		while(X >= B) {
			X -= B;
		}
		System.out.println(X);
	}
}

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

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

using namespace std;

using ll = long long;

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

    int N, K;
    cin >> N >> K;
    K = min(K, 100);
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    while (K-- > 0) {
        vector<int> B(N + 1);
        REP(i, N) {
            B[max(i - A[i], 0)] += 1;
            B[min(i + A[i] + 1, N)] -= 1;
        }
        REP(i, N) {
            B[i + 1] += B[i];
        }
        A = B;
    }

    REP(i, N) {
        cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 5544
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+23;

int main(){
	int n,d;
	cin>>n>>d;
	int cnt=0;
	for(int i=0;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(1ll*x*x+1ll*y*y<=1ll*d*d) cnt++;
	}
	cout<<cnt;
}

Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
int a[100005],n;
char s[100005];
signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;){
        int j=i;
        while(j+1<=n&&s[j+1]=='R') j++;
        int k=j+1,l=k;
        while(l+1<=n&&s[l+1]=='L') l++;
        // printf("%d %d %d %d\n",i,j,k,l);
        int L=j-i+1,R=l-k+1;
        if((L+R)&1)
        {if(L&1){
            a[j]=(L+R)/2+1;
            a[k]=L+R-a[j];
        }
        else{
            a[k]=(L+R)/2+1;
            a[j]=L+R-a[k];
        }}
        else a[j]=a[k]=L+R>>1;
        i=l+1;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
}

Measured memory_bytes: 896
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:1024000000")
#pragma warning( disable : 6031)
#pragma warning( disable : 4244)
#pragma warning( disable : 26451)
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdint>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-15)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef vector<ll> vl;
typedef vector<vector<long long>> vvl;
typedef tuple<int, int, int> tiii;
const long long mod = int(1e9) + 7;
const int INF = 1e9;




int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	const int add = 1e4 + 10;
	int h, n;
	cin >> h >> n;
	vpii sp(n);
	for (int i = 0; i < n; i++)
	{
		cin >> sp[i].first >> sp[i].second;
	}
	vi dp(add * 2 + h, INF);
	dp[add + h] = 0;
	for (int i = add + h - 1; i >= 0; i--)
	{
		for (auto p : sp)
		{
			dp[i] = min(dp[i + p.first] + p.second, dp[i]);
		}
	}
	
	cout << *min_element(dp.begin(), dp.begin() + add + 1);
	return 0;
}

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

typedef long long int ll;

using namespace std;

int main() {
  ll a,b,c;
  cin>>a>>b>>c;
  if(a%2==1&&b%2==1&&c%2==1){
    ll ans=min(a*b,b*c);
      ans=min(ans,c*a);
    cout<<ans;
  }
  else{cout<<0;}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[2][n];
    for(int i=0;i<2;i++){
    	for(int j=0;j<n;j++){
    		cin >> a[i][j];
    	}
    }
    for(int i=1;i<n;i++){
    	a[0][i] += a[0][i-1];
    }
    a[1][0] += a[0][0];
    for(int i=1;i<n;i++){
    	a[1][i] += max(a[0][i], a[1][i-1]);
    }
    cout << a[1][n-1] << endl;
    return 0;
}


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

int main(){
  char s[9];
  int ans=0, count=0;
  //string st; cin >> st;
  //scanf("%s", s);
  cin >> s;
  for ( int i = 0; i < 10; i++ ){
    switch (s[i]) {
      case 'A':
      		count++;
      		break;
      case 'C':
      		count++;
      		break;
      case 'G':
      		count++;
      		break;
      case 'T':
      		count++;
      		break;
      default:
            ans = max(ans, count);
            count = 0;
      		break;
    }
  }
  ans = max(ans, count);
  cout << ans << endl;
  return 0;
}

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

int main() {
    string S;
    cin >> S;

    long long ans = 0, cnt = 0;
    for (int i = 0; i < (int)S.size(); i++) {
        if (S[i] == 'B') cnt++;
        else ans += cnt;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 2005;

char t[N];
string s[3];
int i, j, k, l, ot, res, last, b;
bool ok[3][3][N];

void go(string& s1, string& s2, int ind1, int ind2) {
	for (int i=0;i<s1.size();i++) {
		ok[ind1][ind2][i] = 1;
		for (int j=0;j<min(s1.size() - i, s2.size());j++) if (s1[i + j] != '?' && s2[j] != '?' && s1[i + j] != s2[j]) {
			ok[ind1][ind2][i] = 0;
			break;
		}
	}
}

int main() {
scanf("%s", t);
s[0] = t;
scanf("%s", t);
s[1] = t;
scanf("%s", t);
s[2] = t;
go(s[0], s[1], 0, 1);
go(s[1], s[0], 1, 0);
go(s[0], s[2], 0, 2);
go(s[2], s[0], 2, 0);
go(s[1], s[2], 1, 2);
go(s[2], s[1], 2, 1);
res = s[0].size() + s[1].size() + s[2].size();
for (i=0;i<3;i++) for (j=0;j<3;j++) if (i != j) {
	ot = 3 - i - j;
	for (k=0;k<s[i].size();k++) if (ok[i][j][k]) {
		last = max((int)s[i].size(), k + (int)s[j].size());
		res = min(res, last + (int)s[ot].size());
		for (l=0;l<s[i].size();l++) if (ok[i][ot][l]) {
			b = 0;
			if (l == k && ok[j][ot][0]) b = 1;
			if (l + s[ot].size() <= k) b = 1;
			if (k + s[j].size() <= l) b = 1;
			if (l < k && ok[ot][j][k - l]) b = 1;
			if (k < l && ok[j][ot][l - k]) b = 1;
			if (b) {
				last = max((int)s[i].size(), k + (int)s[j].size());
				last = max(last, l + (int)s[ot].size());
				res = min(res, last);
			}
		}
		for (l=s[i].size() - k;l<s[j].size();l++) if (ok[j][ot][l]) {
			last = max((int)s[i].size(), k + (int)s[j].size());
			last = max(last, k + l + (int)s[ot].size());
			res = min(res, last);
		}
	}
}
printf("%d\n", res);
return 0;
}

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

int main(void){
	int n,m;
	cin>>n>>m;
	vector<int> v(m);
	vector<bool> used(n+1);
	rep(i,m)cin>>v[i];
	reverse(v.begin(), v.end());
	rep(i,m){
		if(!used[v[i]])cout<<v[i]<<endl;
		used[v[i]]=true;
	}
	rep1(i,n)if(!used[i])cout<<i<<endl;
	return 0;
}

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

template<class T> void chmax(T& a, T b) {
        if (a < b) {
                a = b;
        }
        return;
}

int main()
{
        int N; cin >> N;
        vector<vector<ll>> a(N, vector<ll>(3, 0));
        for (int i = 0; i < N; ++i) {
                cin >> a[i][0] >> a[i][1] >> a[i][2];
        }
        vector<vector<ll>> dp(N+1, vector<ll>(3, 0));
        for (int i = 0; i < N; ++i) {
                for (int j = 0; j < 3; ++j) {
                        for (int k = 0; k < 3; ++k) {
                                if (j == k) continue;
                                chmax(dp[i+1][k], dp[i][j] + a[i][k]);

                        }

                }

        }
#if 0
        for (int i = 0; i <= N; ++i) {
                for (int j = 0; j < 3; ++j) {
                        cout << dp[i][j] << " ";
                }
                cout << endl;
        }
#endif
        ll res = 0;
        for (int i = 0; i < 3; ++i)  chmax(res, dp[N][i]);
        cout << res << endl;
}


Measured memory_bytes: 11136
while 1:
    h,w=map(int,input().split())
    if h==w==0:break
    r=h**2+w**2
    d_m=float("inf")
    ax,ay=0,0
    for x in range(1,int(r**0.5)+2):
        y=int([(r-x**2),0][(r-x**2)<0]**0.5)
        y+=[1,0][r==x**2+y**2 and h<x]
        if x>=y:continue
        dia=x**2+y**2
        if d_m>dia:d_m,ax,ay=dia,x,y
    print(ax,ay)


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

int main(void){
    int n,k;
    cin >> n >> k;
    int h[n];
    rep(i,n){
        int x;
        cin >> x;
        h[i] = x;
    }
    int ans = 0;
    rep(i,n){
        if(h[i] >=k){
            ans++;
        }
    }
    cout << ans <<endl;
    
    return 0;
}




Measured memory_bytes: 640
//keshavs first usaco solve :)
 
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
 
		Scanner sc = new Scanner(System.in);
		int total = sc.nextInt();
      	int as = sc.nextInt();
      	int sum = 0;
      	for(int i = 0 ; i<as; i++) 
        {
          sum+= sc.nextInt();
        }
      	if(total-sum >= 0){
         System.out.println(total-sum); 
          
        }
      	else{
         System.out.println(-1); 
        }
	}
 
}

Measured memory_bytes: 46500
n = int(input())
a = list(map(int, input().split()))
cnt = 0
i = 0
while i < n - 1:
    if i < n - 2 and a[i] == a[i + 1] == a[i + 2]:
        cnt += 1
        i += 1
    elif a[i] == a[i + 1]:
        cnt += 1
    i += 1
print(cnt)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define IT iterator
#define vi vector<int>
#define TP template<class o>
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20,mod=998244353,inf=2e9;
const ll INF=1e15;

//char buf[size],*p1=buf,*p2=buf;
TP void qr(o &x) {
    char c=gc; x=0; int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
    while(isdigit(c)) x=x*10+c-'0',c=gc;
    x*=f;
}
TP void qw(o x) {
    if(x/10) qw(x/10);
    putchar(x%10+'0');
}
TP void pr1(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar(' ');
}
TP void pr2(o x) {
    if(x<0)x=-x,putchar('-');
    qw(x); putchar('\n');
}

//math
ll gcd(ll a,ll b) {return !a?b:gcd(b%a,a);}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
ll power(ll a,ll b=mod-2) {
    ll c=1;
    while(b) {
        if(b&1) c=c*a%mod;
        b /= 2; a=a*a%mod;
    }
    return c;
}

TP void cmax(o &x,o y) {if(x < y) x=y;}
TP void cmin(o &x,o y) {if(x > y) x=y;}

//dbinom

//ll jc[N],inv[N];
//void init(int n) {
//	jc[0]=1; for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
//	inv[n]=power(jc[n]); for(int i=n;i;i--) inv[i-1]=inv[i]*i%mod;
//}
//ll C(int x,int y) {
//	if(x<y || y<0) return 0;
//	return jc[x]*inv[y]%mod*inv[x-y]%mod;
//}

int n,m,vis[N],tot;
vi e[N];
void add(int x,int y) {e[x].pb(y);}

void dfs(int x) {
	vis[x]=tot;
	for(int y:e[x]) if(!vis[y]) dfs(y);
}

void solve() {
	qr(n); qr(m);
	for(int i=1,x,y;i<=m;i++) qr(x),qr(y),add(x,y),add(y,x);
	for(int i=1;i<=n;i++) if(!vis[i]) ++tot,dfs(i);
	pr2(tot-1);	
}

int main() {
	int T=1;
//	qr(T);
	while(T--)
		solve();
}





Measured memory_bytes: 12316
#include<bitset>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
char buf[2011];

const int SIZE = 2048;
using Bits = bitset<SIZE>;
Bits A[2011];
Bits L[2011], R[2011];

void MAIN() {
    scanf("%d", &N);
    for (int i=1; i<N; i++) {
	scanf("%s", buf);
	REP (j, i) {
	    if (buf[j] == '1') A[i].set(j);
	    else A[j].set(i);
	}
    }

    REP (i, N) {
	L[i].set(i);
	R[i].set(i);
    }
    for (int add=1; add<N; add++) {
	for (int i=N-1; i>=0; i--) {
	    int k = i+add;
	    if (k >= N) continue;

	    // L[i][k] = R[i+1][j] && L[j][k] && A[i][j];
	    L[k].set(i, (R[i+1] & L[k] & A[i]).any());

	    // R[i][k] = R[i][j] && L[j][k-1] && A[k][j];
	    R[i].set(k, (R[i] & L[k-1] & A[k]).any());
	}
    }

    int ans = (R[0] & L[N-1]).count();;
    printf("%d\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return a.second - a.first > b.second - b.first;
}

int main() {
    int N, k, i;
    for (;;) {
        std::scanf("%d %d", &N, &k);
        if (N == 0 && k == 0) break;
        int arr[k];
        int cnt0 = 0;
        std::vector< std::pair<int, int> > v;
        for (i = 0; i < k; i++) {
            std::scanf("%d", &arr[i]);
        }
        std::sort(arr, arr+k);
        for (i = 0; i < k; i++) {
            if (arr[i] != 0) break;
            cnt0++;
        }
        int idx = i;
        for (i = idx+1; i < k; i++) {
            if (arr[i] - arr[i-1] > 1) {
                v.push_back({idx, i-1});
                idx = i;
            }
        }
        v.push_back({idx, i-1});
        if (cnt0 == 0) {
            std::sort(v.begin(), v.end(), compare);
            std::cout << v[0].second - v[0].first + 1 << std::endl;
        } else {
            int global_max = 0, current_max = 0;
            int diff;
            for (int j = 0; j < v.size()-1; j++) {
                diff = cnt0;
                current_max = v[j].second - v[j].first+1;
                if (arr[v[j+1].first] - arr[v[j].second]-1 > diff) {
                    current_max += diff;
                    global_max = std::max(global_max, current_max);
                }
                else {
                    for (int k = j+1; k < v.size(); k++) {
                        if (arr[v[k].first]-arr[v[k-1].second]-1 > diff) {
                            current_max += diff;
                            break;
                        }
                        current_max += arr[v[k].second]-arr[v[k-1].second];
                        diff -= arr[v[k].first] - arr[v[k-1].second]-1;
                    }
                    global_max = std::max(global_max, current_max);
                }
            }
            std::cout << global_max << std::endl;
        }
    }

    return  0;
}



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

int main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    int min = 200000, ans = 0;
    ;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        if (min >= p[i])
        {
            min = p[i];
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var n = o.a();
  var a = o.l();
  var b = o.l();
  var ans = 0;
  for(var i = 28; i >= 0; i--){
    if(i < 17)b = f(b,i), a = f(a,i).reverse();
    else {b.sort((a,b)=>a-b); a.sort((a,b)=>b-a);}
    var t = 1 << i, t2 = t << 1, t3 = t*3, x = n, x1, x2, x3;
    x1 = x2 = x3 = 0;
    for(var j = 0; j < a.length; j++){
      while(x1 < b.length && t-a[j] > b[x1])x1++;
      while(x2 < b.length && t2-a[j] > b[x2])x2++;
      while(x3 < b.length && t3-a[j] > b[x3])x3++;
      x += -x3+x2-x1;
    }
    if(x % 2)ans += t;
    t--;
    b = b.map(a=>a&t);
    a = a.map(a=>a&t);
  }
  return ans;

  function f(b,n){
    var a = Array(1<<n+1).fill(0), r = [];
    for(var i = 0; i < b.length; i++){
      a[b[i]]++;
    }
    for(i = 0; i < a.length; i++)if(a[i]&1)r.push(i);
    return r;
  }
}

Measured memory_bytes: 107032
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>

using namespace std;

int main(void) {

	string s;

	cin >> s;

	int ok[s.size()] = {}, maxn = 0;

	for (int i = 0; i < s.size(); i++)
	{
		int num = 0;

		if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
			ok[i]++;
		}
		else {
			for (int p = 0; p < s.size(); p++)
			{
				ok[p] = 0;
			}
		}

		for (int k = 0; k < s.size(); k++)
		{
			if (ok[k] > 0)num++;
		}


		maxn = max(maxn, num);

		//printf("i=%d,maxn=%d\n", i, maxn);
	}

	cout << maxn << "\n";

	return 0;
}

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


int main() {
    ll n;
    cin >> n;
    ll ans = 0;
    rep(i, n){
        rep(j,n){
            rep(k,n){
                ans += gcd(i,gcd(j,k));
            }
        }
    }    
    cout << ans << endl;
}

Measured memory_bytes: 3636
import java.util.*;
public class Main{
    public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
    // Long A[] = new Long[N];
    HashMap<Long,Integer> map = new HashMap<Long,Integer>();
    Long sum = 0L;
    for(int i=0;i<N;i++){
      Long tmp = sc.nextLong();
      sum += tmp; 
      if(map.containsKey(tmp)){
        map.put(tmp,map.get(tmp)+1);
      }else{
        map.put(tmp,1);
      }
    }
    int Q = Integer.parseInt(sc.next());
    // System.out.println(Q+"q");
    Long A[] = new Long[Q];
    for(int i=0;i<Q;i++){
      // System.out.println(i+"i");
      Long B = sc.nextLong();
      Long C = sc.nextLong();
      if(map.containsKey(C) && map.containsKey(B)){
        int tmp2 = map.get(B);
        sum += (C - B)*tmp2;
        map.put(C,map.get(C)+tmp2);
        map.put(B,0);
      }else if(map.containsKey(C) && !map.containsKey(B)){
      }else if(!map.containsKey(C) && map.containsKey(B)){
        int tmp3 = map.get(B);
        sum += (C - B)*tmp3;
        map.put(C,tmp3);
        map.put(B,0);
      }
      A[i] = sum;
    }
    for(int i=0;i<Q;i++){
      System.out.println(A[i]);
    }


    // System.out.println(count);
  }
}

Measured memory_bytes: 74056
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

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

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

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

  cin >> n;
  int np = n;
  int nc = 0;
  while(np != 0) {
    np /= 10;
    nc++;
  }

  int nn = 1;
  int ans = 0;
  FOR(i, 1, nc + 1) {
    nn *= 10;
    if(i % 2 != 0) {
      if(i != nc) {
        ans += (nn - (nn / 10));
      } else {
        ans += (n - (nn / 10) + 1);
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256