akhauriyash/Code-Regression huggingface dataset:
from math import factorial

s = int(input())

def cmb(x, y):
 return factorial(x) // (factorial(y) * factorial(x-y))

ans = 0

for i in range(1, s//3+1):
  n = s - 2*i
  ans += cmb(n-1, i-1)

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

Measured memory_bytes: 9172
#include<iostream>
using namespace std;
int main()
{
	int x, y;
	int i, j;
	cin >> x >> y;
	for (i = 0; i <= x; i++) {
		if (i * 2 + (x - i) * 4 == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	int S;

	scanf("%d", &S);

	printf("%d:%d:%d\n", S/3600, (S % 3600)/60, ((S % 3600) % 60));

	return 0;
}


Measured memory_bytes: 2132
#include <stdio.h>

int main(void)
{
	int S,h,m,s;
	scanf("%d",&S);
	h=S/3600;
	S=S%3600;
	m=S/60;
	s=S%60;
	printf("%d:%d:%d\n",h,m,s);
	
	
	return 0;
}


Measured memory_bytes: 2120
n = int(input())
s = input()
from itertools import product

for v in product([1,0], repeat=2):
    v = list(v)
    for i in range(n-2):
        if v[i+1]:
            if s[i+1] == 'o':
                v.append(v[i])
            else:
                v.append(not v[i])
        else:
            if s[i+1] == 'o':
                v.append(not v[i])
            else:
                v.append(v[i])
    ans = [0,0]
    for i in range(-1,1):
        if v[i]:
            if s[i] == 'o':
                if v[i-1] == v[i+1]:
                    ans[i+1] = 1
                else:
                    ans[i+1] = 0
            else:
                if v[i-1] == v[i+1]:
                    ans[i+1] = 0
                else:
                    ans[i+1] = 1
        else:
            if s[i] == 'o':
                if v[i-1] == v[i+1]:
                    ans[i+1] = 0
                else:
                    ans[i+1] = 1
            else:
                if v[i-1] == v[i+1]:
                    ans[i+1] = 1
                else:
                    ans[i+1] = 0
    if ans[0] and ans[1]:
        print(''.join(['S' if x == 1 else 'W' for x in v]))
        exit()
print(-1)

Measured memory_bytes: 5044
n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for _ in range(n)]
ab = sorted(ab)

ans = 0
check=m
for i in range(n):
    if  check > ab[i][1]:
        check = check-ab[i][1]
        ans += ab[i][0]*ab[i][1]
    else:
        ans += ab[i][0]*check
        break
print(ans)

Measured memory_bytes: 22372
#include<iostream>
#include<cstdio>
const int N=105;
using namespace std;
string a,b,c;
int main() {
    int n;cin>>n>>a>>b>>c;
    int ans=0;
    for(int i=0;i<n;i++) {
        if(a[i]==b[i]&&b[i]==c[i]);
        else if(a[i]==b[i]||b[i]==c[i]||a[i]==c[i]) ans++;
        else ans+=2;
    }
    cout<<ans;
    return 0;
}


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

vector<int> primes;
bool is_prime[100010];

void calc_prime(int n){
	for(int i = 0; i <= n; ++i)
		is_prime[i] = true;
	is_prime[0] = is_prime[1] = false;
	
	for(int i = 2; i <= n; ++i){
		if(is_prime[i]){
			primes.push_back(i);
			for(int j = i * 2; j <= n; j += i)
				is_prime[j] = false;
		}
	}
}

int main() {
	calc_prime(100000);
	int n;
	while(cin >> n){
		auto it = lower_bound(primes.begin(), primes.end(), n);
		cout << *(it - 1) << " ";
		if(*it == n)
			cout << *(it + 1) << endl;
		else
			cout << *it << endl;
	}
	return 0;
}

Measured memory_bytes: 1416
#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
    using namespace std;
    #define pii pair<int,int>
    #define fir first
    #define sec second
    #define MP make_pair
    #define rep(i,x,y) for (int i=(x);i<=(y);i++)
    #define drep(i,x,y) for (int i=(x);i>=(y);i--)
    #define go(x) for (int i=head[x];i;i=edge[i].nxt)
    #define templ template<typename T>
    #define sz 1010100
    typedef long long ll;
    typedef double db;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
    templ inline void read(T& t)
    {
        t=0;char f=0,ch=getchar();double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
        t=(f?-t:t);
    }
    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
    char __sr[1<<21],__z[20];int __C=-1,__zz=0;
    inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
    inline void print(register int x)
    {
        if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
        while(__z[++__zz]=x%10+48,x/=10);
        while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
    }
    void file()
    {
        #ifdef NTFOrz
        freopen("a.in","r",stdin);
        #endif
    }
    inline void chktime()
    {
        #ifndef ONLINE_JUDGE
        cout<<(clock()-t)/1000.0<<'\n';
        #endif
    }
    #ifdef mod
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
    ll inv(ll x){return ksm(x,mod-2);}
    #else
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
    #endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n;
int A,B;

void Swap(int &x,int i,int j){if ((x>>i&1)^(x>>j&1)) x^=(1<<i)|(1<<j);}
vector<int> work(int A,int B,int n)
{
	if (n==1) return vector<int>({A,B});
	if (B==0) { vector<int>v=work(B,A,n); reverse(v.begin(),v.end()); return v; }
	if (A!=0) { vector<int>v=work(0,A^B,n); for (int &x:v) x^=A; return v; }
	int p=0;rep(i,0,n-1) if (B>>i&1) p=i;
	Swap(A,n-1,p),Swap(B,n-1,p);
	vector<int>L,R;
	rep(i,0,(1<<(n-1))-1) L.push_back(A^(i^(i>>1)));
	R=work(A^(1<<(n-2)),B^(1<<(n-1)),n-1);
	vector<int>v;for (auto x:L) v.push_back(x);for (auto x:R) v.push_back(x^(1<<(n-1)));
	for (int &x:v) Swap(x,n-1,p);
	return v;
}

int main()
{
    file();
	read(n,A,B);
	if (__builtin_popcount(A)%2==__builtin_popcount(B)%2) return puts("NO"),0;
	puts("YES");
	vector<int>v=work(A,B,n);
	for (auto x:v) printf("%d ",x);
	return 0;
}

Measured memory_bytes: 1648
function Main(input) {
  input=input.split("\n");
  var array=input[0].split(' ').map(e=>{
    return e-0;
  });
  for(var i=0;i<5;i++){
    if(array[i]===0){
      console.log(i+1);
      return;
    }
  }
}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  



  


Measured memory_bytes: 29472
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mk make_pair

template <class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

 
void solve()
{
    string x;
    cin>>x;
    if(count(x.begin(), x.end(), '7'))
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}

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

    // ll t;
    // cin >> t;

    // while (t--)
    // {
    //     solve();
    // }
    solve();
    return 0;
}

Measured memory_bytes: 3656
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    M1, D1 = map(int, readline().split())
    M2, D2 = map(int, readline().split())
    if M1 != M2:
        print('1')
    else:
        print('0')

if __name__ == '__main__':
    main()

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

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



signed main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif      

    int d,s,t;
    cin>>d>>t>>s;
    if(s*t>=d)
        cout<<"Yes";
    else
        cout<<"No";    

}

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

int main() {
    int n;
    cin >> n;
    vi a(n+1);
    rep(i, n-1) {
        int j;
        cin >> j;
        a.at(j)++;
    }
    for (int i = 1; i < n+1; i++) cout << a.at(i) << endl;
}

Measured memory_bytes: 4032
h,w,n=map(int,input().split())
sr,sc=map(int,input().split())
s=input()
t=input()
f=0
y1=sc;y2=sc;x1=sr;x2=sr
for i1 in range(n):
  if s[i1]=='R':
    y1+=1
  if y1==w+1:
    f=1
    break
  if t[i1]=='L' and y1!=1:
    y1-=1

for i2 in range(n):
  if s[i2]=='L':
    y2-=1
  if y2==0:
    f=1
    break
  if t[i2]=='R' and y2!=w:
    y2+=1

for i3 in range(n):
  if s[i3]=='U':
    x1-=1
  if x1==0:
    f=1
    break
  if t[i3]=='D' and x1!=h:
    x1+=1

for i4 in range(n):
  if s[i4]=='D':
    x2+=1
  if x2==h+1:
    f=1
    break
  if t[i4]=='U' and x2!=1:
    x2-=1

if f==0:print('YES')
else:print('NO')

Measured memory_bytes: 3888
"use strict";
function Main(input) {
    let lines = input.split("\n");
    let cols = lines.shift().split(/\s/).map((v) => v - 0);
    let N = cols[0];
    let x = [], y = [], h = [];
    for (let n = 0; n < N; n++) {
        let cols = lines.shift().split(/\s/).map((v) => v - 0);
        x.push(cols[0]);
        y.push(cols[1]);
        h.push(cols[2]);
    }

    const MAX = 100;
    for (let posY = 0; posY <= MAX; posY++) {
        for (let posX = 0; posX <= MAX; posX++) {
            let needH = -1;
            for (let i = 0; i < N; i++) {
                if (h[i] > 0) {
                    let tmp = h[i] + Math.abs(posY - y[i]) + Math.abs(posX - x[i]);
                    if (needH == -1) {
                        needH = tmp;
                    } else {
                        if (needH != tmp) {
                            needH = -2;
                            break;
                        }
                    }
                }
            }
            if (needH == -2) continue;
            for (let i = 0; i < N; i++) {
                if (h[i] == 0) {
                    let dist = Math.abs(posY - y[i]) + Math.abs(posX - x[i]);
                    if (needH > dist) {
                        needH = -2;
                        break;
                    }
                }
            }
            if (needH == -2) continue;
            console.log(posX + " " + posY + " " + needH);
            return 0;
        }
    }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    a, b = input().split()
    print(a * int(b)) if a <= b else print(b * int(a))

if __name__ == "__main__":
    main()

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

public class Main {
    public static void main (String args[]) {
        
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String line = "";
			
			while ((line = br.readLine()) != null) {
				int count = Integer.parseInt(line);
				
				int sum1 = 0;
				int sum2 = 0;
				
				if (count > 0) {
					for (int i = 0; i < count; i++) {
						line = br.readLine();
						String[] str = line.split(" ");
						
						int a = Integer.parseInt(str[0]);
						int b = Integer.parseInt(str[1]);
						
						if (a > b) {
							sum1 += a + b;
						}else if (b > a) {
							sum2 += a + b;
						}else {
							sum1 += a;
							sum2 += b;
						}						
					}
					
					System.out.println(sum1 + " " + sum2);
					
				}else {
					System.exit(0);
				}
			}
		}
		catch (Exception e) {
			e.printStackTrace();
			System.exit(0);
		}
		finally {
			System.exit(0);
		}		
    }
}

Measured memory_bytes: 37240
#include <stdio.h>

int main(void)
{
    int i;
    int h, m, s, ah, am, as;
    int ans[3] = {0};

    for (i = 0; i < 3; i++){
        scanf("%d %d %d %d %d %d", &h, &m, &s, &ah, &am, &as);
        ans[i] = ((ah * 3600) + (am * 60) + as) - ((h * 3600) + (m * 60) + s);
    }

    for (i = 0; i < 3; i++) {
        printf("%d %d %d\n", ans[i] / 3600, (ans[i] % 3600) / 60, (ans[i] % 3600) % 60);
    }

    return (0);
}

Measured memory_bytes: 596
#include <iostream>
#include <stack>

using namespace std;

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

int GCD(int a, int b)
{
	if (a == 0)
	{
		return(b);
	}
	else
	{
		return(GCD(b % a, a));
	}
}

void solve()
{
	int n;
	cin >> n;
	stack<int> stackNum;
	for (int i = 0; i < n; ++i)
	{
		int a;
		cin >> a;
		stackNum.push(a);
	}
	while (stackNum.size() != 1)
	{
		int a = stackNum.top();
		stackNum.pop();
		int b = stackNum.top();
		stackNum.pop();
		if (a > b)
		{
			swap(a, b);
		}
		stackNum.push(a * b / GCD(a, b));
	}
	cout << stackNum.top() << endl;
}

int main()
{
	solve();
	return(0);
}

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

typedef long long ll;
const ll INF = 2000000000000000;

struct node{
	ll l,r;
	int cnt;
	node *chl,*chr;
	void init(ll l_,ll r_){
		l = l_;
		r = r_;
		cnt = 0;
		chl = nullptr;
		chr = nullptr;
	}
	void mkchl(){
		chl = new node;
		chl->init(l,(l+r)/2);
	}
	void mkchr(){
		chr = new node;
		chr->init((l+r)/2,r);
	}
	void add(ll x){
		if(l <= x && x < r){
			cnt ++;
			if(l+1 == r)return;
			if(x < (l+r)/2){
				if(chl == nullptr)mkchl();
				chl->add(x);
			}
			else {
				if(chr == nullptr)mkchr();
				chr->add(x);
			}
		}
	}
	ll query(ll a,ll b){
		if(b <= l || r <= a)return 0;
		if(a <= l && r <= b)return cnt;
		ll ret = 0;
		if(chl != nullptr)ret += chl->query(a,b);
		if(chr != nullptr)ret += chr->query(a,b);
		return ret;
	}
}bit;

int main(){
	static ll n,k;
	static int a[200010];
	scanf("%lld%lld",&n,&k);
	for(int i = 0 ; i < n ; i ++){
		scanf("%d",&a[i]);
	}
	
	static int b[200010];
	vector<ll> X;
	ll sum = 0;
	X.push_back(sum);
	for(int i = 0 ; i < n ; i ++){
		sum += a[i]-k;
		X.push_back(sum);
	}
	sort(X.begin(),X.end());
	sum = 0;
	for(int i = 0 ; i < n ; i ++){
		sum += a[i]-k;
		b[i] = lower_bound(X.begin(),X.end(),sum) - X.begin();
	}
	
	bit.init(0,1<<20);
	ll ret = 0;
	bit.add(lower_bound(X.begin(),X.end(),0)-X.begin());
	for(int i = 0 ; i < n ; i ++){
		ret += bit.query(0,b[i]+1);
		bit.add(b[i]);
	}
	cout << ret << endl;
}


Measured memory_bytes: 22128
import java.util.*

fun main(args:Array<String>){
    solve()
}

fun solve(){
    val (a,b,c) = readints()
    println(if(a == b + c || a + b == c || a + c == b) "Yes" else "No")
}

fun read() = readLine()!!
fun reads() = readLine()!!.split(" ")
fun readint() = readLine()!!.toInt()
fun readints() = readLine()!!.split(" ").map{it.toInt()}
fun readlong() = readLine()!!.toLong()
fun readlongs() = readLine()!!.split(" ").map{it.toLong()}

Measured memory_bytes: 36320
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		ArrayDeque<Integer> list = new ArrayDeque<Integer>();
		int n = scan.nextInt();
		int num;

		for(int i = 0 ; i < n ; i++) {
			if(scan.hasNext()) {
				num = scan.nextInt();
				list.add(num);
			}
		}
		scan.close();

		for(int j = 0 ; j < n ; j++) {
			if(j == n - 1) {
				System.out.println(list.pollLast());
			}else {
				System.out.print(list.pollLast() + " ");
			}
		}
	}
}



Measured memory_bytes: 26388
from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)


Measured memory_bytes: 481152
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string a;std::cin>>a;
  int ans=1;
  for(int i=1;i<a.size();i++){
    ans+=a[i]!=a[i-1];
  }
  ans--;
  std::cout<<ans;
  return 0;
}


Measured memory_bytes: 3728
int main(void){
  int n,i,x;
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    x=i;
    if ( x % 3 == 0 ){
      printf(" %d",i);
    }else{
      do{
        if ( x % 10 == 3 ){
          printf(" %d",i);
          x=0;
        }
        x /= 10;
      }while( x );
    }
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 2132
#include<stdio.h>
#include<string.h>

char so[50001];

main(){
	memset(so,0,sizeof(so));
	
	int n,i,j,count;
	for(i=2;i<225;i++){
		for(j=i;j*i<=50000;j++){
			so[j*i]=1;
		}
	}
	
	while(~scanf("%d",&n)){
		if(n==0)break;
		count=0;
		for(i=2;i<(n>=25000 ? 25000:n);i++){
			if(i>n-i)break;
			if(so[i]==0 && so[n-i]==0){
				++count;
			}
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 812
#include <stdio.h>

#define HOUR    (3600) //sec
#define MINUTE  (60)   //sec
int main()
{
  int a,b;
  scanf("%d %d",&a,&b);

  if (a > b) {
	  printf("a > b\n");
  }
  else {
	  if (a < b) {
		  printf("a < b\n");
	  }
	  else {
		  printf("a == b\n");
	  }
  }
  return 0;
}

Measured memory_bytes: 580
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct ss{
	char s[11];
};

int compare_int(const void *a,const void *b){
		struct ss A=*(struct ss*)a,B=*(struct ss*)b;
		if(strcmp(A.s,B.s)>=0)return 1;
		return -1;
}

int main(){
		int n,i,j;long long k=0;
		struct ss s[100000];
		scanf("%d",&n);
		for(i=0;i<n;i++){
				scanf("%s",s[i].s);
				for(j=0;j<10;j++){
						for(k=0;k<10;k++){
								if(s[i].s[j]<s[i].s[k]){
										char a=s[i].s[j];
										s[i].s[j]=s[i].s[k];
										s[i].s[k]=a;
								}
						}
				}
		}
		qsort(s,n,sizeof(struct ss),compare_int);
		long long ans=0;k=1;
		for(i=1;i<n;i++){
				if(strcmp(s[i-1].s,s[i].s)==0)k++;
				else{
						ans+=k*(k-1)/2;
						k=1;
				}
		}
		ans+=k*(k-1)/2;
		printf("%lld\n",ans);
		return 0;
}


Measured memory_bytes: 2300
s = input()
t = input()
data1 = [[0] for i in range(2)]
data2 = [[0] for i in range(2)]
for i in range(len(s)):
    if s[i] in data1[0]:
        if not data1[1][data1[0].index(s[i])] == t[i]:
            print("No")
            exit()
    else:
        data1[0].append(s[i])
        data1[1].append(t[i])

for i in range(len(s)):
    if t[i] in data2[0]:
        if not data2[1][data2[0].index(t[i])] == s[i]:
            print("No")
            exit()
    else:
        data2[1].append(s[i])
        data2[0].append(t[i])
print("Yes")


Measured memory_bytes: 3632
#include <chrono>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

/**
 * @param N 素因数分解する整数
 * @param result N = 2^3 * 3^2の場合、{{2, 3}, {3, 2}}のような形式のvectorが生成される
*/
void prime_factorize(ll N, vector<pair<ll, ll>>& result) {
  for (ll a = 2; a * a <= N; ++a) {
    if (N % a != 0) continue;
    ll ex = 0;  // 指数

    // 割れる限り割り続ける
    while (N % a == 0) {
      ++ex;
      N /= a;
    }

    result.emplace_back(pair<ll, ll>{a, ex});
  }

  // 最後に残った数
  if (N != 1) result.emplace_back(pair<ll, ll>{N, 1});
}

int main() {
  ll N;
  cin >> N;
  vector<pair<ll, ll>> result;

  prime_factorize(N, result);

  cout << N << ":";
  for (auto v : result) {
    for (ll i = 0; i < v.second; ++i) {
      cout << " " << v.first;
    }
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 3116
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    N, M, K = map(int, input().split())
    dame = [set() for i in range(N)]
    uf = UnionFind(N)

    for i in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        
        dame[a].add(b)
        dame[b].add(a)
        uf.unite(a,b)
    
    for i in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if not uf.isSame(c, d):
            continue
        dame[c].add(d)
        dame[d].add(c)
    
    ans = []
    for i in range(N):
        mem = uf.size(i) - 1
        mem -= len(dame[i])
        ans.append(mem)
    
    print(*ans, sep=' ')

if __name__ == '__main__':
    solve()

Measured memory_bytes: 122860
// link:
// [prajwal1721]
// g++ -Wall -Wextra -Wshadow filename.cpp
// ./a.out >input <output
/*comments:
*/



#include<bits/stdc++.h>
using namespace std; 
#define mod 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b))
#define bits(x) __builtin_popcountll(x)
#define vi              vector<int>
#define vl              vector<ll>
#define all(v)          v.begin(),v.end()
#define UNIQUE(X)       (X).erase(unique(all(X)),(X).end())



typedef long long int ll;
void solve()
{
    string s,t;cin>>s>>t;
    ll n=s.length(),m=t.length();
    ll dp[m+2][n+2]={0};
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(i==0 || j==0 ){dp[i][j]=0;continue;}
            dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            if(t[i-1]==s[j-1])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            // cout<<dp[i][j]<<" ";
        }
        // cout<<"\n";
    }
    string ans="";
    ll i=m,j=n;
    while(i && j)
    {
        if(t[i-1]==s[j-1]){ans=s[j-1]+ans;i--;j--;}
        else if(dp[i-1][j]>dp[i][j-1])i--;
        else j--;
    }
    cout<<ans<<"\n";
    // cout<<dp[m][n]<<"\n";

}


int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // ll t;cin>>t;
    // cout<<t<<"Hi test complete\n";
    // while(t--)
        {
            solve();
        }


    return 0;
}

Measured memory_bytes: 74028
A,B = map(int,input().split())#A=白(.)，B=黒(#)
K = 50
#でっかいグリッドを用意
grid = [['.' for i in range(2*K)] for j in range(2*K)]
#上半分を白，下半分を黒にする
for i in range(K,2*K):
    for j in range(2*K):
        grid[i][j]='#'
bcnt=0
wcnt=0
#白ベースの箇所に黒を，黒ベースの箇所に白を一個ずつ置いていく
for i in range(1,K,2):
    for j in range(0,2*K,2):
        if bcnt < B-1:
            grid[i][j]='#'
            bcnt += 1
for i in range(K+1,2*K,2):
    for j in range(0,2*K,2):
        if wcnt < A-1:
            grid[i][j]='.'
            wcnt +=1

print(2*K,2*K)
for i in range(2*K):
    row_grid=''.join(grid[i])
    print(row_grid)


Measured memory_bytes: 3188
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)


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

int main(){
  vector<int> v(5);
  for(int i=0;i<5;i++) cin >> v[i];
  
  for(int i=0;i<5;i++) {
    if(v[i] == 0)
    {
      cout<<i+1<<endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 3628
N, K = map(int, input().split())
p = list(map(int, input().split()))
q = []
for pp in p:
  q += [(pp+1)/2]
ans = 0
tem = sum(q[:K])
for i in range(K,N+1):
  if i != K: tem += q[i-1] - q[i-K-1]
  ans = max(ans, tem)
print(ans)

Measured memory_bytes: 24812
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main (){
    ll a,b,c;
    cin>>a>>b>>c;
    if(a+b+1>=c)cout<<b+c<<endl;
    else cout<<(b+b+a+1)<<endl;

}


/*

*/


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
 
int main() {
 
  int a,b,c,d;
  cin >> a;
  cin >> b;
  cin >>c;
  cin >>d;
  cout << a*b -d*a-b*c +c*d <<endl;
  
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>

using namespace std;

const int Z = 1e9+7;

int main() {
    int n, m;
    cin >> n >> m;
    int s[n+1], t[m+1];
    s[0] = t[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> t[i];
    }

    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    for (int j = 0; j <= m; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) {
                dp[i][j] = dp[i-1][j-1];
            }
        }
        for (int j = 1; j <= m; j++) {
            dp[i][j] = (dp[i][j] + dp[i][j-1]) % Z;
        }
        for (int j = 0; j <= m; j++) {
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % Z;
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}


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

int main(){
  string s, t; cin >> s >> t;
  int sL = (int)(s.length());
  int tL = (int)(t.length());
  
  int dp[3001][3001];
  for (int i=0; i<=sL; i++){
    for (int j=0; j<=tL; j++) dp[i][j] = 0;
  }

  bool flag = false;
  for (int i=0; i<sL; i++){
    if (flag) dp[i][0] = 1;
    else {
      if (s[i] == t[0]){
        flag = true;
        dp[i][0] = 1;
      }
    }
  }

  flag = false;
  for (int i=0; i<tL; i++){
    if (flag) dp[0][i] = 1;
    else {
      if (s[0] == t[i]){
        flag = true;
        dp[0][i] = 1;
      }
    }
  }

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

  int i = sL-1;
  int j = tL-1;
  if (dp[i][j] == 0){
    cout << "" << endl;
    return 0;
  }

  vector<char> ans(dp[i][j], '\0');
  while (ans[0] == '\0'){
    if (i>0 && dp[i][j] == dp[i-1][j]) i--;
    else if (j>0 && dp[i][j] == dp[i][j-1]) j--;
    else if (i>0 && j>0 && dp[i][j] > dp[i-1][j-1]){
      ans[dp[i][j]-1] = s[i];
      i--;
      j--;
    }
    else if (i == 0 && j == 0 && dp[i][j] == 1){
      ans[dp[i][j]-1] = s[i];
      break;
    }
    else if (i == 0 && dp[i][j] > dp[i][j-1]){
      ans[dp[i][j]-1] = s[i];
      break;
    }
    else if (j == 0 && dp[i][j] > dp[i-1][j]){
      ans[dp[i][j]-1] = s[i];
      break;
    }
  }

  for (int k=0; k<dp[sL-1][tL-1]; k++) cout << ans[k];
  cout << endl;
  return 0;
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
#define Lim 9999991
//#define Jmp 1000003

int dic[Lim];

int toint(string s) {
    int ret = 0;
    for (int i = 0; i < s.size(); ++i) {
        ret *= 5;
        switch (s[i]) {
            case 'A':
                ret += 1;
                break;
            case 'T':
                ret += 2;
                break;
            case 'G':
                ret += 3;
                break;
            case 'C':
                ret += 4;
                break;
        }
    }
    return ret;
}

void push(string s) {
    int a = toint(s);
    int jmp = a % (Lim - 1) + 1;
    int i = a % Lim;
    while (true) {
        if (!dic[i]) {
            dic[i] = a;
            return;
        }
        i = (i + jmp) % Lim;
    }
}

int find(string s) {
    int a = toint(s);
    int jmp = a % (Lim - 1) + 1;
    int i = a % Lim;
    while (true) {
        if (!dic[i]) {
            return 0;
        }
        if (dic[i] == a) {
            return 1;
        }
        i = (i + jmp) % Lim;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s, t;
        cin >> s >> t;
        if (s == "insert") {
            push(t);
        }
        else {
            if (find(t)) {
                printf("yes\n");
            }
            else {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 32928
#include <iostream>
#include <queue>
#define llint long long
#define rep(x, s, t) for(llint x = s; i <= t; x++)

using namespace std;

llint n, p, q;
llint c[500005];
priority_queue<llint, vector<llint>, greater<llint> > Q;

int main(void)
{
  cin >> n >> p >> q;
  rep(i, 1, n) cin >> c[i];

  llint sum = 0;
  rep(i, 1, n){
    Q.push(c[i] + i*p);
    sum += c[i];
  }

  llint ans = -1e18, s = 0;
  rep(i, 0, n){
    llint tmp = (i*(q-1) + i*(i+1)) * p;
    tmp += sum - s;
    ans = max(ans, tmp);
    if(Q.size()){
      s += Q.top();
      Q.pop();
    }
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 10972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

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

vector<ll> tfact(1e7+1);
void fact(ll n) {
  for(ll i=0;i<=n;i++) {
    if(i==0) {
      tfact[i]=1;
    }
    else {
      tfact[i]=tfact[i-1]*i%mod;
    }
  }
}

ll comb(ll n, ll k) {
  return tfact.at(n)*mpow(tfact.at(k),mod-2)%mod*mpow(tfact.at(n-k),mod-2)%mod;
}

int main() {
  ll n;
  cin >> n;
  n++;
  vec a(n);
  fact(n+10);
  for(ll i=0;i<n;i++) cin >> a[i];
  ll f,s;
  set<ll> cnt;
  for(ll i=0;i<n;i++) {
    if(cnt.count(a[i])) {
      s=i;
      for(ll j=0;j<n;j++) {
        if(a[s]==a[j]) {
          f=j;
          break;
        }
      }
      break;
    }
    cnt.insert(a[i]);
  }
  ll res=f+n-s-1;
  for(ll i=1;i<=n;i++) {
    ll ans=comb(n,i);
    if(res>=i-1) ans=(ans-comb(res,i-1)+mod)%mod;
    cout << ans << endl;
  }
}

Measured memory_bytes: 84864
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
using namespace std;

int main()
{
    int N;
    scanf("%d", &N);
    vector<int> L(2*N);
    REP(i, 2*N) scanf("%d", &L[i]);
    sort(L.begin(), L.end());
    int ans = 0;
    REP(i, N){
        ans += L[2*i];
    }
    printf("%d\n", ans);
}

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

int main() {
  int n,m;
  while(cin >> n >> m && n) {
    int M=1<<29,x=1<<29,y;
    for(int w=1; w<=150; w++) {
      for(int h=1; h<w; h++) {
        if(h*h+w*w==n*n+m*m) {
	  if(n<h && h<x) {
	    M=h*h+w*w;
	    x=h,y=w;
	  }
	} else if(h*h+w*w>n*n+m*m) {
          if(h*h+w*w<M) {
            M=h*h+w*w;
            x=h,y=w;
          } else if(h*h+w*w==M && h<x) x=h,y=w;
        }
      }
    }
    cout << x << " " << y << endl;
  }
  return 0;
}


Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
 
using namespace std;

int A[2001];

void solve()
{	int n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>A[i];
	}
	ll ans=0;
	sort(A,A+n);
	for(int i=0; i<n-1; i++){
		for(int j=i+1; j<n; j++){
			ll a = lower_bound(A+j+1,A+n, A[i]+A[j])-A-j-1;
			ans += a;
			//cout<<A[i]+A[j]<<" "<<a<<"\n";
		}
	}
	cout<<ans;
}


int main()
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout<<fixed<<setprecision(12);
	int t =1; //cin>>t;
	for(int i=1; i<=t; i++){
		solve();
		cout<<"\n";
	}
	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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

ll mod = 1e9+7;

vector<ll> inv,fact,invfact;
void mod_build(int n){
	fact.resize(n+1);
	inv.resize(n+1);
	invfact.resize(n+1);
	fact[0]=inv[0]=invfact[0] = 1;
	inv[1] = 1;
	for(int i=0;i<n;i++){
		fact[i+1] = fact[i]*(i+1)%mod;
		if(i > 0) inv[i+1] = mod - inv[mod%(i+1)]*(mod/(i+1))%mod;
		invfact[i+1] = invfact[i]*inv[i+1]%mod;
	}
}
ll perm(int n,int k){
	if(n<0||k<0||k>n) return 0;
	return fact[n]*invfact[n-k]%mod;
}
ll comb(int n,int k){
	if(n<0||k<0||k>n) return 0;
	return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;
}
ll powmod(ll n, ll k){
	k %= mod-1;
	if(k<0) k+= mod-1;
	ll ret=1;
	while(k){
		if(k&1) ret = ret*n % mod;
		n = n*n%mod;
		k >>= 1;
	}
	return ret;
}

int main(){
	mod_build(202020);
	ll n,m,k;
	cin >> n >> m >> k;
	ll res1 = (m*m*m-m)%mod * n %mod * n %mod * inv[6] %mod;
	ll res2 = (n*n*n-n)%mod * m %mod * m %mod * inv[6] %mod;
	ll ans = (res1+res2)*powmod(comb(m*n,2),mod-2)%mod;
	ans*=comb(m*n,k)*comb(k,2)%mod;

	cout << ans%mod << endl;

	return 0;
}

Measured memory_bytes: 4992
/*
 #                                               |
 #   _` |  __ \    _` |   __|   _ \   __ \    _` |   _` |
 #  (   |  |   |  (   |  (     (   |  |   |  (   |  (   |
 # \__,_| _|  _| \__,_| \___| \___/  _|  _| \__,_| \__,_|
 */
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define ZERO_IQ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x, y) cerr << (#x) << " " << (#y) <<" is " << (x) <<" "<< (y) << endl
#define debug2(x, y, z) cerr << (#x) << " " <<(#y) << " " << (#z) << " is " << (x) << " " << (y) << " " << (z) << endl
#define endl '\n'

ll const N = 1e5 + 5;

struct compare {
   bool operator ()(const pair<ll, ll> &a, const pair<ll, ll> &b) {
      if (a.second == b.second) {
         return a.first < b.first;
      }
      return a.second < b.second;
   }
};

int main() {
   ZERO_IQ
   long long n, m;
   cin >> n >> m;
   vector<pair<long long, long long>> input;
   long long summ = 0;
   for (int i = 0; i < n; ++i) {
      long long q, qq;
      cin >> q >> qq;
      input.push_back( { q, qq });
      summ += qq;
   }
   vector<vector<long long>> dp(n, vector<long long>(summ + 1, 1e18));
   long long maxx = 0;
   for (int var = 0; var < n; ++var) {
      dp[var][0] = 0;
   }
   for (int i = 1; i <= summ; ++i) {
      for (int j = 0; j < n; ++j) {
         if (!j) {
            if (i == input[j].second)
               dp[j][i] = input[j].first;
         } else if (input[j].second > i) {
            dp[j][i] = min(dp[j - 1][i], dp[j][i]);
         } else {
            dp[j][i] = min(dp[j - 1][i],
               dp[j - 1][i - input[j].second] + input[j].first);
         }
      }
   }
   for (int i = 0; i <= summ; i++) {
      if (dp[n - 1][i] <= m) {
         maxx = i;
      }
   }
   cout << maxx << endl;
   return 0;
}


Measured memory_bytes: 79488
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin >> n;
	cout << n/3 << endl;
	return 0;
}

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

#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>

using namespace std;

const int N = (int) 2e5 + 10;
const int M = (int) 1e6 + 10;
const int K = (int) 500 + 10;
const int INF = (int) 1e9 + 7;
const int mod = (int) 1e9 + 7;
const ld EPS = (ld) 1e-9;
const ll LINF = (ll) 1e18;

int n;

struct node {
	int id, cnt0, cnt1;

	bool operator < (const node &t) const {
		return cnt0 * 1ll * t.cnt1 < t.cnt0 * 1ll * cnt1; 
	}
};

priority_queue<node> q;
node a[N];
int p[N], c[N];

int get(int x) {
	return c[x] == x ? x : c[x] = get(c[x]);
}

bool u[N];

int main() {
	#ifdef sony
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	srand(time(0));
	cin >> n;
	for (int i = 2; i <= n; i++) {
		cin >> p[i];
	}
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		a[i].id = i;
		if (x) 
			a[i].cnt0 = 0, a[i].cnt1 = 1;
		else 
			a[i].cnt0 = 1, a[i].cnt1 = 0;
		if (i > 1)
			q.push(a[i]);
		c[i] = i;
	}
	ll ans = 0;
	while (!q.empty()) {
		node top = q.top();
		q.pop();
		if (u[top.id]) continue;
		u[top.id] = 1;
		int up = get(p[top.id]); 
		ans += a[up].cnt1 * 1ll * a[top.id].cnt0;
		a[up].cnt0 += a[top.id].cnt0;
		a[up].cnt1 += a[top.id].cnt1;
		c[top.id] = up;
		if (up > 1)
			q.push(a[up]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 8564
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
const ll inf = 1e18;
const int nax = 2e6 + 7;
ll mod;
using namespace std;
ll exp(ll a , ll b){
	if(b == 0)	return 1;
	int x = b % 2 == 0 ?   ((exp(a , b/2)%mod)*(exp(a , b / 2)%mod))%mod :  (a%mod*exp(a , b - 1) % mod)%mod;
	return x;
}
int n , m;
int main(int argc,char ** argv){
	dhoom;
	int n;
	cin >> n;
	int a[n];
	int ans = 0;
	for(int i = 0 ; i < n ;i++){
		cin >> a[i];
		ans = __gcd(ans , a[i]);
	}
	cout << ans << endl;
	return 0;
	
}


Measured memory_bytes: 640
#include<stdio.h>
main()
{
    char a[999];
    int b[999],c[999];
    int n,h,j=0,i;
    scanf("%s",a);
    n=strlen(a);
    for(i=0;i<n;i++)
    {
        b[i]=(int)(a[i]);
        c[b[i]]++;
        if(c[b[i]]>1)
        {
            printf("no\n");
            j=1;
            break;
        }



    }
    if(j==0)
        printf("yes\n");

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
string str[2];
int n,ima;
 
 
int stoi(int &i){
  int res=0;
  while('0'<=str[ima][i]&&str[ima][i]<='9')res=res*10+str[ima][i]-'0',i++;
  return res;
}
 
 
int main(){
  while(1){
 
    cin>>str[1]>>n;
    if(str[1]=="0"&&n==0)break;
    str[0].clear();
    for(int i=0;i<str[1].size();i++) {
      if(str[1][i]=='('&&str[1][i+2]==')') str[0]+=str[1][i+1],i+=2;
      else str[0]+=str[1][i];
    }
    str[1].clear();    
 
    ima=0;
    int f=1;
    int flg=1;
    while(f){
      f=0;
      str[!ima].clear();
      for(int i=0;i<(int)str[ima].size();i++){
    if(!('0'<=str[ima][i]&&str[ima][i]<='9')) str[!ima]+=str[ima][i];
    else {
      f=1;
      int num=stoi(i);
      string pls;
      if(str[ima][i]!='(') pls+=str[ima][i];
      else {
        int c=1;
        while(c){
          i++;
          if(str[ima][i]=='(')c++;
          if(str[ima][i]==')')c--;
          if(c) pls+=str[ima][i];
        }
      }
      while(num--&&(int)str[!ima].size()<=n+1) str[!ima]+=pls;
    }
      }
       
      ima=!ima;
    }
    //cout <<str[ima]<<endl;
    if((int)str[ima].size()<=n&&flg) cout <<0<<endl;
    else cout << str[ima][n]<<endl;
  }
  return 0;
}

Measured memory_bytes: 4832
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		
		long ans = 1;
		for (int i = 1; i <= N; i++) {
			ans = ans * i % 1000000007;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define ll long long
int main()
{
    ll t,n,i,j,k,l,m,a;
    double b,c,d;
    cin>>n>>t>>a;
    d=INT_MAX;
    for(i=0;i<n;i++)
    {
        cin>>k;
        b=k*0.006;
        c=t-b;
        if(abs(a-c)<d)
        {
            d=abs(a-c);
            j=i;
        }
    }
    cout<<j+1<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
 
int main(){
  int n, ans[27], a[27], i, j, k;
  char c;
  string s;
  cin >> n;
  for(i = 0; i < 27; i++){
      ans[i] = 100;
  }
  for(i = 0; i < n; i++){
    cin >> s;
    for(j = 0; j < 27; j++){
      a[j] = 0;
    }
    for(j = 0; j < s.length(); j++){
      for(c = 'a', k = 0; c <= 'z'; c++, k++){
        if(c == s[j]) a[k]++;
      }
    }
    for(j = 0; j < 27; j++){
      ans[j] = (a[j] > ans[j]) ? ans[j] : a[j];
    }
  }
  for(i = 0, c ='a'; c <= 'z'; c++, i++){
    for(j = 0; j < ans[i]; j++) cout << c;
  }
  cout << endl;
}

Measured memory_bytes: 256
import sys
while True:
    n=int(input())
    if n==0:
        sys.exit()

    a=[0]
    for i in range(n):
        a.append(int(input())+a[-1])

    maximum=0
    for i in range(n+1):
        for j in range(i):
            maximum=max(maximum,a[i]-a[j])



    if maximum==0:
        b=[a[i+1]-a[i] for i in range(n)]
        maximum=max(b)

    print(maximum)
            

Measured memory_bytes: 7716
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      // スペース区切りの整数の入力
      string s = Console.ReadLine();
      string[] ss = Console.ReadLine().Split(' ');
      List<int> ns = new List<int>();
      for(int i = 0; i < ss.Length; i++)
        ns.Add(int.Parse(ss[i]));
      int c = 0;
      NewMethod(ns, ref c);
      Console.WriteLine(c);
    }

    private static void NewMethod(List<int> ns, ref int c)
    {
      while(true)
      {
        for(int i = 0; i < ns.Count; i++)
        {
          if(ns[i] % 2 == 1)
            return;
          ns[i] /= 2;
        }
        c++;
      }
    }
  }
}

Measured memory_bytes: 27972
n=int(input())
d,x=[int(u) for u in input().split()]
a=[]
for i in range(n):
  a.append(int(input()))
#print(n,d,x,a)#
for i in range(n):
  m =  (d+a[i]-1)//a[i]
  #print(m)#
  x += m
print(x)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, int> PL;
constexpr ll INF = (1LL << 60);

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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  int si, sj, ti, tj;
  cin >> si >> sj >> ti >> tj;
  si--; sj--; ti--; tj--;
  vector<string> g(h);
  rep(i,h) cin >> g[i];

  auto toid = [&](int i, int j, int v) {
    return (i * w + j) * 4 + v;
  };
  vector<ll> dist(h * w * 4, INF);
  priority_queue<PL, vector<PL>, greater<PL>> pq;
  auto push = [&](int i, int j, int v, ll x) {
    int id = toid(i, j, v);
    if (dist[id] <= x) return ;
    dist[id] = x;
    pq.emplace(x, id);
  };

  auto calc = [&] (ll x) {
    return (x + k - 1) / k * k;
  };

  rep(v, 4) push(si, sj, v, 0);
  
  while (!pq.empty()) {
    auto p = pq.top(); pq.pop();
    ll now = p.first;
    int id = p.second;
    if (dist[id] != now) continue;
    int i = id/w/4;
    int j = id/4%w;
    int v = id%4;
    rep(nv, 4) push(i, j, nv, calc(now));
    int ni = i + dx[v], nj = j + dy[v];
    if (ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
    if (g[ni][nj] == '@') continue;
    push(ni, nj, v, now + 1);
  }

  ll res = INF;
  rep(v, 4) res = min(res, dist[toid(ti, tj, v)]);
  cout << (res == INF ? -1 : calc(res) / k) << endl;

  return 0;
} 

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

int64_t n,A,B,a[100005];

bool Check(int64_t x)
{
    for(int i=1;i<=n;i++)
        a[i]-=x*B;
    int64_t Count=0;
    for(int i=1;i<=n;i++)
        if(a[i]>0)
            Count+=a[i]/A+(a[i]%A>0);
    for(int i=1;i<=n;i++)
        a[i]+=x*B;
    return Count<=x;
}

void Binary()
{
    int64_t res,l=1,r=1e9;
    while(l<=r)
    {
        int64_t mid=(l+r)/2;
        if(Check(mid)==true)
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<res;
}

int main()
{
    cin>>n>>A>>B;
    A-=B;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    Binary();
}


Measured memory_bytes: 1024