akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <complex>
#include <bitset>
#include <random>
#include <numeric>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n) ;++(i))
#define REPN(i,a,n) FOR((i),(a),(a)+(n))
#define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i))
#define PB push_back
#define MP make_pair
#define SE second
#define FI first
#define DBG(a) cerr<<(a)<<endl;
#define ALL(v) (v).begin(),(v).end()
typedef long long LL;  typedef pair<LL, LL> PLL; typedef vector<LL> VLL;
const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=86400;

struct Edge{
    int from,to;
    Edge(int from,int to)
        : from(from),to(to){};
};
typedef vector<vector<Edge>> Graph;

int depth(Graph &T, vector<int> &p, vector<int> &dep,vector<vector<int>> &dtov,int root){
    int ret =0;
    queue<int> Q;
    Q.push(root);
    p[root]=root;
    dtov[0].push_back(root);
    while(!Q.empty()){
        int nex=Q.front();
        Q.pop();
        for(auto x: T[nex]){
            if(p[x.to]==-1){
                p[x.to]=x.from;
                Q.push(x.to);
                dep[x.to]=dep[x.from]+1;
                ret=max(ret,dep[x.to]);
                dtov[dep[x.to]].push_back(x.to);
            }
        }
    }
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<int>par(n,-1),dep(n),subleaf(n),subleng(n);
    Graph T(n);
    vector<vector<int>> d(n);
    REP(i,n-1){
        int a,b;
        cin >> a >>b;
        a--;b--;
        T[a].PB(Edge(a,b));
        T[b].PB(Edge(b,a));
    }
    int r,leaf=0;
    REP(i,n)if(T[i].size()==1){
        r=i;
        leaf++;
    }
    int mdep=depth(T,par,dep,d,r);
    int ans=0,ans2=0;
    for(int i=mdep; i>=0;--i){
        for(auto x : d[i]){
            //vector<int> mainchain;
            if(T[x].size()==1){
                subleaf[x]=1;
            }else{
                int lev=0,len=0,len2=0;
                for(auto y: T[x]){
                    if(y.to!=par[y.from]){
                        lev+=subleaf[y.to];
                        len2=max(len2,subleng[y.to]);
                        if(len2>len)swap(len,len2);
                    }
                }
                if(T[x].size()==2)len++;
                subleaf[x]=lev;
                subleng[x]=len;
                ans=max(ans,leaf+len2+len);
            }
        }
    }
    for(auto x: T[r]){
        ans2+=subleaf[x.to]+subleng[x.to]+1;
    }
    cout << max(ans,ans2) <<endl;

    /*REP(i,n){
        cout << T[i].size()<<' '<<subleaf[i]<<' '<<subleng[i]<<endl;
    }*/
    return 0;
}


Measured memory_bytes: 10752
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

bool isPrime(
    int n) { /* returns whether n is prime number or not * n should be in range
                [0, lim]. * to see detail, search 'Sieve of Eratosthenes' */
  static int lim = 1e5;
  static bool done = false;
  static vector<bool> isp(lim + 1, 1);
  if (!done) {
    isp[0] = isp[1] = false;
    for (int i = 2; i <= lim; i++) {
      if (isp[i]) {
        for (int j = i + i; j <= lim; j += i) {
          isp[j] = false;
        }
      }
    }
    done = true;
  }
  return isp[n];
}
std::map<long long, long long> primeFactorization(
    long long n) { /* prime factorization * nを素因数分解する */
  std::map<long long, long long> pf;
  for (long long i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      n /= i;
      ++pf[i];
    }
  }
  if (n > 1) {
    ++pf[n];
  }
  return pf;
}

int main() {
  LL A,B;
  cin>>A>>B;
  auto ma = primeFactorization(A);
  auto mb = primeFactorization(B);
  // DUMP(ma);
  // DUMP(mb);
  LL cnt= 1;
  for(auto va:ma){
    if(mb[va.first]!=0)cnt++;
  }
  cout<<cnt<<endl;


  return 0;
}


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

#define int long long
#define f first
#define ld long double
#define s second
using namespace std;

template<typename T> using vc = vector<T>;
using pii=pair<int, int>;

void xmax(int & a, int b){
    a=max(a, b);
}
void xmin(int& a, int b){
    a=min(a, b);
}

void print(vc <int> & a, string s){
    cerr << s << " : ";
    for (int i=0; i<a.size(); i++){
        cerr <<a[i] << " ";
    }
    cerr << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL_RUN
    freopen("input.txt", "r", stdin);
    int ttt;
    cin >> ttt;
    while(ttt--){
    #endif // LOCAL_RUN

    int a, b, c;
    cin >> a >> b >> c;
    int prod = 4*a*b;
    int sq = (c-a-b)*(c-a-b);
    if (c-a-b<0 || prod>=sq){
        cout << "No\n";
    }else{
        cout << "Yes\n";
    }

    #ifdef LOCAL_RUN
    }
    #endif // LOCAL_RUN
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll x,y,i,m,s=0,d,c=0,n,c1=0;
    vector<ll>a;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>m;
        a.push_back(m);
        s+=m;
    }
    m=(s/n);
    for(i=0;i<n;i++)
    {
        c+=((m-a[i])*(m-a[i]));
    }
    m++;
    for(i=0;i<n;i++)
    {
        c1+=((m-a[i])*(m-a[i]));
    }
    cout<<min(c,c1)<<endl;
}


Measured memory_bytes: 384
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//最大公約数と最小公倍数
ll gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

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

vector<vector<long long> > comb(int n) {
  vector<vector<long long> > v(n + 1,vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    int c=0;
    while (N>=3)
    {
        N-=3;
        c++;
    }
    
    cout << c << endl;

    return 0;
}



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

ll N;
vector<string> s;

void solve() {
  ll res = 0;
  for (int i = 0; i < N; i++) {
    int n = s[i].size();
    for (int j = 0; j <= n - 2; j++) {
      if (s[i].substr(j, 2) == "AB") {
        res++;
      }
    }
  }
  ll XA = 0, BX = 0, BA = 0;
  for (int i = 0; i < N; i++) {
    int n = s[i].size();
    if (s[i][0] == 'B' && s[i][n - 1] == 'A') {
      BA++;
    }
    else if (s[i][0] == 'B' && s[i][n - 1] != 'A') {
      BX++;
    }
    if (s[i][0] != 'B' && s[i][n - 1] == 'A') {
      XA++;
    }
  }
  res += BA + min(BX, XA);
  if (max(BX, XA) == 0 && BA >= 1) {
    res--;
  }

  cout << res << "\n";
}

int main() {
  cin >> N;
  s.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> s[i];
  }
  solve();
  return 0;
}

Measured memory_bytes: 768
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; ++i)
#define RANGE(i, x, n) for(ll i = x; i < n; ++i)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

void accelerate()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

const ll mod = 998244353;
const int MAXN = 310;
ll dp[MAXN][MAXN*MAXN];

ll dp2[MAXN][MAXN*MAXN];

ll quickpow(ll x, ll n)
{
    ll ans = 1;
    while(n) {
        if(n&1) {
            ans *= x;
            ans %= mod;
        }
        x *= x;
        x %= mod;
        n >>= 1;
    }
    return ans;
}

int main()
{
    accelerate();
    int n;
    cin >> n;
    vector<int> A(n);
    REP(i, n) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    vector<int> sum(n+1);
    REP(i, n) {
        sum[i+1] += sum[i] + A[i];
    }
    REP(i, n+1) {
        if(i == 0) {
            dp[i+1][A[i]] = 1;
            dp[i+1][0] = 2;
        }else {
            REP(j, MAXN*n) {
                dp[i+1][j] += dp[i][j]*2%mod;
                dp[i+1][j] %= mod;
                if(j >= A[i]) dp[i+1][j] += dp[i][j-A[i]];
                dp[i+1][j] %= mod;
            }
        }
    }

    REP(i, n+1) {
        if(i == 0) {
            dp2[i+1][A[i]] = 1;
            dp2[i+1][0] = 1;
        }else {
            REP(j, MAXN*n) {
                dp2[i+1][j] += dp2[i][j]%mod;
                dp2[i+1][j] %= mod;
                if(j >= A[i]) dp2[i+1][j] += dp2[i][j-A[i]];
                dp2[i+1][j] %= mod;
            }
        }
    }


    ll top = sum[n];
    ll ans = 0;
    ll ans2 = 0;
    REP(j, MAXN*n) {
        if(2*j >= top) {
            ans += dp[n][j];
            ans %= mod;
        }
        if(2*j == top){
            ans2 += dp2[n][j];
            ans2 %= mod;
        }
    }
    ans = ans*3%mod;
    ans %= mod;
    ans = quickpow(3, n) - ans + ans2*3;
    ans %= mod;
    if(ans < 0) ans += mod;
    cout << ans << endl;
}

Measured memory_bytes: 453376
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define MAX 10001
#define B 100
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
#define P pair<int,int>
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

chrono::system_clock::time_point  start;
void timerstart(){start = chrono::system_clock::now();}
void timerend(){
	auto end = chrono::system_clock::now();
	int elapsed = chrono::duration_cast<chrono::milliseconds>(end-start).count();
	printf("%d[ms]\n", elapsed);
}


int main(){
	int a, b, f = 0, p = 0;
	string str;
	cin >> a >> b >> str;
	rep(i,a){
		if('9' < str[i] || str[i] < '0')f = 1;
		p++;
	}
	if(str[p] != '-'){
		f = 1;
	}
	p++;
	
	rep(i,b){
		if('9' < str[i+p] || str[i+p] < '0')f = 1;
	}
	//cout << p << f << endl;
	if(f == 0)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
ans :: [Int] -> Int
ans (m:n:_) =
  length $ [ (a,b,c) | a <- [1..m], b <- [1..m], c <- [1..m], a < b, b < c, a + b + c == n ]

main = do
  l <- getContents
  let i  = map (map read) $ map words $ lines l :: [[Int]]
      i' = takeWhile (/= [0,0]) i
      o  = map ans i'
  mapM_ print o
  

Measured memory_bytes: 4904
Array.prototype.remove = function(from, to) {
  var rest = this.slice((to || from) + 1 || this.length);
  this.length = from < 0 ? this.length + from : from;
  return this.push.apply(this, rest);
};
function sortNumber(a,b) {
    return a - b;
}
function Main(input){
 input=input.split("\n")
 var cardsN = parseInt(input[0])
 var cards = input[1].split(" ").map(x=>parseInt(x))
 
 cards.sort(sortNumber).reverse()
 var A=0, B=0
 var isA = true
 while(cards.length!=0) {
   if(isA) {
    A += cards[0]
    cards.remove(0)
   } else {
    B += cards[0]
    cards.remove(0)
   }
   isA = !isA
 }
  console.log(A-B)
}

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


Measured memory_bytes: 7624
#include<iostream>
#include<string>
#include<set>
#include<utility>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<stack>

//#include"gap.h"

using namespace std;


int dp[3005][3005] = {};
	
int main(){
	string s, t;

	cin >> s >> t;

	for(int i=1; i<=s.size(); i++){
		for(int j=1; j<=t.size(); j++){
			if(s[i-1] == t[j-1]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}
			else{
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}

	string ans = "";
	int i = s.size(), j = t.size();
	while (i > 0 && j > 0)
	{
		if(dp[i][j] == dp[i][j-1]){
			j--;
		}
		else if(dp[i][j] == dp[i-1][j]){
			i--;
		}
		else{
			ans += s[i-1];
			i--;
			j--;
		}
	}

	if(ans.size() == 0){
		cout << ' ' << endl;

		return 0;
	}

	reverse(ans.begin(), ans.end());

	cout << ans << endl;


	return 0;
}


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

int main() {
  long long n;
  cin >> n;
  vector<long long> a(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  long long mod = pow(10, 9) + 7, sum = 0, ans = 0;
  for(auto k : a) sum += k;
  for(int i = 0; i < n; i++){
    long long k = a.at(i);
    sum -= k;
    ans += sum % mod * k % mod;
    ans %= mod;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 4840
A, B, K = map(int, input().split())
if A > K:
    print(A-K, B)
if A == K:
    print(0, B)
if (A < K) and (A + B > K) :
    print(0, B - (K - A))
if (A < K) and (A + B <= K) :
    print(0, 0)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int a;
  int b;

  cin >> a >> b;

  int c = a * b;

  if (c % 2 != 0) {
    cout << "Odd" << endl;
  }
  else {
    cout << "Even" << endl;
  }
	
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    map<int,int> a,b;
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    for(int i=0;i<n;i++){
        if(i%2==0){
            a[v[i]]++;            
        }else{
            b[v[i]]++;
        }
    }
    int a1=0,b1=0;
    int a1_num = 0, b1_num = 0; 
    for(auto x:a){
        int k = x.second;
        if(a1 < k){
            a1 = k;
            a1_num = x.first;
        }
    }
    for(auto x:b){
        int k = x.second;
        if(b1 < k){
            b1 = k;
            b1_num = x.first;
        }
    }
    //cout << "a1_num = " << a1_num << " b1_num = " << b1_num << endl;
    if(a1_num != b1_num){cout << n - a1 - b1 << endl; return 0;}
    else{
        int a2 = 0,b2 = 0;
        int a2_num,b2_num;
        map<int,int> ca = a,cb = b;
        ca.erase(a1_num);
        cb.erase(b1_num);
        for(auto x:ca){
            int k = x.second;
            if(a2 < k){
            a2 = k;
            a2_num = x.first;
            }
        }
        for(auto x:cb){
            int k = x.second;
            if(b2 < k){
                b2 = k;
                b2_num = x.first;
            }
        }
        //cout << "a2_num = " << a2_num << " b2_num = " << b2_num << endl;
        cout << min(n-a1-b2,n-a2-b1) << endl;
    }
}

Measured memory_bytes: 9984
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
#include <random>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }


signed main()
{
	int d, t, s;
	cin >> d >> t >> s;
	YesNo(d <= s * t);
}



Measured memory_bytes: 3096
//package src.com.jetman.atcoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @description:
 * @author: Jetman
 * @create: 2020-08-29 14:39
 **/
public class Main {

    Scanner sc = new Scanner(System.in);

    long MOD = 1000000000 + 7;

    long dp[][];

    private void slove() {

        int s = sc.nextInt();

        dp = new long[s+1][s+1];

        long ans = 0;
        int tmp = s/3;
        for (int i = 1; i <= tmp; i++) {

            ans = (ans + Comb(s-2*i-1,i-1,MOD))%MOD;
        }
        System.out.println(ans);

    }

    long exp_mod(long a, long b, long p) {
        long res = 1;
        while(b != 0) {
            if((b&1) > 0) res = (res * a) % p;
            a = (a*a) % p;
            b >>= 1;
        }
        return res;
    }

    long Comb(long a, long b, long p) {
        if(a < b)   return 0;
        if(a == b)  return 1;
        if(b > a - b)   b = a - b;

        long ans = 1, ca = 1, cb = 1;
        for(long i = 0; i < b; ++i) {
            ca = (ca * (a - i))%p;
            cb = (cb * (b - i))%p;
        }
        ans = (ca*exp_mod(cb, p - 2, p)) % p;
        return ans;
    }

    private void cal() {
        long[] sum = new long[2001];
        for (int i = 1; i <=2000 ; i++) {
            dp[i][1] = 1;
            sum[i] = i;
        }
        sum[0] =1;
        for (int k = 2; k <= 2000 ; k++) {
            for (int s = k; s <= 2000; s++) {
                dp[s][k] = sum[s-k];
            }
            sum[0] = 1;
            for (int s = k+1; s <= 2000; s++) {
                sum[s-k] = (sum[s-k] + sum[s-k-1])%MOD;
            }
        }
    }

    private long work(int s,int k) {
        if (dp[s][k] != 0) {
            return dp[s][k];
        }
        if (s == k) {
            return dp[s][k] = 1;
        }
        if (k == 1) {
            return dp[s][k] = 1;
        }
        long ans = 0;
        for (int i = k-1; i <= s-1; i++) {
            ans = (ans + work(i,k-1))%MOD;
        }
        return dp[s][k] = ans;
    }

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


Measured memory_bytes: 84916
N, M, X, Y = gets.chomp.split.map(&:to_i)
x = gets.chomp.split.map(&:to_i).sort
y = gets.chomp.split.map(&:to_i).sort

z_range = ((X+1)..Y)

if x.max >= y.min
  puts 'War'
  exit
end

cond_range = ((x.max+1)..y.min)

if z_range.any? { |z| cond_range.include?(z) }
  puts 'No War'
else
  puts 'War'
end


Measured memory_bytes: 1788
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		for(int i = 1 ; i <= 3 ; ++i){
			if(i == A || i == B){
				continue;
			}
			System.out.println(i);
		}
	}
}


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

int main(){
  int N,i,cnt=0;
  string S;
  cin >> N >> S;

  for(i=0;i<N-2;i++){
    if(S.at(i)=='A'&&S.at(i+1)=='B'&&S.at(i+2)=='C')
    cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		int p = Integer.parseInt(sa[2]);
		List<List<Hen>> list1 = new ArrayList<>(n);
		List<List<Hen>> listn = new ArrayList<>(n);
		for (int i = 0; i < n; i++) {
			list1.add(new ArrayList<>());
			listn.add(new ArrayList<>());
		}
		Hen[] arr = new Hen[m];
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			Hen h = new Hen();
			h.a = Integer.parseInt(sa[0]) - 1;
			h.b = Integer.parseInt(sa[1]) - 1;
			h.c = -Integer.parseInt(sa[2]) + p;
			arr[i] = h;
			list1.get(h.a).add(h);
			listn.get(h.b).add(h);
		}
		br.close();

		boolean[] visit1 = new boolean[n];
		Queue<Integer> que = new ArrayDeque<>();
		que.add(0);
		visit1[0] = true;
		while (!que.isEmpty()) {
			int cur = que.poll();
			for (Hen h : list1.get(cur)) {
				if (!visit1[h.b]) {
					que.add(h.b);
					visit1[h.b] = true;
				}
			}
		}

		boolean[] visitn = new boolean[n];
		que = new ArrayDeque<>();
		que.add(n - 1);
		visitn[n - 1] = true;
		while (!que.isEmpty()) {
			int cur = que.poll();
			for (Hen h : listn.get(cur)) {
				if (!visitn[h.a]) {
					que.add(h.a);
					visitn[h.a] = true;
				}
			}
		}

		boolean[] visit = new boolean[n];
		for (int i = 0; i < n; i++) {
			visit[i] = visit1[i] && visitn[i];
		}

		long[] d = new long[n];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[0] = 0;
		boolean upd = true;
		for (int i = 0; i <= n && upd; i++) {
			upd = false;
			for (Hen h : arr) {
				if (!visit[h.a] || !visit[h.b]) {
					continue;
				}
				long alt = d[h.a] + h.c;
				if (d[h.b] > alt) {
					d[h.b] = alt;
					upd = true;
				}
			}
			if (i == n) {
				System.out.println(-1);
				return;
			}
		}
		System.out.println(Math.max(-d[n - 1], 0));
	}

	static class Hen {
		int a, b, c;
	}
}


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

int main() {
    int n;
    cin >> n;
    int numbers[n];

    for (int i = n - 1; i >= 0; i--) {
        cin >> numbers[i];
    }

    for (int i = 0; i < n; i++) {
    	cout << numbers[i];
    	if (i + 1 != n) cout << ' ';
    }
	cout << endl;;
}



Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	int a, b,c;
	string s="NO";
	cin >> a >> b>>c;
	for (int i = 0; i <= b; i++) {
		if (a*i%b == c) s = "YES";
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <limits>
#include <numeric>
#define FOR(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
using namespace std;

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

	int x, y;

	cin >> x >> y;

	x--; y--;

	cout << x * y << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <math.h>
#include <queue>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end())

const int MOD = 1000000007;
const int INF = INT_MAX;


// a,bの最小公倍数
ll lcm(ll a, ll b){ll lcm = a * b; ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return lcm /= b;}
// a,bの最大公約数
ll gcd(ll a, ll b){ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return b;}
// MOD
ll modadd(ll a, ll b){return (a%MOD+b%MOD+MOD)%MOD;}
ll modmul(ll a, ll b){return a%MOD*b%MOD%MOD;}
ll modexp(ll a, ll n){if(n==0)return 1; if(n%2==0){ll e=modexp(a,n/2); return modmul(e,e);} return modexp(a,n-1)*a%MOD;}
ll modinv(ll n){return modexp(n%MOD,MOD-2);}
ll modfact(ll n){ll res=1; for (int i=1; i <= n; ++i){res *= i; res %= MOD;} return res;}
ll modncr(ll n, ll r){ll numer=1;ll denom=1;for(int i=1;i<=r;++i){numer=modmul(numer,n-r+i);denom=modmul(denom,i);}return modmul(numer, modinv(denom));}


int main(){


    int a, b;
    cin >> a >> b;
    int k;
    cin >> k;

    if (b - k + 1 <= a + k - 1) {
        for (int i = a; i <= b; ++i) cout << i << " ";
    }
    else {
        for (int i = a; i <= a + k - 1; ++i) cout << i << " ";
        for (int i = b - k + 1; i <= b; ++i) cout << i << " ";
    }
    cout << endl;



}



//              g++ -std=c++1z


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


int main(int argc, char const *argv[])
{
	int n,k;
	cin>>n>>k;
	std::vector<int>v(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>v[i];
	}
	std::vector<bool>dp(k+1);
	for(int stones=0;stones<=k;stones++){
		for(int x=0;x<n;x++){
			if(stones>=v[x] && !dp[stones-v[x]]){
				dp[stones]=1;
			}
		}
		
	}
	cout<<(dp[k]?"First":"Second");
	return 0;
}

Measured memory_bytes: 256
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
print((n+1)//2 - 1)


Measured memory_bytes: 5276
#include <bits/stdc++.h>
using namespace std;
int n;
int d[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main(){
	cin>>n;
	cout<<d[n-1];
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
#define mx 1e18
#define pb push_back

int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt" , "r" , stdin);
	// freopen("output.txt" , "w" , stdout);
	// #endif

	ll int n,k;
	cin>>n>>k;

	ll int ar[n+1];
	for(int i=1;i<=n;i++)cin>>ar[i];

	ll int pre[n+1];
	pre[0]=0;

	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+ar[i];

	ll int s=0;

	for(int i=k;i<=n;i++)
	{
		s=max(s,pre[i]-pre[i-k]);
	}

	ll int note = s - k + 1;

	// cout<<s<<endl;

	double ans ;

	ans = ((s*(s+1))/2) - (k*(k-1))/2;

	// cout<<ans<<endl;

	ans/=(1.0*note);

	cout<<fixed<<setprecision(12)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vvi vv(n+1);
	vs ss(n);
	rep(i,n){
		int p;
		string s;
		cin>>p>>s;
		ss[i]=s;
		if(p!=0)vv[p-1].push_back(i);
	}
	stack<pii> stk;
	stk.push(pii(0,0));
	while(!stk.empty()){
		pii t=stk.top();stk.pop();
		rep(i,t.sc)cout<<'.';
		cout<<ss[t.fs]<<endl;
		rrep(i,vv[t.fs].size()){
			stk.push(pii(vv[t.fs][i],t.sc+1));
		}
	}
}



Measured memory_bytes: 3376
#include <iostream>
using namespace std;
int main(){
  int n,a=0;cin >> n;
  string  mo;cin >>mo;
  for(int i=0;i<n-1;i++){
    if((char)mo.at(i)!=(char)mo.at(i+1)){a++;}
  }
  cout << a+1<<endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define K 971
using namespace std;
typedef unsigned long long ull;

string s, t;
map<ull,int> cnt;
ull d[300005], H[300005];

signed main(){
  
  cin>>s>>t;

  ull h=0, x=1;
  
  for(int i=0;i<t.size()-1;i++) x=x*K;
  
  for(int i=0;i<s.size();i++){
    h=h*K+s[i];
    if(i>=t.size()-1){
      cnt[h]++;
      h=h-s[i-(t.size()-1)]*x;
    }
  }

  d[0]=1;
  
  for(int i=1;i<=t.size();i++) d[i]=d[i-1]*K;
  
  h=0;
  
  for(int i=0;i<t.size();i++){
    h=h*K+t[i];
    H[i]=h;
  }
  
  int ans=0;

  for(int i=0;i<t.size();i++){
    for(int j='A';j<='z';j++){
      if((char)j==t[i]) continue;
      ull hash=j;
      if(i!=0) hash=H[i-1]*d[1]+hash;
      if(i!=t.size()-1)
	hash=hash*d[t.size()-i-1]+H[t.size()-1]-H[i]*d[t.size()-i-1];

      if(cnt.count(hash)) ans+=cnt[hash];
    }
  }
  
  cout<<ans<<endl;
  
  return 0;
}

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

int main() {
	int N;
	cin >> N;
	int X[100];
	int aveX=0;
	for(int i=1; i<=N; i++){
		cin >> X[i];
		//cout << X[i] << endl;
		aveX = aveX+X[i];
		
	}
	aveX /= N;
	
	//cout << aveX <<endl;
	
	int ansinf =0;
	int anssup =0;
	for(int i=1; i<=N; i++){
		ansinf += std::pow(X[i]-aveX,2);
		anssup += std::pow(X[i]-aveX-1,2);
	}
	if(ansinf<anssup){
		cout<< ansinf <<endl;
	}
	else{
		cout<< anssup <<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int main(){
	boost;
	string s,t;
	cin>>s>>t;
	int comp=0;
	for (int i = 0; i < 3; ++i)
		comp+=(s[i]==t[i]);
	cout<<comp;
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Measured memory_bytes: 256
List = []
for i in range (3):
  List.append(list(map(int, input().split())))
a = 0
b = 0
c = 0
flg = True
for i in range(2):
  a = List[0][i+1] - List[0][i]
  b = List[1][i+1] - List[1][i]
  c = List[2][i+1] - List[2][i]
  if a != b or b != c or c != a:
    flg = False
  a = List[i+1][0] - List[i][0]
  b = List[i+1][1] - List[i][1]
  c = List[i+1][2] - List[i][2]
  if a != b or b != c or c != a:
    flg = False
if flg:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9244
import bisect
A,B,Q = map(int,input().split())
# INF = 10**18
s=[]
t=[]
for _ in range(A):
    s.append(int(input()))
for _ in range(B):
    t.append(int(input()))
# s.sort()
# t.sort()
# s = [int(input()) for _ in range(A)]
# t = [int(input()) for _ in range(B)]
# s.append(INF)
# t.append(INF)

def solve(x):
    sr = bisect.bisect(s,x)
    tr = bisect.bisect(t,x)
    sRight = s[sr] if sr < A else s[sr-1]
    tRight = t[tr] if tr < B else t[tr-1]
    sLeft = s[sr-1] if sr>0 else s[sr] 
    tLeft = t[tr-1] if tr>0 else t[tr]
    # return(min(
    # print([[sr,sLeft,sRight],[tr,tLeft,tRight]])
    # cand = [
    #     abs(x-sRight) + abs(sRight-tRight),
    #     abs(x-sRight) + abs(sRight-tLeft),
    #     abs(x-tRight) + abs(tRight-sRight),
    #     abs(x-tRight) + abs(tRight-sLeft),
    #     abs(x-sLeft) + abs(sLeft-tLeft),
    #     abs(x-sLeft) + abs(sLeft-tRight),
    #     abs(x-tLeft) + abs(tLeft-sRight),
    #     abs(x-tLeft) + abs(tLeft-sLeft),
    # ]
    # # print(cand)
    # return(min(cand))
    return(min(
        abs(x-sRight) + abs(sRight-tRight),
        abs(x-sRight) + abs(sRight-tLeft),
        abs(x-tRight) + abs(tRight-sRight),
        abs(x-tRight) + abs(tRight-sLeft),
        abs(x-sLeft) + abs(sLeft-tLeft),
        abs(x-sLeft) + abs(sLeft-tRight),
        abs(x-tLeft) + abs(tLeft-sRight),
        abs(x-tLeft) + abs(tLeft-sLeft),
    ))
for _ in range(Q):
    print(solve(int(input())))

Measured memory_bytes: 12092
#include<stdio.h>
int main(void)
{
	int S,h,m,s;

	scanf("%d",&S);

	s=S%3600%60;
	m=(S-s)%3600/60;
	h=(S-(m*60)-s)/3600;

	printf("%d:%d:%d\n",h,m,s);

	return 0;
}


Measured memory_bytes: 2120
N,W = map(int,input().split())
Data = []
for _ in range(N):
    v,w = map(int,input().split())
    Data.append([v,w])
Data.sort(key=lambda x:x[1])
DP = [[0]*(W+1) for _ in range(N+1)]

for n in range(1,N+1):
    for w in range(1,W+1):
        tv,tw = Data[n-1]
        if tw <= w:
            DP[n][w] = max(DP[n][w],DP[n][w-tw]+tv)
        DP[n][w] = max(DP[n][w],DP[n-1][w])
print(DP[N][W])


Measured memory_bytes: 41892
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(void){
	
	string s;
bool ans=true;
cin>>s;
if(s.size()>=4){

if(s[0]!='Y'||s[1]!='A'||s[2]!='K'||s[3]!='I'){
ans=false;
}
}else{
	ans=false;
}
if(ans){
	cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
return 0;
}

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

typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
const double pi = 3.141592653589793238;

ll gcd(ll a, ll b) { return __gcd(a,b); } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; } //最大公倍数

void printV(vector<int> &v);
void printVV(vector<vector<int>> &vv);


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

  vector<int> v(N);
  for(int i = 0; i < N; i++) {
    cin >> v.at(i);
  }

  sort(v.begin(), v.end(), greater<int>());

  int sumA = 0;
  int sumB = 0;
  for(int i = 0; i < N; i++) {
    if(i % 2 == 0) sumA += v.at(i);
    if(i % 2 == 1) sumB += v.at(i);
  }
  cout << sumA - sumB << endl;

  return 0;
}


// ベクターの中身を全部出力
void printV(vector<int> &v) {
  cout << "  [ ";
  for(int i = 0; i < (int)v.size(); i++) {
    cout << v.at(i) << " ";
  }
  cout << "]" << endl;
}

void printVV(vector<vector<int>> &vv) {
  cout << "{" << endl;
  for(int i = 0; i < (int)vv.size(); i++) {
    cout << "  [ ";
    for(int j = 0; j < (int)vv.at(i).size(); j++) {
      cout << vv.at(i).at(j) << " ";
    }
    cout << "]," << endl;
  }
  cout << "}" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n;cin>>n;
    vector<long> h(n+2,0);
    for(int i=1;i<=n;i++)
        cin>>h[i];
    
    long count=0;
    while(1){
        for(int l=0;l<=n;l++){
            if(!h[l]&&h[l+1]){
                for(int r=l+1;r<=n+1;r++){
                    if(!h[r]){
                        vector<long> v;
                        v.assign(&h[l+1],&h[r]);
                        long tag=*min_element(begin(v),end(v));
                        for(int i=l+1;i<r;i++){
                            h[i]-=tag;
                        }
                        count+=tag;
                        break;
                    }
                }
                break;
            }
            if(l==n){
                cout<<count;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    def find(self, x):
        """ 根の検索(グループ番号と言えなくもない) """
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """ 併合 """
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            # グループ0の分を引いて返却
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
AB = []
for i in range(M):
    a, b = MAP()
    AB.append((a, b))

# 終了状態からUnionFindで復元していく
cur = N * (N-1) // 2
ans = [cur]
uf = UnionFind(N)
for a, b in AB[::-1]:
    if not uf.is_same(a, b):
        cur -= uf.get_size(a) * uf.get_size(b)
        uf.union(a, b)
    ans.append(cur)

ans = ans[::-1]
[print(a) for a in ans[1:]]


Measured memory_bytes: 26488
from bisect import bisect_left, bisect_right

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

A = sorted(A)
C = sorted(C)

ans = 0
for i in range(N):
    ans += bisect_left(A, B[i]) * (N - bisect_right(C, B[i]))
print(ans)


Measured memory_bytes: 23232
#include<iostream>

using namespace std;

int main()
{
	int n,m;
	int map[3000]={0};
	int a;
	
	for(;;)
	{
		cin >> n >> m ;
		if(n==0 && m==0)
			break;
		
		int now=0,ans=0;
		
		for(int i=0;i<n;i++)
			cin >> map[i] ;
		
		for(int i=0;i<m;i++)
		{
			cin >> a ;
			now+=a;
			if(map[now]!=0 && ans==0)
				now+=map[now];
			if(now>=n-1 && ans==0)
				ans=i+1;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 0
#include<stdio.h>
#define LEN 100001
#define NILL -1

int main()
{
  int n;
  int P[LEN], L[LEN],R[LEN];
  int id, child;
  int i, j, k, m;  

  //initialization
  for(i=0; i<LEN; i++)
    {
      P[i]=NILL;
      L[i]=NILL;
      R[i]=NILL;
    }

  //make node
  scanf("%d", &n);
  for(i=0; i<n; i++)
    {
      scanf("%d %d", &id, &k);
      for(j=0; j<k; j++)
	{
	  scanf("%d", &child);
	  P[child]=id;
	  if(j==0)L[id]=child;
	  else R[m]=child;
	  m=child;
	}
    }

  //print
  //for(i=0; i<n; i++)printf("n%d p%d L%d R%d\n", i, P[i], L[i], R[i]);
  for(i=0; i<n; i++)
    {
      //node
      printf("node %d: ", i);

      //parent
      printf("parent = %d, ", P[i]);

      //depth
      for(j=P[i], k=0; j!=NILL; j=P[j], k++);
      printf("depth = %d, ", k);

      //type
      if(P[i]==NILL)printf("root, ");
      else if(P[i]!=NILL && L[i]!=NILL)printf("internal node, ");
      else printf("leaf, ");

      //children
      printf("[");
      for(j=L[i]; j!=NILL; j=R[j])
	{
	  if(R[j]!=NILL)printf("%d, ", j);
	  else printf("%d", j);
	}
      printf("]\n");
    }
  return 0;
}

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

int main() {
  string S, T;
  cin >> S >> T;
  int ans = 0;
  for (int i = 0; i < 3; i++) {
    if (S.at(i) == T.at(i)) ans++;
  }
  
  cout << ans;
}

Measured memory_bytes: 256
#pragma region include
#include "bits/stdc++.h"
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
#define MOD (int)(1e9+7)
#define INF (int)(1e9)
#define LLINF (int)(4e18)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
void input() {}
template<typename... R> void input(int& f, R&... r) { scanf("%d", &f); input(r...); }
template<typename... R> void input(double& f, R&... r) { scanf("%lf", &f); input(r...); }
template<typename... R> void input(ll& f, R&... r) { scanf("%lld", &f); input(r...); }
template<typename... R> void input(char& f, R&... r) { scanf("%c", &f); input(r...); }
template<typename... R> void input(string& f, R&... r) { cin >> f; input(r...); }
template<typename T, typename... R> void input(vector<T>& f, R&... r) { REP(i, f.size())input(f[i]); input(r...); }
#pragma endregion

template<class Monoid> struct SegmentTree {
private:
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int n;
    vector<Monoid> node;
public:
    SegmentTree(int m, const Func f,const Monoid &unity) : F(f),UNITY(unity){
        n = 1; while (n < m) n <<= 1;
        node.resize(n * 2 - 1, UNITY);
    }

    SegmentTree(const vector<Monoid>& v,const Func f, const Monoid &unity) : F(f),UNITY(unity) {
        int sz = v.size();
        n = 1; while (n < sz) n <<= 1;
        node.resize(n * 2 - 1,UNITY);
        REP(i, sz) node[i + n - 1] = v[i];
        REPR(i, n - 2) node[i] = F(node[2 * i + 1], node[2 * i + 2]);
    }

    void update(int x, int val) {
        if (x >= n || x < 0) return;
        x += n - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) >> 1;
            node[x] = F(node[2 * x + 1], node[2 * x + 2]);
        }
    }

    int get(int a,int b,int k = 0, int l = 0,int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return UNITY;
        if (a <= l && r <= b) return node[k];
        int vl = get(a, b, 2 * k + 1, l, (r - l) / 2 + l);
        int vr = get(a, b, 2 * k + 2, (r - l) / 2 + l, r);
        return F(vl, vr);
    }
};

//gcd
template<typename T>
T gcd(T a, T b) {
    return b ? gcd(b, a%b) : a;
}

int main() {
    int N; input(N);
    vector<int> a(N); input(a);
    SegmentTree<int> seg(a, [](int a, int b) { return gcd(a, b); }, 0);
    int ans = 0;
    REP(i, N) {
        if (i == 0) {
            ans = max(ans,seg.get(1, N));
        }
        else if (i == N - 1) {
            ans = max(ans,seg.get(0, N - 1));
        }
        else {
            ans = max(ans,gcd(seg.get(0,i),seg.get(i+1,N)));
        }
    }
    cout << ans << endl;
    getchar(); getchar();
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
const long long MOD = 1e9+7;
using namespace std;
#define ll long long
#define ar array

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

	int A,B;
	cin >> A >> B;
	int ans=max({A+B,A-B,A*B});
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main(void)
{
    int K, S, count=0;
    cin >> K >> S;
    for(int x=0;x<=K;x++){
        for(int y=0;y<=K;y++){
            int z = S-x-y;
            if(0 <= z && z <= K)
                count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
class Dice

  def initialize(dice)
    @top  = dice[0]
    @side   = [ dice[2], dice[1], dice[3], dice[4] ]
    @bottom = dice[5]
  end

  def roll(action)
    b = @bottom
    u = @top
    case action
    when "N"
      @top   = @side[2]
      @bottom  = @side[0]
      @side[2] = b
      @side[0] = u
    when "E"
      @top   = @side[3]
      @bottom  = @side[1]
      @side[3] = b
      @side[1] = u
    when "S"
      @top   = @side[0]
      @bottom  = @side[2]
      @side[0] = b
      @side[2] = u
    when "W"
      @top   = @side[1]
      @bottom  = @side[3]
      @side[1] = b
      @side[3] = u
    end
  end

  def same_dice?(sub)
    i = 0
    while true
      if south == sub.south
        4.times do
          if all_num == sub.all_num
            # true
            return true
          end
          roll("E")
        end
      end
      if i > 6
        # false
        return false
      elsif i == 3
        roll("E")
        roll("N")
      else
        roll("N")
      end
      i += 1
    end
  end

  def top
    @top
  end

  def bottom
    @bottom
  end

  def north
    @side[0]
  end

  def east
    @side[1]
  end

  def south
    @side[2]
  end

  def west
    @side[3]
  end

  def all_num
    [@top, @bottom, @side[2], @side[1], @side[3], @side[4]]
  end
end

num = gets.to_i
dice = Dice.new(gets.split.map(&:to_i))

(1..(num-1)).each do |i|
  dice_2 = Dice.new(gets.split.map(&:to_i))
  if dice_2.same_dice?(dice)
    puts "No"
    break
  else
    if i == (num-1)
      puts "Yes"
    else
      next
    end
  end
end

Measured memory_bytes: 8836