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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/05  Problem: 077_arc_b / Link: https://arc077.contest.atcoder.jp/tasks/arc077_b?lang=en  ----- */
/* ------問題------

1,…,n の n 個の整数からなる長さ n+1 の数列 a1,a2,…,an+1 が与えられます。 この数列には 1,…,n のどの整数もかならず 1 回以上出現することが分かっています。
k=1,…,n+1 のそれぞれについて、与えられた数列の長さ k の（連続とは限らない）部分列の個数を求め、 109+7 で割ったあまりを出力して下さい。
注意
2 つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、1 通りと数えます。
数列 a の長さ k の部分列とは、a の要素のうち k 個を選んで、 それらを順番を変えずに取り出して並べた数列のことを指します。 例えば、数列 1,2,3,4,5 の長さ 3 の部分列には、 1,3,5 や 1,2,3 などがあります。 一方で、3,1,2 や 1,10,100 はこの数列の部分列ではありません。

-----問題ここまで----- */
/* -----解説等-----

重複したときにこれらの左右を考えたとき、n+1 Comb k - (N+1 - R + (L-1)) Comb k-1 が組み合わせの数
あとは書くだけ

----解説ここまで---- */

LL N;

LL ans = 0LL;


const long long mod = 1e9 + 7;

long long modpow(long long a, long long b) {
	if (b == 0) return 1;
	return modpow(a * a % mod, b / 2) * (b & 1 ? a : 1) % mod;
}

long long modinv(long long a) {
	return modpow(a, mod - 2);
}

vector<long long> fact, inv_fact;

void init_fact(int n) {
	fact.resize(n);
	fact[0] = 1;
	for (int i = 1; i < n; i++) {
		fact[i] = i * fact[i - 1] % mod;
	}
	inv_fact.resize(n);
	inv_fact[n - 1] = modinv(fact[n - 1]);
	for (int i = n - 2; i >= 0; i--) {
		inv_fact[i] = (i + 1) * inv_fact[i + 1] % mod;
	}
}

long long nPr(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	return fact[n] * inv_fact[n - r] % mod;
}

long long nCr(int n, int r) {
	if (n < r || n < 0 || r < 0) return 0;
	return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod;
}

long long nHr(int n, int r) {
	if (n == 0 && r == 0) return 1;
	return nCr(n + r - 1, r);
}

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

	cin >> N;
	VL a(N + 1);
	map<int, int>cnt;
	int posL, posR;
	FOR(i, 0, N + 1) {
		cin >> a[i];
		if (cnt[a[i]]) {
			posR = i + 1;
		}
		cnt[a[i]]++;
	}
	FOR(i, 0, N + 1) {
		if (cnt[a[i]] == 2) {
			posL = i + 1;
			break;
		}
	}
	//cout << posL << " " << posR << endl;
	init_fact(3 * N);
	FOR(i, 0, N + 1) {
		int k = i + 1;
		//debug(nCr(N + 1, k));
		//debug(nCr((posL - 1) + ((N + 1) - (posR )), k - 1));
		ans = nCr(N + 1, k) - nCr((posL-1 ) + ((N + 1) - (posR )), k - 1);
		cout << (ans+ mod)%mod << endl;
	}


	return 0;
}


Measured memory_bytes: 11392
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define INF 1LL<<60

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll M = 1e9 + 7;

vector<ll> fac(2000001); //n!(mod M)
vector<ll> ifac(2000001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}

int main() {
    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<2000001; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }
    
    ll mod = 1e9 + 7;
    int X, Y;
    cin >> X >> Y;

    ll Nx = 2*X - Y;
    ll Ny = 2*Y - X;

    if(Nx % 3 != 0 || Ny % 3 != 0 || Nx < 0 || Ny < 0) {
        cout << 0 << endl;
        return 0;
    }

    Nx /= 3;
    Ny /= 3;

    ll ans = comb(Nx + Ny, Nx)%M;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 31488
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.math;
import std.regex;
import std.range;

void main() {
	auto X = readln.chomp.to!int, A = readln.chomp.to!int, B = readln.chomp.to!int;
	auto tmp = X - A;
	(tmp % B).writeln;
}


Measured memory_bytes: 256
a, b, c, x, y = map(int, input().split())

count = a * x + b * y
for i in range(10 ** 6):
  num = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b
  if(count > num):
    count = num

print(count)


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

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N;cin>>N;
    ll sum=0;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    for(int i=1;i<N;i++){
        if(A[i-1]>=A[i]) sum++;
    }
    cout<<sum+1<<endl;
    cout<<N<<endl;
}





Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
#define int long long
int gcd(int a, int b) {
	if (b == 0)return a;
	return gcd(b, a%b);
}
int lcm(int a, int b) {
	return a / gcd(a, b)*b;
}
int modpow(int a,int b){
    if(!b)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int fac(int a){
    int Ans=1;
    for(int i=1;i<=a;i++){
        Ans*=i;
        Ans%=MOD;
    }
    return Ans;
}//kaijo
int comb(int a,int b){
    return fac(a)*modpow(fac(a-b),MOD-2)%MOD*modpow(fac(b),MOD-2)%MOD;
}
signed main(){
	int h,w,s,t;
	cin>>h>>w>>s>>t;
	if(h%2&&w%2&&(s+t)%2)puts("No");
	else puts("Yes");
	return 0;
}




Measured memory_bytes: 3076
/**
 * @author: Jun
 * @date  : 03-18-2019
 **/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define el '\n'
#define MOD 1000000007

int n,m;
pair<ll,ll> arr[100005];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int a,b;
        cin >> a >> b;
        arr[i] = make_pair(a, b);
    }
    sort(arr+1,arr+1+n);

    ll res=0;
    ll res2=0;
    ll ptr=1;
    while(res < m){
        if(res + arr[ptr].second <= m){
            res2 += arr[ptr].first*arr[ptr].second;
            res += arr[ptr].second;
            ptr++;
        } else {
            ll sel = m-res;
            res = m;
            res2 += sel*arr[ptr].first;
            break;
        }
    }
    cout << res2 << el;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b, k;
	cin >> a >> b >> k;
	for(int i = max(a, b); i; i--) {
		if(a % i == 0 && b % i == 0) {
			k--;
			if(k == 0) {
				cout << i << endl;
				return 0;
			}
		}
		
	} 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long,long>> vpll;
typedef vector<pair<int,int>> vpii;
int main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	int dp[2][10000010];
	ins(a);
	dp[0][0] = a[0] - '0';
	dp[1][0] = 11 - (a[0] - '0');
	FOR(i,1,a.size()){
		dp[0][i] = min(dp[0][i-1],dp[1][i-1]) + a[i] - '0';
		dp[1][i] = min(dp[0][i-1] + 11 - (a[i] - '0'),dp[1][i-1] + 9 - (a[i] - '0'));
	}
	out(min(dp[0][a.size()-1],dp[1][a.size()-1]));
	return 0;
}

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

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double EPS = 1e-6;
const int MAX_N = 1e5 + 5;

int N, M;
vector<int> adjList[MAX_N];
int memo[MAX_N];

int dfs(int u) {
	if (memo[u] != -1) return memo[u];
	int maxi = 0;
	for (int v: adjList[u]) {
		maxi = max(maxi, dfs(v) + 1);
	}
	return memo[u] = maxi;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int u, v; cin >> u >> v;
		adjList[u].push_back(v);
	}
	memset(memo, -1, sizeof memo);

	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		ans = max(ans, dfs(i));
	}

	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 8192
from collections import deque

h,w = map(int, input().split())
A = [[s for s in input()] for _ in range(h)]

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)

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

using namespace std;

int p[10000010];

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

    for (int i = 2; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            p[j]++;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += 1LL * i * (p[i] + 1);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 42680
#include <iostream>
using namespace std;
int main(void){
    int x,y,X,Y,a,b,c,d,k,h;
    cin>>x>>y>>X>>Y>>a>>b>>c>>d;
    h=x*a+y*b;
    k=X*a+Y*b;
    x=x/10*c;
    y=y/20*d;
    X=X/10*c;
    Y=Y/20*d;
    if(h+x+y>k+X+Y){cout<<"hiroshi"<<endl;}
    else if(h+x+y<k+X+Y){cout<<"kenjiro"<<endl;}
    else{cout<<"even"<<endl;}
    
}



Measured memory_bytes: 3100
package main

import (
	"bufio"
	"fmt"
	"os"
)

type graph struct {
	nodeCount int
	edges     []*edge
}

func (g *graph) finalNode() int {
	return g.nodeCount
}

func (g *graph) doubleWeights() {
	for _, edge := range g.edges {
		edge.weight = 2 * edge.weight
	}
}

type edge struct {
	from, to int
	weight   int
}

func createGraph(L int) *graph {
	if L == 2 {
		edges := make([]*edge, 2)
		edges[0] = &edge{1, 2, 0}
		edges[1] = &edge{1, 2, 1}
		return &graph{
			nodeCount: 2,
			edges:     edges,
		}
	}
	if L%2 == 1 {
		subG := createGraph(L - 1)
		subG.edges = append(subG.edges, &edge{1, subG.finalNode(), L - 1})
		return subG
	} else {
		subG := createGraph(L / 2)
		subG.doubleWeights()

		subG.nodeCount++
		subG.edges = append(subG.edges, &edge{subG.finalNode() - 1, subG.finalNode(), 0})
		subG.edges = append(subG.edges, &edge{subG.finalNode() - 1, subG.finalNode(), 1})

		return subG
	}
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	var L int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d", &L)

	g := createGraph(L)
	fmt.Println(g.nodeCount, len(g.edges))
	for _, edge := range g.edges {
		fmt.Println(edge.from, edge.to, edge.weight)
		//fmt.Println("\t", edge.from, " -> ", edge.to, " [ label=", edge.weight, "];")
	}

}


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

int main(){
  int n,k;cin >> n >> k;
  vector<long long> h(n);
  long long sum=0;
  for(int i=0;i<n;i++){
    cin >> h[i];
  }
  sort(h.begin(),h.end());
  for(int i=0;i<n-k;i++){
    sum += h[i];
  }
  cout << sum << endl;
}

Measured memory_bytes: 1792
import java.util.Scanner;

class Main {
  public static void main(String argv[]) {
    int n, x, a = 1000, m;
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    x = sc.nextInt();
    
    for (int i = 0;i < n;i++) {
      m = sc.nextInt();
      x -= m;
      a = Math.min(a, m);
    }
    
    System.out.println(n + x/a);
  }
}

Measured memory_bytes: 21844
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
B=[0]
S=set()
S.add(0)
cur=A[0]-1
while True:
  if cur in S:
    break
  else:
    S.add(cur)
    B.append(cur)
    cur=A[cur]-1
d=len(B)
ind=B.index(cur)
if k<=ind:
  print(B[k]+1)
else:
  print(B[(k-ind)%(d-ind)+ind]+1)


Measured memory_bytes: 35388
n = input()


if int(n) % 10 != 0:
    print(sum([int(i) for i in list(n)]))
else:
    a = int(int(n)/10)
    b = int(n)-a

    a_sum = sum([int(i) for i in list(str(a))])
    b_sum = sum([int(i) for i in list(str(b))])
    print(a_sum+b_sum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MAXN 100000
typedef long long ll;

using namespace std;

int main(){
    int N;
    cin >> N;
    map<int,bool> a;
    for (int i=0;i<N;i++){
	int x;
	cin >> x;
	if (a[x]) a[x]=false;
	else a[x]=true;
    }

    int res=0;
    for (auto itr=a.begin();itr!=a.end();itr++){
	if (itr->second) res++;
    }

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

Measured memory_bytes: 4864
import sys
input=sys.stdin.readline

n,m = map(int, input().split())
k = []
a = []
for i in range(n):
    s = list(map(int, input().split()))
    k.append(s[0])
    a.append(s[1:])
ans = set(a[0])
for i in a:
    ans = ans & set(i)
print(len(ans))


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

using namespace std;

int main()
{

    int n;

    float s[10000];
     cin >> n;

    float sum = 0;
    for(int i = 0;i < n;i++)
    {

        cin >> s[i];


    }

   sort(s,s+n);

   float ans = 0;
   ans = (s[0] + s[1])/2;
   for(int i = 2;i<n;i++)
   {

       ans = (ans +s[i])/2;
   }


   cout << ans;
}





Measured memory_bytes: 256
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second
#define int long long

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int inf = 1e9 + 5;

int n, A, B;
int h[maxn];

void read_input()
{
    cin >> n >> A >> B;
    for(int i = 1; i <= n; ++i)
        cin >> h[i];
}

bool check(int k)
{
    int need = 0;
    for(int i = 1; i <= n; ++i)
        if(h[i] > B * k)
            need += (h[i] - B * k + A - B - 1) / (A - B);
    return need <= k;
}

void solve()
{
    int low = 1, high = inf;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(check(mid)) high = mid - 1;
        else low = mid + 1;
    }
    cout << low << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



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

using namespace std;

#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,(int)(v.size()-1)) os << v[i] << " ";
    os << v[v.size()-1];
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

const int maxn = 2e5+5;
LL N,D;
LL A[maxn];
LL R[maxn];

LL fee(int l,int r){
    return (r - l)*D + A[l] + A[r];
}



int main()
{
    cin >> N >> D;
    _rep(i,1,N){
        cin >> A[i];
    }
    R[N] = N;
    for(int i = N-1; i>= 0;i--){
        LL bef = R[i+1];
        if( (bef - i)*D + A[bef] > A[i]){
            R[i] = i;
        }
        else R[i] = bef;
    }


    LL ans = 0;
    int l = 1;
    int ll = 1;
    int r = 2;
    while(l < N){
        r = R[r];
        ans += fee(ll,r);
        _for(i,l+1,r){
            ans += min(fee(ll,i),fee(i,r));
        }
        l = r;
        if((l - ll)*D + A[ll] >= A[l]){
            ll = r;
        }
        r++;
    }
    cout << ans << endl;


    return 0;
}


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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

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

    string s;
    cin >> s;

    bool f1 = false;
    bool f2 = false;
    for(int i=0; i<s.size()-1; i++){
        if(s[i] == 'A' && s[i+1] == 'C'){
            f2 = true;
        }

    }

    if(f2){
        puts("Yes");
    }else{
        puts("No");
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iterator>
#pragma warning(disable:4996)
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
#define MOD 1000000007
using namespace std;


int main(int argc, char* argv[])
{
    long w, h, n;
    scanf("%ld%ld%ld", &w, &h, &n);

    long z[4]={0, w, 0, h};
    long i;
    for(i=0; i<n; i++) {
        long x, y, a;
        scanf("%ld%ld%ld", &x, &y, &a);
        if(a==1) {
            z[0]=MAX(z[0], x);
        }
        if(a==2) {
            z[1]=MIN(z[1], x);
        }
        if(a==3) {
            z[2]=MAX(z[2], y);
        }
        if(a==4) {
            z[3]=MIN(z[3], y);
        }
    }
    if(z[0]>z[1] || z[2]>z[3]) {
        printf("0\n");
    }
    else {
        printf("%ld\n", (z[1]-z[0])*(z[3]-z[2]));
    }
    
    return 0;
}



Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

int main(){

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

  vector <long long> ans(N);

  for (int i = 0; i < N; i++){
    if (i % 2 == 0) ans[0] = ans[0] + A[i];
    else ans[0] = ans[0] - A[i];
  }

  for (int i = 0; i < N - 1; i++){
    ans[i + 1] = 2 * A[i] - ans[i];
  }
  
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i != N - 1) cout << " ";
    else cout << endl;
  }
  
  
  

  return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
int main()
{
    double a,b,c,s,l,h;
    cin >> a >> b >> c;

    double rad;
    double PI = acos(-1);  // PI = 3.141593...
    rad = c * PI / 180;

    s = a * b * sin(rad)/2;
    h = a+b+sqrt(a*a+b*b-2*a*b*cos(rad));
    l = b * sin(rad);
    
    cout << fixed << setprecision(8) <<  s << endl;
    cout << fixed << setprecision(8) <<  h << endl;
    cout << fixed << setprecision(8) <<  l << endl;

    return 0;
}



Measured memory_bytes: 3532
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;

    vector<ll> is_prime(pow(*max_element(a.begin(), a.end()), 1.0 / 3.0) + 3,
                        1);
    vector<ll> primes;
    primes.reserve(is_prime.size());

    is_prime[0] = 0;
    is_prime[1] = 0;

    for (int i = 2; i < is_prime.size(); ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < is_prime.size(); j += i) {
                is_prime[j] = 0;
            }
        }
    }

    map<ll, int> cnt;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < primes.size(); ++j) {
            if (primes[j] * primes[j] * primes[j] > a[i]) break;

            while (a[i] % (primes[j] * primes[j] * primes[j]) == 0) {
                a[i] /= primes[j] * primes[j] * primes[j];
            }
        }
        cnt[a[i]]++;
    }

    int ans = 0;
    if (cnt[1] > 0) ans++;

    set<ll> used;

    for (auto& x : cnt) {
        if (x.first == 1) continue;

        if (used.count(x.first)) continue;

        ll y = x.first;
        ll z = 1;
        for (int j = 0; j < primes.size(); ++j) {
            auto divide = primes[j] * primes[j];
            if (y < divide) break;
            if (y % divide == 0) {
                y /= divide;
                z *= primes[j];
            }
        }
        z *= y * y;

        if (cnt.count(z)) {
            ans += max(x.second, cnt[z]);
            used.insert(z);
        } else {
            ans += x.second;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 7680
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, D: int, X: "List[List[int]]"):
    ret = 0
    for i in range(N):
        for j in range(N):
            if j <= i:
                continue

            acc = 0
            for y, z in zip(X[i], X[j]):
                acc += (y - z) ** 2

            tmp = int(sqrt(acc))
            ret += int((tmp * tmp) == acc)
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = [ [ int(next(tokens)) for _ in range(D) ] for _ in range(N) ]  # type: "List[List[int]]"
    result = solve(N, D, X)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5124
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL (1LL<<62) // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, l;
    cin >> n >> l;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    bool ok = false;
    ll okIdx = -1;
    for(ll i=1; i<n; i++){
        if(a[i]+a[i-1] >= l){
            ok = true;
            okIdx = i;
            break;
        }
    }
    if(ok){
        cout << "Possible" << endl;
        for(ll i=1; i<okIdx; i++) cout << i << endl;
        for(ll i=n-1; i>okIdx; i--) cout << i << endl;
        cout << okIdx << endl;
    }
    else cout << "Impossible" << endl;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

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

int main() {
  string s;
  cin >> s;
  int x, y;
  cin >> x >> y;
  int N = s.size();

  vector<int> o;
  s.pb('T');
  int cnt = 0;
  rep(i, s.size()) {
    if (s[i] == 'T') {
      o.pb(cnt);
      cnt = 0;
    } else {
      cnt++;
    }
  }

  vector<int> xx;
  vector<int> yy;
  x -= o[0];
  repp(i, 1, o.size() - 1) {
    if (i % 2 == 0) {
      xx.pb(o[i]);
    } else {
      yy.pb(o[i]);
    }
  }

  N *= 2;
  int X = xx.size();
  vector<vector<bool>> xdp(X + 1, vector<bool>(2 * N + 1, false));
  xdp[0][N] = true;
  rep(i, X) {
    rep(j, 2 * N + 1) {
      int nj = j + xx[i];
      if (nj < 2 * N * 1)
        xdp[i + 1][nj] = (xdp[i][j] || xdp[i + 1][nj]);

      nj = j - xx[i];
      if (nj >= 0)
        xdp[i + 1][nj] = (xdp[i][j] || xdp[i + 1][nj]);
    }
  }
  bool XX = xdp[X][N + x];

  int Y = yy.size();
  vector<vector<bool>> ydp(Y + 1, vector<bool>(2 * N + 1, false));
  ydp[0][N] = true;
  rep(i, Y) {
    rep(j, 2 * N + 1) {
      int nj = j + yy[i];
      if (nj < 2 * N * 1)
        ydp[i + 1][nj] = (ydp[i][j] || ydp[i + 1][nj]);

      nj = j - yy[i];
      if (nj >= 0)
        ydp[i + 1][nj] = (ydp[i][j] || ydp[i + 1][nj]);
    }
  }
  bool YY = ydp[Y][N + y];

  if (XX && YY)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

int main() {
	ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ans = a * c;
    ans = max(ans, b * d);
    ans = max(ans, a * d);
    ans = max(ans, b * c);
    cout << ans << endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <numeric>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <random>
#include <list>

using namespace std; 

int main()
{
	int n;
	cin >> n;
	string a;
	list<char> b;
	
	cin >> a;
	
	for (int i = 0; i < a.size(); i++)
	{
		b.push_back(a[i]);
	}

	int count = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == '(') count++;
		else count--;

		if (count < 0)
		{
			b.push_front('(');
			count = 0;
		}
	}
	if (count > 0)
	{
		for (int i = 0; i < count; i++)
		{
			b.push_back(')');
		}
	}

	for (auto v : b)
	{
		cout << v;
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>

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

using namespace std;

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

int tx,ty,bx,by,memo[3][3][16];

void f(char c,int &x,int &y){
	x=(c-'A')%3;
	y=(c-'A')/3;
}

int dfs(int x,int y,int batt){
	if(~memo[y][x][batt])	return memo[y][x][batt];
	if(batt==0)	return (x==tx && y==ty);

	int cnt=0;
	rep(i,4){
		int xx=x+dx[i],yy=y+dy[i];
		if(0<=xx && xx<3 && 0<=yy && yy<3 && !(xx==bx && yy==by));
		else	xx=x,yy=y;
		cnt+=dfs(xx,yy,batt-1);
	}
	return memo[y][x][batt]=cnt;
}

int main(){
	int n;
	for(char s,t,b;scanf("%d %c %c %c",&n,&s,&t,&b),n;){
		memset(memo,-1,sizeof(memo));
		int sx,sy;
		f(s,sx,sy);
		f(t,tx,ty);
		f(b,bx,by);
		printf("%.9f\n",dfs(sx,sy,n)/pow(4.0,n));
	}
	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"

using namespace std;

typedef long long LL;
typedef unsigned long UL;

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

int main()
{
    int n;
    cin >> n;
    
    vector<pair<int, int>> ab(n), cd(n);
    REP(i, n)
    {
        cin >> ab[i].first >> ab[i].second;
    }
    REP(i, n)
    {
        cin >> cd[i].first >> cd[i].second;
    }

    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());

    int ans = 0, mj;
    vector<int> used(n, -1);

    REP(i, n)
    {
        mj = -1;
        REP(j, n)
        {
            if (cd[i].first > ab[j].first && cd[i].second > ab[j].second && find(used.begin(), used.end(), j) == used.end() && ab[j].second == max(ab[j].second, mj))
            {
                used[i] = j;
                mj = ab[j].second;
            }
        }

        if (used[i] != -1)
        {
            ++ans;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
#include <climits>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;

int N,Q;

//BIT
ll bit0[100001],bit1[100001];

ll sum(ll *b,int i){
    ll s=0;
    while(i>0){
        s+=b[i];
        i-=i&-i;
    }
    return s;
}

void add(ll *b,int i,int v){
    while(i<=N){
        b[i]+=v;
        i+=i&-i;
    }
}

int main(){
    cin>>N>>Q;
    int q,s,t,x;

    for(int i=0;i<Q;i++){
        cin>>q;
        if(q==0){
            cin>>s>>t>>x;
            add(bit0,s,-x*(s-1));
            add(bit1,s,x);
            add(bit0,t+1,x*t);
            add(bit1,t+1,-x);
        }else{
            cin>>s>>t;
            ll res=0;
            res+=sum(bit0,t)+sum(bit1,t)*t;
            res-=sum(bit0,s-1)+sum(bit1,s-1)*(s-1);
            cout<<res<<endl;
        }
    }
}


Measured memory_bytes: 4660
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<int, int> mp;
map<int, int>mm;
#define ll long long
#define ld long double
#define PI 3.14159265358979l

int gcd(int a, int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}


int main() {
	char b;
	cin >> b;
	if (b == 'A')cout << 'T' << endl;
	else if (b == 'C')cout << 'G' << endl;
	else if (b == 'G')cout << 'C' << endl;
	else if (b == 'T')cout << 'A' << endl;
	return 0;
}

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

const int mnx = 3e5 + 9;
const int mod = 1e9 + 7;

ll a, b;

int main(){

cin>>a>>b;

if(a < 0 && b > 0){ cout<<"Zero\n"; return 0; }
if(a > 0 && b < 0){ cout<<"Zero\n"; return 0; }
if(a > 0 && b > 0){ cout<<"Positive"; return 0; }
if(a < 0 && b < 0){
    if(abs(abs(a) - abs(b)) % 2 == 0){
        cout<<"Negative";
        return 0;
    } else {
        cout<<"Positive";
        return 0;
    }
}

return 0;

}















Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
using namespace std;

int main() {
    string s;
    
    cin>>s;
    
    if(s == "Sunny") s = "Cloudy";
    
    else if(s == "Cloudy") s = "Rainy";
    
    else s = "Sunny";
    
        
    cout<<s<<endl;
    
    return 0;
}


Measured memory_bytes: 256
s = input()
for _ in [0]*int(input()):
    command = []
    command.append(list(map(str,input().split())))
   # print(command[0][0])
    if command[0][0] == 'replace':
        s = s[:int(command[0][1])] + command[0][3] + s[int(command[0][2])+1:]
    elif command[0][0] == 'reverse':
        temp =  s[int(command[0][1]):int(command[0][2])+1:]
        s = s[:int(command[0][1])] +temp[::-1] + s[int(command[0][2])+1:]
    elif command[0][0] == 'print':
        print(s[int(command[0][1]):int(command[0][2])+1])



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

signed main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (auto&& w : a) cin >> w;
  sort(begin(a), end(a));
  copy(begin(a), end(a), begin(b));
  for (int i = 0; i < n - 1; i++) {
    b[i + 1] += b[i];
  }
  int num = -1;

  for (int i = n - 2; i >= 0; i--) {
    if (a[i + 1] > 2 * b[i]) {
      num = i;
      break;
    }
  }
  if (num == -1)
    cout << n << endl;
  else
    cout << n - 1 - num << endl;
  //   for (auto&& w : a) cout << w << " ";
  //   cout << endl;
  //   for (auto&& w : b) cout << w << " ";
  //   cout << endl;
  //   cout << num;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
const int MOD=1E9+7;
const int N=100000+5;
const int dx[]={-1,1,0,0,-1,-1,1,1};
const int dy[]={0,0,-1,1,-1,1,-1,1};
using namespace std;
vector<int> vc[N];
int vis[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++)
	{
        int x,y;
        cin>>x>>y;
        vc[x].push_back(y);
        vc[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    q.push(n);
    vis[1]=1;
    vis[n]=2;
    int fc=0,se=0;
    while(!q.empty())
	{
        int x=q.front();
        q.pop();
        for(int i=0;i<vc[x].size();i++)
		{
            int y=vc[x][i];
            if(vis[y]==0)
			{
                q.push(y);
                vis[y]=vis[x];
                if(vis[y]==1)
                    fc++;
                else if(vis[y]==2)
                    se++;
            }
        }
    }
    if(fc>se)
        cout<<"Fennec";
    else
        cout<<"Snuke";
    return 0;
}

Measured memory_bytes: 6272
import sys
import math
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [I() for i in range(5)]

print(math.ceil(N/min(a))+4)

Measured memory_bytes: 38384
A,B,H,M=map(int,input().split())
N=abs(H*30+M*0.5-M*6)
if N >= 180 :
    N=360-N
import math
ans2=A**2+B**2-2*A*B*math.cos((math.radians(N)))
#print(A**2,B**2,2*A*B,math.cos(math.radians(N)))
ans=math.sqrt(ans2)
print(ans)

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

#define F first
#define S second
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(int i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cout << str << " : " << t << endl;}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cout << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cout << "["; for (T i = a; i != b; ++i) {if (i != a) cout << ", "; cout << *i;} cout << "]";cout<<endl;}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	vi f(4);
	FOR (i, 1, n) {
		int x; cin >> x;
		f[x&3]++;
	}
	cout << (f[1] + f[3] + min(1, f[2]) <= f[0] + 1 ? "Yes\n" : "No\n");

	return 0;
}


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

using namespace std;
#define ll  long long
#define ld  long double

#define endl '\n'
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int MAXN=1e5 + 5;
bool comp(pair<int,int>p1,pair<int,int>p2)
{
    return p1.second<p2.second;
}
ll gcd (ll a,ll b)
{
    if(a==0)
        return b;
    return gcd(b%a,a);
}
ll lcm(ll a, ll b)
{
    return (a*b)/gcd(a, b);
}

int main()
{
    FAST
string h;
cin>>h;
string rev=h;
reverse(rev.begin(),rev.end());
h==rev?cout<<"Yes":cout<<"No";

    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

ll n, m;
vector<vector<ll>> g;
vector<ll> dp;

ll dfs(ll v, ll p = -1) {
    if (dp[v] != -1) return dp[v];
    ll res = 0;
    for(auto u : g[v]) {
        if (u == p) continue;
        res = max(res, dfs(u, v) + 1);
    }
    dp[v] = res;
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    cin >> n >> m;
    g.resize(n);
    rep(i, m) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
    }
    dp.resize(n, -1);
    ll ans = 0;
    rep(i, n) ans = max(ans, dfs(i));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
   int K,S;
   cin>>K>>S;
   int count=0;
   for(int i=0;i<=K;i++){
       for(int j=0;j<=i;j++){
           for(int k=0;k<=j;k++){
               if(i+j+k==S) {
                   if(i==j&&j==k){count++;}
                   else if(i!=j&&j!=k){count+=6;}
                   else count+=3;
                   
               }
           }
       }
   }
   cout<<count;
   return 0;
}


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init));

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,h,m;
  vector<pll> v;
  cin >> n;
  rep(i,n){
    cin >> h >> m;
    v.push_back(make_pair(h,m));
  }
  cin >> n;
  rep(i,n){
    cin >> h >> m;
    v.push_back(make_pair(h,m));
  }
  Unique(v);
  rep(i,v.size()){
    if(i) cout << " " ;
    cout << v[i].fi << ":";
    cout << setw(2) << setfill('0')<<v[i].se;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
int n = 100005;
vector<int> dp(n,-1);

int dfs(int i){
  int res = INF;
  if(i==0) return 0;
  if(dp.at(i-1) == -1) dp.at(i-1) = dfs(i-1);
  res = min(res,dp.at(i-1)+1);
  int j = 6;
  int count = 1;
  while(i-j>=0){
    if(dp.at(i-j) == -1) dp.at(i-j) = dfs(i-j);
    res = min(res,dp.at(i-j)+count);
    j *= 6;
  }
  j = 9;
  while(i-j>=0){
    if(dp.at(i-j) == -1) dp.at(i-j) = dfs(i-j);
    res = min(res,dp.at(i-j)+count);
    j *= 9;
  }
  return res;
}

 
int main() {
  cin >> n;
  dp.at(0) = 0;
  cout << dfs(n) << endl;
  //rep(i,n) cout << dp.at(i) << " ";
  
  return 0;
}





Measured memory_bytes: 6912
#!/usr/bin/env python3

import functools


def div_ceil(a, b):
    return (a + b - 1) // b


def simulate(cs, ss, fs, goal_sta, start_sta):
    assert start_sta <= goal_sta
    cur_t = 0
    for i in range(start_sta, goal_sta):
        next_start_t = max(ss[i], div_ceil(cur_t, fs[i]) * fs[i])
        cur_t = next_start_t + cs[i]
    return cur_t


def solve(n, cs, ss, fs):
    sim_from = functools.partial(simulate,
                                 cs=cs, ss=ss, fs=fs, goal_sta=n - 1)
    return [sim_from(start_sta=i) for i in range(n)]


def main():
    n = int(input())
    cs = [-1 for _ in range(n - 1)]
    ss = [-1 for _ in range(n - 1)]
    fs = [-1 for _ in range(n - 1)]
    for i in range(n - 1):
        cs[i], ss[i], fs[i] = (int(z) for z in input().split())
    print(*solve(n, cs, ss, fs), sep="\n")


if __name__ == '__main__':
    main()


Measured memory_bytes: 4188
r1, c1, r2, c2 = map(int, input().split())

MOD=10**9+7
MAXN=4000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1): 
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

def comb(n, r): 
    if r<0 or r>n: 
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

ans = comb(r2+c2+2, r2+1)-1
ans -= comb(r2+1+c1, c1)-1
ans -= comb(r1+c2+1, r1)-1
ans += comb(r1+c1, r1)-1

print(ans%MOD)

Measured memory_bytes: 208688
#include <bits/stdc++.h>
using namespace std;
int main()
{

  int w,h,n;
  cin>>w>>h>>n;
  int X1=0,X2=w,Y1=0,Y2=h;
  for(int i=0;i<n;i++)
  {
    int x,y,a;
    cin>>x>>y>>a;
    if(a==1)
    {
      X1=max(X1,x);
    }
    else if(a==2)
    {
      X2=min(X2,x);
    }
    else if(a==3)
    {
      Y1=max(Y1,y);
    }
    else if(a==4)
    {
      Y2=min(Y2,y);
    }
  }
  
  long long ans=(X2-X1)*(Y2-Y1);
  if(X2<=X1 ||Y2<=Y1)ans=0;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll i,j,k,n,a[1000],c=0;
    cin>>n;
    for(i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    c=0;
    for(i=0;i<n-2;i++) {
    	for(j=i+1;j<n-1;j++) {
    		for(k=j+1;k<n;k++) {
    			if(a[i]!=a[j] && a[j]!=a[k] && a[k]!=a[i] && a[i]+a[j]>a[k]) c++;
			}
		}
	}
    cout<<c;
}

Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.Collectors;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		String word1 = stdin.readLine();
		String word2 = stdin.readLine();
		String sorted1 = Arrays.stream(word1.split("")).sorted().collect(Collectors.joining());
		String sorted2 = Arrays.stream(word2.split("")).sorted(Comparator.reverseOrder()).collect(Collectors.joining());
		String answer = sorted2.compareTo(sorted1) > 0 ? "Yes" : "No" ;
		System.out.println(answer);
	}

}

Measured memory_bytes: 26452
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

struct tree
{
    vector<tree*> neighbors;
    long count = 0;

    void prop(tree* root)
    {
        count += root->count;
        for (auto t : neighbors)
        {
            if (t != root)
            {
                t->prop(this);
            }
        }
    }
};

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

    long n, q;
    cin >> n >> q;
    tree* ts = new tree[n];
    rep(i, n - 1)
    {
        long a, b;
        cin >> a >> b;
        ts[a - 1].neighbors.push_back(&ts[b - 1]);
        ts[b - 1].neighbors.push_back(&ts[a - 1]);
    }
    rep(i, q)
    {
        long p, x;
        cin >> p >> x;
        ts[p - 1].count += x;
    }
    for(auto t : ts[0].neighbors)
    {
        t->prop(&ts[0]);
    }
    rep(i, n)
    {
        cout << ts[i].count << " ";
    }
    cout << endl;

    return 0;
}

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

int main(){
    string s; cin>>s;
    if(s=="ABC") cout<<"ARC"<<endl;
    else cout<<"ABC"<<endl;
    return 0;
}


Measured memory_bytes: 3596
n,m,k = map(int,input().split())
tmp_a = list(map(int,input().split()))
tmp_b = list(map(int,input().split()))
a = [0]
b = [0]
for i in range(n):
    a.append(a[i]+tmp_a[i])
for i in range(m):
    b.append(b[i]+tmp_b[i])
#print(a)
#print(b)
ans = 0
j = m
for i in range(n+1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)

Measured memory_bytes: 47520
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(){
    int n, V[25] = {0}, C[25] = {0}, sum = 0;
    cin >> n;
    REP(i, n)cin >> V[i];
    REP(i, n)cin >> C[i];
    REP(i, n){
        int diff = V[i] - C[i];
        if(diff >= 0){
            sum += diff;
        }else continue;
    }
    cout << sum << endl;
    return 0;
}


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

bool sosuu(ll N){
    //vector<pair<ll,ll>> v;
    for(int i= 2; i*i <= N; i++){
        if(N % i != 0)continue;
        //v.push_back(make_pair(i,0));
        return false;
        // while(N % i == 0){
            //N /= i;
            //v.back().second++;
        //}
    }
    //if(N != 1) v.push_back(make_pair(N,1));

    return true;
}

int main(){
    ll Q;
    cin >> Q;
    vector<ll> l(Q),r(Q),memo(100010,0),memo2(100010,0),memo3(100010,0);
    for(ll i =2;i<100010;i++){
        if(sosuu(i)){
            memo[i] = 1;
        }
    }
    for(ll i =3;i<100010;i += 2){
        if(memo[i] == 1 && memo[(i+1)/2] == 1){
            memo2[i] = 1;
        }
    }
    /*
    rep(i,14){
        cout << memo2[i] <<" ";
    }
    cout << endl;
    */
    rep(i,100009){
        memo3[i+1] = memo3[i] + memo2[i];
    }
    rep(i,Q){
        cin >> l[i] >> r[i];
    }
    rep(i,Q){
        //if(l[i] < 2)l[i]=2;
        cout << memo3[r[i]+1] - memo3[l[i]] << endl;
    }

}


Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W,N;
  cin>>H>>W>>N;
vector<int>A={};
  for(int i=1;i<=N;i++){
  int a;
    cin>>a;
    for(int j=0;j<a;j++)
      A.push_back(i);
  }
  int k=0;
  vector<vector<int>>M(H,vector<int>(W));
  for(int i=0;i<H;i++){
  if(i%2==0){
  for(int j=0;j<W;j++){
  M.at(i).at(j)=A.at(k);
    k++;
  }
  }else{
  for(int j=W-1;0<=j;j--){
  M.at(i).at(j)=A.at(k);
    k++;
  }
  }
 
  }for(int i=0;i<H;i++){
  for(int j=0;j<W-1;j++)
    cout<<M.at(i).at(j)<<" ";
    cout<<M.at(i).at(W-1)<<endl;
  
  }
  
   return 0;
}

Measured memory_bytes: 384