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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
    int x, a, b; cin >> x >> a >> b;
    if(abs(x - a) < abs(x - b)) cout << 'A' << endl;
    else cout << 'B' << endl;
    return 0;
}

Measured memory_bytes: 3640
function Main (input) {
  input = input.split("\n")[0].split(" ").map(inp => parseInt(inp, 10));
  var ans = "No";
  var a = input[0], b = input[1], c = input[2];
  if (a == b && a != c) ans = "Yes";
  else if (a == c && a != b) ans = "Yes";
  else if (b == c && a != b) ans = "Yes";
  console.log(ans);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include<iostream>
#include<map>

int main(){
    int n;
    std::cin >> n;

    long long ans = 1;
    long long mod = 1e9 + 7;

    std::map<int, long long> mp;

    for(int i = 2; i <= n; i++){
        int d = i;
        for(int j = 2; j * j <= d; j++){ //素因数分解を高速化しておく
            while(d % j == 0){
                d /= j;
                mp[j]++;
            }
        }
      if(d != 1) mp[d]++; //上記の高速化した素因数分解では, 最後に残る素数をうまくカウントできないため, d != 1の場合は最後にインクリメントしておく
    }

    for(auto p : mp) ans = ans * (1 + p.second) % mod;
    std::cout << ans << std::endl;

}

Measured memory_bytes: 256
#include <stdio.h>
#define ENU 500000
#define INF 1000000000

void mergeSort(int S[], int, int);
void merge(int S[], int, int, int);
int left, right, S[ENU], enu, count = 0;


int main() {
	int i, j;

	scanf("%d", &enu);
	for (i = 0; i < enu; i++) {
		scanf("%d", &S[i]);
	}
	left = 0;
	right = enu;
	mergeSort(S, left, right);
	for (i = 0; i < enu - 1; i++) {
		printf("%d ", S[i]);
	}
	printf("%d\n", S[enu - 1]);
	printf("%d\n", count);
	return 0;
}


void mergeSort(int S[], int left, int right) {
	if (left + 1 < right) {
		int mid = (left + right) / 2;
		mergeSort(S, left, mid);
		mergeSort(S, mid, right);
		merge(S, left, mid, right);
	}
}

void merge(int S[], int left, int mid, int right) {
	int n1, n2, i, j, k;
	n1 = mid - left;
	n2 = right - mid;

	int L[n1], R[n2];
	for (i = 0; i < n1; i++) {
		L[i] = S[left + i];
	}
	for (j = 0; j < n2; j++) {
		R[j] = S[mid + j];
	}

	L[n1] = INF;
	R[n2] = INF;
	i = 0;
	j = 0;

	for (k = left; k < right; k++) {
		count++;
		if (L[i] <= R[j]) {
			S[k] = L[i];
			i++;
		}
		else {
			S[k] = R[j];
			j++;
		}
	}
}




Measured memory_bytes: 5600
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);
    private static final long DIV = 1000000007;

    public static void main(String[] args) {
	int n = Integer.parseInt(scan.next());
	int m = Integer.parseInt(scan.next());
	long[] x = new long[n];
	long[] y = new long[m];
	
	for (int i = 0; i < n; i++) {
	    x[i] = Long.parseLong(scan.next());
	}
	for (int i = 0; i < m; i++) {
	    y[i] = Long.parseLong(scan.next());
	}

	long sumX = 0;
	for (int i = 1; i <= n; i++) {
	    long add = ((2*i-1-n)*x[i-1]) % DIV;
	    sumX = (sumX + add) % DIV;
	}
	long sumY = 0;
	for (int i = 1; i <= m; i++) {
	    long add = ((2*i-1-m)*y[i-1]) % DIV;
	    sumY = (sumY + add) % DIV;
	}

	System.out.println((sumX * sumY) % DIV);
	scan.close();
    }
}


Measured memory_bytes: 51012
#include<bits/stdc++.h>
using namespace std;
    static const double pi = 3.141592653589793;
 typedef pair<int64_t,int64_t> P;
#define rep(i, n) for (int i = 0; i < (n); i++)
 int64_t dp[105][100005];

int main() {
int64_t a,b;
  cin>>a>>b;
int64_t value[a]; 
int64_t weight[a];
  rep(i,a) cin>>weight[i]>>value[i];
 
  rep(i,a){
    
  dp[0][i]=0;
  
  }
  for(int i=0;i<a;i++){
   for(int j=1;j<=b;j++){
  if(j>=weight[i]) dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j]);
  else dp[i+1][j]=dp[i][j];
   }
  }
  cout<<dp[a][b];
  
  
  
  
  
  
}

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

int main()
{
    vector<int> v1, v2, v3;
    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        v1.push_back(x);
    }
    int m;
    cin >> m;
    while (m--)
    {
        int x;
        cin >> x;
        v2.push_back(x);
    }
    set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));
    int i;
    for (i = 0; i < v3.size(); i++)
    {
        cout << v3[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 6556
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) ((x).begin(), (x).end())
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

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

/*-------------------------------------------*/

class UnionFind {
    vector<int> par, Size;

  public:
    int c; // 連結成分
    UnionFind(int n) : par(n), Size(n, 1), c(n) { rep(i, n) par[i] = i; }

    int root(int x) {
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    bool same(int x, int y) { return root(x) == root(y); }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return false;
        if(Size[x] > Size[y]) {
            Size[x] += Size[y];
            par[y] = x;
        } else {
            Size[y] += Size[x];
            par[x] = y;
        }
        c--;
        return true;
    }
    int size(int x) { return Size[root(x)]; }
};

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

    int n, m;
    cin >> n >> m;
    UnionFind UF(n);
    rep(i, m) {
        int x, y, z;
        cin >> x >> y >> z;
        UF.unite(x - 1, y - 1);
    }
    cout << UF.c << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s,t;
    cin>>s>>t;
    int cnt=0;
    
    for(int i=0; i<s.length(); i++){
        if(s[i]!=t[i]){
            cnt+=1;
        }
    }
    
    cout<<cnt<<endl;
}

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

int main() {
  int N;
  cin >> N;
  int K;
  cin >> K;
  int dat[N];
  for (int i = 0; i < N; ++i) {
    cin >> dat[i];
  }
  sort(dat, dat+N);
  int sum = 0;
  for (int i = 0; i < K; ++i) {
    sum += dat[i];
  }
  cout << sum << '\n';
  return 0;
}

Measured memory_bytes: 3644
#include <iostream>

using namespace std;

int main() {
    int s = 0, m = 0;
    for (int i = 0; i < 3; i++) {
        int a;
        cin >> a;
        s += a;
        if (a > m) {
            m = a;
        }
    }

    cout << s - m << endl;

    return 0;
}

Measured memory_bytes: 256
class UnionFind
    attr_reader :set_size
    def initialize(n)
        @par = Array.new(n)
        n.times{ |i| @par[i] = i }
        @rank = Array.new(n, 0)
        @set_size = Array.new(n, 0)
    end

    def find(x)
        if @par[x] == x
            x
        else
            @par[x] = find(@par[x])
        end
    end

    def unite(x,y)
        x = find(x)
        y = find(y)
        return if x == y

        if @rank[x] < @rank[y]
            @par[x] = y
            @set_size[y] += @set_size[x]
        else
            @par[y] = x
            @set_size[x] += @set_size[y]
            @rank[x] += 1 if @rank[x] == @rank[y]
        end
    end

    def same?(x, y)
        find(x) == find(y)
    end
end

num = gets.split.map(&:to_i)
queue = []
uf = []
2.times do |i|
    num[i].times do |j|
        queue.push([i, j, gets.to_i])
    end
    num[i] += 1
    uf[i] = UnionFind.new(num[i])
end

queue.sort_by!{|arr|arr[2]}
ans = 0
queue.each do |i, j, cost|
    unless uf[i].same?(j, j+1)
        uf[i].unite(j, j+1)
        num[i] -= 1
    end
    ans += num[1-i] * cost
end
puts ans

Measured memory_bytes: 29176
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] v = new boolean[n];
        boolean[][] g = new boolean[n][n];
        for(int i = 0;i < m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            g[a-1][b-1] = true;
            g[b-1][a-1] = true;
        }
        int cnt = 0;
        v[0] = true;
        cnt = dfs(0,n,cnt,g,v);
        System.out.println(cnt);
    }
    public static int dfs(int i,int n,int cnt,boolean[][] g,boolean[] v){
        boolean all_visited = true;
        //System.out.println(Arrays.toString(v));
        for(int j = 0;j < n;j++){
            if(!v[j]){
                all_visited = false;
            }
        }
        if(all_visited){
            cnt++;
            return cnt;
        }
        for(int j = 0;j < n;j++){
            if(!g[i][j]){
                continue;
            }
            if(v[j]){
                continue;
            }
            v[j] = true;
            cnt = dfs(j,n,cnt,g,v);
            //   System.out.println(Arrays.deepToString(g));
            v[j] = false;
        }
        return cnt;
    }
}


Measured memory_bytes: 21840
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  string s,t;
  cin >> s >> t;
  int n = t.size();
  int ans = 10000;
  int move = s.size() - n + 1;
  rep(i, move){
    int cnt = n;
    rep(j, n) if(t[j] == s[i + j]) cnt--;
    ans = min(ans, cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+10;

struct data{
  int aa,bb;
};

struct node{
  int val;
  int id;
  node(int _val=0,int _id=0){val=_val;id=_id;}
};

int n,m;
data a[maxn];
node it[4*maxn];
long long kq;

bool cmp(data x,data y){
  return x.aa<y.aa;
}

node join(node x,node y){
  node res;
  res.val=max(x.val,y.val);
  if (res.val==x.val) res.id=x.id;
    else res.id=y.id;
  return res;
}

void update(int k,int l,int r,int i,int val){
  if (i<l || r<i) return;
  if (l==r){
    it[k]=node(val,i);return;
  }
  int mid=(l+r)/2;
  update(k*2,l,mid,i,val);
  update(k*2+1,mid+1,r,i,val);
  it[k]=join(it[k*2],it[k*2+1]);
}

node query(int k,int l,int r,int i,int j){
  if (r<i || j<l) return node(0,0);
  if (i<=l && r<=j) return it[k];
  int mid=(l+r)/2;
  node z1=query(k*2,l,mid,i,j);
  node z2=query(k*2+1,mid+1,r,i,j);
  return join(z1,z2);
}

int find(int z){
  int inf=1,sup=n,res=0;
  while(inf<=sup){
    int mid=(inf+sup)/2;
    if (a[mid].aa<=z){
      res=mid;inf=mid+1;
    }
    else sup=mid-1;
  }
  return res;
}

int main(){
  //freopen("input.txt","r",stdin);
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d%d",&a[i].aa,&a[i].bb);
  sort(a+1,a+n+1,cmp);kq=0;
  //for(int i=1;i<=n;i++) cout<<"("<<a[i].aa<<" "<<a[i].bb<<")";cout<<endl;
  for(int i=1;i<=n;i++) update(1,1,n,i,a[i].bb);
  for(int i=1;i<=m;i++){
    int ii=find(i);
    node z=query(1,1,n,1,ii);
    kq=kq+z.val;
    update(1,1,n,z.id,0);
  }
  cout<<kq;
}


Measured memory_bytes: 4096
//@source : 
//@create : 23:54:34 Monday 29/06/2020
//@author : nghethuat102
//@status : 
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int all = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        all ^= a[i];
    }
    for (int i = 0; i < n; ++i) {
        a.push_back(a[i]);
    }
    if (n == 2) {
        cout << a[1] << " " << a[0] << "\n";
        return;
    }
    vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        b[(i + (n - 1)) % n] = all ^ a[i + (n - 1)]; 
    }
    for (int i = 0; i < n; ++i) {
        cout << b[i] << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    while (t--) {
        solve();
    }
 //   cerr << fixed << setprecision(5) << double(clock()) * 1000 / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

Measured memory_bytes: 5284
n, m, q = map(int, input().split())
train = []
for _ in range(m):
    l, r = map(int, input().split())
    train.append((l, r))
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for [l, r] in train:
    dp[l][r] += 1
for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] += dp[i + 1][j]
for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] += dp[i][j + 1]
for i in range(q):
    l, r = map(int, input().split())
    print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])

Measured memory_bytes: 35636
#define NAME "a"

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <ctime>
#include <cctype>
#include <cassert>
#include <memory>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <iterator>

#define pb push_back
#define mp make_pair
#define frs first
#define snd second

using namespace std;

#ifdef WIN32
    #define lld "%I64d"
#else
    #define lld "%lld"
#endif

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 7;
const ll INFLONG = (ll) 1e18 + 7;
const double EPS = 1e-9;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<string> vs;

typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

typedef vector<pii> vpii;
typedef vector<pil> vpil;
typedef vector<pli> vpli;
typedef vector<pll> vpll;

template <typename T>
T sqr(T a) {
    return a * a;
}

int main() {
    srand(time(0));

//    freopen(NAME".in", "r", stdin);
//    freopen(NAME".out", "w", stdout);

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int curr = 0;

    while (a > 0 && c > 0) {
        if (curr == 0) {
            c -= b;
        } else {
            a -= d;
        }

        curr++;
        curr %= 2;
    }

    cout << ((a > 0) ? "Yes" : "No") << endl;

//    printf("%.3lf\n", (double) clock() / CLOCKS_PER_SEC);
    return 0;
}


Measured memory_bytes: 3624
/*COMPETITIVE PROGRAMMING C++ TEMPLATE */

#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>
#include <climits>
#include <iomanip>
#include <iterator>

#define all(x) x.begin(), x.end()
#define MOD 998244353
const unsigned int M = 1000000007;
const long double PI = 3.141592653589793236L;

typedef long long int ll;
typedef long double ld;
#define MAX 50
using namespace std;
void printString(ll n)
{
    ll arr[10000];
    ll i = 0;


    while (n) {
        arr[i] = n % 26;
        n = n / 26;
        i++;
    }


    for (ll j = 0; j < i - 1; j++) {
        if (arr[j] <= 0) {
            arr[j] += 26;
            arr[j + 1] = arr[j + 1] - 1;
        }
    }

    for (ll j = i; j >= 0; j--) {
        if (arr[j] > 0)
            cout << char('A' + arr[j] - 1+32);
    }


}
ll power(int x, unsigned int y, int p)
{
    ll res = 1;     // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    if (x == 0) return 0; // In case x is divisible by p;

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}
void constructXOR(int A[], int n)
{
    // calculate xor of array
    int XOR = 0;
    for (int i = 0; i < n; i++)
        XOR ^= A[i];

    // update array
    for (int i = 0; i < n; i++)
        A[i] = XOR ^ A[i];
}

void solve(){
   int n;
   cin>>n;
   int arr[n];
   for(int i=0;i<n;i++){
       cin>>arr[i];
   }
    constructXOR(arr,n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
}

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

    int T = 1;
    solve();

    return 0;
}

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

int main()
{
	int N, K;
	cin >> N >> K;

	int h[100000];
	for (int i = 0; i < N; i++)
	{
		cin >> h[i];
	}
	
	sort(h, h + N);
	
	int mirai = h[0 + K - 1] - h[0];
	for (int i = 0; i < N - K + 1; i++)
	{
		if (mirai > h[i + K - 1] - h[i])
			mirai = h[i + K - 1] - h[i];

	}
	cout << mirai;

	return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

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

vector<vector<int>> v(111111);

void modmul(ll &a, ll b){
	a *= b;
	a %= MOD;
}

pair<ll,ll> dfs(int a,int par){
	ll A = 1;
	ll B = 1;
	REP(i,v[a].size()){
		if(v[a][i] == par)continue;
		auto now = dfs(v[a][i], a);
		modmul(A,(now.FI + now.SE) % MOD);
		modmul(B,now.FI);
	}
	return MP(A,B);
}

int main(){
	
	int n;cin >> n;
	REP(i,n-1){
		int a,b;cin >> a >> b;
		a--;b--;
		v[a].EB(b);
		v[b].EB(a);
	}
	
	auto ans = dfs(0,-1);
	cout << (ans.FI + ans.SE) % MOD << endl;
		
	
	return 0;
}


Measured memory_bytes: 12928
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(ll)n;++i)
int main(){
  ll n,m;
  cin >> n >> m;
  ll ans = 0;
  if( n >= 3 && m >= 3 ){
    ans += (n-2)*(m-2);
  }else if( n == 1 && m == 1 ){
    ans += 1;
  }else if( n == 1 || m == 1 ){
    ans += max(n,m)-2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]
switch = 0
for li in L:
    t = li[0]
    co = li[1]+li[2]
    if t >= co:
        if co % 2 == 0 and t % 2 == 0:
            pass
        elif co % 2 != 0 and t % 2 != 0:
            pass
        else:
            switch += 1
            break
    else:
        switch += 1
        break
if switch == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 27300
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
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; }
const int INF = 1<<30;

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n,-1){}

    int root(int x){
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y){
        int rx = root(x), ry = root(y);
        if(rx == ry) return false;
        if(size(rx) < size(ry)) swap(rx, ry);
        par[rx] += par[ry];
        par[ry] = rx;
        return true;
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return -par[root(x)];
    }
};

int main(){
	int n, m;
	cin >> n >> m;
	UnionFind uf(n);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		uf.unite(x-1, y-1);
	}
	int a[100010] = {0};
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if(!a[uf.root(i)]){
			ans++;
			a[uf.root(i)]++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
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;
}

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;


typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    int N;
    cin >> N;

    vi h(N);
    REP(i,N) cin >> h[i];

    int ans = 0;
    int MAX_H = *max_element(ALL(h));
    REP(ct,MAX_H){
        int line = h[0]!=0?1:0;

        REP(i,N-1) if (h[i]==0 and h[i+1] > 0) line++;
        ans += line;
        //cout << ct << " : " << line << endl;
        REP(i,N) if (h[i] != 0) h[i]--;
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
    int a, b, x;
    cin >> a >> b >> x;
    if(a+b>=x && a <=x){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;cin>>s;
    int pcnt = 0;
    for(char c : s){
        if(c=='p'){
            pcnt++;
        }
    }
    int n=s.size();
    cout<<(n/2)-pcnt<<endl;

}

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

int main(){
	while(1){
		int n;
		cin>>n;
		
		if(n==0){
			break;
		}
		
		int a[1000];
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		int dif=10000000;
		for(int i=0;i<n-1;i++){
			for(int j=i+1;j<n;j++){
				int d=abs(a[i]-a[j]);
				if(d<dif){
					dif=d;
				}
			}
		}
		cout<<dif<<endl;
	}
	return 0;
}

Measured memory_bytes: 3076
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>


using namespace std;

int main(){
    string str;
    cin >> str;
    
    bool found = true;
    for(char c = 'a'; c <= 'z'; c++){
        found = false;
        for(int i = 0; i < str.size(); i++){
            if(c == str[i]){
                found = true;
                break;
            }
        }
        
        if(!found){
            cout << c << endl;
            return 0;
        }
    }
    
    cout << "None" << endl;
    return 0;
    
    
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int64_t INF=1000000000000;
struct edge {int64_t from,to,cost;};
int main(){
 int64_t N,M,P;
  cin>>N>>M>>P;vector<edge>es(M);
  for(int k=0;k<M;k++){
  int64_t a,b,c;cin>>a>>b>>c;
    es[k].from=a-1;
    es[k].to=b-1;
    es[k].cost=P-c;
    
  }vector<int64_t>d(N);
  for(int64_t i=0;i<N;i++)d[i]=INF;
  d[0]=0;
  for(int i=0;i<N-1;i++)
  for(int j=0;j<M;j++){
    edge e=es[j];
    if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
      d[e.to]=d[e.from]+e.cost;
  }
  for(int i=0;i<N;i++)
  for(int j=0;j<M;j++){
    edge e=es[j];
    if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost)
      d[e.to]=-INF;
  }
  if(d[N-1]<=-INF)
    cout<<-1<<endl;
  else{
  if(d[N-1]<=0)
    cout<<-d[N-1]<<endl;
    else
      cout<<0<<endl;
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 100;

int n;

string s;

int b[maxn];

int a[maxn];

int main(){
    #ifdef ONPC
    ifstream cin("a.in");
    ofstream cout("a.out");
    #endif
    ios::sync_with_stdio(0);
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        b[i] = (s[i] == 'o');
    for (int v1 = 0; v1 < 2; v1++)
        for (int v2 = 0; v2 < 2; v2++){
            a[0] = v1;
            a[1] = v2;
            for (int i = 2; i < n; i++)
                if ((a[i - 1] ^ b[i - 1]) == 0)
                    a[i] = a[i - 2];
                else
                    a[i] = a[i - 2] ^ 1;
            int val;
            if ((a[n - 1] ^ b[n - 1]) == 0)
                val = a[n - 2];
            else
                val = a[n - 2] ^ 1;
            bool ez = 1;
            if (val != a[0])
                ez = 0;
            if ((a[0] ^ b[0]) == 0)
                val = a[n - 1];
            else
                val = a[n - 1] ^ 1;
            if (val != a[1])
                ez = 0;
            if (ez){
                for (int i = 0; i < n; i++)
                    if (a[i])
                        cout << 'S';
                    else
                        cout << 'W';
                return 0;
            }
        }
    cout << -1;
}


Measured memory_bytes: 1360
#include <iostream>
#include <string>

using namespace std;

int main (void) {
	string o, e;
	cin >> o >> e;
	int i;
	for (i = 0; i < o.length(); i++) {
		cout << o[i];
		if (i < e.length()) cout << e[i];
	}
	for (; i < e.length(); i++) {
		cout << e[i];
	}
	cout << endl;
	return 0;
}

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

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  
  if (B-A <= 200) {
    for (int i = A; i <= B; i++) {
      if (i-A < K || B-i < K)
        cout << i << endl;
    }
  } else {
    for (int i = A; i < A+K; i++) {
      cout << i << endl;
    }
    for (int i = B-K+1; i <= B; i++) {
      cout << i << endl;
    }
    
  }
}

Measured memory_bytes: 3608
#include <stdio.h>

int main(){
  int x ,y , t;
  scanf("%d %d", &x ,&y);
  
  if (x < y){ t = x;x = y; y =t; }

  t = x % y;
  while( t > 0){
    x = y;
    y = t;
    t = x % y;
  }
  printf("%d\n" ,  y);
  return 0;
  
}


Measured memory_bytes: 2144
import sys
N, M, X=map(int, sys.stdin.readline().rstrip().split())
A = [list(map(int, sys.stdin.readline().rstrip().split())) for i in range(N)]
cost=[]
for i in range(1<<N):	#Bit All Search
	l=[0]*(M+1)
	for j in range(N):
		if((i>>j)&1)==1:
			l=[l[k]+A[j][k] for k in range(M+1)]
	for k in range(M):
		if l[k+1]<X:
			break
	else:
		cost.append(l[0])
cost.sort()
print(-1 if cost==[] else cost[0])

Measured memory_bytes: 9144
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define DEBUG if(0)
#define pb push_back
#define pf push_front
#define mp make_pair
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k, ans = 0;
    cin >> n >> k;
    int arr[n];
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int i = 0; i < n; i++) ans += (arr[i] >= k);
    cout << ans << endl;
    return (0);
}

Measured memory_bytes: 768
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

class SegTree { // index starts at 0.
public:
  int N;
  int* dat;
  static int INFTY; // (1 << 31) - 1;
  
  SegTree(int n) {
    N = 1;
    while (N < n) N *= 2;
    dat = new int[2 * N - 1];
    for (auto i = 0; i < 2 * N - 1; ++i) {
      dat[i] = INFTY;
    }
  }

  ~SegTree() {
    delete[] dat;
  }

  void update(int k, int a) {
    k += N - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1)/2;
      dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }

  int find(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return INFTY;
    if (a <= l && r <= b) return dat[k];
    int vl = find(a, b, k * 2 + 1, l, (l + r) / 2);
    int vr = find(a, b, k * 2 + 2, (l + r) / 2, r);
    return min(vl, vr);
  }

  int find(int a, int b) {
    return find(a, b, 0, 0, N);
  }
  
};

int SegTree::INFTY = 2147483647; // (1 << 31) - 1;

int N;
int b[200020];
int Q;
vector<int> V[200020];

int score(int x) {
  if (b[x] == 0) return -1;
  return 1;
}

int main () {
  cin >> N;
  for (auto i = 0; i < N; ++i) {
    cin >> b[i];
  }
  cin >> Q;
  for (auto i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    V[l].push_back(r);
  }
  for (auto i = 0; i < N; ++i) {
    sort(V[i].begin(), V[i].end());
  }
  int zeros = 0;
  for (auto i = 0; i < N; ++i) {
    if (b[i] == 0) ++zeros;
  }
  SegTree S(N+1);
  S.update(0, zeros);
  for (auto i = 0; i < N; ++i) {
    for (auto x : V[i]) {
      S.update(x+1, S.find(i, x+2));
    }
    S.update(i+1, min(S.find(i, i+1) + score(i), S.find(i+1, i+2)));
    cerr << "DP[" << i+1 << "] = " << S.find(i+1, i+2) << endl;
  }
  cout << S.find(N, N+1) << endl;
}


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

int main() {
  int s;
  cin >> s;
  vector<int> seqence(1100000, 0);
  seqence[0] = s;
  int ans;
  if (s == 1) cout << 4 << endl;
  else if (s == 2) cout << 4 << endl;
  else {
    for (int i = 0; i < seqence.size(); i++) {
      if (seqence[i] % 2 == 0) seqence[i+1] = seqence[i]/2;
      else seqence[i+1] = 3*seqence[i] + 1;
      if (seqence[i+1] == 2) {
        cout << i+4 << endl;
        break;
      }
    }
  }
}


Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int k;
	cin>>k;
	ll ans=0;
	for(int i=1; i<=k; i++)
	{
		int num=k/i;
		ll temp=2*i+(num-1)*i;
		ans+=(num*temp/2);
	}
	cout<<ans;
	return 0;
	
}

Measured memory_bytes: 3568
package main

import (
	"fmt"
)

func main() {
	var n,d int
	fmt.Scan(&n,&d)
	
	ans := n / (2 * d + 1)
	
	if n % (2 * d + 1) != 0 {
		ans++
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        if ((b / a) >= c) {
            System.out.println(c);
        } else {
            System.out.println(b / a);
        }
    }
}


Measured memory_bytes: 23380
#include <stdio.h>

int main(void)
{
	int a, i, j;
	for(i=1;i<10;i++){
		for(j=1;j<10;j++){
			a = i * j;
			printf("%dx%d=%d\n",i,j,a);
		}
	}
	return 0;
}

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

int main(){
   int n,w;
  scanf("%d%d",&n,&w);
  long long int w1,v1;
  vector<long long int> dp(w+5);
  
  for(int i=0;i<n;i++){
     scanf("%lld%lld",&w1,&v1);
    for(long long int weight=w-w1;weight>=0;--weight){
      dp[weight+w1]=max(dp[weight+w1],dp[weight]+v1);
    }
  }
  long long max1=0;
  for(int i=0;i<=w;i++){
    max1=max(max1,dp[i]);
  }
  printf("%lld\n",max1);
  return 0;
}

    

Measured memory_bytes: 1024
<?php
# 入力部
fscanf(STDIN, "%s", $s);
// fscanf(STDIN, "%d %d %d", $x, $y, $z);
// $s1 = fgets(STDIN); //"\n"の2文字
// $s2 = fgets(STDIN);
// fscanf(STDIN, "%d", $n);
// fscanf(STDIN, "%s", $s);
// fscanf(STDIN, "%s", $s2);

# 処理部
$arr = str_split($s);
// $arr2 = str_split($s2);
// $arr1 = explode(" ", $s1);
// $arr2 = explode(" ", $s2);
// for ($i = 0; $n > $x * $i; $i++) {
// }
// if (strpos($s, 'RRR') !== false) {
//   $r = 3;
// } elseif (strpos($s, 'RR') !== false) {
//   $r = 2;
// } elseif (strpos($s, 'R') !== false) {
//   $r = 1;
// } else {
//   $r = 0;
// }
// $s = "No";
// if ($x >= 30) {
//   $s = "Yes";
// }
// for ($i = 0; $i * 1000 < $n; $i++) {
// }
// $c = "a";
// if (ctype_upper($a)) {
//   $c = "A";
// }
// $s = "Yes";
// echo count($arr1);
// for ($i = 0; $i < strlen($s1); $i++) {
//   if ($arr1[$i] != $arr2[$i]) {
//     $s = "No";
//   }
// }
// $unit;
// switch ($n % 10) {
//   case 0:
//   case 1:
//   case 6:
//   case 8:
//     $unit = "pon";
//     break;
//   case 3:
//     $unit = "bon";
//     break;
//   default:
//     $unit = "hon";
//     break;
// }
// if ($s == "ABC") {
//   $r = "ARC";
// } else {
//   $r = "ABC";
// }
// $r = "NG";
// for ($i = $a; $i <= $b; $i++) {
//   if ($i % $k == 0) {
//     $r = "OK";
//   }
// }
// $r = "safe";
// if ($s <= $w) {
//   $r = "unsafe";
// }
// $r = "No";
// if (strpos($n, "7") !== false) {
//   $r = "Yes";
// }
$r = "No";
if ($arr[2] == $arr[3] && $arr[4] == $arr[5]) {
  $r = "Yes";
}

# 出力部
echo $r . "\n";
// echo $z . " " . $x . " " . $y . "\n";
// echo ($i * 1000) - $n . "\n";

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

int main() {
	int a, b;
	cin >> a >> b;
	if(a + b == 15){
		cout << "+" << endl;
		return 0;
	}
	if(a * b == 15){
		cout << "*" << endl;
		return 0;
	}
	cout << "x" << endl;
}

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

struct object{
    int v,w;
    char t;
    unsigned long d;
    string s;
    
    bool operator < (const object &o) const {
        // 価値
        if(v != o.v){
            return v < o.v;
        }
        else {
            // 重さ
            if(w != o.w){
                return w < o.w;
            }
            else{
                // 型 char
                if(t != o.t){
                    return t < o.t;
                }
                else{
                    // 日時 unsinged long
                    if(d != o.d){
                        return d < o.d;
                    }
                    else{
                        // 名前 string
                        if(s != o.s){
                            return lexicographical_compare(s.begin(),s.end(),o.s.begin(),o.s.end());
                        }
                    }
                }
            }
        }
        return false;
    }
};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    object o[n];

    for(int i = 0;i < n;++i){
        cin >> o[i].v >> o[i].w >> o[i].t >> o[i].d >> o[i].s;
    }

    sort(o,o + n);

    for(int i = 0;i < n;++i){
        cout << o[i].v << " " << o[i].w << " " << o[i].t << " " <<  o[i].d << " " << o[i].s << endl;
    }
}



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

int main(){
	int q;
	cin>>q;
	while(q--){
		int n;
		set<int> s;
		cin>>n;
		int ans=0;
		while(10<=n){
			if(s.find(n)!=s.end()){
				ans=-1;
				break;
			}
			s.insert(n);
			int next=0;
			int b=10;
			while(b<=n){
				int t=(n%b)*(n/b);
				next=max(next,t);
				b*=10;
			}
			n=next;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1196
#include <iostream>

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		int ans = 0;
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++)
				for (int k = 0; k < 10; k++)
					for (int l = 0; l < 10; l++)
						if (i + j + k + l == n)
							ans++;
		cout << ans << endl;
	}
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  
  vector<int> A(100,1);
  int x = 0;
  for (int i = 1; i < 10; i ++ ){
    for (int j = 1; j < 10; j++){
      A.at(x) = i*j;
      x++;
    }
  }
  
 int K = 0; 
 for (int i = 0; i < 100; i++){ 
  if (A.at(i) == N){
    cout << "Yes" <<endl;
    K++;
    break;
  }
 }
  
 if (K == 0){
   cout << "No" << endl;
 }
}
    

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  int l = s.size();
  int l2 = l;
  for(int i=0; i<l2-1; i++){
    if(s.at(i) == s.at(i+1)) l -= 1;
  }
  cout << l << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long int
#define ldouble long double
#define vin vector<int>
#define rep(a,n) for(int i=(a);i<(n);i++)
#define INF (int)1000000007


//setprecision()<<

using namespace std;

void fin(int n,vin &a){
    rep(0,n){
        cin>>a.at(i);
    }
}

bool comp(pair<int,int> a,pair<int,int> b){ //比較関数
    if(a.second<=b.second) return true;
    else return false;
}

signed main(){
    typedef pair<int,int> P;
    int N;
    cin>>N;
    vin x(N),l(N);
    vector<P> work(N);
    rep(0,N){
        cin>>x.at(i)>>l.at(i);
    }
    rep(0,N){
        work.at(i)=make_pair(x.at(i)-l.at(i),x.at(i)+l.at(i));
    }
    sort(work.begin(),work.end(),comp);

    int i=1,sum=1,endtime=work.at(0).second;
    while(i<N){
        if(endtime<=work.at(i).first){
            sum++;
            endtime=work.at(i).second;
            i++;
        }
        else{
            i++;
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3328
import java.io.*;
import java.util.*;

public class Main {
    Scanner sc;
    int n, m;
    Set<String> key = new HashSet<String>();
    boolean open;

    Main() {
        sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) 
            key.add(sc.next());
        m = sc.nextInt();
        open = false;
    } 

    void println(Object s) {
        System.out.println(s);
    }

    void run() {
        for (int i = 0; i < m; i++) {
            String s = sc.next();
            if (key.contains(s)) {
                if (open) {
                    println("Closed by " + s);
                    open = false;
                } else {
                    println("Opened by " + s);
                    open = true;
                }
            } else {
                println("Unknown " + s);
            }
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }
}            

Measured memory_bytes: 12000
using System;
using System.Linq;

namespace ATCoder
{
    class Program
    {
        static void Main( string[] args )
        {
            var input = Console.ReadLine();
 
            string[] token = input.Split(' ');
            int H = int.Parse(token[0]);
            int A = int.Parse(token[1]);
            int count = 0;

            while(H > 0)
            {
                H -= A;
                count++;
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
const long long MOD=1e09+7;



#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define vi vector<int>

int main(){

  ll n,k,q;
  cin>>n>>k>>q;
  
  vi winners(n+1,0);

  rep(i,q){
    ll tmp;
    cin>>tmp;
    winners.at(tmp)++;  
  }
  
  for (ll i=1;i<=n;i++){
    if (k-(q-winners.at(i))>0){
      cout<<"Yes"<<endl;
    }
    else {
      cout<<"No"<<endl;
    }
  }
  
   
  
  


  
}



Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  long long n, a, b;
  cin >> n >> a >> b;
  if((a-b)%2 == 0){
    cout  << (b-a)/2 << endl;
  }else{
    cout << min(a-1, n-b)+1+(b-a-1)/2 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=3003,INF=1<<30;

ll rui[MAX][MAX];

void make(ll mo){
    for(int i=0;i<mo;i++){
        rui[i][0]=1;
        for(int j=1;j<mo;j++){
            rui[i][j]=rui[i][j-1]*i;
            if(rui[i][j]>=mo) rui[i][j]%=mo;
        }
    }
}

int main(){
    
    int P;cin>>P;
    make(P);
    
    vector<ll> A(P),C(P),S(P+1,0),mae(P+1,0);//cは係数,Sは累積和,maeは(x-xi)の累積積
    mae[0]=1;
    for(int i=0;i<P;i++) cin>>A[i];
    
    for(int i=0;i<P;i++){
        int div=1,sum=0;
        for(int j=0;j<i;j++){
            div*=(i-j);
            if(div>=P) div%=P;
        }
        for(int j=0;j<=P;j++){
            sum+=S[j]*rui[i][j];
            if(sum>=P) sum%=P;
        }
        
        C[i]=(A[i]+P-sum)*rui[div][P-2]%P;
        
        vector<ll> save(P+1,0);//変えるようの配列
        
        if(i){
            for(int j=0;j<P;j++){
                save[j]+=(P-(i-1))%P*mae[j];
                save[j+1]+=mae[j];
                
                if(save[j]>=P) save[j]%=P;
                if(save[j+1]>=P) save[j+1]%=P;
            }
            
            for(int j=0;j<P+1;j++){
                mae[j]=save[j];
            }
        }
        
        for(int j=0;j<P+1;j++){
            S[j]+=mae[j]*C[i];
            if(S[j]>=P) S[j]%=P;
        }
        
    }
    
    //バラすパート
    
    vector<ll> ans(P+1,0);
    for(int i=0;i<P+1;i++) mae[i]=0;
    mae[0]=1;
    
    for(int i=0;i<P;i++){
        for(int j=0;j<P+1;j++){
            ans[j]+=mae[j]*C[i];
            if(ans[j]>=P) ans[j]%=P;
        }
        
        vector<ll> save(P+1,0);//変えるようの配列
        
        for(int j=0;j<P;j++){
            save[j]+=(P-i)%P*mae[j];
            save[j+1]+=mae[j];
            
            if(save[j]>=P) save[j]%=P;
            if(save[j+1]>=P) save[j+1]%=P;
        }
        
        for(int j=0;j<P+1;j++){
            mae[j]=save[j];
        }
        
    }
    
    for(int i=0;i<P;i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;
}



Measured memory_bytes: 70912
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    unsigned long long t,a,b,c,d;
    cin >> t;
    for(int i=0;i<t;i++){
        cin >> a >> b >> c >> d;
        if(b>d || a<b){
            cout << "No" << endl;
        } else if(b<=c){
            cout << "Yes" << endl;
        }else{
            bool f=1;
            unsigned long long x = __gcd(b,d);
                if(b-x+a%x>c){
                    cout << "No" << endl;
                }else{
                cout << "Yes" << endl;
            }
        }
    }
}

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

int main()
{
    int N;

    cin >> N;

    int A[N], B[N], C[N], ans = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    for (int i = 0; i < N; i++)
    {
        cin >> B[i];
    }

    for (int i = 0; i < N - 1; i++)
    {
        cin >> C[i];
    }

    for (int i = 0; i < N; i++)
    {
        ans += B[i];
    }

    for (int i = 0; i < N - 1; i++)
    {
        if (A[i] + 1 == A[i + 1])
        {
            ans += C[A[i] - 1];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
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

p = 10**9 + 7
N = 10**6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N+1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

    
x,y=map(int,input().split())
if ((x+y)%3!=0):
  print(0)
else:
  xx=(2*x-y)//3
  yy=(2*y-x)//3
  if (xx<0 or yy<0):
    print(0)
  else:
    ans=cmb(xx+yy,xx,p)
    print(ans)

Measured memory_bytes: 127432
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn main() {
    let v: Vec<u32> = read_vec();
    let (mut n, k) = (v[0], v[1]);
    let mut digit = 0;
    while n != 0 {
        n /= k;
        digit += 1;
    }
    println!("{}", digit);
}


Measured memory_bytes: 4352
#include <stdio.h>

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0,c = getchar_unlocked();
	do n = 10*n + (c & 0xf),c = getchar_unlocked(); while (c >= '0');
	return n;
}

int main(){
	int n, a, min, ans;

	n = in()-2;
	min = in(), a = in();
	ans = a-min;
	if (a < min) min = a;
	while (n--) {
		a = in();
		if (a < min) min = a;
		else if (a-min > ans) ans = a-min;
	}
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 2128
#include<stdio.h>

int selectionSort(int A[], int N)
{
	int i, j, t, sw = 0, minj;

	for ( i = 0; i < N - 1; i++)
	{
		minj = i; //とりあえず最小の位置を先頭に仮置き
		for (j = i; j < N; j++)
		{
			if( A[j] < A[minj] ) minj = j; // minjを変えていき
		}
		t = A[i]; A[i] = A[minj]; A[minj] = t; // 一時変数tを使って入れ替え
		if( i != minj ) sw++;
	}
	return sw;
}

int main()
{
	int A[100], N, i, sw;

	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}
	sw = selectionSort(A, N);
	for (i = 0; i < N; i++)
	{
		if( i > 0 ) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
	printf("%d\n", sw);
	return 0;
}


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

#define rep(i, b, e) for(i = b; i < e; ++i)
#define repr(i, b, e) for (i = b; i >= e; --i)
#define ull unsigned long long int

#define M_DEBUG 1
#define PI 3.141592653589793

#define DEBUG 1

int kaijou(int n) {
    int kai = 1;
    for (int i = 1; i <= n; ++i) kai *= i;

    return kai;
}

int main(void) {
    int n, i, j;
    cin >> n;
    vector<int> x(n), y(n);
    rep (i, 0, n) cin >> x[i] >> y[i];
    int a[8];
    a[0] = 2;

    for (int i = 1; i < 8; ++i)
        a[i] = a[i - 1] * (i + 1);

    float sum = 0;

    rep (i, 0, n - 1)
        rep (j, i + 1, n) 
            sum += sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) * a[n - 2];

cout << setprecision(10) << (float)(sum / kaijou(n)) << endl;

    return 0;
}

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

int main() {

    int h,w;
    cin >> h >> w;

    int hei[h] ={};
    int wid[w] ={};
    for(int i=0; i<h; i++) {
	string s; cin >> s;
	for(int j=0; j<w; j++) {
	    if( s[j] == '#' ) {
		hei[i]++;
		wid[j]++;
	    }
	}
    }

    int sum=0;
    for(int i=0; i<h; i++) {
	if( hei[i] == 0 ) {
	    cout << "Impossible" << endl;
	    return 0;
	}
	sum += hei[i];
    }
    for(int i=0; i<w; i++){
	if( wid[i] == 0 ) {
	    cout << "Impossible" << endl;
	    return 0;
	}
    }
    if( sum != h+w-1 ) {
	cout << "Impossible" << endl;
	return 0;
    }
    cout << "Possible" << endl;
    return 0;
    
}


Measured memory_bytes: 384