akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect



class ModInt(int):

    MOD = None

    def __add__(self, other):
        self = ModInt(int.__add__(self, other) % ModInt.MOD)
        return self

    def __mul__(self, other):
        self = ModInt(int.__mul__(self, other) % ModInt.MOD)
        return self

def make_2d_arr(s1, s2, default=0):
    a = [None] * s1
    for i, _ in enumerate(a):
        a[i] = [default] * s2
    return a


if __name__ == '__main__':
    n, s = list(map(int, input().split()))
    data = list(map(int, input().split()))

    ModInt.MOD = 998244353
    dp = [ModInt(0)] * (s + 1)
    dp[0] = 1
    dp_arr = [dp, dp[:]]
    frm = 0
    to = 1

    for i in range(n):
        frm, to = to, frm
        for v in range(s + 1):
            dp_arr[to][v] = dp_arr[frm][v] * 2
            src = v - data[i]
            if src >= 0:
                dp_arr[to][v] += dp_arr[frm][src]
    #print('dp_arr') # debug
    #pp(dp_arr) # debug
    print(dp_arr[to][s])




    #print('\33[32m' + 'end' + '\033[0m') # debug


Measured memory_bytes: 172380
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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 = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
ll N, K, C;
string S;
int a[201010], b[201010];

int main()
{
    cin >> N >> K >> C;
    cin >> S;

    int cnt = 0;
    for (int i = 0; i < S.size(); i++) {
        if (cnt == K) {
            break;
        }

        if (S[i] == 'o') {
            a[cnt] = i;
            cnt++;
            i += C;
        }
    }

    cnt = K - 1;
    for (int i = S.size() - 1; i >= 0; i--) {
        if (cnt < 0) {
            break;
        }

        if (S[i] == 'o') {
            b[cnt] = i;
            cnt--;
            i -= C;
        }
    }

    for (int i = 0; i < K; i++) {
        if (a[i] == b[i]) {
            cout << a[i] + 1 << endl;
        }
    }
}


Measured memory_bytes: 3332
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
void input() {
  cin >> N;
  cin >> M;
  cin >> K;
}
void solve() {
  cout << (N + M) * K / 2 << endl;
  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

int n,ans=0;
int a[100005],b[100005],c[100005];

int p[100005][205];

signed main()
{
	cin>>n;
	n++;
	for (int i=1;i<=n;i++)  cin>>a[i];
	
	b[1]=1,c[n]=a[n];
	for (int i=2;i<=n;i++)  b[i]=(b[i-1]-a[i-1])*2;
	for (int i=n-1;i>=1;i--)  c[i]=c[i+1]+a[i];
	for (int i=1;i<=n;i++)  ans+=min(b[i],c[i]);
	for (int i=1;i<=n;i++)
	{
		if (a[i]>b[i])  return cout<<-1<<endl,0;
	}
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 5972
s = gets.chomp.split("")

red = 0
blue = 0
ans = 0
s.each do |n|
    if n.to_i == 0
        red += 1
    else
        blue += 1
    end
=begin
    if n.to_i == 0
        red += 1
        if blue > 0
            red -= 1
            blue -= 1
            ans += 2
        end
    else
        blue += 1
        if red > 0
            red -= 1
            blue -= 1
            ans += 2
        end
    end
=end
    # puts "#{red}, #{blue}"
end

ans = red < blue ? red : blue
puts ans * 2


Measured memory_bytes: 8988
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main()
{
    ll n;
    cin >> n;
    string namecache;
    ll nm[5] = {}; // M = [0], A = [1], ... , H = [4]
    for(int i = 0; i < n; ++i) {
        cin >> namecache;
        switch(namecache[0]) {
            case 'M':
                nm[0]++;
                break;
            case 'A':
                nm[1]++;
                break;
            case 'R':
                nm[2]++;
                break;
            case 'C':
                nm[3]++;
                break;
            case 'H':
                nm[4]++;
                break;
        }
    }
    //5C3 = 5C2だから5*4/2より、10パターン
    ll res = nm[0]*nm[1]*nm[2]+nm[0]*nm[1]*nm[3]+nm[0]*nm[1]*nm[4]
         +nm[0]*nm[2]*nm[3]+nm[0]*nm[2]*nm[4]
         +nm[0]*nm[3]*nm[4]
         +nm[1]*nm[2]*nm[3]+nm[1]*nm[2]*nm[4]
         +nm[1]*nm[3]*nm[4]
         +nm[2]*nm[3]*nm[4];

    cout << res << '\n';
}


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

int main() {
  int N, A = 0, B = 0;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for (int i = 0; i < N; i += 2) {
    A += vec.at(i);
    if (N % 2 == 0) {
      B += vec.at(i + 1);
    }
    else {
      if (i == N - 1) {
        break;
      }
      else {
        B += vec.at(i + 1);
      }
    }
  }
  
  cout << A - B << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#define MP make_pair
using ll = long long;
using namespace std;

int main()
{
  int H,W;
  cin >> H >> W;
  vector<string>S(H);
  for(int i=0; i < H; i++)
    cin >> S[i];

  vector<vector<int> >A(H, vector<int>(W));
  for(int i=0; i < W; i++){
    for(int j=0; j < H; j++){
      int n = 0;
      for(int dx = -1; dx <= 1; dx++){
	for(int dy = -1; dy <= 1; dy++){
	  if(i+dx >= 0 && i+dx < W && j+dy >= 0 && j+dy < H)
	    if(S[j+dy][i+dx] == '#')
	      n++;
	}
      }
      if(S[j][i] == '#')
	n = -1;
      A[j][i] = n;
    }
  }

  for(int j=0; j < H; j++){
    for(int i=0; i < W; i++){
      if(A[j][i] >= 0)
	cout << A[j][i];
      else
	cout << S[j][i];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
round = lambda x:(x*2+1)//2
a,b = list(map(int,input().split()))
S = input()
sub= "AC"
l = [0]*(len(S)+1)
for i in range(len(S)):
  l[i+1] = l[i] + (1 if S[i:i+2]=="AC" else 0)

for i in range(b):
    r,t = list(map(int,input().split()))
    n = l[t-1]-l[r-1]
    print(int(n))


Measured memory_bytes: 9412
#include <bits/stdc++.h>
 
#define ll long long int
#define ld long double
#define pb push_back
#define pq priority_queue
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vvll vector<vector<ll>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define MODNUM 1000000007
#define lp(i,a,b) for(ll i=a; i<b; i++)
#define all(v) v.begin(), v.end()
 
using namespace std;
 
ll mex(ll a, ll b, ll m) {
	if(b==0) return 1;
	if(b%2) return a*mex((a*a)%m,(b-1)/2,m)%m;
	else return mex((a*a)%m,b/2,m);
}
 
int x,y;
void exteu(ll a, ll m) {
	if(m==0) { x=1;y=0; }
	else {
		exteu(m,a%m);
		ll temp = x;
		x=y;
		y=temp-(a/m)*y;
	}
}
 
ll fact(ll n) 
{	ll prod=1;
	for(ll i=2; i<=n; i++) {
		prod*=i;
	}
	return prod;
}
 
ll gcd(ll a, ll b) {
	if(b==0) return a;
	return gcd(b, a%b);
}
 
// bool isprime[200001];
// void makesieve() {
// 	memset(isprime, true, sizeof(isprime));
// 	for (int i = 2; i <= sqrt(200000); ++i)
// 	{
// 		/* code */
// 		if(isprime[i]) {
// 			for (int j = i*i; j <= 200000; j+=i)
// 			{
// 				/* code */
// 				isprime[j]=false;
// 			}
// 		}
// 	}
// }
// 
// 1 2 4 5 8
void solve() {
	// ll n,m,k; cin>>n>>m>>k;
	// vll a(n),b(m); lp(i,0,n) {cin>>a[i];} lp(i,0,m) {cin>>b[i];}
	// ll s=0, res=0, i=0,j=0;
	// while(s<k && (i<n || j<m))
	// {
	// 	if(i<n && a[i] < b[j]) {
	// 		if(s + a[i] > k) {cout<<res; return;}
	// 		s += a[i];
	// 		res++;
	// 		i++;
	// 	}
	// 	else if(j<m) {
	// 		if(s + b[j] > k) {cout<<res;return;}
	// 		s += b[j];
	// 		res++;
	// 		j++;
	// 	}
	// 	else break;
	// }
	// cout<<res;
	ll n; cin>>n;
	// vll sum(n+1, 2);
	ll s = n*(n+1) - 1;
	for (int i = 2; i <= n/2; ++i)
	{
		s += (i*(((n/i)*(n/i + 1)) - 2))/2;
		// cout<<(i*(((n/i)*(n/i + 1)) - 2))/2<<" ";
		// for (int j = 2*i; j <= n; j+=i)
		// {
		// 	s+=j;
		// }
	}
	cout<<s;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll TESTS=1;
	// cin >> TESTS;
	// makesieve();
	while(TESTS--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3632
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

#define INF (1ll<<60)


long long M = 1000000007;

int main(int argc, char const *argv[]) {
    long long n;cin>>n;
    vector<long long> a(n);
    for(int i=0;i<n;++i)cin>>a[i];
    vector<long long> inv(n+1),suminv(n+1);
    inv[1] = 1;
    suminv[1] = 1;
    for(int i=2;i<n+1;++i){
        inv[i] = M - (M/i)*inv[M%i];
        inv[i] %= M;
        suminv[i]=suminv[i-1]+inv[i];
        suminv[i] %= M;
    }
    long long res=0;
    for(long long i=0;i<n;++i){
        res += a[i] * suminv[i+1];
        res %= M;
        res += a[i] * suminv[n-i];
        res %= M;
        res -= a[i];
        res %= M;
    }
    for(int i=0;i<n;++i)res = (res*(i+1))%M;
    cout<<(res+M)%M<<endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;


/*
Log order calcuration of power
*/
ll bi_pow(ll x, ll n){
  ll res = 1;
  while (n>0){
    if (n%2==1) {res = res * x % MOD;}
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}


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

  ll N;
  cin >> N;
  vector<ll> T(N);
  vector<ll> seen(N,0);
  for(ll i=(N+1)%2;i<N;i+=2){
    if (i==0){
      seen[i] = 1;
    } else {
      seen[i] = 2;
    }
  }
  REP(i,N){
    cin >> T[i];
    seen[T[i]]--;
    if (seen[T[i]] < 0){
      cout << 0 << "\n";
      return 0;
    }
  }

  ll ans = bi_pow(2, N/2);
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 1792
use std::collections::HashSet;

fn main(){
    let nm: Vec<usize> = read_vec();
    let n = nm[0];
    let m = nm[1];
    
    let vh: Vec<u32> = read_vec();
    let vab: Vec<Vec<usize>> = (0..m).map(|_| read_vec()).collect();

    let mut hs = HashSet::new();

    for ab in &vab {
        if vh[ab[0]-1] < vh[ab[1]-1] {
            hs.insert(ab[0]);
        } else if vh[ab[0]-1] > vh[ab[1]-1] {
            hs.insert(ab[1]);
        } else {
            hs.insert(ab[0]);
            hs.insert(ab[1]);
        }
    }

    let ans: usize = n - hs.len();
    
    println!("{}", ans);
}

#[allow(dead_code)]
fn read_vec<T>() -> Vec<T>
where T: std::str::FromStr,
      T::Err: std::fmt::Debug
{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    buf.split_whitespace().map(|e| e.parse().unwrap()).collect()
}


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

using namespace std;

typedef long long int lli ;

lli i,j,k,l,m,n,t,a,b,c,d,x,y,sum=0,total=0,num=0,res=0;

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

    //freopen("Input.txt","r",stdin);

    cin>>n>>a>>b;

    if(a==0)
    {
        cout<<"0\n";
        return 0;
    }

    total=a+b;

    num=n/total;

    sum=n%total;

    res=num*a;

    if(sum>=a)
    {
        res += a;
    }
    else if(sum<a)
    {
        res += sum;
    }
    cout<<res<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
#include <cassert>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define MOD (long long int)(1e9+7)
#define INF (int)(1e9)
#define LINF (long long int)(1e18)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  if(n <= 1e7){
    ret *= kaijo(n); ret %= MOD;
    ret *= gyaku_kaijo(r); ret %= MOD;
    ret *= gyaku_kaijo(n-r); ret %= MOD;
  }else{
    rep(i,r){
      ret *= n-i; ret %= MOD;
      ret *= mpow(r-i, MOD-2); ret %= MOD;
    }
  }
  return ret;
}

int main(void){
  fast_io
  cout<<fixed<<setprecision(15);

  int x,y;cin>>x>>y;
  if(x*2 <= y && y <= x*4 && y%2 == 0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}

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

// 桁数
int getDigit(int n) {
  if (n == 0) return 1;
  int d = 0;
  while (n) {
    n /= 10;
    d++;
  }
  return d;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> s(m);
  vector<int> c(m);
  rep(i, m) { cin >> s[i] >> c[i]; }

  rep(i, 1000) {
    int k = getDigit(i);
    if (k != n) continue;

    bool f = false;
    string str = to_string(i);
    rep(j, m) {
      char ch = str[s[j] - 1];
      if ((int)(ch - '0') != c[j]) {
        f = true;
        break;
      }
    }
    if (f) continue;
    cout << i << endl;
    return 0;
  }

  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll a, b;
  cin >> a >> b;
  if(a > b) swap(a, b);
  vl f;
  rep2(i, 2, sqrt(a) + 1) {
    if(a % i) continue;
    ll j = a / i;
    f.push_back(i);
    if(j > i) f.push_back(j);
  }
  if(a > 1) f.push_back(a);
  sort(all(f));
  set<ll> st;
  rep(i, f.size() - 1) rep2(j, i + 1, f.size()) if(f[j] % f[i] == 0)
      st.insert(j);
  ll ans = 0;
  rep(i, f.size()) {
    if(st.count(i)) continue;
    if(b % f[i] == 0) ans++;
  }
  cout << ans + 1 << endl;
}

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

typedef struct
{
	int i;
	int A;
} record_t;

int cmp(const void *p, const void *q)
{
	return ((record_t *)p)->A - ((record_t *)q)->A;
}

int main()
{
	int N;

	cin >> N;

	record_t toukou[N];

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

	qsort(toukou, N, sizeof(record_t), cmp);

	for (int j = 0; j < N; j++)
	{
		cout << toukou[j].i << endl;
	}

	return 0;
}


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N,A=0;
  string S;  
  cin >> N >> S;
  for (int i =0; i < N-2; i++){
    if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C'){
      A++;
    }
  }
  cout << A << endl;
}

Measured memory_bytes: 3604
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
using namespace std;
typedef long long LL;
#define ms(a,b) memset(a,b,sizeof(a))
#define eps 1e-8
const int MAXN=1e5+100;
LL a[90];
int main ()
{
    int N;
    cin>>N;
    a[0]=2;a[1]=1;
    for(int i=2;i<=N;i++){
        a[i]=a[i-1]+a[i-2];
    }
    cout<<a[N]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define bitsz(x) int(__builtin_popcount(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb(x) push_back(x)
#define INF 2e9
#define LINF 1e18
#define mod 1000000007
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
const int di[4] = {1,0,-1,0};
const int dj[4] = {0,1,0,-1};


int main() {
    int n,x,t; cin >> n >> x >> t;
    int num = n/x;
    if (n%x!=0) num++;
    cout << num*t << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
int n,dat[400001];
void init(int n_){
	n=1;
	while(n<n_)n*=2;
}
void update(int k,int a){
	k+=n-1;
	dat[k]+=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=dat[k*2+1]+dat[k*2+2];
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<=a||b<=l)return 0;
	if(a<=l&&b>=r)return dat[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return vl+vr;
}
int q;
signed main(){
	cin>>n>>q;
	init(n); 
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		if(a)cout<<query(b-1,c,0,0,n)<<endl;
		else update(b-1,c);
	}
	return 0;
}




Measured memory_bytes: 4688
#include <iostream>

using namespace std;

int main() {
	int n, k; cin >> n >> k;
	if (n>=k&&n%k !=0)cout << 1<< endl;
	if (n>=k&&n%k == 0)cout << 0 << endl;
	if (n < k)cout << 1 << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){

  string S;
  cin>>S;
  string sub1;
  string sub2;
  sub1=S[0];
  int ans=0;
  for(size_t i=1;i<=S.length()-1;i++){
  
    sub2=S[i];
    if(sub1==sub2){
    
      if(i==S.length()-1){
      
         break;
      }
      sub2+=S[i+1];
      i++;
    }
    else sub2;
    //cout<<sub1<<" "<<sub2<<endl;
    sub1=sub2;
    ans++;
  }
  cout<<ans+1;
}

Measured memory_bytes: 3780
from collections import deque
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
m = [["#"] * (W+2)] + [["#"] + list(input()) + ["#"] for _ in range(H)] + [["#"] * (W+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
	for w in range(1, W+1):
		if m[h][w] == "#":
			q.appendleft([h, w])
			step[h][w] = 0

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "#" and step[h][w] > step[label[0]][label[1]] + 1:
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Measured memory_bytes: 171016
package main

import (
	"bufio"
	"errors"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const (
	initialBufSize = 1000
	maxBufSize     = 100000000
	stackLength    = 100
)

var sc *bufio.Scanner = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
	return sc
}()

func scanString() (s string) {
	sc.Scan()
	return sc.Text()
}

// Stack represent stack
type Stack struct {
	Stack [stackLength]int
	Len   int
}

func (s *Stack) push(num int) error {
	if s.Len >= stackLength {
		return errors.New("stack overflow")
	}
	s.Stack[s.Len] = num
	s.Len++
	return nil
}

func (s *Stack) pop() (int, error) {
	if s.Len <= 0 {
		return 0, errors.New("stack have no operand")
	}
	num := s.Stack[s.Len-1]
	s.Len--
	return num, nil
}

func (s *Stack) pop2() (int, int, error) {
	if s.Len <= 1 {
		return 0, 0, errors.New("stack have no operand")
	}
	second := s.Stack[s.Len-1]
	first := s.Stack[s.Len-2]
	s.Len -= 2
	return first, second, nil
}

func main() {
	input := scanString()
	slice := strings.Split(input, " ")

	var s Stack
	var first, second, result int
	var err error

	for _, token := range slice {
		i, err := strconv.Atoi(token)
		// operand
		if err != nil {
			first, second, err = s.pop2()
			if token == "+" {
				result = first + second
			} else if token == "-" {
				result = first - second
			} else if token == "*" {
				result = first * second
			} else {
				reportErr(errors.New("invalid input"))
			}
			err = s.push(result)
			if err != nil {
				reportErr(err)
			}
		} else {
			err = s.push(i)
			if err != nil {
				reportErr(err)
			}
		}
	}
	result, err = s.pop()
	if err != nil {
		reportErr(err)
	}
	fmt.Println(result)
}

func reportErr(err error) {
	fmt.Println(err)
	os.Exit(1)
}



Measured memory_bytes: 1136
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

bool isPrime(int p) {
	if (p == 1) return false;
	for (ll i = 2; i * i <= p; ++i) {
		if (p % i == 0)
			return false;
	}
	return true;
}

struct BipartiteMatching {
	vector< vector< int > > graph;
	vector< int > match, alive, used;
	int timestamp;

	BipartiteMatching(int n) : graph(n), alive(n, 1), used(n, 0), match(n, -1), timestamp(0) {}

	void add_edge(int u, int v) {
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	bool dfs(int idx) {
		used[idx] = timestamp;
		for (auto& to : graph[idx]) {
			int to_match = match[to];
			if (alive[to] == 0) continue;
			if (to_match == -1 || (used[to_match] != timestamp && dfs(to_match))) {
				match[idx] = to;
				match[to] = idx;
				return true;
			}
		}
		return false;
	}

	int bipartite_matching() {
		int ret = 0;
		for (int i = 0; i < graph.size(); i++) {
			if (alive[i] == 0) continue;
			if (match[i] == -1) {
				++timestamp;
				ret += dfs(i);
			}
		}
		return ret;
	}
};

int main() {
	int N; cin >> N;
	vector<int> x(N);
	for (int i = 0; i < N; ++i)
		cin >> x[i];
	vector<int> idx_even, idx_odd;
	for (int i = 0; i < N; ++i) {
		if (i == 0 || x[i - 1] + 1 != x[i]) {
			if (x[i] % 2) idx_even.push_back(x[i] - 1);
			else idx_odd.push_back(x[i] - 1);
		}
		if (i == N - 1 || x[i] + 1 != x[i + 1]) {
			if (x[i] % 2) idx_odd.push_back(x[i]);
			else idx_even.push_back(x[i]);
		}
	}

	/*
	for (auto i : idx_even) cout << i << " ";
	cout << endl;
	for (auto i : idx_odd) cout << i << " ";
	cout << endl;
	*/

	int sz = idx_even.size() + idx_odd.size();
	BipartiteMatching bm(sz);
	for (int i = 0; i < idx_even.size(); ++i) {
		for (int j = 0; j < idx_odd.size(); ++j) {
			int d = abs(idx_even[i] - idx_odd[j]);
			if (d != 2 && isPrime(d)) {
				int id1 = i, id2 = idx_even.size() + j;
				bm.add_edge(id1, id2);
			}
		}
	}

	int res = bm.bipartite_matching();
	int left_even = idx_even.size() - res;
	int left_odd = idx_odd.size() - res;
	res += left_even / 2 * 2;
	res += left_odd / 2 * 2;
	if (left_even % 2) {
		res += 3;
	}

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

Measured memory_bytes: 384
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    while(true){
        int n;
        cin >> n;
 
        if(n==0)
            break;
 
        string w[40];
        int len[40];
        for(int i=0; i<n; i++){
            cin >> w[i];
            len[i] = w[i].size();
        }
 
        for(int i=0; i<n; i++){
            bool flg = false;
            int sta = 0;
            int sum = 0;
 
            for(int j=i; j<n; j++){
                sum += len[j];
 
                if(sum==5 || sum==12 || sum==17 || sum==24 || sum==31){
                    sta++;
                }
 
                if(sta==5){
                    flg = true;
                    break;
                }
                else if(sum>=31){
                    break;
                }
            }
 
            if(flg){
                cout << i+1 << endl;
                break;
            }
        }
    }
 
    return 0;
}


Measured memory_bytes: 3116
import std;

alias sread = () => readln.chomp();
alias lread = () => readln.chomp.to!long();
alias aryread(T = long) = () => readln.split.to!(T[]);
//aryread!string();
//auto PS = new Tuple!(long,string)[](M);
//x[]=1;でlong[]全要素1に初期化
void main()
{
    auto n = sread();
    // writeln(n);
    long sum_n;
    foreach (i; 0 .. (n.length))
    {
        sum_n += n[i] - '0';
    }
    // writeln(sum_n);
    auto tmp = new long[](n.length);
    auto long_n = n.to!long();
    // writeln(long_n / (10 ^^ ((n.length) - 1)) - 1);
    tmp[0] = long_n / (10 ^^ ((n.length) - 1)) - 1;
    foreach (i; 1 .. (n.length))
    {
        tmp[i] = 9;
    }
    // writeln(tmp);
    // writeln(tmp.sum());
    writeln(max(sum(tmp), sum_n));
}

void scan(L...)(ref L A)
{
    auto l = readln.split;
    foreach (i, T; L)
    {
        A[i] = l[i].to!T;
    }
}

void arywrite(T)(T a)
{
    a.map!text.join(' ').writeln;
}


Measured memory_bytes: 3616
#include <iostream>
using namespace std;
int main(void){
      
    int a,b;
    cin >>a>>b;
    
    if(a==1)a=14;
    if(b==1)b=14;
    
    if(a>b){
        cout<<"Alice"<<endl;
    }
    
    else if(b>a){
        cout<<"Bob"<<endl;
    }
    else if(a==b){
        cout<<"Draw"<<endl;
    }
    
    
    }


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

int main() {

	string s; cin >> s;
	int x,y; cin >> x >> y;

	REP(i,s.size()) {
		if (s[i] == 'F') x--;
		else {
			s = s.substr(i, (int)s.size() - i);
			break;
		}
		if (i == s.size() - 1) {
			if (x == 0 && y == 0) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	vector < pair < int, int > > state;
	int cntF = 0, cntT = 0;
	REP(i,s.size()) {
		if (s[i] == 'F') cntF++;
		if (i > 0) if (s[i] == 'T' && s[i - 1] == 'F') {
			state.push_back(make_pair(cntT, cntF));
			cntF = 0;
			cntT = 0;
		}
		if (s[i] == 'T') cntT++;
		if (i == s.size() - 1) state.push_back(make_pair(cntT, cntF));
	}

	REP(i,state.size()) state[i].first %= 2;

	vector < int > xd,yd;
	int dir = 0;
	REP(i,state.size()) {
		if (state[i].first == 0) {
			if (dir == 0) xd.push_back(state[i].second);
			else yd.push_back(state[i].second);
		} else {
			if (dir == 0) {
				dir = 1;
				yd.push_back(state[i].second);
			} else {
				dir = 0;
				xd.push_back(state[i].second);
			}
		}
	}

	set < int > can_x, can_y;
	can_x.insert(0);
	can_y.insert(0);
	REP(i,xd.size()) {
		set < int > can_t;
		for (auto xt : can_x) {
			can_t.insert(xt + xd[i]);
			can_t.insert(xt - xd[i]);
		}
		can_x = can_t;
	}
	REP(i,yd.size()) {
		set < int > can_t;
		for (auto yt : can_y) {
			can_t.insert(yt + yd[i]);
			can_t.insert(yt - yd[i]);
		}
		can_y = can_t;
	}

	if (can_x.find(x) != can_x.end() && can_y.find(y) != can_y.end()) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 768
#include <stdio.h>

int main()
{
  long w, h, x, y;
  int flag;
  scanf("%ld%ld%ld%ld", &w, &h, &x, &y);
  flag=0;
  if(w==2*x && h==2*y){
    flag=1;
  }
  printf("%.6f %d\n", (double)w*(double)h*0.5, flag);
  return 0;
}

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

struct Edge {
    int from, to, cost;
};

int main() {
    int l;
    cin >> l;
    int r = log2(l);
    vector<Edge> es;
    int nv = r + 1, ne = 2 * r;
    for (int i = 0; i < r; i++) {
        es.push_back(Edge{i + 1, i + 2, 0});
        es.push_back(Edge{i + 1, i + 2, 1 << i});
    }
    int pow_r = 1 << r;
    for (int i = r; i >= 1 && l - pow_r > 0; i--) {
        int pow_i = 1 << (i - 1);
        if (l - pow_r >= pow_i) {
            l -= pow_i;
            es.push_back(Edge{i, nv, l});
            ne++;
        }
    }


    cout << nv << " " << ne << endl;
    for (Edge e : es)
        cout << e.from << " " << e.to << " " << e.cost << endl;
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;

const int N = 1e5 + 10;
set<int> a[N];
bool visit[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x; --y;
    a[x].insert(y);
    a[y].insert(x);
  }
  set<int> Q;
  for (int i = 0; i < n; ++i) {
    if (a[i].size() == 1) {
      Q.insert(i);
    }
  }
  bool found = false;
  while (!found && !Q.empty()) {
    set<int> nxt;
    for (auto& u : Q) {
      if (a[u].empty()) {
        found = true;
        break;
      }
      int v = *a[u].begin();
      if (Q.find(v) != Q.end()) continue;
      if (nxt.find(v) == nxt.end()) {
        nxt.insert(v);
      } else {
        found = true;
        break;
      }
    }
    // trace(found);
    for (auto& u : nxt) {
      // trace(u);
      visit[u] = true;
    }
    set<int> Q2;
    for (auto& u : nxt) {
      for (auto& v : a[u]) {
        if (Q.find(v) != Q.end() || visit[v]) continue;
        a[v].erase(u);
        if (a[v].size() == 1) {
          Q2.insert(v);
        }
      }
    }
    Q = move(Q2);
    // cout << "Q: " << endl;
    // for (auto& it : Q) {
    //   cout << it << " ";
    // }
    // cout << endl;
  }
  puts(found ? "First" : "Second");
  return 0;
}


Measured memory_bytes: 19584
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define loop1(n, i) for(int i=1;i<=n;i++)
#define rloop(n, i) for(int i=n-1;i;i--)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;

void solve(string s){
    int n = s.length();
    s.push_back('.');
    V<ll> A;
    loop (n, i) {
        if (s[i] == 'A') {
            A.push_back(0);
            continue;
        }
        if (s[i] == 'B' && s[i + 1] == 'C') {
            A.push_back(1);
            i++;
            continue;
        }
        A.push_back(-1);
    }
    int m = A.size();
    V<ll> B = A;
    rloop (m, i) {
        if (i && B[i - 1] != -1 && B[i] != -1) {
            B[i - 1] += B[i];
        }
    }
    ll ans = 0;
    loop (m, i) {
        if (A[i] == 0) {
            ans += B[i];
        }
    }
    cout << ans << endl;
}

int main(){
    string s;
    cin >> s;
    solve(s);
    return 0;
}



Measured memory_bytes: 3956
from math import ceil, floor

h, n = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]

if n == 1:
  print(ceil(h/l[0][0]) * l[0][1])
  exit(0)

dp = [ceil(hp/l[0][0]) * l[0][1] for hp in range(h + 1)]

for i in range(1, n):
  for hp in range(h + 1):
    if hp >= l[i][0]:
      dp[hp] = min([dp[hp], dp[hp - l[i][0]] + l[i][1]])
    else:
      dp[hp] = min([dp[hp], l[i][1]])

print(dp[-1])

Measured memory_bytes: 85724
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
	int N, W; cin >> N >> W;
	vector<int> w(N + 1), v(N + 1);
	for (int i = 1; i <= N; ++i) cin >> w[i] >> v[i];
	vector<vector<long long> > dp(N + 1, vector<long long>(N * 1000 + 1, 1e10));
	dp[0][0] = 0;
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j <= N * 1000; ++j) {
			if (j < v[i]) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= N * 1000; ++i)
    	if (dp[N][i] <= W) ans = i;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 80256
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
long long int dp[100020] = {};
int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b == c + d) {
		cout << "Balanced";
	}
	else if (a + b < c + d) {
		cout << "Right";
	}
	else {
		cout << "Left";
	}
}

Measured memory_bytes: 384
n,t=gets.chomp.split.map(&:to_i)
c = []
n.times do
    cc, tt = gets.chomp.split.map(&:to_i)
    if tt <= t
        c << cc
    end
end
if c.size > 0
    puts c.sort[0]
else
    puts "TLE"
end

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

using namespace std;

using ull = unsigned long long;


int main() {
    int N, B[100], sum = 0;
    cin >> N;
    for(int i = 0; i < N-1; ++i) {
        cin >> B[i];
    }
    B[N-1] = 100000;
    sum = B[0];
    for(int i = 1; i < N; ++i) {
        sum += min(B[i - 1], B[i]);
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ri register int 
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = (x << 1) + (x << 3) + (c & 15); x *= f;
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	// no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} 
using io :: gi;
using io :: putc;
using io :: print;
const int N=2005;
int tot,head[N],nxt[N<<1],adj[N<<1],mark[N][N],fa[N][N];
inline void addedge(ri x,ri y){
	nxt[++tot]=head[x];
	adj[head[x]=tot]=y;
}
inline void predfs(ri u,ri x){
	for(ri y,i=head[x];i;i=nxt[i])
		if((y=adj[i])!=fa[u][x])
			fa[u][y]=x,
			predfs(u,y);
}
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
pii q[N*N];
int r,ans;
inline void dfs(ri u,ri v,ri x){
	mark[u][x]=v;
	for(ri y,i=head[x];i;i=nxt[i])
		if((y=adj[i])!=fa[u][x]){
			if(!mark[u][y])
				dfs(u,v,y);
			else // mark[u][y] == y
				q[++r]=mp(v,mark[u][y]);
		}
}
inline void calc(ri x,ri lst,ri u){
	if(mark[u][x]==x)
		++ans,u=x;
	for(ri y,i=head[x];i;i=nxt[i])
		if((y=adj[i])!=lst)
			calc(y,x,u);
}
int main(){
	ri n,m,i,x,y,l;
	gi(n);gi(m);
	for(i=1;i^n;++i)
		gi(x),gi(y),
		addedge(x,y),
		addedge(y,x);
	for(i=1;i<=n;++i)
		predfs(i,i);
	l=1;r=0;
	while(m--) gi(x),gi(y),q[++r]=mp(x,y);
	while(l<=r){
		x=q[l].fi;
		y=q[l].se;
		++l;
		while(mark[x][y]) x=mark[x][y];
		while(mark[y][x]) y=mark[y][x];
		if(x==y) continue;
		dfs(x,y,y);
		dfs(y,x,x);
	}
	for(x=1;x<=n;++x)
		for(i=head[x];i;i=nxt[i])
			calc(adj[i],x,x);
	ans>>=1;
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 35200
N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])

Measured memory_bytes: 258568
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	log.SetFlags(log.Lshortfile)
	a1 := nextInt()
	a2 := nextInt()
	a3 := nextInt()
	if a1+a2+a3 >= 22 {
		fmt.Println("bust")
	} else {
		fmt.Println("win")
	}
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type pair struct {
	a, b int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


Measured memory_bytes: 640
import java.io.*;
import java.util.Arrays;
public class Main {
        public static void main(String[] args) throws IOException {
                BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                String is; 
                String ia[];
                while((is = in.readLine()) != null){
                        ia = is.split(" ");
                        System.out.println(ea(Integer.parseInt(ia[0]),Integer.parseInt(ia[1])));
                }   
        }   
            
        static int ea(int m, int n){ 
                if(n == 0){ 
                        return m;
                }   
                return ea(n, m%n);
        }   
}

Measured memory_bytes: 9208
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define ll long long
#define ld long double
#define fi first
#define se second
#define sz(x) x.size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define rep(i, x, n) for (ll i = x; i < n; i++)
#define fastio() ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0)
#define endl '\n'

typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> ii;
typedef vector<pair<int, int> > vii;

template <class T> inline T RD(T &a) {T x; cin >> x; return a = x;}
template <class T> T gcd(T a, T b) {if (b) return gcd(b, a % b); else return a;}
template <class T> T lcm(T a, T b) {return (a * b) / gcd(a,b);}

signed main() {
    ll a, b; cin >> a >> b;
    ll ans = 0;
    for (ll i = a; i % 4 != 0; i++) {
        ans ^= i;
    }
    for (ll i = b; i % 4 != 0; i--) {
        b--;
        ans ^= i;
    }
    ans ^= b;
    cout << ans;
}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

const ll MAX_N = 1e5 + 5, MOD = 1e9 + 7;
ll n, m;
ll p[MAX_N];
ll q[MAX_N];
ll Arr[MAX_N];

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

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		cin >> Arr[i];
		Arr[i] >>= 1;
	}

	ll tmp = 1;
	for (ll i = 0; i < n; i++) {
		tmp = tmp * Arr[i] / _gcd(tmp, Arr[i]);
	}

	for (ll i = 0; i < n; i++)
		if ((tmp / Arr[i]) % 2 == 0) {
			cout << "0\n";
			return 0;
		}

	cout << (m / tmp + 1) / 2 << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <cassert>
#include <cstdint>
#include <functional>
#include <vector>

template <typename Monoid> class SegmentTree {
	using uint32 = std::uint_fast32_t;
	using F = std::function<Monoid(const Monoid &, const Monoid &)>;
	const F f;
	const Monoid neutral_;
	const uint32 size_;
	std::vector<Monoid> tree;
	static uint32 getsize(const uint32 size) {
		uint32 ret = 1;
		while (ret < size)
			ret <<= 1;
		return ret;
	}
	void recalc(const uint32 index) {
		tree[index] = f(tree[index << 1], tree[index << 1 | 1]);
	}

public:
	SegmentTree(const uint32 size, const Monoid &neutral = Monoid(),
		const F &f = std::plus<Monoid>())
		: f(f), neutral_(neutral), size_(getsize(size)),
		tree(size_ << 1, neutral_) {}
	SegmentTree(const std::vector<Monoid> &arr, const Monoid &neutral = Monoid(),
		const F &f = std::plus<Monoid>())
		: f(f), neutral_(neutral), size_(getsize(arr.size())),
		tree(size_ << 1, neutral_) {
		for (uint32 i = 0; i < arr.size(); ++i)
			tree[size_ + i] = arr[i];
		for (uint32 i = size_; --i;)
			recalc(i);
	}
	void update(uint32 index, const Monoid &data) {
		assert(index < size_);
		tree[index += size_] = data;
		while (index >>= 1)
			recalc(index);
	}
	void update(uint32 index, const std::function<Monoid(const Monoid &)> &g) {
		update(index, g(tree[index + size_]));
	}
	Monoid range(uint32 begin, uint32 end) const {
		assert(begin <= end);
		assert(begin <= size_);
		assert(end <= size_);
		Monoid retL = neutral_, retR = neutral_;
		for (begin += size_, end += size_; begin < end; begin >>= 1, end >>= 1) {
			if (begin & 1)
				retL = f(retL, tree[begin++]);
			if (end & 1)
				retR = f(tree[end - 1], retR);
		}
		return f(retL, retR);
	}
	const Monoid &operator[](const uint32 index) const {
		assert(index < size_);
		return tree[index + size_];
	}
};
#include<iostream>
#include<algorithm>
int main(void) {
	int n, q;
	std::cin >> n >> q;
	SegmentTree<int> T(n, 2147483647, [](int l, int r) {return std::min(l, r);});
	while (q--) {
		int c, x, y;
		std::cin >> c >> x >> y;
		if (c) {
			std::cout << T.range(x, y + 1) << "\n";
		}
		else {
			T.update(x, y);
		}
	}
	return 0;
}


Measured memory_bytes: 3820
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


x, y = map(int, input().split())

b = max(x, y)
s = min(x, y)

n = (2 * y - x) // 3
m = (2 * x - y) // 3

ans = 0
if (x+y) % 3 != 0 or b / s > 2:
    print(ans)
else:
    print(cmb(n+m, n) % (10 ** 9 + 7) )

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

#define ll long long int

ll get(ll n){
    set<ll> s;
    while (n % 2 == 0){
        //cout << 2 << " ";
        s.insert(2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i + 2){
        while (n % i == 0){
            //cout << i << " ";
            s.insert(i);
            n = n/i;
        }
    }
    if (n > 2)
        s.insert(n);
    return s.size() + 1;
}

int main(){
    ll a,b;
    cin>>a>>b;
    ll g = __gcd(a,b);
    //cout<<g;
    cout<<get(g);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007; // 998244353
using ll = long long;
using namespace std;

int main(){
	int a, b, k; cin >> a >> b >> k;
	if( b-a < 2*k ){
		for( int i = a; i <= b; ++i ) cout << i << endl;
		return 0;
	}
	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: 256
$a[1]=<>;
chomp($a[1]);
$l[$a[1]]=1;
for($i=2;;$i++){
    $a[$i]=($a[$i-1]%2==0)?$a[$i-1]/2:3*$a[$i-1]+1;
    if ($l[$a[$i]]){
        print $i;
        exit;
    }else{
        $l[$a[$i]]=1;
    }
}

Measured memory_bytes: 512
n = int(input())
l_s = list(map(int,input().split()))
l_s.append(0)
l_s.sort()
ans = 0
#一番長い辺を選ぶ
#print(l_s)
for i in range(3,n+1):
    for j in range(2,i):
        if l_s[i] < l_s[j] + l_s[j-1]:
            
            OK = j-1
            NG = 0
            while (OK - NG) > 1:
                mid = (OK+NG)//2
                if l_s[i] < l_s[j] + l_s[mid]:
                    OK = mid
                else:
                    NG = mid
            ans = ans + j - OK 
print(ans)



Measured memory_bytes: 42348