akhauriyash/Code-Regression huggingface dataset:
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

static vi child[5010];
int dp[5010][2];
void dfs(int v) {
  dp[v][0] = dp[v][1] = 0;
  int S = 0;
  for (int u : child[v]) {
    dfs(u);
    S += max(dp[u][0], dp[u][1]);
  }
  dp[v][0] = S;
  for (int u : child[v]) {
    int T = S - max(dp[u][0], dp[u][1]) + dp[u][0] + 1;
    cmax(dp[v][1], T);
  }
}

main {
  int n;
  cin >> n;
  rep(i, n) {
    int p;
    cin >> p;
    child[p].push_back(i + 1);
    dfs(0);
    cout << max(dp[0][0], dp[0][1]) << endl;
  }
}

Measured memory_bytes: 3448
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int selectionSort(int a[], int n) {
    int i, j, minj, t, sw = 0;
    for(i = 0; i < n-1; i++) {
        minj = i;
        for(j = i; j < n; j++) {
            if(a[j] < a[minj]) {
                minj = j;
            }
        }
        t = a[i];
        a[i] = a[minj];
        a[minj] = t;
        if(i != minj) {
            sw++;
        }
    } 
    
    return sw;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i, n) {
        cin >> a[i];
    }

    int sw = selectionSort(a, n);

    rep(i, n) {
        if(i) {
            cout << " ";
        }
        cout << a[i];
    }
    cout << "\n";
    
    cout << sw << endl;

    return 0;
}


Measured memory_bytes: 3096
<?php
  $x=fgets(STDIN);
  $cnt=1;


  while($cnt<10)
  {
    if($x%$cnt==0)
    {
      if($x/$cnt<=9)
      {
      echo'Yes';
      break;
      }
      else
      {
        $cnt++;
      }
    }
    elseif($cnt==9)
    {
      echo'No';
      break;
    }
    else
    {
      $cnt++;
    }
  }
?>

Measured memory_bytes: 4604
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N, M = map(int, raw_input().split())
a = [-1]*N
a[0] = 1 
for i in xrange(M):
    x, y = map(int, raw_input().split())
    x, y = x - 1, y - 1
    if a[x] >= 1:
        a[y] = abs(a[y]) + 1
        a[x] -= 1
    elif a[x] <= -1:
        if a[y] <= 0:
            a[y] = a[y] - 1
        elif a[y] > 0:
            a[y] += 1
        a[x] += 1
ans = 0
for ai in a:
    if ai > 0:
        ans += 1
print ans


Measured memory_bytes: 4772
//Be Name Khoda
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma optimize O3
using namespace __gnu_pbds;
using namespace std;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long int LL;
typedef LL ll;
typedef long double ld;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;
 
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for (int i=a;i<b;i++)
#define Ford(i,a,b) for (int i=a;i>=b;i--)
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define ER(a) cout << #a << ' ' << a << endl
#define LB(a,n,x) (lower_bound(a,(a)+(n),x)-(a))
#define RET(x) { cout << x; exit(0); } 
#define RETD(x) { cout << fixed << setprecision(15) << x; exit(0); }
const ll M=2e5+5,LG=32,SM=600+5,inf=1e18+5;
ll mod=1e9+7;

ll n;
vll g[M];
ll mark[M][LG];
 
void dfs(ll x,ll p)
{
    for (ll y:g[x])
    {
        if (y!=p)
        {    
            dfs(y,x);
            For(i,0,LG)
            {
                mark[x][i]+=mark[y][i];
            }
        }
    }
    ll nd=-1;
    For(i,0,LG)
    {
        if (mark[x][i]>1)
            nd=i;    
    }
    nd++;
    For(i,0,nd)
        mark[x][i]=0;
    while (mark[x][nd]!=0)
    {
        mark[x][nd]=0;
        nd++;
    }
    mark[x][nd]=1;
    return;
}
 
int main()
{
	ios::sync_with_stdio(0);
    cin >> n;
    For(i,1,n)
    {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        g[a].PB(b);g[b].PB(a);
    }
    dfs(0,0);
    ll cnt=0;
    For(i,0,LG)
    {
        if (mark[0][i])
            cnt=i;
    }
    RET(cnt);
}    


Measured memory_bytes: 41216
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 
#define int long long
#define double long double

////////////////////////////////////////////////////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
///////////////////////___prime_factor___////////////////////
map<int, int> prime_factor(int n){
  map<int, int> ret;
  for(int i = 2;i*i <= n;i++){
    while(n % i == 0){
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1){
    ret[n] = 1;
  }
  return ret;
}

////////////////////////////////////////////////////////////////////

int n,a[11000];map<int, int> mp;
vector<map<int,int>> v(11000);
signed main(){
  cin>>n;rep(i,n)cin>>a[i];
  int ans = 0;
  rep(i,n){
    v[i] = prime_factor(a[i]);
    for(auto itr = v[i].begin();itr != v[i].end();itr++){
      if(mp.count(itr->first) == 0 || mp[itr->first] < itr->second)mp[itr->first] = itr->second;
    }
  }
  int l = 1;
  for(auto itr = mp.begin();itr != mp.end();itr++){
    l = l*modpow(itr->first, itr->second)%MOD;
  }
  rep(i,n){
    
    ans = (ans+(l*modinv(a[i])%MOD)) % MOD;
  }
  cout << ans << endl;
}




Measured memory_bytes: 3968
#include <bits/stdc++.h>		//万能头文件 
using namespace std;

int main()
{
	string a;
	int pos=0;		//记录位置 
	cin>>a;
	a=a+"D";		//为防止最后一个字母是"A",添加一个不是"C"的字母 
	while(1)
	{
		pos=a.find("A",pos);		//find()函数查找位置 
		if(pos<0)		//如果没找到，返回-1 
		{
			cout<<"No"<<endl;		//endl养成好习惯 
			break;		//跳出循环 
		}
		if(a[pos+1]=='C')		//判断"A"下一个是不是"C"
		{
			cout<<"Yes"<<endl;
			break;		//跳出循环
		}
		pos++;		//下一次从pos+1找起 
	}
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5,M=5e6+5;
int en=1,h[N],n,a[N],b[N],id1[N],id2[N],cnt,cnt1,cnt2,d[N],cur[N];

struct edge{
	int n,v,w;
}e[M<<1];

void add(int x,int y,int z){
	e[++en]={h[x],y,z};
	h[x]=en;
}

void exadd(int x,int y,int f){
	add(x,y,f);
	add(y,x,0);
}

bool bfs(int s,int aim){
	memset(d,0,sizeof d);
	memcpy(cur,h,sizeof cur);
	queue<int> q;
	q.push(s);
	d[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=h[x];i;i=e[i].n){
			int y=e[i].v;
			if(!d[y]&&e[i].w){
				d[y]=d[x]+1;
				if(y==aim) return 1;
				q.push(y);
			}
		}
	} 
	return 0;
}

int dfs(int x,int flow,int aim){
	if(x==aim) return flow;
	int rest=flow;
	for(int &i=cur[x];i&&rest;i=e[i].n){
		int y=e[i].v;
		if(d[y]==d[x]+1&&e[i].w){
			int tp=dfs(y,min(rest,e[i].w),aim);
			if(!tp) d[y]=0;
			rest-=tp;
			e[i].w-=tp;
			e[i^1].w+=tp;
		}
	}
	return flow-rest;
}

int dinic(int s,int t){
	int res=0;
	while(bfs(s,t)) res+=dfs(s,INT_MAX,t);
	return res;
}

signed main(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),a[i]++;
	for(int i=1;i<=n;i++) read(b[i]),b[i]++;
	for(int i=1;i<=n;i++) if(!id1[i]){
		cnt1++;
		int x=i;
		do{
			id1[x]=cnt1;
			x=a[x];
		}while(x!=i);
	}
	for(int i=1;i<=n;i++) if(!id2[i]){
		cnt2++;
		int x=i;
		do{
			id2[x]=cnt2;
			x=b[x];
		}while(x!=i);
	}
  	for(int i=1;i<=n;i++){
  		int x=id1[i],y=id2[i];
  		if(a[i]!=i&&b[i]!=i){
  			exadd(x,cnt1+y,1);
  			if(a[i]==b[i]) exadd(cnt1+y,x,1);
		}
		else if(a[i]!=i) exadd(x,cnt1+cnt2+1,1);
		else if(b[i]!=i) exadd(0,cnt1+y,1);
		else cnt++;
	}
  	write(n-cnt-dinic(0,cnt1+cnt2+1));
}


Measured memory_bytes: 15220
use std::env;
use std::io::*;
use std::str::FromStr;
use std::char;
use std::error::Error;
use std::io::prelude::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
fn main() {
    
    let n: u32 = read();
    
    let mut cnt:u32 = 0;
    while n != cnt {
        let query: String = read();
        let v: Vec<char> = query.chars().collect();
            
            //println!("{:?}", v);
            let mut i = 0_i32;
            println!("{}", expr(&v, &mut i));

            //println!("{}", number(&v, &mut i));
        
        cnt+=1;
    }
}


fn expr(s: &Vec<char>, i: &mut i32) -> i32 {
    let mut val = term(s, i);

    let mut idx = *i as usize;
    
    while idx < s.len() && (s[idx] == '+' || s[idx] == '-') {
        let op = s[idx];
        *i += 1;
        let val2 = term(s, i);
        val = if op == '+' {
            val + val2
        }else {
            val - val2
        };
        idx = *i as usize;
    }
    
    val
}

fn term(s: &Vec<char>, i: &mut i32) -> i32 {
    let mut val = factor(s, i);
    
    let mut idx = *i as usize;

    while idx < s.len() && (s[idx] == '*' || s[idx] == '/') {
        let op = s[idx];
        *i += 1;
        let val2 = factor(s, i);

        val =  if op == '*' {
            val * val2
        } else {
            val / val2
        };
        idx = *i as usize;
    }

    val
}

fn factor(s: &Vec<char>, i: &mut i32) -> i32 {
    let idx = *i as usize;
    if idx < s.len() && s[idx].is_digit(10){
         return number(s, i);
    }

    *i += 1;
    let res = expr(s, i);
    *i += 1;

    res
}

fn number(s: &Vec<char>, i: &mut i32) -> i32 {
    let mut idx = *i as usize;
    
    let mut n: u32 = s[idx].to_digit(10).unwrap();
    
    *i += 1;
    idx = *i as usize;
    while idx < s.len() && s[idx].is_digit(10) {
        
        let m: u32 = s[idx].to_digit(10).unwrap();
        n = n * 10 + m;
        *i += 1;
        idx = *i as usize;
    }

    n as i32
}


/* 参考 
 - http://dai1741.github.io/maximum-algo-2012/docs/parsing/

 <expr>   ::= <term> [ ('+'|'-') <term> ]*
 <term>   ::= <factor> [ ('*'|'/') <factor> ]*
 <factor> ::= <number> | '(' <expr> ')'
 <number> :== 1つ以上の数字
*/

/* &str型
・文字列を固定する（メモリサイズ）
・スライスで参照できる
・文字列長は不変

   String型
・文字列長は可変
・サイズが可変であるため参照ができない
*/



Measured memory_bytes: 5016
MOD = 10**9 + 7

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res




# print(combination(10,2))


s = int(input())
n = s//3
ans = 0
while n:
    S = s - n*3
    # print(S+n-1,n-1)
    ans += combination(S+n-1,n-1)
    n-=1

print(ans%MOD)

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

using namespace std;

int main()
{
    double a,b;
    double x=1;
    while(cin>>a>>b)
    {
        if(a>b)
        {
            x=a/b;
            cout<<ceil(x)<<endl;
        }
        else
        {
            cout<<"1"<<endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
n,k=[int(i) for i in input().split()]
count=0
lst=[]
for i in range(n):
    lst.append([int(i) for i in input().split()])
lst.sort()
for i in range(n):
    a,b=lst[i]
    count+=b
    if(count>=k):
        print(a)
        exit()


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

int main() {
	int iInputNum;
	int iNumS1;
	int iNumS2;
	int iNumS3;

	cin >> iInputNum;

	iNumS1 = iInputNum / 100;
	iNumS2 = ( iInputNum - iNumS1 * 100 ) / 10;
	iNumS3 = iInputNum - ( ( iNumS1 * 100 ) + ( iNumS2 *10 ) );

	//cout << iNumS1 << " " << iNumS2 << " " << iNumS3 << endl;
	cout << iNumS1 + iNumS2 + iNumS3 << endl;

	return 0;
}

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

int main(){
		long int N;
		cin >> N;
		vector<int> v(N);
		for(int i = 0; i < N; ++i){
				cin >> v[i];
		}
		sort(v.begin(), v.end());
		double answer = v[0];
		for(int i = 1; i < N; ++i){
			answer = (answer + v[i])/2;
		}
		cout << answer << endl;
}


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

int main(){
  int S;
  int h,m,s;
  cin >> S;
  h = S / 3600;
  m = (S % 3600) / 60;
  s = (S % 3600) % 60;
  cout << h << ":" << m << ":" << s << endl;

  return 0;
}

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

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int main() {
  int N, H;
  cin >> N >> H;
  vector<ll> A(N), B(N);
  ll maxa = 0;
  REP(i, N) { cin >> A[i] >> B[i]; }
  sort(A.begin(), A.end(), greater<ll>());
  sort(B.begin(), B.end(), greater<ll>());
  A.push_back(0);
  B.push_back(0);
  ll b = 0;
  ll ans = 0;
  while (H > 0) {
    if (B[b] > A[0]) {
      H -= B[b];
      b++;
      ans++;
    } else {
      ans += (H + A[0] - 1) / A[0];
      H = 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using vvb = vector<vector<bool>>;
using vvll = vector<vector<long long>>;
using pii = pair<int, 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 rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define rreps(i,n) for(int i = (int)(n); i > 0; i--)
#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define RFOR(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define call(x) (x).cbegin(), (x).cend()
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
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 (b<a) {a=b; return 1;} return 0;}
const int INF = INT_MAX;
const int MOD = 1000000007;
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int N;
    cin >> N;
    auto dp = make_vec<long long> (N+1, 5, 5, 5);
    dp[0][0][0][0] = 1;
    rep(n, N) rep(i, 5) rep(j, 5) rep(k, 5) reps(l, 4) {
        if (j == 1 && k == 2 && l == 3) continue;
        if (j == 1 && k == 3 && l == 2) continue;
        if (j == 2 && k == 1 && l == 3) continue;
        if (i == 1 && k == 2 && l == 3) continue;
        if (i == 1 && j == 2 && l == 3) continue;
        dp[n+1][j][k][l] += dp[n][i][j][k];
        dp[n+1][j][k][l] %= MOD;
    }
    ll ans = 0;
    reps(i, 4) reps(j, 4) reps(k, 4) {
        ans += dp[N][i][j][k];
        ans %= MOD;
    }
    cout << ans << endl;
}

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

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

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;

    int tmp = 0;
    while (true)  {
        if (tmp > K) break;
        if (B > A) break;
        tmp++;
        B *= 2;
    }
    if (tmp > K) cout << "No" << endl;
    else {
        if (K == tmp) {
            if (C > B) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            if (C * pow(2,(K - tmp)) > B) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 4112
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int mask=0;do{snum[mask++]=n%10+48;n/= 10;}while(n);--mask;if (_)pc(45);while(mask>=0)pc(snum[mask--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

using namespace std;
const int MM = 1005;

int n, m, k, ans = 1e9;
int sum[11];
char s[11][MM];

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 0; i < n; i++){
        scanf("%s", s[i]);
    }
    
    for(int mask = 0; mask < (1<<n); mask++){
        set<int> st;
        for(int j = 0; j <= n; j++){
            sum[j] = 0;
            if(mask&(1<<j))
                st.insert(j);
        }
        //st of split points
        bool pos = 1;
        int cnt = st.size();
        st.insert(-1);
        for(int i = 0; i < m; i++){
            bool b = 0;
//            printf("i %d\n", i);
            for(int j = 0, pre = 0; j < n; j++){
                if(st.count(j-1)){
                    pre = j;
                    //new group
                }
                sum[pre] += (s[j][i] == '1');
                if(sum[pre] > k){
                    b = 1;
                }
//                printf("j %d %d\n", j, sum[pre]);
            }
            
            if(b){
//                printf("b\n");
                cnt++;
                b = 0;
                for(int j = 0, pre = 0; j < n; j++){
                    if(st.count(j-1)){
                        pre = j;
                        sum[pre] = 0;
                        //new group
                    }
                    sum[pre] += (s[j][i] == '1');
                    if(sum[pre] > k){
                        b = 1;
                    }
                }
                if(b)
                    pos = 0;
            }
        }
        if(pos)
            ans = min(ans, cnt);
//        print(mask, pos, cnt);
    }
    
    print(ans);
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

int main() {
	int r,d,x;
	std::cin >> r>>d>>x;

	for (int i = 0; i < 10; i++) {
		x = r * x - d;
		std::cout << x << std::endl;
	}

	//std::cout << n << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<int> > mat;

const int max_n = 100000;

int main()
{
  int n, m;
  cin >> n >> m;
  int u, v;
  int a[3 * max_n + 10];
  mat g;
  g.assign(3 * n, vector<int> ());
  memset(a, -1, sizeof(a));
  for (int i = 0; i < m; i++)
  {
    cin >> u >> v;
    u--;
    v--;
    g[u].push_back(v + n);
    g[u + n].push_back(v + 2 * n);
    g[u + 2 * n].push_back(v);
  }
  int s, t;
  cin >> s >> t;
  s--;
  t--;
  a[s] = 0;

  queue<int> que;
  que.push(s);
  while (!que.empty())
  {
    int check = que.front();
    que.pop();
    for (int i:g[check])
    {
      if (a[i] == -1)
      {
        a[i] = a[check] + 1;
        que.push(i);
      }
    }
  }

  cout << (a[t] == -1 ? -1 : a[t] / 3) << "\n";
}

Measured memory_bytes: 17792
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

int cnt[100010];

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

    int n;
    cin >> n;
    rep(i, n)
    {
        int a;
        cin >> a;
        a--;
        cnt[a]++;
    }
    rep(i, 100010) if (cnt[i] > 2)
    {
        if (cnt[i] % 2 == 0)
            cnt[i] = 2;
        else
            cnt[i] = 1;
    }
    int tmp = 0;
    rep(i, 100010)
    {
        if (cnt[i] > 1)
        {
            cnt[i]--;
            if (tmp == 0)
                tmp = 1;
            else
                tmp = 0;
        }
    }
    int ans = 0;
    rep(i, 100010) ans += cnt[i];
    cout << ans - tmp << endl;
}

Measured memory_bytes: 1024
using System;
class Program
 {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();
            string s2 = Console.ReadLine();

            if(s1.Length > s2.Length){
                Console.WriteLine("GREATER");
            }else if(s1.Length < s2.Length){
                Console.WriteLine("LESS");
            }else{
                for(int i = 0 ; i < s1.Length; i++){
                    int n1 = int.Parse(s1[i].ToString());
                    int n2 = int.Parse(s2[i].ToString());

                    if(n1 > n2){
                        Console.WriteLine("GREATER");
                        break;
                    }else if(n1 < n2){
                        Console.WriteLine("LESS");
                        break;
                    }else if((n1 == n2) && (i+1 == s1.Length)){
                        Console.WriteLine("EQUAL");
                    }
                }
            }
        }
 }

Measured memory_bytes: 13140
N = int(input())
count = {}
for i in range(2,N+1):
    f = 2
    tmp = i
    while f**2<=tmp:
        if tmp%f == 0:
            if f not in count:
                count[f] = 0
            count[f] += 1
            tmp //= f
        else:
            f += 1
    if tmp != 1:
        if tmp not in count:
            count[tmp] = 0
        count[tmp] += 1
ans = 1
for v in count.values():
    ans *= (v+1)

mod = 10**9 +7
print(ans%mod)



Measured memory_bytes: 39152
#include <cstdio>
#include <iostream>

#define MAX_PROBLEM 10
#define MAX_TEAM 50

using namespace std;

struct Team {
	int num;
	int min;
	int point;
	bool prob[MAX_PROBLEM];
	int judge[MAX_PROBLEM];
};

bool lessTeam(const Team &l, const Team &r) {
	if (l.point < r.point) { return false; }
	if (l.point > r.point) { return true; }

	if (l.min < r.min) { return true; }
	if (l.min > r.min) { return false; }

	if (l.num < r.num) { return false; }
	if (l.num > r.num) { return true; }
}

int main(void) {
	for (;;) {
		int M, T, P, R;
		cin >> M >> T >> P >> R;
		if (M == 0 && T == 0 && P == 0 && R == 0) {
			break;
		}

		Team team[MAX_TEAM];
		for (int i = 0; i < T; i++) {
			team[i].num = i + 1;
			team[i].min = 0;
			team[i].point = 0;
			for (int j = 0; j < MAX_PROBLEM; j++) {
				team[i].prob[j] = false;
				team[i].judge[j] = 0;
			}
		}

		for (int i = 0; i < R; i++) {
			int m, t, p, j;
			cin >> m >> t >> p >> j;
			
			if (j == 0) {
				team[t - 1].min += m;
				team[t - 1].prob[p - 1] = true;
				team[t - 1].point++;
			} else {
				team[t - 1].judge[p - 1]++;
			}
		}

		for (int i = 0; i < T; i++) {
			for (int j = 0; j < P; j++) {
				if (team[i].prob[j]) {
					team[i].min += team[i].judge[j] * 20;
				}
			}
		}

		for (int i = 0; i < T; i++) {
			for (int j = i + 1; j < T; j++) {
				if (lessTeam(team[j], team[i])) {
					Team tmp = team[i];
					team[i] = team[j];
					team[j] = tmp;
				}
			}
		}

		for (int i = 0; i < T - 1; i++) {
			printf("%d", team[i].num);
			if (team[i].point == team[i + 1].point && team[i].min == team[i + 1].min) {
				printf("=");
			} else {
				printf(",");
			}
		}
		printf("%d\n", team[T-1].num);
	}
	return 0;
}

Measured memory_bytes: 1148
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstdio>

using namespace std;

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

int main(){
    double l;
    cin >> l;
    double ans = l * l * l;
    ans /= 27;
    printf("%.10f\n", ans);
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n = 0;
  int m = 0;
  int k = 0;
  int i = 0;
  int j = 0;
  int flag = 0;
  scanf("%d %d %d",&n,&m,&k);
  for(i=0;i<=n;i++){
    for(j=0;j<=m;j++){
      if(i*j + (n-i)*(m-j) == k){
        flag = 1;
      }
    }
  }
  if(flag){
    printf("Yes");
  }else{
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int x;
    int ans = 0, cnt = 0;

    cin >> x;

    for (int i = 1; i <= x; i++) {
        ans += i;
        cnt++;
        if (ans >= x) break;
    }

    cout << cnt << endl;
}


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

using namespace std;

int main()
{
  int N,M; cin>>N>>M;
  vector<int> X(M),Y(M-1);
  for(int i=0; i<M; i++) cin>>X[i];
  if (N>=M){
    cout<<0<<endl;
    return 0;
  }
  sort(X.begin(), X.end());
  for(int i=0; i<M-1; i++) Y[i]=X[i+1]-X[i];
  sort(Y.rbegin(), Y.rend());
  int ans=0;
  for(int i=0; i<M-1; i++) ans+=Y[i];
  for(int i=0; i<N-1; i++) ans-=Y[i];
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int N;
    while(1){
        cin>>N;
        if(N==0) break;
        int cur = 0;
        int right = 1;
        int left = 1;

        while(1){
            if(cur < N) cur += right++;
            else if(cur > N) cur -= left++;
            else break; 
        }

        cout<<left<<" "<<right-left<<endl;
    }

    return 0;
}


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

int main()
{
    long long x;
    cin >> x;
    bool af = false;
    for (long long a = -3000; a < 3000; a++) {
        for (long long b = a + 1; b <= 3000; b++) {
            long long aa = a * a * a * a * a;
            long long bb = b * b * b * b * b;
            if (bb - aa == x) {
                af = true;
                cout << b << " " << a << endl;
            } else if (aa - bb == x) {
                af = true;
                cout << a << " " << b;
            }
            if (af) break;
        }
        if (af) break;
    }
    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
#include<string.h>
#define ll long long 
using namespace std;
 struct value
{
	ll x;
	ll y;
};
bool compare(value a, value b)
{
	//for descending order replace with a.roll >b.roll
	if(a.y < b.y)		
		return 1;
	else
		return 0;
}
int main()
{
	ll n,k;
	cin>>n>>k;
	vector <ll> arr;
	ll temp;
	for(ll i=0;i<n;i++)
	{
		cin>>temp;
		arr.push_back(temp);
	}	
	sort(arr.begin(),arr.end());
	ll sum=0;
	for(ll i=0;i<k;i++)
	{
		sum=sum+arr[i];
	}
	cout<<sum;
}


Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int main(void){
    long long n,max1=-10000000000;
    long long r[200000];
    
    cin >> n;
    for (int i=0;i<n;i++)
        cin >> r[i];
    
    long long minj = 10000000000;
    for (int i=0;i<n;i++){
        max1 = max(r[i]-minj, max1);
        minj = min(r[i], minj);
    }
    
    cout << max1 <<endl;
}




Measured memory_bytes: 4680
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
#include <array>
#include <numeric>
#include <regex>
#include <bitset>
#include <deque>

using namespace std;
typedef long long ll;
typedef pair<int, int> p_ii;

const int INF = 1e9;
const double PI = acos(-1.0);
const ll MOD = 1e9 + 7;



int main() {
    int N, K;
    cin>>N>>K;
    vector<int> h(N);
    for (int i = 0; i < N; i++) {
        cin>>h[i];
    }

    sort(h.begin(),h.end());
    reverse(h.begin(),h.end());

    int res = 1e9+7;
    for (int i = 0; i < N-K+1; i++) {
        res=min(res, h[i]-h[i+K-1]);
    }
    cout<<res<<endl;

    return 0;
}

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

using namespace std;

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

	int a, b;
	char c;
	cin >> a >> c >> b;
	cout << (c == '+' ? a + b : a - b) << '\n';

	return 0;
}



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

int main() {
  int N, M;
  cin >> N >> M;
  int a[M] = {}, b[M] = {};
  for(int i = 0; i < M; i++) cin >> a[i] >> b[i];
  int counterA[N] = {};
  int counterB[N] = {};
  for(int i = 0; i < M; i++) {
    counterA[a[i] - 1]++;
    counterB[b[i] - 1]++;
  }
  for(int i = 0; i < N; i++) {
    cout << counterA[i] + counterB[i] << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m; i < n; i++) 
typedef long long int ll;
int main(){
    int K,X;
    cin>>K>>X;
    if(500*K>=X){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    
    return 0;
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

int main() {
	int x;
	cin >>x;
	cout <<360/__gcd(x, 360)<<endl;
	return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main() {
    int N; cin >> N;
    vector<int>A(N+3);
    vector<int>B(N+3);
    long long ans = 0;
    A[0] = 0;
    A[N + 1] = 0;
    REP(i, N+2) {
        if(i!=0&&i!=N+1) cin >> A[i];
        ans += abs(A[i]-A[i-1]);
    }
    REP(i, N+1) {
        B[i-1] = abs(A[i-1]-A[i])+abs(A[i]-A[i+1])- abs(A[i - 1] - A[i + 1]);
        cout << ans - B[i-1]<<endl;
    }
}

Measured memory_bytes: 4036
# https://atcoder.jp/contests/abc160/submissions/11310424

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    def dist(a, b):
        return min(
            abs(a - b),
            abs(a - X) + abs(b - Y) + 1,
            abs(a - Y) + abs(b - X) + 1
        )

    ctr = [0] * N
    for b in range(N):
        for a in range(b):
            ctr[dist(a, b)] += 1

    it = iter(ctr)
    next(it)
    print(*it, sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int W[] = new int[2];
		int H[] = new int[2];

		W[0] = 0;
		W[1] = sc.nextInt();
		H[0] = 0;
		H[1] = sc.nextInt();


		int N = sc.nextInt();

		int x[] = new int[N];
		int y[] = new int[N];
		int a[] = new int[N];

		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			a[i] = sc.nextInt();
		}

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

			if (a[i]==1) {
				if (W[0] < x[i]) {
					W[0] = x[i];
				}
			}
			if (a[i]==2) {
				if(W[1] > x[i]) {
					W[1] = x[i];
				}
			}
			if (a[i]==3) {
				if (H[0] < y[i]) {
					H[0] = y[i];
				}
			}
			if (a[i]==4) {
				if (H[1] > y[i]) {
					H[1] = y[i];
				}
			}
		}

		int S = 0;

		if (W[1] > W[0] && H[1] > H[0]) {
			S = (W[1]-W[0])*(H[1]-H[0]);
		}
		System.out.println(S);
	}
}


Measured memory_bytes: 21332
#include <stdio.h>


int main()
{
	int M1,D1,M2,D2;
	long int a3=100000,a2=200000,a1=300000,s=400000;
	
	scanf("%d%d%d%d",&M1,&D1,&M2,&D2);
	
	if(M1!=M2 && D2==1){
		printf("1\n");
		return 0;
	}

	printf("0\n");
	return 0;
}

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

int main() {
	int n, m;
	cin >> n >> m;

	int mn = 0;
	int mx = n + 1;
	rep(i, m) {
		int l, r;
		cin >> l >> r;
		if (l > mn) mn = l;
		if (r < mx) mx = r;
		if (mx < mn) {
			cout << 0 << endl;
			return 0;
		}
	}
	cout << mx - mn + 1 << endl;

}

Measured memory_bytes: 256
import sys
from bisect import bisect as br
A, B, Q = map(int, input().split())
inf = 10**11
S = [-inf] + [int(sys.stdin.readline()) for _ in range(A)] + [inf]
T = [-inf] + [int(sys.stdin.readline()) for _ in range(B)] + [inf]
X = [int(sys.stdin.readline()) for _ in range(Q)]

StoT = [0]*A
for i, s in enumerate(S[1:-1]):
    x = br(T, s)
    StoT[i] = (s, min(s - T[x-1], T[x] - s))

TtoS = [0]*B
for i, t in enumerate(T[1:-1]):
    x = br(S, t)
    TtoS[i] = (t, min(t - S[x-1], S[x] - t))

M = [(-inf, inf)] + TtoS + StoT + [(inf, inf)]
M.sort()
Mk , Mv = list(map(list, zip(*M)))
for x in X:
    idx = br(Mk, x)
    print(min(Mk[idx] - x + Mv[idx], x - Mk[idx-1] + Mv[idx-1]))


Measured memory_bytes: 56016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 410;
const ll INF = 1e14;
ll dp[MAXN][MAXN],V[MAXN],pref[MAXN];
int N;
ll calc(ll a,ll b){
	if(a > b) return INF;
	return pref[b] - pref[a-1];
}
ll solve(int ini,int fim){
	if(dp[ini][fim] != -1) return dp[ini][fim];
	if(ini == fim) return dp[ini][fim] = 0;
	if(ini + 1 == fim) return dp[ini][fim] = V[ini] + V[fim];
	ll best = INF;
	for(int i = ini;i<fim;i++){
		ll cand = solve(ini,i) + solve(i+1,fim) + calc(ini,fim);
		best = min(best,cand);
	}
	return dp[ini][fim] = best;
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin >> N;
	for(int i = 1;i<=N;i++) cin >> V[i];
	for(int i = 1;i<=N;i++) pref[i] = pref[i-1] + V[i];
	cout << solve(1,N) << endl;
	return 0;
}

Measured memory_bytes: 1536
import sys
from itertools import product

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    A, B, C, D = il()
    return max(min(B, D) - max(A, C), 0)


if __name__ == "__main__":
    print(solve())


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

#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 reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n, k;
  cin >> n >> k;
  vi32 v(n);
  cin >> v;
  int ans = 0;
  repc(l, n) for (int r = n; r >= l; r--) {
    cerr << l << " " << r << endl;
    int c = l + (n - r);
    if (c > k) continue;
    int rest = k - c;
    int sum = 0;
    pqasc<int> q;
    rep(i, l) {
      sum += v[i];
      q.emplace(v[i]);
    }
    for (int i = n - 1; i >= r; i--) {
      sum += v[i];
      q.emplace(v[i]);
    }
    while (sz(q) && rest--) {
      int x = q.top();
      q.pop();
      if (x >= 0) break;
      sum -= x;
    }
    amax(ans, sum);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_set>

#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pl;

#define FST first
#define SND second

#define MAX_N   (100000)                  // 10^5
#define BASE    (1000000000 + 7)          // 10^9 + 7
#define INFI    (1000000000 + 7)          // 10^9 + 7
#define INFL    (1000000000000000000 + 7) // 10^18 + 7

int N;
set<int> G[MAX_N];
bitset<MAX_N> V(0);

void make_tree(int v) {
  for (auto u: G[v]) {
    G[u].erase(v);
    make_tree(u);
  }
}

void remove_match(int v) {
  for (auto u : G[v]) {
    remove_match(u);
    if (V[v] && V[u]) V[v] = V[u] = 0;
  }
}

string winner() {
  int root = 0;
  make_tree(root);
  remove_match(root);
  return V.none()? "Second": "First";
}

int main() {
  cin >> N;

  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].insert(b); G[b].insert(a);
    V.set(a); V.set(b);
  }

  string ans = winner();
  cout << ans << endl;

  return 0;
}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li cnt_sa[100100];
li cnt_sb[100100];

li cnt_ta[100100];
li cnt_tb[100100];

int main() {
    string s, t;
    cin >> s >> t;
    rep(i, sz(s)) {
        cnt_sa[i + 1] = cnt_sa[i] + (s[i] == 'A');
        cnt_sb[i + 1] = cnt_sb[i] + (s[i] == 'B');
    }
    rep(i, sz(t)) {
        cnt_ta[i + 1] = cnt_ta[i] + (t[i] == 'A');
        cnt_tb[i + 1] = cnt_tb[i] + (t[i] == 'B');
    }
    li q;
    cin >> q;
    rep(i, q) {
        li a, b, c, d;
        cin >> a >> b >> c >> d;
        a--;
        b--;
        c--;
        d--;
        li val_s = (cnt_sa[b + 1] - cnt_sa[a]) * 2 + (cnt_sb[b + 1] - cnt_sb[a]);
        li val_t = (cnt_ta[d + 1] - cnt_ta[c]) * 2 + (cnt_tb[d + 1] - cnt_tb[c]);
        cout << (val_s % 3 == val_t % 3 ? "YES" : "NO") << endl;
    }


    return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
struct Node{
  int key;
  Node *parent,*left,*right;
};

Node *root,*NIL;

void Preorder(Node *pp){
  if(pp==NIL)return;
  cout<<" "<<pp->key;
  Preorder(pp->left);
  Preorder(pp->right);
}
void Inorder(Node *in){
  if(in==NIL)return;
  Inorder(in->left);
  cout<<" "<<in->key;
  Inorder(in->right);
}

void insert(int k){
  Node *z;
  Node *y=NIL; //x's parent
  Node *x=root; //T's root
  z=(Node *)malloc(sizeof(Node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;
  while(1){
    if(x==NIL)break;
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL){
    root=z;
  }
  else {
    if(z->key<y->key){
      y->left=z;
    }
    else {
      y->right=z;
    }
  }
}
Node * treesearch(Node *x, int k){
  while(x!=NIL&&k!=x->key){
    if(k<x->key)x=x->left;
    else x=x->right;
  }
  return x;
}
Node * treemini(Node *x){
  while(x->left!=NIL)x=x->left;
  return x;
}

Node * treesucces(Node *x){
  if(x->right!=NIL)return treemini(x->right);
  Node *y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->right;
  }
  return y;
}

void treedel(Node *z){
  Node *y;
  Node *x;
  if(z->left==NIL||z->right==NIL)y=z;
  else y=treesucces(z);
  if(y->left!=NIL){
    x=y->left;
  }
  else{
    x=y->right;
  }
  if(x!=NIL){
    x->parent=y->parent;
  }
  if(y->parent==NIL)root=x;
  else{
    if(y==y->parent->left)y->parent->left=x;
    else y->parent->right=x;
  }
  if(y!=z)z->key=y->key;
  free(y);
}
int main(){
  int n=0,in=0;
  int i=0;
  char cel[10];
  int x;
  Node *f;
  cin>>n;
  for(i=0;i<n;i++){
    cin>>cel;
    if(!strcmp(cel, "insert")){
      cin>>in;
      insert(in);
    }
    else if(!strcmp(cel, "print")){
      Inorder(root);
      cout<<endl;
      Preorder(root);
      cout<<endl;
    }
    else if(!strcmp(cel, "find")){
      cin>>in;
      f= treesearch(root,in);
      if(f!=NIL){
	cout<<"yes"<<endl;
      }
      else {
	cout<<"no"<<endl;
      }
    }
    else if(!strcmp(cel, "delete")){
      cin>>x;
      treedel(treesearch(root,x));
    }
  }
  return 0;
}



Measured memory_bytes: 21804
n=int(input())
if n==1:
  print(0)
  exit()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
arr=factorization(n)
sumarr=[]
ans=0
for i in range(42):
    sumarr.append(i*(i+1)//2)
for i in arr:
    for j in range(1,41):
        if sumarr[j]<=i[1]<sumarr[j+1]:
            ans+=j
print(ans)

Measured memory_bytes: 9504
#include <bits/stdc++.h>
#define rep(a,n) for (int a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<vector<ll> > Graph;
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 ll INF = 1e9;


int main(){
    string s;
    cin >> s;
    int l = s.size();
    int cnt = 0;
    rep(i,l-1){
        if(s[i]!=s[i+1])cnt++;
    }
    cout << cnt << endl;

    return 0;
}

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

using namespace std;

int main() {
  string s,t;
  cin >> s >> t;
  int ns = s.size();
  int nt = t.size();
  bool ans = false;

  for (int i=ns-1; i>=0; i--) {
    bool f = true;  
    for (int j=0; j<min(ns,nt); j++) {
      if (s[i-j] != t[nt-j-1] && s[i-j] != '?') {
        f = false;
        break;
      }
    }

    if (f) {
      for (int j=0; j<min(ns,nt); j++) {
        s[i-j] = t[nt-j-1];
      }
      ans = true;
      break;
    }
  }
  ans = ans && ns>=nt;
  if (ans) {
    for (auto c : s)
      cout << (c=='?'? 'a' : c);
    cout << endl;
  } else {
    cout << "UNRESTORABLE" << endl;
  }
}


Measured memory_bytes: 256