akhauriyash/Code-Regression huggingface dataset:
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const set<T> &st) {
	for (const auto &e : st) os << e << " ";
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
	for (const auto &e : mp) os << e << " ";
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int bit_cnt(long bits){
	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

template<class T>
inline bool chmax(T &a, const T b) { return a < b && (a = b, true); }

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<vector<pair<int, int>>> xy(N);
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		xy[i].resize(a);
		for (int j = 0; j < a; j++) {
			int x, y;
			cin >> x >> y;
			x--;
			xy[i][j] = { x,y };
		}
	}

	DMP(xy);

	int ans = 0;
	for (int bit = 0b0; bit < (1 << N); bit++) {

		bool ok = true;
		for (int i = 0; i < N; i++) {

			if (bit & (1 << i)) {
				for (int j = 0; j < xy[i].size(); j++) {

					DMP(bit, (1 << xy[i][j].first), xy[i][j].second);
					if ((bit & (1 << xy[i][j].first)) != (xy[i][j].second << xy[i][j].first)) {
						ok = false;
						break;
					}

				}
			}
			if (!ok) break;

		}
		if (ok) chmax(ans, bit_cnt(bit));

	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for(int i = 1; i <= n; i+= 2) {
            int c = 0;
            for(int j = 1; j <= i; j++) if(i % j == 0) c++;
            if(c == 8) ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
// C - One Quadrillion and One Dalmatians
#include <bits/stdc++.h>
using namespace std;


int main(){
    long long n;
    cin >> n;
    string ans = "";
    while(n > 0){
        n -= 1;
        ans += ('a'+n%26);
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

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

  
int main(){
  int n;
  cin >>n;
  vector<ll> a(n);
  rep(i,n) cin >> a.at(i);
 sort(a.begin(),a.end());
  bool b=true;
  rep(i,n-1){
    if(a.at(i)==a.at(i+1)) b=false;
  }
  if(b) cout <<"YES" <<endl;
  else cout <<"NO" <<endl;
  
 
}
  

Measured memory_bytes: 1792
N = int(input())
A, B, C = input(), input(), input()
ans = 0
for i in range(N):
    if A[i] == B[i] == C[i]:
        pass
    elif A[i] != B[i] and B[i] != C[i] and C[i] != A[i]:
        ans += 2
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <tuple>
#include <iomanip>

using namespace std;

const int MOD = 1000000007;
typedef long long ll;

template<class T = ll>
struct Edge {
  int to;
  T cost;
  Edge() {}
  Edge(int to, T cost) : to(to), cost(cost) {}
  bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

template<class T = ll>
vector<T> Dijkstra(vector<vector<Edge<T>>> &edges, int st) {

  int V = (int)edges.size();
  const int INF = numeric_limits<T>::max();
  vector<T> dist(V, INF);
  dist[st] = 0;

  priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> p_que;
  p_que.emplace(dist[st], st);

  while (!p_que.empty()) {

    Edge<T> now(p_que.top().to, p_que.top().cost);
    p_que.pop();

    if (dist[now.to] < now.cost) continue;
    for (const Edge<T> &e : edges[now.to]) {
      T tmp_cost = now.cost + e.cost;
      if (dist[e.to] > tmp_cost) {
        dist[e.to] = tmp_cost;
        p_que.emplace(e.to, dist[e.to]);
      }
    }
  }

  return dist;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W;
  cin>>H>>W;
  vector<vector<Edge<int> > > edges(10);

  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      int c;
      cin>>c;
      int jj=j,ii=i;
      if(jj==0){
        jj=1;
      }else if(jj==1){
        jj=0;
      }
      if(ii==0){
        ii=1;
      }else if(ii==1){
        ii=0;
      }

      edges[jj].emplace_back(ii,c);
    }
  }
  auto dij = Dijkstra<int>(edges,0);

  vector<int> cost;
  for (auto& i : dij) {
    cost.push_back(i);
  }

  int ans=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      int tmp;
      cin>>tmp;
      if(tmp==0){
        tmp=1;
      }else if(tmp==1){
        tmp=0;
      }
      if(tmp!=-1){
        ans+=cost[tmp];
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
s = str(input())
k = int(input())
 
n = len(s)
l = [0] * n

for i in range(n-1):
    if s[i] == s[i+1] and l[i] == 0:
        l[i+1] = 1

if s.count(s[0]) == n:
    print(n*k//2)
elif s[0] != s[-1]:
    print(sum(l) * k)
else:
    a = 0
    b = 0
    ac = True
    bc = True
    for i in range(n-1):
        if s[i] == s[0] and ac == True:
            a += 1
        elif s[i] != s[0]:
            ac = False
        if s[n-1-i] == s[n-1] and bc == True:
            b += 1
        else: bc = False  
    sub = a//2 + b//2 - (a+b)//2
    print(sum(l)*k - sub*(k-1))

Measured memory_bytes: 9152
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cmath>
#include <climits>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)
#define rep1(i, n) for(int i = 1; i <= (int) n; i++)
#define all(v) v.begin(),v.end()
const long double PI = 3.14159265358979323846;
 
int main() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    int len = min((int)s.size(),k);
    rep(i,len) {
        cout << s[i];
    }
    if ((int)s.size() > k) {
        cout << "...";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3628
N = int(input())
A = list(map(int, input().split()))
L = []
n = 0
a = 0
for i in range(1,N+1):
    if n >= N:
        break
    elif a == N-1:
        break
    else:
        for j in range(n,N):
            if A[j] == i:
                L.append(A[j])
                n = j+1
                break
            elif j == N-1:
                a = N-1
                break
if L != []:
    print(len(A)-len(L))
elif len(A) == 1:
    print(0)
else:
    print(-1)

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

int main() {
  string s;
  cin >> s;
  string result;
  if (s[0] == s[1] && s[1] == s[2]) {
    result = "No";
  } else {
    result = "Yes";
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: usize = input();
    let k: usize = input();
    let l: usize = input();
    let pq: Vec<(usize, usize)> = (0..k)
        .map(|_| {
            let p = input();
            let q = input();
            (p, q)
        })
        .collect();
    let rs: Vec<(usize, usize)> = (0..l)
        .map(|_| {
            let r = input();
            let s = input();
            (r, s)
        })
        .collect();

    let mut uf_k = UnionFind::new(n);
    for (p, q) in pq {
        uf_k.union(p - 1, q - 1);
    }
    let mut uf_l = UnionFind::new(n);
    for (r, s) in rs {
        uf_l.union(r - 1, s - 1);
    }

    let mut u = vec![];
    let mut m = std::collections::HashMap::new();
    for i in 0..n {
        let x = (uf_k.find(i), uf_l.find(i));
        u.push(x);
        let e = m.entry(x).or_insert(0);
        *e += 1;
    }

    for i in 0..n {
        let x = u[i];
        print!("{} ", m.get(&x).unwrap());
    }
}

struct UnionFind {
    parent: Vec<usize>,
    size: Vec<i64>,
}
impl UnionFind {
    fn new(n: usize) -> UnionFind {
        let mut p = vec![0; n];
        for i in 0..n {
            p[i] = i;
        }
        UnionFind {
            parent: p,
            size: vec![1; n],
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] == x {
            x
        } else {
            let p = self.parent[x];
            self.parent[x] = self.find(p);
            self.parent[x]
        }
    }

    fn union(&mut self, x: usize, y: usize) {
        let mut x = self.find(x);
        let mut y = self.find(y);
        if x != y {
            if self.size[x] < self.size[y] {
                let t = x;
                x = y;
                y = t;
            }
            self.parent[y] = x;
            self.size[x] += self.size[y];
        }
    }
}


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

int main()
{
    string S, T;
    int N, ans=0;
    cin >> S >> T;
    N = S.size();

    for(int i=0; i<N; i++){

        if(S.at(i)==T.at(i)){

        }else{
            ans++;
        }
    }
    cout <<  ans;   
    
    
}

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

#define task "D" //ABC136
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define pb push_back
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;

// Limit

// Struct

// Variables
string s;
vi v;
int ans[100005];
// Function

int main()
{
	//freopen(task".in","r",stdin);
	//freopen(task".out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	cin >> s;
	int n=s.size();
	rep(i,0,n-2) if (s[i]=='R'&&s[i+1]=='L') v.pb(i+1);
	rep(i,0,n-1)
	{
	    if (s[i]=='R')
        {
            //int pos=lower_bound(v.begin(),v.end(),i)-v.begin();
            int ipos=(*lower_bound(ALL(v),i));
            if ((ipos-i)%2==0) ans[ipos]++;
            else ans[ipos-1]++;
        } else
        {
            int ipos=*(upper_bound(ALL(v),i)-1);
            if ((i-ipos)%2==0) ans[ipos]++;
            else ans[ipos-1]++;
        }
	}
	rep(i,0,n-1) cout << ans[i] << ' ';

}


Measured memory_bytes: 1232
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<ll, ll>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%MOD+MOD)%MOD) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

/* -- template -- */

int main() {
    int K, A, B;
    cin >> K >> A >> B;
    for(int i = A; i <= B; ++i) {
        if(i % K == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


Measured memory_bytes: 3636
h,n=map(int,input().split())
a=[0]*n
b=[0]*n
inf=10**10
for i in range(n):
    a[i],b[i]=map(int,input().split())
dp = [[inf for i in range(h+1)] for j in range(n+1)]
for i in range(n):
    cnt=1
    for j in range(h+1):
            if j-a[i]<0:
                dp[i+1][j]=min(dp[i][j],dp[i][0]+b[i],b[i]*cnt)
            else:
                dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i]]+b[i],dp[i][j-a[i]]+b[i],b[i]*cnt)
                cnt+=1
"""
for i in range(1,n+1):
    for j in range(h+1):
        if j+a[i]<=h:
            dp[i+1][j+a[i]]=min(dp[i+1][a[i]],dp[i][j]+b[i])"""
print(dp[n][h])
#print(dp)


Measured memory_bytes: 125788
# 入れ子で引き算、setでかぶりを消して、sorted,reverseで降順にし、0番を出す
N = int(input())
A = list(map(int, input().split()))
sub = []

for i in A:
    for j in A:
        sub.append(abs(i - j))

descending_sub = sorted(set(sub), reverse=True)
# print(descending_sub)

print(descending_sub[0])


Measured memory_bytes: 9900
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int H = Integer.parseInt(sc.next());
		int W = Integer.parseInt(sc.next());
		String[] text = new String[H];
		for(int i=1;i<=H;i++){
			text[i-1] = sc.next();
		}
		for(int i=1;i<=W+2;i++){
			System.out.print("#");
		}
		System.out.println("");
		for(int i=1;i<=H;i++){
			System.out.println("#"+text[i-1]+"#");
		}
		for(int i=1;i<=W+2;i++){
			System.out.print("#");
		}
	}
}

Measured memory_bytes: 23252
import           Data.Functor ((<$>))

check :: Int -> Int -> Int -> Int -> Int -> Bool
check w h x y r
    | x - r < 0 = False
    | x + r > w = False
    | y - r < 0 = False
    | y + r > h = False
    | otherwise = True

main :: IO ()
main = do
    [w,h,x,y,r] <- fmap read . words <$> getLine :: IO [Int]
    if check w h x y r
       then putStrLn "Yes"
       else putStrLn "No"



Measured memory_bytes: 3584
#include<stdio.h>
#define MAX 100000
int A[MAX];
int partition(int p, int r){
    int i,x,j,change;
    x = A[r];
    i = p-1;
    for(j = p; j < r; j++){
        if(A[j] <= x){
            i = i+1;
            change = A[i];
            A[i] = A[j];
            A[j] = change;
        }
    }
    change = A[i+1];
    A[i+1] = A[r];
    A[r] = change;
    return i+1;
}

int main(){
    int n,i,j,r,p;
    scanf("%d",&n);
    for(i = 0;i < n;i++){
        scanf("%d",&A[i]);
    }
    p = partition(0,n-1);
    for(i = 0;i < p;i++){
        printf("%d ",A[i]);
    }
    printf("[%d] ",A[p]);
    for(i = p+1;i<n-1;i++){
        printf("%d ",A[i]);
    }
    printf("%d\n",A[n-1]);
    return 0;
}

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

akun = [0]*N
count = N

for i in range(K):
    di = int(input())
    tmp = list(map(int,input().split()))
    for j in tmp:
        if akun[j-1] == 0:
            akun[j-1] +=1
            count -=1

print(count)


Measured memory_bytes: 9180
# D - String Equivalence
abc = "abcdefghij"


def dfs(n: int) -> list:
    if n == 1:
        return ["a"]
    cur = dfs(n - 1)
    result = []
    for s in cur:
        for c in abc[: len(set(s)) + 1]:
            result.append(s + c)
    return result


def main():
    N = int(input())
    result = dfs(N)
    result.sort()
    print("\n".join(result))


if __name__ == "__main__":
    main()


Measured memory_bytes: 15380
while True:
    q = int(input())
    if q == -1: break
    x = q/2
    err = abs(x**3 - q)
    while err >= 0.00001*q:
        x = x - (x**3 - q)/(3*x**2)
        err = abs(x**3 - q)
    print(x)



Measured memory_bytes: 5656
#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 RREP(i,n) for(int i=n-1;i>=0;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;

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

  cin >> s >> q;

  string s_f, s_b;
  int count = 0;

  REP(i, q) {
    int t;
    cin >> t;
    if(t == 1) {
      count++;
    } else {
      int f;
      char c;
      cin >> f >> c;
      if((f + count) % 2 == 1) s_f.push_back(c);
      else s_b.push_back(c);
    }
  }

  if(count % 2 == 0) {
    RREP(i, s_f.size()) cout << s_f[i];
    REP(i, s.size()) cout << s[i];
    REP(i, s_b.size()) cout << s_b[i];
    cout << endl;
  } else {
    RREP(i, s_b.size()) cout << s_b[i];
    RREP(i, s.size()) cout << s[i];
    REP(i, s_f.size()) cout << s_f[i];
    cout << endl;
  }
}


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

#define MAX 1000000

int main() {
  int k, x;
  int start, end;
  cin >> k >> x;
  
  start = x - k + 1;
  if (start < -MAX)
    start = -MAX;
  
  end = x + k - 1;
  if (end > MAX)
    end = MAX;

  for (int i = start; i <= end; i++)
    cout << i << " ";
  
  return 0;
}

Measured memory_bytes: 256
use std::io;

/// 一行を読み込んで、空白で区切ったベクタにして返す
#[allow(dead_code)]
fn read<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect()
}

/// n行を読み込んで、数字を空白で区切って二次元のベクタにして返す
#[allow(dead_code)]
fn read_table<T>(n: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut ret: Vec<Vec<T>> = Vec::new();
    for _ in 0..n {
        ret.push(read::<T>());
    }
    ret
}

/// n行を読み込んで、1文字ずつを二次元のベクタにして返す
#[allow(dead_code)]
fn read_char_table(n: usize) -> Vec<Vec<char>> {
    let mut ret: Vec<Vec<char>> = Vec::new();
    for _ in 0..n {
        let mut buf = String::new();
        io::stdin().read_line(&mut buf).unwrap();
        let chr = buf.trim().chars().collect();
        ret.push(chr);
    }
    ret
}

/// n行を読み込んで、一次元のベクタにして返す
#[allow(dead_code)]
fn read_array<T>(n: usize) -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut array = Vec::new();

    for _ in 0..n {
        let mut buf = String::new();
        io::stdin().read_line(&mut buf).unwrap();
        array.push(buf.trim().parse().unwrap());
    }
    array
}

fn main() {
    let n = read::<String>();
    let n = &n[0];

    let mut sn: u64 = 0;

    for c in n.chars() {
        sn += c.to_digit(10).unwrap() as u64;
    }

    let n: u64 = n.parse().unwrap();
    if n % sn == 0 {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

long long dp[4009][4009], N, K, mod = 998244353;

void init() {
	for (int i = 0; i < 4009; i++) {
		for (int j = 0; j < 4009; j++) {
			if (i == 0 || j == 0) dp[i][j] = 1;
			else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
}
long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return dp[r][n - r];
}

int main() {
	cin >> K >> N; init();
	for (int i = 1; i <= 2 * K - 1; i++) {
		int Z = min(i - 1, (int)(2 * K - 1) - i); Z /= 2; Z++;

		long long ans = 0;
		for (int j = 0; j <= Z; j++) {
			long long p1 = ncr(Z, j);
			long long p2 = ncr((N - j) + (K - Z - 1), K - Z - 1);
			ans += (p1 * p2) % mod; ans %= mod;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 125824
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

constexpr int64_t kModBase = 1'000'000'007;

int64_t pow3(int64_t b) {
  static int64_t cache[100'001];
  if(b == 0) return 1;
  if(cache[b]) return cache[b];
  int64_t half_pow = pow3(b / 2);
  cache[b] = half_pow * half_pow * ((b & 1) ? 3 : 1) % kModBase;
  return cache[b];
}

int64_t solve(const char *s, int64_t len) {
  int64_t ans = pow3(len - 1);
  const char *p = s;
  p++;
  while (*p == '0') p++;
  ans += 2 * (*p == '1' ? solve(p, len - (p - s)) : 1);
  return ans % kModBase;
}

int main(int argc, char *argv[]) {
  string s;
  cin >> s;
  cout << solve(s.c_str(), s.size()) << endl;
  return 0;
}


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

using ll = long long;

int const N = 200 * 1000 + 16;
int const M = 1000 * 1000 * 1000 + 7;

int n, W;
int v[128];
int w[128];
map<pair<int,int>, int> dp;

int f(int i, int j) {
  if(i == n)
    return 0;
  auto x = dp.find({i, j});
  if(x != dp.end())
    return x->second;
  
  int& ans = dp[{i, j}];
  if(w[i] <= j)
    ans = v[i] + f(i+1, j-w[i]);

  ans = max(ans, f(i+1, j));
  return ans;
}

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  cin >> n >> W;
  for(int i = 0; i < n; ++i)
    cin >> w[i] >> v[i];

  int ans = f(0, W);

  cout << ans << endl;
}

Measured memory_bytes: 6272
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

    //Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    String res;
    int in = cin.nextInt();

    if (in==25) {
      res = "Christmas";
    }
    else if (in==24) {
      res = "Christmas Eve";
    }
    else if (in==23) {
      res = "Christmas Eve Eve";
    }
    else {
      res = "Christmas Eve Eve Eve";
    }
    System.out.println(res);

  }

}


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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi >

int main()
{
  ios::sync_with_stdio(0), cin.tie(0);
    int n,a,b;
    cin>>n>>a>>b;
    if(((b-a)%2!=1&&(n-b+n-a)%2!=1)||((a-1+b-1)%2!=1&&(a-1+n-b+n-1)%2!=1))
      cout<<"Alice";
    else if(((b-a)%2==1&&(a-1+b-1)%2==1)||((n-b+n-a)%2==1&&(n-b+a-1+n-1)%2==1))
      cout<<"Borys";
    else
      cout<<"Draw";
  return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100100)

n = int(input())
route = [[] for i in range(n)]
for i in range(n-1):
	u, v, w = map(int,input().split())
	route[u-1].append((v-1,w))
	route[v-1].append((u-1,w))
	
ans=[-1]*n
def dfs(p,d):
	ans[p] = d
	for i,j in route[p]:
		if ans[i] < 0:
		    dfs(i, (d+j) % 2)
dfs(0,0)

for i in range(n):
	print(ans[i])

Measured memory_bytes: 79408
#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	string S;
	scan(S);
	if(S[2]==S[3]&&S[4]==S[5]) prin("Yes");
	else prin("No");
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 10000000007

int main() {
	ll a,b;
	cin>>a>>b;
	cout << max(ll(0),a-2*b);
	// your code goes here
	return 0;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

int n,ans,cnt;
string s = "ACGT",memo[14] = {"AACG","AAGC","AGAC","AGGC","AGTC","ATGC","CACG","CAGC","CGAC","GAGC","GGAC","TACG","TAGC","TGAC"};


map<string,int> m;

main() {
    clock_t start = clock();
    ans = pow(4,3);
    rep(i,4) rep(j,4) rep(k,4) {
        string stmp;
        stmp.pb(s[i])
        stmp.pb(s[j])
        stmp.pb(s[k])
        if (stmp == "AGC" || stmp == "GAC" || stmp == "ACG") ans--;
        else m[stmp]++;
    }
    cin >> n;
    rep(i,n-3) {
        ans = (ans*4)%MOD;
        map<string,int> tmpm;
        for(auto j : m) {
            string tmps = j.fi;
            if (i) rep(k,3) tmps[k] = tmps[k+1];
            else tmps.pb('a')
            rep(k,4) {
                string tmptmps = tmps;
                bool f = true;
                tmptmps[3] = s[k];
                rep(l,14) if (tmptmps == memo[l]) f = false;
                if (f) tmpm[tmptmps] = (tmpm[tmptmps]+j.se)%MOD;
                else ans = (ans-j.se+MOD) %MOD;
            }
        }
        m = tmpm;
    }
    cout << ans << endl;
}



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

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

int main() {
    long long A, B, C, K;
    cin >> A >> B >> C >> K;
    if(A+B >= K){
        cout << std::min(A,K) << endl;
    } else {
        cout << A - (K- A -B) << endl;
    }
}

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

int main() {
  long long n;
  cin >> n;
  if(n%2==1) {
    cout << 0;
    return 0;
  }else{
    long long ans=0;
    long long i=0;
    long double p=10.0;
    while(true){
      if(n<p) break;
      ans+=floor(n/p);
      p*=5;
    }
    cout << ans;
    return 0;
  }
}


Measured memory_bytes: 256
#include <set>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=1e5+5;
 
int fa[N];
std::set<int> st[N];
std::pair<int,int> q[N];
 
inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
int Find(int x)
{
	return x==fa[x]?x:fa[x]=Find(fa[x]);
}
 
int main()
{
	const int n=read();
	int h=0,t=0;
	for(int i=n-1<<1; i; --i)
	{
		int u=read(),v=read();
//		if(u>v) std::swap(u,v);
		if(!st[u].count(v)) st[u].insert(v), st[v].insert(u);
		else q[t++]=std::make_pair(u,v);
	}
	for(int i=1; i<=n; ++i) fa[i]=i;
	while(h<t)
	{
		int x=Find(q[h].first),y=Find(q[h++].second);
		if(st[x].size()<st[y].size()) std::swap(x,y);//x<-y
		for(std::set<int>::iterator it=st[y].begin(); it!=st[y].end(); ++it)
			if(*it!=x)
			{
				int u=x,v=*it;
				st[v].erase(y);
//				if(u>v) std::swap(u,v);
				if(!st[u].count(v)) st[u].insert(v), st[v].insert(u);
				else q[t++]=std::make_pair(u,v);		
			}
		st[x].erase(y), fa[y]=x;
	}
	puts(t==n-1?"YES":"NO");
 
	return 0;
}

Measured memory_bytes: 27136
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);
	        int H = 55555;
	        int[] m = new int[H];
	        int[] p = new int[H];
	        int k=0;
	        m[1]=1;
	        int cnt=0;
	        int[] ans = new int[2000];
	        for(int i=2;i<H;i++) {
	        	if(m[i]==0) {
	        		m[i]=1;
	        		p[k]=i;
	        		k++;
	        		if(i%5==1) {
	        			ans[cnt]=i;
	        			cnt++;
	        		}
	        		for(int j=i+i;j<H;j=j+i) {
	        			m[j]=i;
	        		}
	        	}
	        }
	        
	        int N = sc.nextInt();
	        
	        for(int i=0;i<N;i++) {
		        System.out.print(ans[i]);
		        if(i!=N-1) {
			        System.out.print(" ");		        	
		        }
	        }
	    }
	}

Measured memory_bytes: 22100
s=input()
t=input()

if len(set(t)-set(s))>0:
  print(-1)
else:
  s2=s*2
  s2pos={}
  for i in range(len(s2)):
    if s2[i] in s2pos:
      s2pos[s2[i]].append(i)
    else:
      s2pos[s2[i]]=[i]

  cur=-1
  import bisect
  rev=0
  for c in t:
    cur+=1
    pos=s2pos[c]
    p=bisect.bisect_left(pos,cur)
    cur=pos[p]
    if cur>=len(s):
      cur-=len(s)
      rev+=1
  else:
    print(rev*len(s)+cur+1)


Measured memory_bytes: 12148
#include <algorithm>
#include <cstdio>
using namespace std;
static const double EPS = 1e-9;
int main(){
	double a,b,c,d,e,f;
	while(~scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)){
		double x = (b*f-e*c)/(b*d-e*a);
		double y = (c-a*x)/b;
		printf("%.3lf %.3lf\n",x+EPS,y+EPS);
	}
}

Measured memory_bytes: 1084
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll 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;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b) {
  return b ? GCD(b,a%b) : a;
}


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}

ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


string Toupper(string s){
  string ans="";
  rep(i,s.size()){
    if('a'<=s[i] && s[i]<='z') ans+=(char)s[i]-32;
    else ans+=s[i];
  }
  return ans;
}
string Tolower(string s){
  string ans="";
  rep(i,s.size()){
    if('A'<=s[i] && s[i]<='Z') ans+=(char)s[i]+32;
    else ans+=s[i];
  }
  return ans;
}


const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*bool cmp(pint a, pint b) { return a.second < b.second; }*/

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n;
  cin>>n;
  vector<ll> v(n);
  rep(i,n) cin>>v[i];
  ll cnt=0;
  rep(i,n){
    if(v[i]%2==1) cnt++;
  }
  if(cnt%2==0) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int const INF = 1001001001;


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

int n;
cin >> n;

vi a(n);
rep(i,n) cin >> a[i];

map<int,int> mp;

rep(i,n) mp[a[i]]++;

for(auto x : mp){
    if(x.second >= 2){
        cout << "NO" << endl;
        return 0;
    }
}

cout << "YES" << endl;

return 0;
}

Measured memory_bytes: 10368
using System;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            int max = 0;
            for(int i=1; i < n - 1; i++)
            {
                string s1 = s.Substring(0, i);
                string s2 = s.Substring(i);
                int count = 0;
                for(char j = 'a'; j <= 'z'; j++)
                {
                    if (s1.IndexOf(j) != -1 && s2.IndexOf(j) != -1) count++;
                }
                if (max < count) max = count;
            }
            Console.WriteLine(max);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define Debug printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define debug(x) cerr<<#x<<'='<<x<<endl
#define mem(x,val) memset(x,val,sizeof x)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
    template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
    bool IN(ll x,ll l,ll r){return l<=x and x<=r;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=4e2+10;

    int n,m,dis[N][N];int id(int x,int y){return (x-1)*m+y;}
    char str[N][N];
    const int tx[]={0,0,-1,1};
    const int ty[]={-1,1,0,0};
    void main()
	{
        n=qread(),m=qread();fo(i,1,n) scanf("%s",str[i]+1);mem(dis,0x3f);
        fo(i,1,n) fo(j,1,m) dis[id(i,j)][id(i,j)]=0;
        fo(i,1,n) fo(j,1,m) fo(t,0,3) if(str[i][j]=='.')
        {
            int i2=i+tx[t],j2=j+ty[t];if(i2<1 or i2>n or j2<1 or j2>m) continue;
            if(str[i2][j2]!='.') continue;dis[id(i,j)][id(i2,j2)]=dis[id(i2,j2)][id(i,j)]=1;
        }
        fo(k,1,n*m) fo(i,1,n*m) fo(j,1,n*m) chmin(dis[i][j],dis[i][k]+dis[k][j]);
        int mx=0;fo(i,1,n*m) fo(j,1,n*m) if(dis[i][j]!=dis[0][0]) chmax(mx,dis[i][j]);write(mx);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}


Measured memory_bytes: 1024
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

struct town {
  ll x;
  ll y;
  int id;
};

struct edge {
  ll cost;
  int src;
  int dst;
};

struct uf {
  int n;
  VI p;
  uf(int n) : n(n), p(n) {
    REP(i,0,n) {
      p[i] = i;
    }
  }
  int root(int x) {
    if(p[x] == x) return x;
    return p[x] = root(p[x]);
  }
  void unite(int x, int y) {
    p[root(x)] = root(y);
  }
  bool find(int x, int y) {
    return root(x) == root(y);
  }
};

int main() {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<town> ts(N);
  FOR(t,ts) {
    cin >> t.x >> t.y;
  }
  REP(i,0,N) {
    ts[i].id = i;
  }
  vector<edge> es;
  sort(ts.begin(), ts.end(), [](town a, town b){return a.x < b.x;});
  REP(i,0,N-1) {
    town a = ts[i];
    town b = ts[i+1];
    es.push_back({b.x-a.x, a.id, b.id});
  }
  sort(ts.begin(), ts.end(), [](town a, town b){return a.y < b.y;});
  REP(i,0,N-1) {
    town a = ts[i];
    town b = ts[i+1];
    es.push_back({b.y-a.y, a.id, b.id});
  }
  sort(es.begin(), es.end(), [](edge a, edge b){return a.cost < b.cost;});
  uf u(N);
  ll ans = 0;
  FOR(e,es) {
    if(u.find(e.src, e.dst)) continue;
    ans += e.cost;
    u.unite(e.src, e.dst);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8816
import numpy as np
h, n = map(int, input().split())
ab = np.array([np.fromstring(input(), dtype=np.int64, sep=" ") for _ in range(n)])

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(10**6, dtype=np.int)

for i in range(1,h+1):
    dp[i] = min(dp[i-a]+b)

print(dp[h])

Measured memory_bytes: 14688
n = int(input())
A = [int(i) for i in input().split()]
thres = 10**18
if 0 in A:
    print(0)
else:
    ans = 1
    for i in A:
        ans *= i
        if ans > thres:
            print(-1)
            break
    else:
        print(ans)

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

#define rep(i, n) for(int i=0; i<n; ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
#define ll long long int

int main(){
   int h, w, k;
   cin>>h>>w>>k;
   char c[6][6];
   rep(i, h) rep(j, w) cin>>c[i][j];

   ll ans=0;
   rep(co, (1<<(h+w))){
      int cnt=0;
      rep(i, h) if((co>>w+i)&1) rep(j, w) if((co>>j)&1) if(c[i][j]=='#') cnt++;
      if(cnt==k) ans++;
   }

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


Measured memory_bytes: 3572
n = int(input())
h = list(map(int,input().split()))
flug = 1
for i in range(n-1):
  if h[i] <= h[i+1]-1:
    h[i+1]-=1
  elif h[i] > h[i+1]:
    flug = 0
    break
if flug == 1:
  print('Yes')
else :
  print('No')

Measured memory_bytes: 14396
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(2, 3, 9), 'No')

    def test_2(self):
        self.assertEqual(think(2, 3, 10), 'Yes')


def solve():
    a, b, c = read()
    result = think(a, b, c)
    write(result)


def read():
    return read_int(3)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a, b, c):
    d = c - a - b
    return 'Yes' if d ** 2 > 4 * a * b and d > 0 else 'No'


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Measured memory_bytes: 50952
#include<bits/stdc++.h>
using namespace std;
namespace io{
	const int l=1<<20;
	char buf[l],*s,*t,c;
	inline void gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			c=s==t?EOF:*s++;
		}else c=*s++;
	}
	template<class IT>inline void gi(IT &x){
		x=0;gc();while(c<'0'||c>'9')gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}
	}
	char buf0[20];int a;
	template<class IT>inline void pi(IT x){
		if(x<0){putchar('-');x=-x;}
		do buf0[++a]=x%10+48;while(x/=10);
		while(a)putchar(buf0[a--]);
		putchar('\n');
	}
};
using io::gi;
using io::pi;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll > pil;
typedef pair<ll ,int> pli;
typedef pair<ll ,ll > pll;
#define pque priority_queue
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const int N=105;
vector<int>e[N][N];
int f[N][N],a[N][N],s[N][N],p[N],vis[N],nn;
bool dfs(int v){
	int i;
	rep(i,1,nn)if(vis[i]&&f[v][i]){
		vis[i]=0;
		if(!p[i]||dfs(p[i])){p[i]=v;return true;}
	}
	return false;
}
int main(){
	int n,m,i,j,x;
	scanf("%d%d",&n,&m);nn=n;
	rep(i,1,n){
		rep(j,1,m){
			scanf("%d",&x);
			e[i][(x-1)/m+1].pb(x);
		}
	}
	rep(i,1,n)rep(x,1,n)f[i][x]=e[i][x].size();
	rep(j,1,m){
		rep(i,1,n)p[i]=0;
		rep(i,1,n){
			rep(x,1,n)vis[x]=1;
			dfs(i);
		}
		rep(i,1,n){x=p[i];s[j][x]=e[x][i][--f[x][i]];e[x][i].pob();}
	}
	rep(i,1,n){rep(j,1,m)printf("%d ",s[j][i]);printf("\n");}
	rep(j,1,m)sort(s[j]+1,s[j]+n+1);
	rep(i,1,n){rep(j,1,m)printf("%d ",s[j][i]);printf("\n");}
	return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long x = sc.nextLong();
        long y = sc.nextLong();

        long sum = 0;

        if ((a + b) > (c * 2)) {
            long cbuy = Math.min(x, y);
            sum = sum + ((c * 2) * cbuy);
            x = x - cbuy;
            y = y - cbuy;
        }

        if (a > (c * 2)) {
            long cbuy = x;
            sum = sum + ((c * 2) * cbuy);
            x = x - cbuy;
        }

        if (b > (c * 2)) {
            long cbuy = y;
            sum = sum + ((c * 2) * cbuy);
            y = y - cbuy;
        }

        sum = sum + (a * x);
        sum = sum + (b * y);

        System.out.println(sum);
    }
}

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

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

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

int main(){
  int n;
  cin >> n;
  int p[n];
  REP(i, n) cin >> p[i];
  int res = 0;
  for(int i=1; i<n-1; i++){
  if(p[i-1]<p[i] && p[i]<p[i+1]) res++;
  if(p[i-1]>p[i] && p[i]>p[i+1]) res++;

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

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}

int main(){
	int X,Y,Z;scanf("%d%d%d",&X,&Y,&Z);
	printf("%d\n",(X-Z)/(Y+Z));
}

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

int main(void){
  int L, R, d;
  cin >> L >> R >> d;

  int ans = 0;
  for(int i = L; i <= R; i++){
    if(i%d == 0){
      ans = ans + 1;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define REPEACH(i, k) for (auto &i : k)
#define all(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

const ll INF = 1LL << 60;

signed main()
{
	int h, w, n;
	cin >> h >> w >> n;
	queue<int> q;
	REP(i, n)
	{
		int a;
		cin >> a;
		while(a!=0){
			a--;
			q.push(i+1);
		}
	}
	vector<vector<int>> v(h,vector<int>(w));
	REP(i,h/2){
		i*=2;
		REP(j,w){
			v[i][j]=q.front();
			q.pop();
		}
		i++;
		IREP(j,w){
			v[i][j] = q.front();
			q.pop();
		}
		i=(i-1)/2;
	}
	if(h%2==1){
		int i=h-1;
		REP(j, w)
		{
			v[i][j] = q.front();
			q.pop();
		}
	}
	REP(i,h){
		REP(j,w){
			cout << v[i][j];
			if(j==w-1){
				cout << endl;
			}
			else{
				cout << " ";
			}
		}
	}
}

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

typedef pair<long long, long long> ii;

int main(){
	//freopen("i.txt","r",stdin);
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	ii arr[n];
	for(int i = 0;i < n;i++){
		cin >> arr[i].first >> arr[i].second;
	}
	
	sort(arr,arr+n);
	
	long double ans = 0.0;
	do{
		long double len = 0.0;
		for(int i = 0;i < n-1;i++){
			long double a = arr[i].first;
			long double b = arr[i].second;
			long double c = arr[i+1].first;
			long double d = arr[i+1].second;
			len += sqrt((d-b)*(d-b) + (c-a)*(c-a));
		}
		ans += len;
	}while(next_permutation(arr,arr+n));
	for(int i = 1;i <= n;i++){
		ans /= (double) i;
	}
	cout << std::setprecision(14) << ans;
}


Measured memory_bytes: 256