akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ass 1e18
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define debug(x) cout << #x << ": " << x << endl;
#define debug2(x,y) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<< endl;
#define debug3(x,y,z) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<<" "<<#z<<" : "<<z<< endl;
using namespace std;
typedef long long int ll;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
string s1,s2;
ll a,b,dp[3005][3005],i,j;
vector<char>v;

void dfs(ll x,ll y)
{
	if(x==0||y==0)
		return ;
	if(dp[x][y]==max(dp[x][y-1],dp[x-1][y]))
	{
		if(dp[x-1][y]>dp[x][y-1])
			dfs(x-1,y);
		else
			dfs(x,y-1);
	}
	else
	{
		v.pb(s1[x-1]);
		dfs(x-1,y-1);
	}
}

int main()
{
	cin>>s1>>s2;
	a=s1.length();
	b=s2.length();
	for(i=1;i<=a;i++)
	{
		for(j=1;j<=b;j++)
		{
			if(s1[i-1]==s2[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	dfs(a,b);
	reverse(v.begin(),v.end());
	for(i=0;i<v.size();i++)
		cout<<v[i];
	return 0;
}

Measured memory_bytes: 70656
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
B = []
Vector = [0]*N
j = 0
 
for i in range (0,K):
	if Vector[A[j]-1] == 1:
		Value = B.index(A[j])
		C = B[B.index(A[j])::]
		break
	else:
		B.append(A[j])
		Vector[A[j]-1] = 1
		j = A[j]-1

if A[0] ==1:
	print(1)
elif len(B) == K:
	print(B[-1])
else:
	print(C[(K-Value-1)%len(C)])

Measured memory_bytes: 32244
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000006

struct info
{
    string s;
    int val;
};

bool less_than_equal(info a,info b)
{
    if(a.val <= b.val) return true;
    return false;
}

bool greater_than(info a,info b)
{
    if(a.val > b.val) return true;
    return false;
}

void Sort(info *arr,int L,int M,int R)
{
    int s1 = M-L+1;
    int s2 = R-M;

    info v1[s1],v2[s2];

    for(int i=0;i<s1;i++)
    {
        v1[i] = arr[L+i];
    }
    for(int i=0;i<s2;i++)
    {
        v2[i] = arr[M+1+i];
    }
    int i,j,k;
    i = j = 0;
    k = L;

    while(i<(s1) && j<(s2))
    {
        if(less_than_equal(v1[i],v2[j]))
        {
            arr[k++] = v1[i];
            i++;
        }
        else
        {
            arr[k++] = v2[j];
            j++;
        }
    }
    while(i<s1)
    {
        arr[k++] = v1[i++];
    }
    while(j<s2)
    {
        arr[k++] = v2[j++];
    }
}

void MergeSort(info *arr,int L,int R)
{
    if(L<R)
    {
        int M = L+(R-L)/2;
        MergeSort(arr,L,M);
        MergeSort(arr,M+1,R);
        Sort(arr,L,M,R);
    }
}

void some_stable_sort(info *arr,int n)
{
    MergeSort(arr,0,n-1);
}

int Partition(info *A,int p,int r)
{
    info x = A[r];
    int i = p - 1;
    for(int j = p;j<r;j++)
    {
        if(less_than_equal(A[j],x))
        {
            i = i + 1;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i + 1;
}

void QuickSort(info *A,int p,int r)
{
    if(p<r)
    {
        int q = Partition(A,p,r);
        QuickSort(A,p,q-1);
        QuickSort(A,q+1,r);
    }
}

info arr1[MAX];
info arr2[MAX];

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n; i++)
    {
        cin >> arr1[i].s >> arr1[i].val;
        arr2[i] = arr1[i];
    }
    some_stable_sort(arr1,n);
    QuickSort(arr2,0,n-1);

    bool isStable = true;

    for(int i = 0 ; i < n ; i++)
    {
        if(arr1[i].s != arr2[i].s) isStable = false;
    }
    if(isStable) puts("Stable");
    else puts("Not stable");

    for(int i = 0 ; i < n ; i++)
    {
        cout << arr2[i].s << " " << arr2[i].val << endl;
    }
    return 0;
}


Measured memory_bytes: 40568
package main

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

func main() {

	scanner := bufio.NewScanner(os.Stdin)
	var D, G int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d %d", &D, &G)

	ps := make([]int, D)
	cs := make([]int, D)
	for i := 0; i < D; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d %d", &ps[i], &cs[i])
	}

	ans := math.MaxInt64
	for index := uint(0); index < 1<<uint(D); index++ {
		targets := make(map[int]struct{})
		for shift := uint(0); shift < uint(D); shift++ {
			if ((index >> shift) & 1) == 1 {
				targets[int(shift)] = struct{}{}
			}
		}

		count, cost := 0, 0
		// get bonus
		for i, _ := range targets {
			cost = cost + ps[i]*100*(i+1) + cs[i]
			count = count + ps[i]
		}
		if cost < G {
		B: // without bonus
			for i := D - 1; i >= 0; i-- {
				if _, e := targets[i]; e {
					continue
				}
				for j := 0; j < ps[i]-1; j++ {
					cost = cost + 100*(i+1)
					count++
					if cost >= G {
						break B
					}
				}
			}
		}

		if cost >= G {
			ans = min(ans, count)
		}
	}
	fmt.Println(ans)

}

func min(ns ...int) int {
	ret := math.MaxInt64
	for _, n := range ns {
		if n < ret {
			ret = n
		}
	}
	return ret
}


Measured memory_bytes: 640
program tests
  implicit none
  integer :: n, d, i
  integer(8) :: x, b(100000,4) = 0_8, s(0:100000) = 0_8, t = 0_8, ans, r
  read(*,*) n, x
  do i = 1, n
    read(*,*) b(i,1:3)
    b(i,4) = b(i,1)*b(i,2)+(x-b(i,1))*b(i,3)
  end do
  call quick_sort(b(1:n,:),4)
  do i = 1, n
    s(i) = s(i-1)+b(i,4)
    t = t+b(i,1)*b(i,2)
  end do
  d = bisearch(n,s(0:n),t)
  if (d >= 0) then
    write(*,'(i0)') x*int(d,8)
    stop
  end if
  d = not(d)
  ans = x*int(n,8)
  do i = 1, d
    r = t-(s(d)-b(i,4))
    if (r <= 0_8) then
      ans = min(ans,x*int(d-1,8))
    else if (r <= b(i,1)*b(i,2)) then
      ans = min(ans,x*int(d-1,8)+(r+b(i,2)-1_8)/b(i,2))
    else
      r = r-b(i,1)*b(i,2)
      ans = min(ans,x*int(d-1,8)+b(i,1)+(r+b(i,3)-1_8)/b(i,3))
    end if
  end do
  do i = d+1, n
    r = t-s(d-1)
    if (r <= b(i,1)*b(i,2)) then
      ans = min(ans,x*int(d-1,8)+(r+b(i,2)-1_8)/b(i,2))
    else
      r = r-b(i,1)*b(i,2)
      ans = min(ans,x*int(d-1,8)+b(i,1)+(r+b(i,3)-1_8)/b(i,3))
    end if
  end do
  write(*,'(i0)') ans
  stop
contains
  function bisearch(n,a,x) result(r)
    implicit none
    integer, intent(in) :: n
    integer(8), intent(in) :: a(0:n), x
    integer :: l, r, m
    r = not(n+1)
    if (x > a(n)) return
    r = n
    l = -1
    do while (r-l > 1)
      m = (l+r)/2
      if (x <= a(m)) then
        r = m
      else
        l = m
      end if
    end do
    if (a(r) /= x) r = not(r)
    return
  end function bisearch
  recursive subroutine quick_sort(a,i)
    implicit none
    integer(8), intent(inout) :: a(:,:)
    integer, intent(in) :: i
    integer(8) :: p, c(size(a(1,:)))
    integer :: n, l, r, m
    n = size(a(:,1))
    l = 1
    r = n
    m = (l+r)/2
    p = a(l,i)+a(m,i)+a(r,i)-max(a(l,i),a(m,i),a(r,i))-min(a(l,i),a(m,i),a(r,i))
    do
      do while (a(l,i) > p)
        l = l+1
      end do
      do while (a(r,i) < p)
        r = r-1
      end do
      if (l >= r) exit
      c = a(l,:)
      a(l,:) = a(r,:)
      a(r,:) = c
      l = l+1
      r = r-1
    end do
    if (l > 2) call quick_sort(a(1:l-1,:),i)
    if (n > r+1) call quick_sort(a(r+1:n,:),i)
    return
  end subroutine quick_sort
end program tests

Measured memory_bytes: 4096
n, m = map(int, input().split())
matrixA = [[0] * (m) for i in range(n)]
matrixB = [[0] for i in range(m)]
matrix = [[0] for i in range(n)]

for i in range(0, n):
    listnum = input().split()
    for j in range (0, m):
        matrixA[i][j] = listnum[j]

for i in range(0,m):
    matrixB[i][0] = input()

for i in range(0,n):
    s = 0
    for j in range(0,m):
        s = s+int(matrixA[i][j])*int(matrixB[j][0])
        matrix[i][0] = str(s)

for i in range(0, n):
    print(" ".join(matrix[i]))


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vl v(n);
	REP(i, n)cin >> v[i];
	vl a(n + 1);
	a[0] = 0;
	REP(i, n)a[i + 1] = a[i] + v[i];
	vl s;
	REP(i, n) {
		FOR(j, i, n) {
			s.push_back(a[j + 1] - a[i]);
		}
	}
	ll ans = 0;
	for (int i = 40; i >= 0; --i) {
		int cnt = 0;
		REP(j,s.size()){
			if (s[j] & (1ll << i))cnt++;
		}
		
		if (cnt >= k) {
			vl tmp;
			REP(j, s.size()) {
				if (s[j] & (1ll << i))tmp.push_back(s[j]);
			}
			ans |= (1ll << i);
			s = tmp;
		}
	}
	cout << ans << endl;

}


Measured memory_bytes: 6384
from heapq import heappop, heappush
from collections import defaultdict

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

pq = []
heappush(pq, (-(A[0] + B[0] + C[0]), 0, 0, 0))
visited = defaultdict(bool)
visited[(0, 0, 0)] = True

ans = []
for _ in range(K):
    p, i, j, k = heappop(pq)
    ans.append(-p)

    if (i + 1 < X) and (not visited[(i + 1, j, k)]):
        visited[(i + 1, j, k)] = True
        heappush(pq, (-(A[i + 1] + B[j] + C[k]), i + 1, j, k))
    if (j + 1 < Y) and (not visited[(i, j + 1, k)]):
        visited[(i, j + 1, k)] = True
        heappush(pq, (-(A[i] + B[j + 1] + C[k]), i, j + 1, k))
    if (k + 1 < Z) and (not visited[(i, j, k + 1)]):
        visited[(i, j, k + 1)] = True
        heappush(pq, (-(A[i] + B[j] + C[k + 1]), i, j, k + 1))
        
print(*sorted(ans, reverse=True), sep='\n')


Measured memory_bytes: 57308
import std.stdio, std.string, std.conv;

void main()
{
	auto n = readln.chomp;
	if((n[0] == n[1] && n[1] == n[2])||(n[1] == n[2] && n[2] == n[3])){
		writeln("Yes");
	} else {
		writeln("No");
	}
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
int main(){
  ll n,m;cin>>n>>m;
  vl a(m),b(m);
  rep(i,m)cin>>a[i]>>b[i];
  vector<ll>start;
  vector<ll>finish;
  rep(i,m){
    if(a[i]==1){
      start.push_back(b[i]);
    }
    if(b[i]==n)finish.push_back(a[i]);
  }
  bool ans=false;
  sort(finish.begin(),finish.end());
  rep(i,start.size()){
    if(std::binary_search(finish.begin(),finish.end(),start[i]))ans=true;
  }
  if(ans)cout<<"POSSIBLE"<<endl;
  else cout<<"IMPOSSIBLE"<<endl;
}

Measured memory_bytes: 5084
def main():
    n = int(input())
    
    graph = [[0 for _ in range(n)] for _ in range(n)]

    for _ in range(n):
        u, k, *v_s = map(int, input().split(' '))
        for j in range(k):
            graph[u-1][v_s[j-1]-1] = 1
    
    for row in graph:
        print(' '.join(map(str, row)))


if __name__ == "__main__":
    main()



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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 n,m;
  cin >> n >> m;
  vector<vector<pll>> adj(n);
  REP(i,m){
    int64 l,r,d;
    cin >> l >> r >> d;
    l--;r--;
    adj[l].emplace_back(r,d);
    adj[r].emplace_back(l,-d);
  }
  set<int32> vertex;
  REP(i,n){
    vertex.insert(i);
  }
  vector<int64> pos(n,LLINF);
  while(!vertex.empty()){
    int32 x = *vertex.begin();
    vertex.erase(x);
    queue<int32> que;
    que.push(x);
    pos[x] = 0;
    while(!que.empty()){
      int32 y = que.front();
      que.pop();
      for(pll p : adj[y]){
        int64 z,d;
        tie(z,d) = p;
        if(pos[z] == LLINF){
          pos[z] = pos[y] + d;
          que.push(z);
          vertex.erase(z);
        }else{
          if(pos[z] != pos[y] + d){
            cout << "No\n";
            return 0;
          }
        }
      }
    }
  }
  cout << "Yes\n";
  return 0;
}

Measured memory_bytes: 18176
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int W,N;
    for(int ii=1;;ii++){
        scanf("%d",&W);
        if(W==0) break;
        int values[W+1];
        for(int i=0;i<=W;i++){
            values[i]=0;
        }
        scanf("%d",&N);
        int v,n;
        for(int i=0;i<N;i++){
            scanf("%d,%d",&v,&n);
            for(int j=W;j>=n;j--){
                values[j]=max(values[j],values[j-n]+v);
            }
        }
        int maxw,maxv=-1;
        for(int i=0;i<=W;i++){
            if(values[i]>maxv){
                maxw=i;
                maxv=values[i];
            }
        }
        printf("Case %d:\n%d\n%d\n",ii,maxv,maxw);
    }
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		while(true){
			String input = in.next();
			if(input.equals("."))break;
			new AOJ1155().doIt(input+"=");
		}
	}
	class AOJ1155{
		char[] line;
		int pos;
		int P,Q,R;
		int exp(){
//			System.out.println("exp-- "+pos);
			int r = term();
//			System.out.println("exp-- "+r);
			while(true){
				char c = line[pos++];
				if(c=='+'){
					int a = term();
					if(r==2||a==2)r = 2;
					else if(r==1||a==1)r=1;
					else r = 0;
				}else if(c=='*'){
					int a = term();
					r = Math.min(a, r);
				}
				else break;
			}
			return r;
		}

		int term(){
			return fact();
		}

		int fact(){
			char c = line[pos++];
			if(c=='(')return exp();
			if(c=='-'){
				int a = fact();
				return Math.abs(a-2);
			}
			if(c=='P')return P;
			if(c=='Q')return Q;
			if(c=='R')return R;
			int x = c-'0';
			while(true){
				c = line[pos++];
				if(Character.isDigit(c)){
					x *= 10;
					x += c-'0';
				}
				else break;
			}
			pos--;
			return x;
		}
		
		void doIt(String input){
			line = input.toCharArray();
			int cnt = 0;
			for(P=0;P<3;P++)for(Q=0;Q<3;Q++)for(R=0;R<3;R++){
//				System.out.println(P+" "+Q+" "+R);
				pos = 0;
				if(exp()==2)cnt++;
			}
			System.out.println(cnt);
		}
		
	}
}

Measured memory_bytes: 34836
#include <iostream>

using namespace std;

#ifndef ONLINE_JUDGE
  #include <fstream>
  #define cin fin
  #define cout fout
  ifstream fin ("test.in");
  ofstream fout ("test.out");
#endif

int p[11];
int n, m, q;
int a[60], b[60], c[60], d[60];

int f (int i, int fn) {
  if (i == n + 1) {
    int r = 0;
    /*for (int j = 1; j <= n; j++)
      cout << p[j] << ' ';*/
    for (int j = 1; j <= q; j++) {
      if (p[b[j]] - p[a[j]] == c[j])
        r += d[j];
    }
    //cout << r << endl;
    return r;
  }
  int r = 0;
  for (int j = fn; j <= m; j++) { //intram cu toate permutarile de lungime n cu valori de la 1 la m
    p[i] = j;
    r = max (r, f(i + 1, j));
  }
  return r;
}

int main() {
  cin >> n >> m >> q;
  for (int i = 1; i <= q; i++)
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  /*for (int i = 0; i < q; i++) {
    a[i]--; b[i]--;
  }*/
  cout << f (1, 1) << endl;
  return 0;
}


Measured memory_bytes: 3188
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
typedef pair<lint,int> pl;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

vector<lint> a[100100];//各色のボールにどういう重さのがあるか
vector<pl> b;//すべてのボールの集合
int num[100100];//各色のボールを何個ずつ使ったか
priority_queue<pl> used;//既に使った3個目以降のボール
priority_queue<pl> rest;//まだ使ってない3個目以降のボール
priority_queue<pl> r2;//まだ1個も使ってない色のトップ3
lint inf=1234567890123456LL;

lint cal(){
	while(!r2.empty()){
		pl p=r2.top();
		if(num[p.se]<2) return p.fi;
		r2.pop();
	}
	return -inf;
}

int main()
{
	int n,k,c,v;
	cin>>n>>k;
	rep(i,n){
		cin>>c>>v;c--;v*=2;a[c].pb(v);
	}
	rep(i,k){
		sort(All(a[i]));reverse(All(a[i]));
		a[i][0]=a[i][1]=(a[i][0]+a[i][1])/2;
		rep(j,a[i].size()) b.pb(mp(a[i][j],i));
		if(a[i].size()>2) r2.push(mp(a[i][0]+a[i][1]+a[i][2],i));
	}
	sort(All(b));reverse(All(b));
	lint sum=0;int pre=-1;
	rep(i,n){
		int it=b[i].se;
		sum+=b[i].fi;num[it]++;
		if(num[it]==1){
			lint ret=-2;
			if(!used.empty()){
				ret=max(ret,sum+b[i+1].fi+used.top().fi);
			}
			if(!rest.empty()){
				ret=max(ret,sum-b[i].fi+rest.top().fi);
			}
			lint th=cal(),tr=inf;
			if(pre>=0) tr=min(tr,a[pre][0]+a[pre][1]);
			if(used.size()>1){
				pl p,q;p=used.top();used.pop();q=used.top();
				tr=min(tr,-p.fi-q.fi);used.push(p);
			}
			ret=max(ret,sum-tr-b[i].fi+th);
			cout<<ret/2<<endl;
		}
		else{
			cout<<sum/2<<endl;
			if(num[it]==2){
				REP(j,2,a[it].size()) rest.push(mp(a[it][j],it));
				pre=it;
			}
			else{
				pl p=rest.top();rest.pop();
				assert(p==b[i]);
				p=mp(-p.fi,p.se);
				used.push(p);
			}
		}
	}
}


Measured memory_bytes: 22564
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int A[200000];
	ll goukei = 0;
	rep(i, N) goukei += (A[i] = getint());


	ll kotae = 1e18;

	int q = 1, s = 3;
	ll PQ = A[0] - A[1];
	ll RS = -goukei + A[2] + A[0] + A[1] + A[2] ;
	ll diff = -goukei + A[0] + A[1] + A[0] + A[1];
	for (int r = 2; r < N - 1; r++) {
		while (abs(PQ) > abs(PQ + 2 * A[q])) {
			PQ += 2 * A[q];
			q++;
		}
		while (abs(RS) > abs(RS + 2 * A[s])) {
			RS += 2 * A[s];
			s++;
		}
		ll kari = max(abs(diff) + abs(PQ) + abs(RS), max(abs(PQ), abs(RS)) * 2);
		kotae = min(kotae, kari);

		PQ -= A[r];
		RS -= A[r];
		diff += 2 * A[r];
	}

	printf("%lld", kotae / 2);

	Would you please return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,count=0;
  cin >> N;
  vector<int> H(N);
  for(int i=0;i<N;i++){
    cin >> H[i];
  }
  int highest=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<i;j++){
        if(H[j]>highest){
          highest = H[j];
        }
    }
    if(H[i]>=highest){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    int[][][] MEMO;
    MEMO.length = N;
    foreach (i; 0..N) {
        auto A = readln.chomp.to!int;
        MEMO[i].length = A;
        foreach (j; 0..A) {
            auto xy = readln.split.to!(int[]);
            xy[0] -= 1;
            MEMO[i][j] = xy;
        }
    }

    int solve(int i, uint s) {
        if (i == N) {
            int c;
            foreach (j; 0..N) if (s & (1<<j)) {
                ++c;
                foreach (xy; MEMO[j]) {
                    auto x = xy[0];
                    auto y = xy[1];
                    if (!!(s & (1<<x)) != !!y) return 0;
                }
            }
            return c;
        } else {
            return max(solve(i+1, s), solve(i+1, s | (1<<i)));
        }
    }
    writeln(solve(0, 0));
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define INFTY 2000000001
#define LEN 1000000
using namespace std;
struct edge {
  int from,to,cost,k;
};
edge es[LEN];
int main(){
  int n,u,k,E,c,v;
  int d[LEN];
  E = 0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v>>c;
      es[E].from = u;
      es[E].to = v;
      es[E++].cost = c;
    }
  }
  for(int i=0;i<n;i++)d[i] = INFTY;
  d[0] = 0;
  while(true){
    bool update = false;
    for(int i=0;i<E;i++){
      edge e = es[i];
      if(d[e.from] != INFTY && d[e.to] > d[e.from] + e.cost){
    d[e.to] = d[e.from] + e.cost;
    update = true;
      }
    }
    if(update==false)break;
  }
  for(int i=0;i<n;i++)cout << i << " " << d[i] << endl;
  return 0;
}



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

typedef struct node {
    int value;
    struct node* parent;
    struct node* left;
    struct node* right;
} Node;

typedef Node* NodePointer;

NodePointer serialize(int val) {
    NodePointer newNode = malloc(sizeof(Node));
    newNode->value = val;
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

NodePointer insert(NodePointer node, int val) {
    NodePointer currentNode = node;
    int flag = 0;
    int dir = 0;
    while(!flag) {
        if (currentNode->value > val) {
            if (currentNode->left == NULL) flag = 1;
            else currentNode = currentNode->left;
            dir = 0;
        } else if (currentNode->value < val) {
            if (currentNode->right == NULL) flag = 1;
            else currentNode = currentNode->right;
            dir = 1;
        } else {
            return node;
        }
    }

    if (dir) {
        currentNode->right = serialize(val);
        currentNode->right->parent = currentNode;
    } else {
        currentNode->left = serialize(val);
        currentNode->left->parent = currentNode;
    }

    return node;
}

void inorderPrint(NodePointer node) {
    if (node == NULL) return;
    inorderPrint(node->left);
    printf(" %d", node->value);
    inorderPrint(node->right);
}

void preorderPrint(NodePointer node) {
    if (node == NULL) return;
    printf(" %d", node->value);
    preorderPrint(node->left);
    preorderPrint(node->right);
}

void nodePrint(NodePointer node) {
    inorderPrint(node);
    printf("\n");
    preorderPrint(node);
    printf("\n");
}

int main() {
    NodePointer node = NULL;
    int n, m;
    char cmd[16];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", cmd);
        if (!strcmp(cmd, "insert")) {
            scanf("%d", &m);
            if (node == NULL) node = serialize(m);
            else insert(node, m);
        } else if (!strcmp(cmd, "print")) {
            nodePrint(node);
        }
    }
    return 0;
}



Measured memory_bytes: 25276
N = int(input())

x_list = []
y_list = []
for i in range(N):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

ans_max_p = 0
ans_min_p = 2*10**9+1
ans_max_n = 0
ans_min_n = 2*10**9+1
ans = 0

for i in range(N):
    ans_min_p = min(ans_min_p, x_list[i] + y_list[i])
    ans_max_p = max(ans_max_p, x_list[i] + y_list[i])
    ans_min_n = min(ans_min_n, -1*x_list[i] + y_list[i])
    ans_max_n = max(ans_max_n, -1*x_list[i] + y_list[i])
    
ans_p = ans_max_p - ans_min_p
ans_n = ans_max_n - ans_min_n
ans = max(ans_p, ans_n)
print(ans)

Measured memory_bytes: 24912
n = int(input())
all_sum = n * (n + 1)//2

number_3 = n//3
number_5 = n//5
number_15 = n//15

sum_number_3 = 3 * (number_3 * (number_3 + 1)//2)
sum_number_5 = 5 * (number_5 * (number_5 + 1)//2)
sum_number_15 = 15 * (number_15 * (number_15 + 1)//2)

sum_not_number = sum_number_3 + sum_number_5 - sum_number_15

s = all_sum - sum_not_number

print(s)


Measured memory_bytes: 9192
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef complex<double> xy_t;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
ll inf = llmax / 2;
double eps = 1e-11;

vector<ll> v;

int ketasum(ll n) {
    int ans = 0;
    while (true) {
        ans += n % 10;
        n /= 10;
        if (n == 0) {
            break;
        }
    }
    return ans;
}

vector<ll> q;
vector<ll> p;

int main() {
    ll K;
    cin >> K;
    for (int i = 0; i < 100000; i++) {
        q.push_back(i);
    }
    for (int i = 0; i < 12; i++) {
        ll num = 10;
        for (int j = 0; j < i; j++) {
            num *= 10;
        }
        for (int j = 10000; j < 100000; j++) {
            q.push_back(j * num + num - 1);
        }
    }
    int len = q.size();
    double min = q[len - 1] * 1.0 / (ketasum(q[len - 1]) * 1.0);
    for (int i = len - 1; i >= 0; i--) {
        double now = q[i] * 1.0 / (ketasum(q[i]) * 1.0);
        if (now <= min) {
            p.push_back(q[i]);
            min = now;
        }
    }
    int len2 = p.size();
    int c = 0;
    for (int i = len2 - 1; i >= 0; i--) {
        cout << p[i] << endl;
        c++;
        if (c == K) {
            break;
        }
    }
}


Measured memory_bytes: 18024
s = list(input())
k = int(input())
if len(s) == 1:
    print(k//2)
    exit()
cnt = 0
# ランレングス圧縮
def rle(lst):
    ans = []
    cnt = 1
    ini = lst[0]
    for i in range(1, len(lst)):
        if ini == lst[i]:
            cnt += 1
        else:
            ans.append((ini, cnt))
            cnt = 1
            ini = lst[i]
    ans.append((ini, cnt))
    return ans

sr = rle(s)
if len(sr) == 1:
    print(sr[0][1]*k//2)
    exit()
for i in range(len(sr)):
    if sr[i][1] >= 2:
        cnt += sr[i][1]//2 * k
if sr[0][0] == sr[-1][0]:
    x = sr[0][1]
    y = sr[-1][1]
    cnt -= (x//2 + y//2 - (x+y)//2) *(k-1)
print(cnt)









Measured memory_bytes: 9248
import itertools as it

N = int(input())
sides = [int(i) for i in input().split()]


combs = it.combinations(sides, 3)
combs = it.filterfalse(lambda x: not (x[0] != x[1] and x[1] != x[2] and x[0] != x[2]) ,combs)



def is_triangle(comb):
    if comb[0] + comb[1] > comb[2] and comb[1] + comb[2] > comb[0] and comb[0] + comb[2] > comb[1]:
        return True
    return False

count = 0
for comb in combs:
    if is_triangle(comb):
        count += 1

print(count)





Measured memory_bytes: 9216
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

int main(void) {
    int D, T, S;
    
    cin >> D >> T >> S;
    if (T * S < D) {
        cout << "No";
    }else{
        cout << "Yes";
    }
    
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n;
  cin >> n;
  bool y = false;
  rep(i,n){
      string s;
      cin >> s;
      if(s=="Y"){
          y=true;
          }
      }
  if (y) cout<<"Four"<<endl;
  else cout<<"Three"<<endl;
}

Measured memory_bytes: 3584
#include <stdio.h>

int min(int a,int b){
  if(a < b){
    return a;
  }
  return b;
}

int main(void){
  int data[3][3];
  int b[3];

  for(int i = 0;i < 3;i++){
    for(int j = 0;j < 3;j++){
      scanf("%d",&data[i][j]);
    }
  }


  for(int i = 0;i <= min(min(data[0][0],data[0][1]),data[0][2]);i++){
    b[0] = data[0][0]-i;
    b[1] = data[0][1]-i;
    b[2] = data[0][2]-i;
    int flag = 0;
    for(int j = 1;j < 3;j++){
      if(data[j][0]-b[0] == data[j][1]-b[1] && data[j][1]-b[1] == data[j][2]-b[2]){
        if(data[j][0]-b[0] >= 0){
          flag++;
        }
      }
    }
    if(flag == 2){
      printf("Yes\n");
      return 0;
    }
  }

  printf("No\n");

  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  int n,m;
  double a,b;
  cin >> n;
  if(n%2==0){
    m=n/2;
  }
  else{
    m=n/2+1;
  }
  a=n;
  b=m;
  printf("%lf\n",b/a);
}

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

using namespace std;

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

int main(){
    int n;
    cin >> n;
    double ans = (double)(n / 2 + n % 2) / (double)n;
    cout << ans << endl;
}


Measured memory_bytes: 256
fn input_one<T: std::str::FromStr> () -> Result<T, T::Err> {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    n.trim().parse()
}

fn main() {
    let r: usize = input_one().unwrap();
    println!("{}", r * r);
}


Measured memory_bytes: 2140
#include <cstdio>
#include <iostream>
#define MAX 10000

using namespace std;

struct Node{int parent,left,right;};
Node T[MAX];
int n,D[MAX],H[MAX];

string getstate(int x){
  if(T[x].parent==-1) return "root";
  else if(T[x].left==-1&&T[x].right==-1) return "leaf";
  else return "internal node";
}

int setheight(int u){
  int h1=0,h2=0;
  if(T[u].left!=-1) h1=setheight(T[u].left)+1;
  if(T[u].right!=-1) h2=setheight(T[u].right)+1;
  return H[u]=(h1>h2 ? h1:h2);
}

void setdepth(int u,int p){
  if(u==-1) return;
  D[u]=p;
  if(T[u].left!=-1) setdepth(T[u].left,p+1);
  if(T[u].right!=-1) setdepth(T[u].right,p+1);
}

int getsibling(int u){
  if(T[u].parent==-1) return -1;
  if(T[T[u].parent].left!=u&&T[T[u].parent].left!=-1)
    return T[T[u].parent].left;
  if(T[T[u].parent].right!=u&&T[T[u].parent].right!=-1)
    return T[T[u].parent].right;
  return -1;
}

int getdegree(int x){
  int num=0;
  if(T[x].left!=-1) num++;
  if(T[x].right!=-1) num++;
  return num;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++) T[i].parent=-1;
  for(int i=0;i<n;i++){
    int v,l,r;
    scanf("%d %d %d",&v,&l,&r);
    T[v].left=l;
    T[v].right=r;
    if(l!=-1) T[l].parent=v;
    if(r!=-1) T[r].parent=v;
  }
  int root;
  for(int i=0;i<n;i++){
    if(T[i].parent==-1) root=i;
  }
  setheight(root);
  setdepth(root,0);
  for(int i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n",
     i,T[i].parent,getsibling(i),getdegree(i),D[i],H[i],getstate(i).c_str());
  }
}

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

int main()
{
    ll a,b,n;
    scanf("%lld %lld %lld",&a ,&b ,&n);
    if(n==b || n>b) n=b-1;
    printf("%lld\n",(a*n/b));
}



Measured memory_bytes: 3764
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int MOD = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;

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

// value


void solve() {

	int N;
	cin >> N;
	int C[30], V[30];

	for (int i = 0; i < N; i++) {
		cin >> V[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

	int ans = 0;

	for (int i = 0; i < (1 << N); i++) {
		int value = 0, cost = 0;
		for (int j = 0; j < N; j++) {
			if ((i >> j) & 1) {
				value += V[j];
				cost += C[j];
			}
		}
		ans = max(ans, value - cost);
	}

	cout << ans << endl;

	return;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

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

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

    int A[n][m] = {};
    int b[m] = {};

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> A[i][j];
        }
    }

    for (int k = 0; k < m; k++){
        cin >> b[k];
    }

    for (int l = 0; l < n; l++){
        int x = 0;
        for (int s = 0; s < m; s++){
            x += A[l][s] * b[s];
        }
        cout << x << endl;
    }

    return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define FOR(i, a, b) for (int i=(a); i<(b); ++i)
#define ROF(i, b, a) for (int i=(b); i>(a); --i)
#define CASET int _T; cin >> _T; FOR(caset, 0, _T)
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vi>
#define vvb vector<vb>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define mii map<int,int>
#define vpii vector<pii>
#define vt3i vector<t3i>
#define sq(x) (x)*(x)
#define inv(x) powa(x, MOD-2)
 
long long INF = 1LL<<60;
long long MOD = 1e9+7;
 
template <typename A, typename B> istream &operator>>(istream &is, pair<A, B> &pr) {is >> pr.first >> pr.second; return is;}
template <typename A> istream &operator>>(istream &is, vector<A> &v) {for (auto &x : v) is >> x; return is;}
ostream &operator<<(ostream &os, char &c) {os << (char)c; return os;}
ostream &operator<<(ostream &os, const char s[]) {os << (string)s; return os;}
ostream &operator<<(ostream &os, string &s) {for (char &c : s) os << (char)c; return os;}
template <typename A, typename B> ostream &operator<<(ostream &os, pair<A, B> &pr) {os << '(' << pr.first << ", " << pr.second << ')'; return os;}
ostream &operator<<(ostream &os, vb &v) {
    bool first = true;
    os << '[';
    for (const bool &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
template <class C> ostream &operator<<(ostream &os, C &v) {
    bool first = true;
    os << '[';
    for (auto &x : v) {
        if (!first) os << ", ";
        first = false;
        os << x;
    }
    os << ']';
    return os;
}
int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    vi a(3);
    cin >> a;
    sort(a.begin(), a.end());
    if ((a[0] == a[1] && a[1] != a[2]) || (a[0] != a[1] && a[1] == a[2])) cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func ScanInt() int {
	sc.Scan()
	var a int
	a,_ = strconv.Atoi(sc.Text())
	return a
}

func dfs(a int, t,c [][]int, ans []int) {
	for i, e := range t[a] {
		if ans[e]!=-1 {
			continue
		}
		ans[e] = (ans[a]+c[a][i])%2
		dfs(e,t,c,ans)
	}
}

func main() {
	var n int
	fmt.Scan(&n)

	t := make([][]int,n)
	c := make([][]int,n)

	sc.Split(bufio.ScanWords)

	for i:=0; i<n-1; i++ {
		var u,v,w int
		u,v,w = ScanInt(),ScanInt(),ScanInt()
		u--
		v--
		t[u],c[u] = append(t[u],v),append(c[u],w)
		t[v],c[v] = append(t[v],u),append(c[v],w)
	}

	ans := make([]int,n)

	for i:=0; i<n; i++ {
		ans[i] = -1
	}

	ans[0] = 0

	dfs(0,t,c,ans)

	for i:=0; i<n; i++ {
		fmt.Println(ans[i])
	}
}


Measured memory_bytes: 27264
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

string s[] = { "AAA","AA","A","B","C","D","E" };
double t1[] = { 35.5,37.5,40,43,50,55,70 };
double t2[] = { 71,77,83,89,105,116,148 };

signed main() {
	for (double a, b; cin >> a >> b;) {
		rep(i, 0, 8) {
			if (i == 7) {
				cout << "NA" << endl;
				break;
			}
			if (t1[i] > a&&t2[i] > b) {
				cout << s[i] << endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3148
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)


Measured memory_bytes: 90032
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(int)(a); i++)
typedef long long ll;
template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////
const ll inf = 1LL<<60;
const ll mod = 1000000007;

const ll MAX_N = 100005;

struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
  mint operator+(const mint a) const { return mint(*this)+=a; }
  mint operator-(const mint a) const { return mint(*this)-=a; }
  mint operator*(const mint a) const { return mint(*this)*=a; }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod-2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this)/=a; }
  bool operator==(const mint a) const { return x == a.x; }
  bool operator!=(const mint a) const { return x != a.x; }
  friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
  friend istream &operator>>(istream &is, mint &a) {
    ll t;
    is >> t;
    a = mint(t);
    return (is);
  }
};

template<typename T>
struct Comb {
  vector<T> fact, finv, inv;
  Comb(int n) : fact(n, 1), finv(n, 1), inv(n, 1) { init(n); }
  void init(int n) {
    fact.assign(n, 1), finv.assign(n, 1), inv.assign(n, 1);
    for (ll i=2; i<n; i++) {
      fact[i] = fact[i-1] * i % mod;
      inv[i] = mod - inv[mod%i] * (mod/i) % mod;
      finv[i] = finv[i-1] * inv[i] % mod;
    }
  }
  T nck(int n, int k) {
    if (n<k || n<0 || k<0) return 0;
    return fact[n] * (finv[k] * finv[n-k] % mod) % mod;
  }
  T nhk(int n, int k) { return nck(n+k-1, k); }
  T npk(int n, int k) {
    if (n<k || n<0 || k<0) return 0;
    return fact[n] * finv[n-k] % mod;
  }
};

vector<vector<int>> tr(MAX_N);

int n,k;
Comb<ll> comb(MAX_N);

mint ans;

void dfs(int v, int par=-1)
{
  for (auto nv: tr[v]) {
    if (par == nv) continue;
    dfs(nv, v);
  }

  int col = k;
  int chi = tr[v].size() + 1;
  if (par > -1) {
    col -= 2;
    chi -= 2;
  }

  ans *= comb.npk(col, chi);
}

int main()
{
  cin>>n>>k;
  rep(i, n-1) {
    int a, b; cin>>a>>b; a--; b--;
    tr[a].push_back(b);
    tr[b].push_back(a);
  }
  ans = 1;
  dfs(0);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 11520
# -*- Coding: utf-8 -*-
import numpy as np

N = int(raw_input())
W = map(int,raw_input().split())
W = np.array(W)
W_sum = np.sum(W)
ans = W_sum
left = 0
for i in xrange(N-1):
	left += W[i]
	right = W_sum - left
	ans = min(ans,abs(left-right))

print ans


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

using namespace std;

typedef long long int ll;

void solve()
{
	int n, x, y;
	cin >> n >> x >> y;
	for(int i = x; i <= y; i++)
	{
		if(i % n == 0)
		{
			cout << "OK";
			return;
		}
	}
	cout << "NG";
}

int main()
{
	int t = 1;
	//cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}



Measured memory_bytes: 3620
N = int(input())
A = list(map(int, input().split()))
sort_A = sorted(A)
str_A = list(map(str, sort_A))
o = 'YES'
for i in range(1, len(A)):
	if str_A[i-1] == str_A[i]:
		o = 'NO'
		break
print(o)

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

int n = 105;
int cnt = 1;
vector<vector<int>> Graph(n,vector<int>());
vector<bool> visited(n,0);
vector<int> first(n);
vector<int> last(n);

void dfs(int i,int &cnt ){
        //行き
        first.at(i) = cnt;
        cnt ++;
        visited.at(i) = 1;
        
        for(auto p:Graph.at(i)){
                if(visited.at(p)) continue;
                dfs(p,cnt);
        }
        
        //帰り
        last.at(i) = cnt;
        cnt ++;
}

int main(){
        int n;
        cin >>n;
        rep(i,n){
                 int u,k;
                cin >> u >> k;
                --u;
                rep(j,k){
                         int p;
                        cin >> p;
                        --p;
                        Graph.at(u).push_back(p);
                }
        }
        rep(i,n){
                 if(!visited.at(i)) dfs(i,cnt);
        }
        rep(i,n){
                 cout << i+1 <<" ";
                cout << first.at(i) << " ";
                cout << last.at(i) << endl;
        }
        

        return 0;
}



Measured memory_bytes: 3172
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <deque>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef bitset<16> BS;

const ll MOD = 1E+09 + 7;
const ll INF = 1E18;
const int MAX_N = 1E+05;

ll X, Y;

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

    cin >> X >> Y;

    int l = 0;
    for (; X <= Y; X *= 2) {
        l++;
    }

    /*
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n";
        }
    }
    */

    cout << l << "\n";

    return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main(){
	string o,e;
	cin>>o>>e;
	for(int i=0;i<o.size()+e.size();i++){
		if(i%2==0){
			cout<<o[i/2];
		}
		else{
			cout<<e[i/2];
		}
	}
	cout<<endl;
}


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

using namespace std;

static inline int in(){ int x; scanf("%d", &x); return x; }

int main()
{
  int field[1024][1024];
  int n;
  while (n = in()){
    for (int i = 0; i < n; i++){
      string s;
      cin >> s;
      for (int j = 0; j < n; j++){
        field[i][j] = s[j] == '.';
      }
    }
    int maxi = 0;
    for (int i = 1; i < n; i++){
      for (int j = 1; j < n; j++){
        if (field[i][j]){
          field[i][j] = min(field[i - 1][j - 1], min(field[i - 1][j], field[i][j - 1])) + 1;
          maxi = max(maxi, field[i][j]);
        }
      }
    }
    printf("%d\n", maxi);
  }

  return 0;
}

Measured memory_bytes: 5232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define INF 1e8
#define EPS 1e-9
#define ALL(x) x.begin() , x.end()
#define ALLR(x) x.rbegin() , x.rend()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define PI acos(-1.0) // important constant; alternative #define PI (2.0 * acos(0.0))
ll factorial(int i)
{
    if(i==1||i==0)return 1;
    return i*factorial(i-1);
}
int main()
{
    ll n,m,sum=0;
    cin>>n>>m;
    if(n>=2)sum+=n*(n-1)/(2);
    if (m>=2)sum+=m*(m-1)/(2);
    cout<<sum<<"\n";

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define REP(i,N) for(int i=0;i<N;i++)
int main(){
    string s; cin>>s;
    int a = (s[0]-'0')*10+(s[1]-'0');
    int b = (s[2]-'0')*10+(s[3]-'0');
    if(a<=12 && a>0 && b<=12 && b>0){
        cout<<"AMBIGUOUS"<<endl;
    } else if((a>12||a==0)&&b<=12&&b>0){
        cout<<"YYMM"<<endl;
    } else if(a<=12&&a>0&&(b>12||b==0)){
        cout<<"MMYY"<<endl;
    } else {
        cout<<"NA"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
typedef struct{
    int k, l, r;
}node;
 
node nodes[500001];
 
void insert(int index, int z)
{
    int x = 0, y;
 
    nodes[index].k = z;
    nodes[index].l = -1;
    nodes[index].r = -1;
 
    if(index == 0)
        return ;
 
    while(x >= 0){
        y = x;
        if(z < nodes[x].k){
            x = nodes[x].l;
        }else{
            x = nodes[x].r;
        }
    }
 
    if(z < nodes[y].k)
        nodes[y].l = index;
    else
        nodes[y].r = index;
}
 
void find(int z)
{
    int x = 0;
    while(x >= 0 && nodes[x].k != z){
        if(z < nodes[x].k){
            x = nodes[x].l;
        }else{
            x = nodes[x].r;
        }
    }
 
    if(nodes[x].k == z)
        printf("yes\n");
    else
        printf("no\n");
}
 
void pre(int id)
{
    if(id == -1)
        return ;
    printf(" %d", nodes[id].k);
    pre(nodes[id].l);
    pre(nodes[id].r);
}
 
void ino(int id)
{
    if(id == -1)
        return ;
    ino(nodes[id].l);
    printf(" %d", nodes[id].k);
    ino(nodes[id].r);
}
 
int main(void)
{
    int i, n;
    int index = 0, z;
    char buf[16];
    scanf("%d", &n);
 
    for(i = 0; i < n; i++){
        scanf("%s", buf);
        if(buf[0] == 'i'){
            scanf("%d", &z);
            insert(index++, z);
        }else if(buf[0] == 'p'){
            if(index > 0){
                ino(0);
                printf("\n");
                pre(0);
                printf("\n");
            }
        }else if(buf[0] == 'f'){
            scanf("%d", &z);
            find(z);
        }
    }
 
    return 0;
}



Measured memory_bytes: 6412