akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


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


def main():
    N = int(input())
    A, B = [], []

    total = 0
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        total += a

    r = INF
    for a, b in zip(A, B):
        if a == 0 and b == 0:
            continue
        if b < a:
            r = min(r, b)

    if r == INF:
        print(0)
    else:
        print(total - r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5676
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <list>
#include <cmath>
using namespace std;
#define rep(i,m,n) for (int i = (int) (m); i < (int) (n); i++)
#define rep1(i,m,n) for (int i = (int) (m); i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
int main(void){
    int R;
    cin>>R;
    printf("%lf",2*R*M_PI);
    cout<<endl;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  while(cin>>n,n){
    int ans=1;
    int m=n;
    for(int i=2;i*i<=n;i++){
      if(m%i) continue;
      int tmp=1,res=1;
      while(m%i==0){
	m/=i;
	res*=i;
	tmp+=res;
      }
      ans*=tmp;
      if(ans>n*2) break;
    }
    if(m!=1) ans*=m+1;
    if(ans==n*2) cout<<"perfect number"<<endl;
    if(ans<n*2) cout<<"deficient number"<<endl;
    if(ans>n*2) cout<<"abundant number"<<endl;
  }
  return 0;
}

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

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,ans;
    while(cin >> n)
    {
        ans = 1;
        for(int b = 2; b*b <= n; b++)
        {
            int p = b;
            while(p <= n)
            {
                ans = max(ans, p);
                p *= b;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#include <cstring>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

int n,root,e[100100][2],ans[100100];
struct edge
{
    int v;
    edge *nxt;
} pool[100100],*tp,*fst[100100];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()) && ch!='-');
    bool flag=ch=='-';
    if (flag)
        ch=getchar();
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return flag?-x:x;
}

void addedge(int u,int v)
{
    (e[u][0]?e[u][1]:e[u][0])=v;
    (e[v][0]?e[v][1]:e[v][0])=u;
}

int dfs1(int x)
{
    int ret=0;
    for (edge *i=fst[x]; i; i=i->nxt)
    {
        int t=dfs1(i->v);
        if (ret)
            addedge(ret,t),ret=0;
        else
            ret=t;
    }
    return ret?ret:x;
}

void dfs2(int x,int w)
{
    ans[x]=w;
    repu(i,0,1)
        if (!ans[e[x][i]])
            dfs2(e[x][i],-w);
}

int main()
{
    n=getint();
    repu(j,1,2)
    {
        memset(fst,0,sizeof(fst)),tp=pool;
        repu(i,1,n)
        {
            int fa=getint();
            if (fa==-1)
                root=i;
            else
                *tp=(edge){i,fst[fa]},fst[fa]=tp++;
        }
        int t=dfs1(root);
        addedge(n+1,t);
    }
    repu(i,1,n)
        if (e[i][0])
        {
            if (!e[i][1])
            {
                puts("IMPOSSIBLE");
                return 0;
            }
            if (!ans[i])
                dfs2(i,1);
        }
    puts("POSSIBLE");
    repu(i,1,n)
        printf("%d ",ans[i]);
    return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  bool res = abs(A - B) % 2 == 0;
  cout << (res ? "Alice" : "Borys") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int n;

int main(){
	while(cin>>n,n){
		int a=0;
		rep2(i,n+1,2*n+1){
			int ok=1;
			for(int j=2;j*j<=i;j++)if(i%j==0)ok=0;
			a+=ok;
		}
		cout<<a<<endl;
	}
}

Measured memory_bytes: 868
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    int a,b;
    cin >> a >> b;
    int ans = max(a+b,a-b);
    ans = max(ans,a*b);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#coding:utf-8

a_list = list(raw_input())
b_list = list(raw_input())
c_list = list(raw_input())

mode = "a"
while(True):
	if mode == "a":
		if len(a_list) == 0:
			print "A"
			break
		mode = a_list.pop(0)
	elif mode == "b":
		if len(b_list) == 0:
			print "B"
			break
		mode = b_list.pop(0)
	elif mode == "c":
		if len(c_list) == 0:
			print "C"
			break
		mode = c_list.pop(0)
	else:
		print "Invalid Input"
		break


Measured memory_bytes: 2568
#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <vector>
#define pb push_back
#define mp make_pair
using namespace std;
vector<int> v[100010];
queue<int> q;
int a[100010];
int b[100010];
int vis[100010];
int n;
void bfs()
{
    q.push(1);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<v[now].size();i++)
        {
            if(!vis[v[now][i]])
            {
                vis[v[now][i]]=1;
                a[v[now][i]]=a[now]+1;
                q.push(v[now][i]);
            }
        }
    }
    memset(vis,0,sizeof(vis));
    q.push(n);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<v[now].size();i++)
        {
            if(!vis[v[now][i]])
            {
                vis[v[now][i]]=1;
                b[v[now][i]]=b[now]+1;
                q.push(v[now][i]);
            }
        }
    }
}

int main()
{
    int aa,bb,sa=0,sb=0;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&aa,&bb);
        v[aa].pb(bb);
        v[bb].pb(aa);
    }
    bfs();
    for(int i=2;i<n;i++)
    {
        if(a[i]<=b[i]) sa++;
        else sb++;
    }
   /* printf("%d %d\n",sa,sb);
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    printf("\n");
    for(int i=1;i<=n;i++) printf("%d ",b[i]);*/
    if(sa>sb) printf("Fennec");
    else printf("Snuke");
    return 0;
}


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

using namespace std;

int main(){
    long long int N,x,ans=0;
    cin >> N >> x;
    vector<int> a(N);
    for(int i=0;i<N;i++){
        cin >> a[i];
    }

    for(int i=0;i<N-1;i++){
        if(x<a[i]+a[i+1]){
            ans += a[i]+a[i+1]-x;
            if(x<a[i]){
                a[i+1]=0;
                a[i] -= x-a[i+1];
            }else{
                a[i+1] -= a[i]+a[i+1]-x;
            }
        }
    }

    cout << ans;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cctype>
using namespace std;
int ctoi(const char& c) {
  if(c >= '0' && c <= '9') return (c-'0');
  return -1;
}
int main() {
    char ch;
    int sum = 0;
    while(true) {
        scanf("%c", &ch);
        if(ch == '\n') {
            if(sum == 0) break;
            printf("%d\n", sum);
            sum = 0;
            continue;
        }
        sum += ctoi(ch);
    }
    return 0;
}


Measured memory_bytes: 2708
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static void Main()
    {
        string[] input = Console.ReadLine().Split();
        long N = long.Parse(input[0]);
        long A = long.Parse(input[1]);
        long B = long.Parse(input[2]);
        long ans = ((N / (A + B)) * A)+ Math.Min(A,(N % (A + B)));
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
#include <stdio.h>
#define false 0
#define true 1
 
int main(){
  char is_prime[1000000];
  int n;
  int n_prime[1000000];
 
  is_prime[0]=is_prime[1]=false;
  for(int i=2;i<1000000;i++){
    is_prime[i] = true;
  }
 
  for(int i=2;i*i<1000000;i++){
    if(is_prime[i]){
      for(int j=i*i;j<1000000;j=j+i){
        is_prime[j] = false;
      }
    }
  }
  int cnt = 0;
  for(int i=0;i<1000000;i++){
    if(is_prime[i]){
      cnt++;
    }
    n_prime[i] = cnt;
  }
 
  while(scanf("%d",&n) != EOF){
    printf("%d\n",n_prime[n]);
  }
 
  return 0;
}


Measured memory_bytes: 7436
seigen = int(input())
word = input()
mojisuu = len(word)
mojiretu = list(word)
tansyuku = ""

if mojisuu > seigen:
    mojiretu = list(word)
    for i in range(seigen):
        tansyuku += mojiretu[i]
    tansyuku += "..."
    print(tansyuku)
else:
    print(word)

Measured memory_bytes: 9188
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=Integer.parseInt(sc.next());
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}

for(int i=0;i<n;i++){
    System.out.print(a[n-i-1]);
    if(i!=n-1)System.out.print(" ");
}System.out.println("");
}
}


Measured memory_bytes: 26512
#include <stdio.h>

int N,K;
int map[51][51];
int wariate[50][50];
int wariateNum[50];

int main(void) {
	int i,j,k,R;
	int b1,b2;
	int outCount;
	scanf("%d%d",&N,&K);
	for(i=0;i<K;i++) {
		scanf("%d",&wariateNum[i]);
		for(j=0;j<wariateNum[i];j++) {
			scanf("%d",&wariate[i][j]);
		}
	}
	scanf("%d",&R);
	for(i=0;i<R;i++) {
		scanf("%d%d",&b1,&b2);
		map[b1][b2]=1;
		map[b2][b1]=1;
	}
	outCount=0;
	for(i=0;i<K;i++) {
		for(j=0;j<wariateNum[i];j++) {
			for(k=0;k<wariateNum[i];k++) {
				if(map[wariate[i][j]][wariate[i][k]]) {
					outCount++;
					break;
				}
			}
		}
	}
	printf("%d\n",outCount);
	return 0;
}

Measured memory_bytes: 616
#include <stdio.h>
#include <math.h>
int main (void)
{
  int H,W, i, s;
for(;;)
{
  scanf("%d %d", &H, &W);
  if( H == 0 && W == 0) break;

  for(i = 1; i<= H; i++)
  {
    printf("#");
      for(s= 2; s<= W; s++)
      {
        if(i ==1 || i == H || s == W){
        printf("#");
        } else  {
          printf(".");
        }
      }
      printf("\n");
  }
  printf("\n");
}
  return 0;
}

Measured memory_bytes: 1716
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){


}

Node treeSearch(Node u, int k){
  if(u->key>k)
    {
      if(u->left==NIL)
	{
	  return NIL;
	}
      return treeSearch(u->left,k);
    }
  if(u->key<k)
    {
      if(u->right==NIL)
	{
	  return NIL;
	}
      return treeSearch(u->right,k);
    }

  return u;

}

Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x!=NIL)
    {
      y=x;
      if(z->key<x->key)
	{
	  x=x->left;
	}
      else
	{
	  x=x->right;
	}
    }
  z->parent=y;
  if(y==NIL)
    {
      root=z;
    }
  else if(z->key<y->key)
    {
      y->left=z;
    }
  else
    {
      y->right=z;
    }
}





void inorder(Node u){
  if(u->left!=NIL)
    {
      inorder(u->left);
    }
  printf(" %d",u->key);
  if(u->right!=NIL)
    {
      inorder(u->right);
    }
}
void preorder(Node u){
  printf(" %d",u->key);
   if(u->left!=NIL)
    {
      preorder(u->left);
    }
  if(u->right!=NIL)
    {
     preorder(u->right);
    }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Measured memory_bytes: 19364
import sys
sysinput = sys.stdin.readline

N = int(sysinput())
A = []
for i in range(N):
  A.append(int(sysinput()))

A_sort = sorted(A)
ans_list =[]
for A_i in A:
  if A_i == A_sort[-1]:
    ans_list.append(A_sort[-2])
  else:
    ans_list.append(A_sort[-1])

for ans in ans_list:
  print(ans)
  

Measured memory_bytes: 16288
using System;
namespace ITP1_1_C
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split();
            int a;
            int b;
            a = int.Parse(s[0]) * int.Parse(s[1]);
            b = 2 * (int.Parse(s[0]) + int.Parse(s[1]));
            Console.WriteLine("{0} {1}", a, b);
        }
    }
}


Measured memory_bytes: 17992
#include <stdio.h>

int main()
{
	int w=0;
	int n=0;
	int a=0,b=0;
	int i=0;
	int tmp;
	char comma;
	int Bar[30];
	
	for(i=0;i<30;i++)Bar[i]=i+1;
	
	scanf("%d",&w);
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%c%d",&a,&comma,&b);
		tmp=Bar[a-1];
		Bar[a-1]=Bar[b-1];
		Bar[b-1]=tmp;
	}
	for(i=0;i<w;i++){
		printf("%d\n",Bar[i]);
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main (void){

    int d[100][2];
    int n,zoro,flag;
    char c;

    scanf("%d",&n);
    scanf("%c",&c);

    zoro=0;
    flag=0;

    for(int i=0;i<n;i++){
        scanf("%d %d",&d[i][0],&d[i][1]);
        scanf("%c",&c);

        if(d[i][0]==d[i][1]){
            zoro++;
            if(zoro>2){
                flag=1;
            }
        }else{
            zoro=0;
        }
    }

    if(flag==1){
        printf("Yes");
    }else{
        printf("No");
    }






    return 0;
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const long double EPS = 1e-14;
const int maxn = 100500;
const int mod = 1e9 + 7;
int dp[2 * maxn];
vector < int > cnt[30];
string s;

int solve(int i){
    if(i >= sz(s)) return i == sz(s);
    int &ret = dp[i];
    if(~ret) return ret;
    ret = 1e9;
    for(int j = 0 ; j < 26 ; ++j){
        int idx = upper_bound(all(cnt[j]), i - 1) - cnt[j].begin();
        if(idx == sz(cnt[j])){
            ret = 1;
            break;
        }
        ret = min(ret, 1 + solve(cnt[j][idx] + 1));
    }
    return ret;
}

void track(int i){
    if(i >= sz(s)){
        if(i == sz(s)) cout << "a";
        cout << '\n';
        return ;
    }
    int ad = 1e9, k = -1, nxt = -1;
    for(int j = 0 ; j < 26 ; ++j){
        int idx = upper_bound(all(cnt[j]), i - 1) - cnt[j].begin();
        if(idx == sz(cnt[j])){
            k = j;
            nxt = sz(s) + 1;
            break;
        }
        int sm = 1 + solve(cnt[j][idx] + 1);
        if(sm < ad) ad = sm, k = j, nxt = cnt[j][idx] + 1;
    }
    cout << (char)(k + 'a');
    track(nxt);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> s;
    for(int i = 0 ; i < sz(s); ++i) cnt[s[i] - 'a'].push_back(i);
    memset(dp, -1, sizeof dp);
    solve(0);
    track(0);
    return 0;
}

Measured memory_bytes: 4628
#include<stdio.h>
#include<math.h>
int main(){
    long long int n;
    scanf("%lld",&n);
    long long int k = (long long int)sqrt(n);
    while(n%k!=0){
        k--;
    }
    long long int s = n/k;
    printf("%lld\n",s+k-2);
    return 0;
}

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

int main(void) {
    const ll INF = 1e9+7;
    ll N; cin >> N;
    vector<ll> A;
    vector<ll> sum;
    sum.push_back(0);
    ll ans = 0;
    rep(i,N) {
        ll a; cin >> a;
        A.push_back(a);
        ll b = (sum[i] + a);
        //b%=INF;
        sum.push_back(b);
    }

    for(ll i=0; i<N-1; i++) {
        ll x = (sum[N]-sum[i+1])%INF;
        ans += (A[i]*x)%INF;
        ans = (ans+INF)%INF;
    }
    ans = (ans + INF)%INF ;
    cout << ans << endl;
}

Measured memory_bytes: 6632
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main(){
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout.precision(20);

  int k, x;
  cin >> k >> x;

  cout << (500 * k >= x ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = [0] * N + [-1] * 9
for i in range(1, N+1):
    dp[i] = max(dp[i-int('0255456376'[a])] * 10 + a for a in A)

print(dp[N])

Measured memory_bytes: 14388
N = int(input())
L = [int(e) for e in input().split()]
c = 0

if len(set(L)) >= 3:
  for i in range(N-2):
    for j in range(i+1, N-1):
      for k in range(j+1, N):
        if L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
          if L[i] < L[j] + L[k] and L[j] < L[k] + L[i] and L[k] < L[i] + L[j]:
            c += 1
print(c)

Measured memory_bytes: 9200
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,x,y,e,f,g;
    scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&x,&y);
    g=(a*x)+(b*y);
    if(x>y)
    {
        e=(2*x)*c;
        f=((2*y)*c)+((x-y)*a);
    }
    else
    {
        e=(2*y)*c;
        f=((2*x)*c)+((y-x)*b);
    }
    if(e<=g && e<=f)
        printf("%lld\n",e);
   else if(f<=e && f<=g)
        printf("%lld\n",f);
   else
        printf("%lld\n",g);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,k,sum=0;
    cin>>n>>k;
    int a[n],i;
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(i=0;i<k;i++)
        sum=sum+a[i];
    cout<<sum<<endl;
    return 0;
}




Measured memory_bytes: 3640
import sys
import itertools

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M, Q = [int(x) for x in input().split()]
    ABCD = [[int(x) for x in input().split()] for _ in range(Q)]

    ans = 0

    A = [[0] * N for j in range(N)]

    for m in itertools.combinations_with_replacement(range(1, M + 1), r=N):
        m = list(m)
        m.sort()
        tmp = 0
        for a, b, c, d in ABCD:
            if m[b - 1] - m[a - 1] == c:
                tmp += d
        ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 80228
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

const ll inf = (ll)(1e17 + 17);
const ll mod = (ll)(1e9 + 7);


int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  ll a, b;
  cin >> a >> b;
  ll xx = __gcd(a, b);
  cout << (a*b)/xx << endl;
  return 0;
} //good night.

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    int N; cin >> N;
    vector<int> a(N);
    rep(i,N){
        cin >> a[i];
    }
    int cnt2 = 0;
    int cnt4 = 0;
    rep(i,N){
        if(a[i] % 2 == 0 && a[i] % 4 != 0) cnt2++;
        else if(a[i] % 4 == 0) cnt4++;
    }
    N -= cnt2-(cnt2 % 2 == 0 ? 0 : 1);
    if(cnt4 >= N/2) cout << "Yes" << endl;
    else cout << "No" << endl;
}
    



Measured memory_bytes: 640
import java.util.Scanner;

public class Main{
	public static void main(String args[]){
      Scanner sc = new Scanner(System.in);
      
      String s = sc.next();
      String t = sc.next();
      
      if(s.equals(t)){
        System.out.print("0");
        return;
      }
        
      
      int result = 0;
      for(int i=0; i < s.length(); i++){
      	if(!s.substring(i,i+1).equals(t.substring(i, i+1))){
          result++;
        }
      }
        
      System.out.print(result);
    }
}


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

int main() {
  vector<int> a(3);
  cin >>a.at(0) >>a.at(1) >>a.at(2);
  sort(a.begin(), a.end());
  int ans = a.at(2) - a.at(0);
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] arg) {
		boolean[] notPrime = new boolean[50001];
		notPrime[0] = true;
		notPrime[1] = true;
		for (int i = 4; i <= 50000; i += 2) {
			if (!notPrime[i]) {
				notPrime[i] = true;
			}
			final int k = i - 1;
			if (!notPrime[k]) {
				for (int j = k * 2; j <= 50000; j += k) {
					if (!notPrime[j]) {
						notPrime[j] = true;
					}
				}
			}
		}
		int primeCount = 0;
		for (int i = 0; i <= 50000; i++) {
			if (!notPrime[i]) {
				primeCount++;
			}
		}
		int[] primes = new int[primeCount];
		primes[0] = 2;
		int index = 1;
		for (int i = 3; i <= 50000; i += 2) {
			if (!notPrime[i]) {
				primes[index++] = i;
			}
		}
		int[] gbc = new int[50001];
		for (int i = 0; i < primes.length; i++) {
			for (int j = i; j < primes.length; j++) {
				int val = primes[i] + primes[j];
				if (val > 50000) {
					break;
				}
				gbc[val]++;
			}
		}

		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			if (n != 0) {
				System.out.println(gbc[n]);
			}
		}

	}
}

Measured memory_bytes: 33236
a,b,c =map(int,input().split())
if a ==max (a,b,c):
    print(int(str(a)+str(b))+c)
elif b ==max(a,b,c):
    print(int(str(b)+str(c))+a)
else:
    print(int(str(c)+str(a))+b)

Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>

int main() {
  int i;

  int n, k;
  scanf("%d %d", &n, &k);

  double probability = 0.0;
  for(i = 1; i <= n; i++) {
    int score = i;
    int num_throw_coin = 0;
    while(score < k) {
      score *= 2;
      num_throw_coin++;
    }
    probability += 1 / pow(2, num_throw_coin);
  }

  printf("%.10f\n", probability / n);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <cstdint>
#include <istream>
#include <sstream>
#include <cctype>
#include <functional>
#include <iomanip>
#define fore(i,x,y) for(ll i=(x);i<(y);i++)
#define disp(a) cout << a << endl;
#define PI 3.14159265359
typedef long long ll;
using namespace std;
int main()
{
	int k;
	string s;
	cin>>k>>s;
	if(s.size()>k){
		for(int i=0;i<k;i++){
			cout<<s[i];
		}
		cout<<"..."<<endl;
	}	
	else{
		for(int i=0;i<s.size();i++){
			cout<<s[i];
		}
		cout<<endl;
	}

}

Measured memory_bytes: 3104
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n;
int head[140010], to[140010], cot[140010], nxt[140010], cnt;
inline void addedge (int u, int v, int w) { cnt++, to[cnt] = v, nxt[cnt] = head[u], head[u] = cnt, cot[cnt] = w; }
int son[2];
long long mid;
bool ok;
vector <pair <long long, long long> > f[140010], c, d;
inline void dfs (int u) {
	f[u].clear ();
	if (!head[u]) { f[u].push_back (make_pair (0, 0)); return; }
	dfs (to[head[u]]), dfs (to[nxt[head[u]]]);
	vector <pair <long long, long long> > & a = f[to[head[u]]], & b = f[to[nxt[head[u]]]], &res = f[u];
	if (!a.size () || !b.size ()) return;
	c.clear (), d.clear ();
	for (int i = 0; i < a.size (); i++) a[i].first += cot[head[u]], a[i].second += cot[head[u]];
	for (int i = 0; i < b.size (); i++) b[i].first += cot[nxt[head[u]]], b[i].second += cot[nxt[head[u]]];
	for (int i = 0, j = 0; i < a.size (); i++) {
		while (j < b.size () - 1 && a[i].second + b[j + 1].first <= mid) j++;
		if (a[i].second + b[j].first > mid) continue;
		c.push_back (make_pair (a[i].first, b[j].second));
	}
	for (int i = 0, j = 0; i < b.size (); i++) {
		while (j < a.size () - 1 && b[i].second + a[j + 1].first <= mid) j++;
		if (b[i].second + a[j].first > mid) continue;
		d.push_back (make_pair (b[i].first, a[j].second));
	}
	long long t = 17179869185ll;
	int x = 0, y = 0;
	while (x < c.size () && y < d.size ()) {
		if (c[x].first < d[y].first) {
			if (c[x].second >= t) x++;
			else t = c[x].second, res.push_back (c[x++]);
		} else if (d[y].first < c[x].first) {
			if (d[y].second >= t) y++;
			else t = d[y].second, res.push_back (d[y++]);
		} else {
			pair <long long, long long> w = min (c[x], d[y]); x++, y++;
			if (w.second >= t) continue;
			t = w.second, res.push_back (w);
		}
	}
	while (x < c.size ()) {
		if (c[x].second >= t) x++;
		else t = c[x].second, res.push_back (c[x++]);
	}
	while (y < d.size ()) {
		if (d[y].second >= t) y++;
		else t = d[y].second, res.push_back (d[y++]);
	}
	if (!res.size ()) ok = false;
}
int main () {
	scanf ("%d", &n);
	for (int i = 2; i <= n; i++) {
		int f, w;
		scanf ("%d%d", &f, &w);
		addedge (f, i, w);
	}
	long long l = 0, r = 17179869184ll;
	while (l < r) {
		ok = true; mid = (l + r) >> 1;
		dfs (1);
		if (ok) r = mid;
		else l = mid + 1;
	}
	printf ("%lld\n", l);
	return 0;
}

Measured memory_bytes: 29788
program redistribution
  implicit none
  integer(8), parameter :: modu = 1000000007_8
  integer :: s
  integer(8) :: m(3, 3) = 0
  read(*,*) s
  if (s < 6) then
    write(*,'(i0)') s / 3
    stop
  end if
  m(1, 1) = 1
  m(2, 1) = 1
  m(3, 2) = 1
  m(1, 3) = 1
  m = modmatpow(m, s - 6)
  write(*,'(i0)') mod(m(1, 1) + m(1, 1) + m(1, 2) + m(1, 3), modu)
contains
  function modmatmul(x, y) result(res)
    integer(8), intent(in) :: x(3, 3), y(3, 3)
    integer(8) :: tmp, res(3, 3)
    integer :: j, k
    do j = 1, 3
      res(1, j) = 0
      res(2, j) = 0
      res(3, j) = 0
      do k = 1, 3
        tmp = y(k, j)
        res(1, j) = res(1, j) + x(1, k) * tmp
        res(2, j) = res(2, j) + x(2, k) * tmp
        res(3, j) = res(3, j) + x(3, k) * tmp
      end do
      res(1, j) = mod(res(1, j), modu)
      res(2, j) = mod(res(2, j), modu)
      res(3, j) = mod(res(3, j), modu)
    end do
  end
  function modmatpow(x, n) result(res)
    integer(8), intent(in) :: x(3, 3)
    integer, intent(in) :: n
    integer(8) :: res(3, 3), tmp(3, 3)
    integer :: m
    res(1, 1) = 1
    res(2, 1) = 0
    res(3, 1) = 0
    res(1, 2) = 0
    res(2, 2) = 1
    res(3, 2) = 0
    res(1, 3) = 0
    res(2, 3) = 0
    res(3, 3) = 1
    tmp = x
    m = n
    do while (m > 0)
      if (btest(m, 0)) res = modmatmul(res, tmp)
      tmp = modmatmul(tmp, tmp)
      m = rshift(m, 1)
    end do
  end
end program redistribution

Measured memory_bytes: 2880
#include <cstdio>
#include<iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;

const int maxe=1e4+100;
struct point
{
    int x,y;
};
struct edge
{
    int to,w,next;
} e[maxe<<1];
int head[maxe],cnt,N;
point a[110],b[110];

void init()
{
    memset(head,-1,sizeof(head));
    cnt=-1;
}

void add_edge(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void _add(int u,int v,int w)
{
    add_edge(u,v,w);
    add_edge(v,u,0);
}

int depth[maxe];
bool bfs()
{
    memset(depth,-1,sizeof(depth));
    depth[0]=0;
    queue<int> que;
    que.push(0);
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u]; i!=-1; i=e[i].next)
        {
            int v=e[i].to;
            if(depth[v]==-1&&e[i].w>0)
            {
                depth[v]=depth[u]+1;
                que.push(v);
            }
        }
    }
    if(depth[N*2+1]==-1)
        return false;
    return true;
}
int dfs(int u,int flow)
{
    if(u==N*2+1)
        return flow;
    int ret=0;
    for(int i=head[u]; i!=-1&&flow; i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].w>0&&depth[u]+1==depth[v])
        {
            int tmp=dfs(v,min(e[i].w,flow));
            if(tmp>0)
            {
                ret+=tmp;
                e[i].w-=tmp;
                e[i^1].w+=tmp;
                flow-=tmp;
            }
        }

    }
    return ret;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        ans+=dfs(0,INF);
    }
    return ans;
}

int main()
{

    scanf("%d",&N);
    for(int i=1; i<=N; i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1; i<=N; i++)
    {
        scanf("%d%d",&b[i].x,&b[i].y);

    }

    init();
    for(int i=1; i<=N; i++)
    {
        _add(0,i,1);
        _add(i+N,N*2+1,1);
        for(int j=1; j<=N; j++)
        {

            if(a[i].x<b[j].x&&a[i].y<b[j].y)
            {
                _add(i,j+N,1);
            }

        }
    }

    printf("%d\n",dinic());

    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
using namespace std;
int main(){
    string t;
    int n,cnt=0;
    cin>>n>>t;
    while(n--){
        string w;
        cin>>w;
        for(int i=0;i<w.length();i++){
            bool breakFlag=false;
            for(int j=1;j<200;j++){
                bool outSideFlag=false,goalFlag=true;
                for(int k=0;k<t.length();k++){
                    if(i+k*j>=w.length()){
                        outSideFlag=true;
                        break;
                    }
                    if(t[k]!=w[i+k*j]){
                        goalFlag=false;
                        break;
                    }

                }
                if(outSideFlag)break;
                if(goalFlag){
                    cnt++;
                    breakFlag=true;
                    break;
                }
            }
            if(breakFlag)break;
        }
    }
    cout<<cnt<<endl;
}

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

const double EPS = 1.0e-12;

struct Point {
  public:
    double x, y;
    Point() {};
    Point(double _x, double _y) : x(_x), y(_y) {};
    Point operator+(const Point &rhs) const {
      return Point(this->x + rhs.x, this->y + rhs.y);
    }
    Point operator-(const Point &rhs) const {
      return Point(this->x - rhs.x, this->y - rhs.y);
    }
    Point operator*(double rhs) const {
      return Point(this->x * rhs, this->y * rhs); 
    }
};

Point intersect(Point &a0, Point &a1, Point &b0, Point &b1, int &err) {
  Point p;
  double s, t;
  Point a01 = a1 - a0;
  Point b10 = b0 - b1;
  Point c = b0 - a0;
  double det = a01.x * b10.y - a01.y * b10.x;
  
  err = 0;
  if (abs(det) < EPS) { // two lines are parallel
    err = 1;
  } else {
    s = (b10.y * c.x - b10.x * c.y) / det;
    t = (a01.x * c.y - a01.y * c.x) / det;
    if (s < -EPS || s > 1.0 + EPS || t < -EPS || t > 1.0 + EPS) {
      err = 2;
    }
    p = a0 + a01 * s;
  }
  return p;
}

double triangleArea(Point &a, Point &b, Point &c) {
  Point ab = b - a;
  Point ac = c - a;
  return abs(ab.x * ac.y - ab.y * ac.x) * 0.5;
}

int main() {
  int err;
  double area;
  Point p[6];
  Point a, b, c;
  while (1) {
    cin >> p[0].x >> p[0].y;
    cin >> p[1].x >> p[1].y;
    if (!p[0].x && !p[0].y && !p[1].x && !p[1].y) {
      break;
    }
    for (int i=2; i<6; i++) {
      cin >> p[i].x >> p[i].y;
    }
    a = intersect(p[0], p[1], p[2], p[3], err);
    if (!err) b = intersect(p[2], p[3], p[4], p[5], err);
    if (!err) c = intersect(p[4], p[5], p[0], p[1], err);
    if (err) {
      cout << "kyo" << endl;
    } else {
      area = triangleArea(a, b, c);
      if (area < EPS) {
        cout << "kyo" << endl;
      } else if (area < 100000) {
        cout << "syo-kichi" << endl;
      } else if (area < 1000000) {
        cout << "kichi" << endl;
      } else if (area < 1900000) {
        cout << "chu-kichi" << endl;
      } else {
        cout << "dai-kichi" << endl;
      }
    }
  }
}

Measured memory_bytes: 1212
#include<stdio.h>

int main(){
	int d[2][102][102];
	int i,j,k;
	int w,h;
	while(1){
	scanf("%d %d",&w,&h);
		if(w==0)return 0;
	for(i=0;i<w+2;i++)for(j=0;j<h+2;j++)for(k=0;k<2;k++)d[k][i][j]=0;
	d[0][2][2]=1;
	d[1][2][2]=1;
	d[0][2][3]=1;
	d[1][2][3]=1;
	d[0][3][2]=1;
	d[1][3][2]=1;
	d[0][3][3]=1;
	d[1][3][3]=1;
	for(i=2;i<w+2;i++)for(j=2;j<h+2;j++){
		d[0][i][j]=(d[0][i][j]+d[1][i-2][j]+d[1][i-2][j-1]+d[0][i][j-2])%100000;
		d[1][i][j]=(d[1][i][j]+d[1][i-2][j]+d[0][i-1][j-2]+d[0][i][j-2])%100000;
	}
	printf("%d\n",(d[0][w+1][h]+d[1][w][h+1])%100000);
	}
}

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

char change(char c, int n) {
    char new_c;
    int diff = (int)('Z' - c);
    if (diff >= n) {
        new_c = (char)(c + n);
    } else {
        new_c = (char)('A' - 1 + (n - diff));
    }
    return new_c;
}

void solve() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  string str;
  cin >> n >> str;

  for (int i = 0; i < str.size(); i++) {
    str[i] = change(str[i], n);
  }
  cout << str << endl;
}

int main() {
  solve();
}


Measured memory_bytes: 256
#line 2 "header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

// template version 2.0
using namespace std;
#include <bits/stdc++.h>

// varibable settings
const long long INF = 1e18;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T>
inline void chmax(T &a, const T &b) {
    if ((a) < (b)) (a) = (b);
}
template <class T>
inline void chmin(T &a, const T &b) {
    if ((a) > (b)) (a) = (b);
}

#define divceil(a, b) ((a) + (b)-1) / (b)
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x)    \
    sort(all(x)); \
    x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef long double ld;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
    }
} fast;
void check_input() {
    assert(cin.eof() == 0);
    int tmp;
    cin >> tmp;
    assert(cin.eof() == 1);
}

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "solve.cpp"
template<class T=ll> using vec = vector<T>;


int solve() {
    string s;cin>>s;
    reverse(all(s));
    int n = sz(s);

    vector<string> t(4);
    t[0] = "dream";
    t[1] = "dreamer";
    t[2] = "erase";
    t[3] = "eraser";
    rep(i, 4) reverse(all(t[i]));

    int cur = 0;
    dump(s);
    dump(s.find("a", 2));
    while(cur<n){
        bool valid = false;
        rep(i, 4){
            dump(s.find(t[i], cur), t[i], cur);
            if (s.find(t[i], cur)==cur){
                cur += sz(t[i]);
                dump(i, cur);
                valid = true;
                break;
            }
        }
        if (!valid){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

    return 0; 
}


int main(){/*{{{*/
    solve();
    check_input();
    return 0;
}/*}}}*/


Measured memory_bytes: 512
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
using namespace std;
#define ll long long
int n;
signed main(){
	cin>>n;
	int p=ceil((long double)n/1000);
	int ans=p*1000-n;
	cout<<ans<<endl;
	return 0;
} 

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

using namespace std;

#define white first
#define black second

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

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

int N, M;
vector<int> adjList[MAX_N], children[MAX_N];
pi down[MAX_N], up[MAX_N];
vector<pi> downs[MAX_N], pre[MAX_N], su[MAX_N];

namespace modOp {
    int add(int a, int b, int mod = M) {return (a + b) % mod; /*int r = a + b; if (r >= mod) r -= mod; return r;*/}
    void ADD(int& a, int b, int mod = M) {a = (a + b) % mod; /*a += b; if (a >= mod) a -= mod;*/}
    int sub(int a, int b, int mod = M) {return (a - b + mod) % mod; /*int r = a - b; if (r < 0) r += mod; return r;*/}
    void SUB(int& a, int b, int mod = M) {a = (a - b + mod) % mod; /*a -= b; if (a < 0) a += mod;*/}
    int mul(int a, int b, int mod = M) {return (ll)a * b % mod;}
    void MUL(int& a, int b, int mod = M) {a = (ll)a * b % mod;}
}
using namespace modOp;

pi merge(pi& a, pi& b) {
	pi res;
	res.white = mul(a.white, b.white);
	res.black = add(mul(a.black, add(b.white, b.black)), mul(a.white, b.black));
	return res;
}

pi process(pi p) {
	return {p.white, add(p.black, p.white)};
}

void dfs1(int u, int p) {
	pi res = {1, 0};
	for (int v: adjList[u]) {
		if (v != p) {
			children[u].push_back(v);
			dfs1(v, u);
			res = merge(res, down[v]);
			downs[u].push_back(down[v]);
		}
	}
	int w = res.white;
	int b = add(res.black, res.white);
	down[u] = {w, b};
}

void dfs2(int u, int p) {
	for (int i = 0; i < children[u].size(); ++i) {
		pi res = {1, 0};
		if (i != 0) {
			res = merge(res, pre[u][i - 1]);
		}
		if (i != downs[u].size() - 1) {
			res = merge(res, su[u][i + 1]);
		}
		if (u != 1)  {
			res = merge(res, up[u]);
		}
		int v = children[u][i];
		up[v] = {res.white, add(res.black, res.white)};
		dfs2(v, u);
	}
}

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

	dfs1(1, -1);

	for (int u = 1; u <= N; ++u) {
		pi p = {1, 0};
		for (int i = 0; i < children[u].size(); ++i) {
			p = merge(p, downs[u][i]);
			pre[u].push_back(p);
		}
		p = {1, 0};
		for (int i = children[u].size() - 1; i >= 0; --i) {
			p = merge(p, downs[u][i]);
			su[u].push_back(p);
		}
		reverse(su[u].begin(), su[u].end());
	}

	dfs2(1, -1);

	for (int u = 1; u <= N; ++u) {
		pi res = {1, 0};
		if (u != 1) {
			res = merge(res, up[u]);	
		}
		if (!children[u].empty()) {
			res = merge(res, pre[u].back());
		}
		res = process(res);
		cout << res.black << '\n';
	}

	return 0;
}

Measured memory_bytes: 35328
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
V = []


def set_inputs():
    global N, V
    N = get_int()
    V = get_li()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    x = V[0::2]
    y = V[1::2]
    x_counter = Counter(x)
    y_counter = Counter(y)
    x_val, x_cnt = x_counter.most_common(1)[0]
    y_val, y_cnt = y_counter.most_common(1)[0]
    ans = N - x_cnt - y_cnt
    if x_val == y_val:
        if len(x_counter) == 1:
            if len(y_counter) == 1:
                ans = N // 2
            else:
                _, y_cnt = y_counter.most_common(2)[1]
                ans = N - x_cnt - y_cnt
        else:
            if len(y_counter) == 1:
                _, x_cnt = x_counter.most_common(2)[1]
                ans = N - x_cnt - y_cnt
            else:
                _, x_cnt_2 = x_counter.most_common(2)[1]
                _, y_cnt_2 = y_counter.most_common(2)[1]
                ans = min(N - x_cnt - y_cnt_2, N - x_cnt_2 - y_cnt)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()


Measured memory_bytes: 64584
#include <bits/stdc++.h>
#define endl        '\n'
#define db          double
#define ld          long double
#define ll          long long
#define ull         unsigned long long
#define sqr(x)      (x) * (x)
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)   ((a/gcd(a,b)) * b)
#define pf(x) 		push_front(x)
#define pb(x)       push_back(x)
#define eb(x)		emplace_back(x)
#define all(x)      (x).begin(), (x).end()
#define rall(x) 	(x).rbegin(), (x).rend()
#define sz(x) 		(int)x.size()
#define debug(x) 	cerr << #x << " = " << (x) <<endl
#define unsyncIO    ios_base::sync_with_stdio(0); cin.tie(0)

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

using namespace std;

int main()
{
    //freopen("/home/taalpatar_shepai/Documents/my_codes/out.txt", "w", stdout);
    unsyncIO;
    int x;
    cin >> x;
    for (int i = 0; i < 100000; i++) {
        if(x <= (i*(i+1)) / 2) {
            cout << i << endl;
            break;
        }
    }
        return 0;
}


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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

namespace IO {
    #define gc getchar()
    template <typename T>
    inline void read(T& x) {
        x = 0; bool f = 1; char ch;
        for (ch = gc; ch < '0' || '9' < ch; ch = gc) if (ch == '-') f ^= 1;
        for (; '0' <= ch && ch <= '9'; ch = gc) x = (x << 3) + (x << 1) + (ch ^ 48);
        x = f ? x : -x;
    }
    #undef gc
}
int x;
int main() {
    IO::read(x);
    puts(x >= 30 ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 3588
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::cmp::{min, max};
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
   input!{
       a:i32, b:i32, c:i32,
   } 
   let ans = max(0, c - (a - b));
   println!("{}", ans);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

Measured memory_bytes: 8572