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


int b()
{
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    
    while(true)
    {
        c = c - b;
        if(c <= 0)
        {
            std::cout << "Yes" << std::endl;
            break;
        }
        
        a = a - d;
        if(a <= 0)
        {
            std::cout << "No" << std::endl;
            break;
        }
    }
    
    return 0;
}

int main(int argc, const char * argv[])
{
    b();
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
#define P pair<int,int>
using namespace std;
int a[100000],b[100000],c[100010];
signed main(){
	int n;
	cin>>n;
	int z=n;
	f(i,n) cin>>a[i];
	f(i,n){
		cin>>b[i];
		c[i]=a[i]-b[i];
	}
	sort(c,c+n);
	c[n]=0;
	int i=0;
	for(;i<n&&c[i]<0;i++){
		while(c[i]<0){
			if(c[z]==0) z--;
			if(c[z]<=0){
				puts("-1");
				return 0;
			}
			int zz=c[i]+c[z];
			c[i]+=min(c[i]*-1,c[z]);
			c[z]=zz-c[i];
		}
	}
	cout<<i+n-z<<endl;
	return 0;
}


Measured memory_bytes: 2560
class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

MOD = 10**9+7

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    primeOpt = PrimeOptimizer()
    D = {}
    for i in range(n):
        prime_num_mapping = primeOpt.prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum([L * mod_inv(x) % MOD for x in a])
    return res % MOD

N = int(input())
A = list(map(int, input().split()))
print(solve(N, A))

Measured memory_bytes: 4596
#include <stdio.h>

int main(){	
	int num;
	scanf("%d", &num);

	if(num/100==7){
		printf("Yes\n");
	} else if(num/10%10==7){
		printf("Yes\n");
	} else if(num%10==7){
		printf("Yes\n");
	} else{
		printf("No\n");
	}
	
	
	return 0;
}

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

int main(void) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if (a+b+c >= 22) {
        printf("bust\n");
    } else {
        printf("win\n");
    }

    return 0;
}


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

int main(){
string S;
cin >> S;
int count1 = 0, count0 = 0;


  for(int i = 0; i < S.size(); i++){
 
    // 一桁目1の場合
   //偶数番目は0
    if(i % 2 == 1){
     if(S.at(i) == '1'){
     count1++;
     }
    }

    //奇数番目は1
    if(i % 2 == 0){
     if(S.at(i) == '0'){
     count1++;
     }
    }
    
    // 一桁目0の場合
   //偶数番目は1
    if(i % 2 == 1){
     if(S.at(i) == '0'){
     count0++;
     }
    }

    //奇数番目は1
    if(i % 2 == 0){
     if(S.at(i) == '1'){
     count0++;
     }
    }
    
    //　1ケタ目0の場合
   
    
  }
if(count1 > count0){
  cout << count0 << endl;
}else{
   cout << count1 << endl; 
}

 }

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


int main() {
    int a,b,ans=0;
    cin>>a>>b;
    
    if(b == 1) ans = 0;
    
    else{
        if(b-a<=0) ans = 1;
        
        else{
            b = b-a;
            ans += 1;
            if(b%(a-1) == 0){
                ans += (b/(a-1));
            }
            else{
                ans += (b/(a-1)) + 1;
            }
        }
    }
    
       
    cout<<ans<<endl;
    return 0;
}



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

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

#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int N = 100000;
const int oo = 0x3f3f3f3f;

template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int n, h;
bool vis[N + 5];
int deg[N + 5][2];

int fa[N + 5];
int findset(int u) {
    return fa[u] == u ? u : fa[u] = findset(fa[u]);
}

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif

    n = read<int>();
    h = read<int>();

    for(int i = 0; i <= (h<<1); ++i) fa[i] = i;

    for(int i = 1; i <= n; ++i) {
        int a, b, c, d, x, y;
        a = read<int>(); b = read<int>();
        c = read<int>(); d = read<int>();

        if(c == 0) x = h - a; else x = h + c;
        if(d == 0) y = h + b; else y = h - d;

        ++ deg[x][0], ++ deg[y][1];
        fa[findset(x)] = findset(y);
    }

    vector<int> t0, t1;
    for(int i = 0; i < h; ++i) {
        if(deg[i][0] < deg[i][1]) return puts("NO"), 0;
        if(deg[i][0] > deg[i][1]) {
            vis[findset(i)] = true;
        }
    }

    for(int i = h; i <= (h << 1); ++i) {
        if(deg[i][0] > deg[i][1]) return puts("NO"), 0;
        if(deg[i][0] < deg[i][1]) {
            vis[findset(i)] = true;
        }
    }

    for(int i = 0; i <= (h << 1); ++i) {
        if(i == findset(i) && deg[i][0] + deg[i][1] && !vis[i]) 
            return puts("NO"), 0;
    }
    puts("YES");

    return 0;
}


Measured memory_bytes: 256
from itertools import product

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

ans = 0
for row in product([0,1], repeat=h):
    for col in product([0,1], repeat=w):
        cnt = 0
        for i in range(h):
            if row[i] == 1:
                continue
            for j in range(w):
                if col[j] == 1:
                    continue
                if grid[i][j] == '#':
                    cnt += 1
        if cnt == k:
            ans += 1

print(ans)


Measured memory_bytes: 9096
#include<cstdio>

int N,Last;
long long Ans;

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int x;
        scanf("%d",&x);
        if(x<Last)
            Ans+=x,Last=x%2;
        else
            Ans+=Last+(x-Last)/2,Last=(x-Last)%2;
    }
    printf("%lld",Ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define endl '\n'
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

signed main(void){
    int a,b,c; cin>>a>>b>>c;
    if(a==b and b==c){
        if(a%2==0)cout<<-1<<endl;
        else cout<<0<<endl;
    }else{
        int ans=0;
        while(true){
            if(a%2==1 or b%2==1 or c%2==1)break;
            int d=a/2,e=b/2,f=c/2;
            a=e+f;
            b=d+f;
            c=d+e;
            ans++;
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rrep(i,n) REP(i,1,n+1)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
typedef vector<ll> Vl;
typedef vector<int> VI;
typedef tuple<int, int, int> TT;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
const int MAX = 500000;
const int inf = 1000000007;
const ll mod = 1000000007;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

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




int n, ans;
map <string, bool> mp;

int main() {

	cin >> n;

	rep(i, n) {
		string s;
		cin >> s;
		if (!mp[s]) {
			mp[s] = true;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 19100
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
char in[110000];
int cnt[4];
int main(){
	scanf("%s",in);
	for(int i=0;in[i];i++)cnt[in[i]-'a']++;
	std::sort(cnt,cnt+3);
	if(cnt[2]-cnt[0]>1)printf("NO\n");else printf("YES\n");
}

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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T &b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T &b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { 1,  0, -1,  0,  1, -1,  1, -1};
static const int dy[8] = { 0,  1,  0, -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;

const int maxn = 1e5+5;

struct Edge{
    int v,w,c;
    Edge(int v,int w,int c):v(v),w(w),c(c){;}
};

vector<int> G[maxn];
vector<Edge> edges;

int c[maxn];
int vis[maxn];
int maxcolor = 1;

void cal(int v, int e,int color){
    vis[v] = 1;

    //if(c[e]  == -1){
    c[e] = color;
    maxcolor = max(maxcolor,color);
    //}else{
        //color = -1;
    //}

    int i = 1;
    for(auto a:G[v]){
        if(i == color && a != e) i++;
        Edge ee = edges[a];
        int w = ee.v;
        if(w == v) w = ee.w;

        if(vis[w] == -1){
            cal(w,a,i);
            i++;
        }
    }
}

int main()
{
    int num;scanf("%d",&num);
    _for(i,0,num-1){
        int a,b;
        scanf("%d %d",&a,&b);
        Edge edge(a,b,-1);
        edges.PB(edge);
        int m = edges.size() - 1;
        G[a].PB(m);
        G[b].PB(m);
    }

    memset(c,-1,sizeof(c));
    memset(vis,-1,sizeof(vis));

    cal(edges[0].v,0,1);
    printf("%d\n",maxcolor);
    _for(i,0,num-1){
        printf("%d\n",c[i]);
    }

    return 0;
}

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

class Program
{
    static void Main(string[] args)
    {
        var N = long.Parse(Console.ReadLine());
        var max = Math.Sqrt(N);
        var sum = 0L;
        // N = m * r + r = r(m+1)
        // r <= m であることに注意する
        for (long r = (long)max; r >= 1; r--)
        {
            if (N % r != 0) continue;

            var A = N / r;
            var m = A - 1;
            if (r < m)
                sum += m;
        }

        Console.WriteLine(sum);
    }
}



Measured memory_bytes: 13140
#include<iostream>
#include<stdio.h>

using namespace std;

double mul(double x1, double y1, double x2, double y2)
{
	return x1*x2+y1*y2;
}

int main(void)
{
	double x1,x2,y1,y2,xq,yq;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf",&x1,&y1,&x2,&y2,&xq,&yq)!=EOF){
		double sx,sy;
		double t;
		double rx,ry;
		t=mul(xq-x1,yq-y1,x2-x1,y2-y1)/mul(x2-x1,y2-y1,x2-x1,y2-y1);
		sx=t*(x2-x1)+x1;
		sy=t*(y2-y1)+y1;
		rx=2*sx-xq;
		ry=2*sy-yq;
		printf("%.6lf %.6lf\n",rx,ry);
	}
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
    string a,b,c;
    cin>>a>>b>>c;
    cout<<a[0]<<b[0]<<c[0]<<endl;
}

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

void Main() {
	std::list<vector<int> > ls;
	while (true) {
		vector<int> vec(2);
		cin >> vec[0] >> vec[1];
		if (vec[0] == 0 && vec[1] == 0) {
			break;
		}
		for (int i = 0; i < vec[0]; i++) {
			for (int j = 0; j < vec[1]; j++) {
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}
}

int main() {
	std::cout << std::fixed << std::setprecision(15);
	Main();
}



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

int main(){
  int r0,w0,c,r;
  while(cin>>r0>>w0>>c>>r,c){
    //r0+xR>=wc
    cout<<max(int(ceil(1.0*(w0*c-r0)/r)),0)<<endl;

  }

  return 0;
}

Measured memory_bytes: 3104
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
	public static final int[] vx = {1,0,-1,0};
	public static final int[] vy = {0,-1,0,1};
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int h = sc.nextInt();
		char[][] s = new char[w][h];
		for (int y=0;y<h;y++) {
			String line = sc.next();
			for (int x=0;x<w;x++) {
				s[x][y] = line.charAt(x);
			}
		}
		int n = sc.nextInt();
		Pos2d[] open = new Pos2d[n];
		for(int i=0;i<n;i++) {
			open[i] = new Pos2d(sc.nextInt(),sc.nextInt());
		}

		int ans = -1;
		boolean[][] reach = new boolean[w][h];//壁にめり込むところまでtrue
		reach[0][0] = true;
		if (s[0][0]=='t') {
			ans = 0;
		}
		Queue<Pos2d> q = new ArrayDeque<Pos2d>();
		q.offer(new Pos2d(0,0));
		for(int time=0;time<=n;time++) {
			if (time!=0) {
				s[open[time-1].x][open[time-1].y] = '.';
				if (reach[open[time-1].x][open[time-1].y]) {
					q.offer(open[time-1]);
				}else{
					continue;
				}
			}
			while(!q.isEmpty()) {
				Pos2d p = q.poll();
				for(int i=0;i<4;i++) {
					int nx = p.x + vx[i];
					int ny = p.y + vy[i];
					if (nx>= 0 && nx<w && ny>=0 && ny<h) {
						if (!reach[nx][ny]) {
							reach[nx][ny] = true;
							if (s[nx][ny]=='t') {
								ans = time;
							}else if (s[nx][ny]!='#') {
								q.offer(new Pos2d(nx,ny));
							}
						}
					}
				}
			}
			if (ans!=-1) {
				break;
			}
		}
		System.out.println(ans);
		sc.close();
	}
}
class Pos2d {
	public int x;
	public int y;
	public Pos2d(int x,int y) {
		this.x = x;
		this.y = y;
	}
}

Measured memory_bytes: 57832
<?php

$s = explode(' ',trim(fgets(STDIN)));
$m = [];

array_push($m,abs($s[0]-$s[1]),abs($s[0]-$s[2]),abs($s[1]-$s[2]));
rsort($m);

echo 0 + $m[1] + $m[2];
  
?>

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

int main()
{
	int a[3];
	while(cin>>a[0]>>a[1]>>a[2]&&(a[0]||a[1]||a[2]))
	{
		sort(begin(a),end(a));
		int n;cin>>n;
		int l=a[0]*a[0]+a[1]*a[1];
		
		for(int i=0;i<n;i++)
		{
			int k;cin>>k;
			k*=2;
			k*=k;
			cout<<(l>=k?"NA":"OK")<<endl;
			
		}
	}
	
	
}

Measured memory_bytes: 3084
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(void) {
	while(true) {
		int n, m, p, a, b;
		cin>>n>>m>>p>>a>>b;
		if(n == 0 && m == 0 && p == 0 && a == 0 && b == 0) break;
		--a;
		--b;
		vector<int> card(n);
		REP(i, n) cin>>card[i];
		vector<vector<P> > l(m);
		REP(i, p) {
			int x, y, z;
			cin>>x>>y>>z;
			--x;
			--y;
			l[x].pb(P(y, z));
			l[y].pb(P(x, z));
		}
		vector<vector<double> > d(m, vector<double>(pow(2, n), INF * INF));
		d[a][pow(2, n) - 1] = 0;
		priority_queue<pair<pair<double, ll>, ll>, vector<pair<pair<double, ll>, ll> >, greater<pair<pair<double, ll>, ll> > > que;
		que.push(pair<pair<double, ll>, ll>(pair<double, ll>(0, a), pow(2, n) - 1));
		while(!que.empty()) {
			pair<pair<double, ll>, ll> np = que.top();
			double o = np.first.first;
			ll p = np.first.second;
			que.pop();
			if(d[p][np.second] != o) continue;
			REP(i, l[p].size()) {
				REP(j, n) {
					if((np.second & (int)pow(2, j)) != 0) {
						if(d[l[p][i].first][(np.second ^ (int)pow(2, j))] > d[p][np.second] + (double)l[p][i].second / card[j]) {
							d[l[p][i].first][(np.second ^ (int)pow(2, j))] = d[p][np.second] + (double)l[p][i].second / card[j];
							que.push(pair<pair<double, ll>, ll>(pair<double, ll>(d[l[p][i].first][(np.second ^ (int)pow(2, j))], l[p][i].first), (np.second ^ (int)pow(2, j))));
						}
					}
				}
			}
		}
		double res = INF;
		REP(i, pow(2, n)) {
			res = min(res, d[b][i]);
		}
		if(res != INF) cout<<fixed<<showpoint<<setprecision(39)<<res<<endl;
		else cout<<"Impossible"<<endl;
	}
}

Measured memory_bytes: 5616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
#define MOD 1000000007 //998244353

vp e[100100];// <F:V,  S:length>
vl ans(100100);

void dfs(ll root, ll now){
    vl N;
    for(auto x:e[now]) {
        if(x.F != root) N.PB(x.F);
        else {
            if(x.S%2) ans[now] = (ans[root] != 1);
            else      ans[now] = ans[root];
        }
    }
    for(auto x:N) dfs(now, x);
}

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

    // solution comes here

    ll N;
    cin >> N;
    
    ll u, v, w;
    rep(i, N-1) {
        cin >> u >> v >> w;
        u--;v--;//0-indexed
        e[u].PB({v,w});
        e[v].PB({u,w});
    }

    dfs(0,0);

    rep(i, N) cout << ans[i] << nl;
}


Measured memory_bytes: 15744
n,k=[int(x) for x in input().split(" ")]
ans=0.0
for i in range(1, n+1):
    if i<k:
        j=i
        count=0
        while j<k:
            j*=2
            count+=1
        ans += (1/n)*(1/2)**count
    else:
        ans += (n-k+1)*(1/n)
        break
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int k,ans;
int gcd(int x,int y) {
	if(x%y==0)
		return y;
	else
		return gcd(y,x%y);
}
int main(){
	cin>>k;
	for (int i=1;i<=k;i++)
		for (int j=1;j<=k;j++)
			for (int l=1;l<=k;l++)
				ans+=gcd(gcd(i,j),l);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3644
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int[] a=new int['z'-'a'+1];
			String str=sc.next();
			for(int i=0;i<str.length();i++) a[str.charAt(i)-'a']++;
			boolean flag=true;
			for(int i=0;i<a.length;i++) if(a[i]%2!=0) flag=false;
			if(flag) System.out.println("Yes");
			else System.out.println("No");
		}
	}
}

Measured memory_bytes: 9680
#include <cstdio>

int main()
{
  int n;
  scanf("%d", &n);
  int sum = 0;
  int max = 0;
  for (int i = 0; i < n; ++i)
  {
    int p;
    scanf("%d", &p);
    if (p > max) max = p;
    sum += p;
  }
  printf("%d\n", sum - max / 2);
  return 0;
}

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

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

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

	int n, k; cin >> n >> k;
	int x; cin >> x;
	int mx = x;
	for (int i = 1; i < n; ++i) {
		int y; cin >> y;
		x = __gcd(x, y);
		mx = max(mx, y);
	}
	if (!(k <= mx && k % x == 0)) cout << "IM";
	cout << "POSSIBLE\n";

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int INF = numeric_limits<int>::max();
const ll INFL = numeric_limits<ll>::max();


// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

ll factorial(ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

int main()
{
    int a, b, c; cin >> a >> b >> c;
    int d = a + b + c;
    if (d >= 22) {
        cout << "bust" << endl;
    } else {
        cout << "win" << endl;
    }
    return 0;
}


Measured memory_bytes: 3644
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    ll A, B; cin >> A >> B;
    char C; cin >> C;
    int D; cin >> D;
    B *= 100; B += D;
    ll X = A*B; X /= 100;
    cout << X << nl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

static const long long MOD = 998244353;


int n, k;
vector<pair<int, int> > vec;

int main(void) {
  cin >> n >> k;
  
  for (int i=2; i<=n; i++) vec.pb(mp(1, i));
  int t = ((n-1)*(n-2))/2;
  
  int u = 2, v = u + 1;
  while (t>k) {
    vec.pb(mp(u, v));
    t--;
    v++;
    if (v>n) {
      u++;
      v = u + 1;
    }
  }
  
  if (t!=k) puts("-1");
  else { 
    cout << sz(vec) << "\n";
    for (auto p : vec) printf("%d %d\n", p.first, p.second);
  }

    return 0;
}



Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
dif = 0
sum = 0

for i in range(N - 1):
  if A[i] > A[i + 1]:
    dif = A[i] - A[i + 1]
    sum += dif
    A[i +1] = A[i + 1] + dif
    
print(sum)


Measured memory_bytes: 32248
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int n,m,k,ans,tmp;
int a[22][22];
int b[22],c;

int main()
{
    //freopen("new.txt","r",stdin);
    scanf("%d %d %d",&n,&m,&c);
    for(int i = 1;i <= m;i++)scanf("%d",b + i);
    for(int i = 1;i <=n;i++)
    {
        for(int j = 1;j <= m;j++)scanf("%d",&a[i][j]);
    }
    ans = 0;
    for(int i = 1;i <= n;i++)
    {
        tmp = 0;
        for(int j = 1;j <= m;j++)tmp += b[j]*a[i][j];//printf("b[%d] = %d,a[%d][%d] = %d,tmp = %d\n",j,b[j],i,j,a[i][j],tmp);
        tmp += c;
        if(tmp > 0)
        {
            //printf("tmp= %d\n",tmp);
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}


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

int main(){
    ll N;
    cin >> N;
    ll zero = 0, two = 0, odd = 0;
    rep(i, 0, N){
        ll a;
        cin >> a;
        if(a % 4 == 0) zero++;
        if(a % 4 == 2) two++;
        if(a % 2 == 1) odd++;
    }
    two = min(1LL, two);
    if(two + odd > zero + 1){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#define PMAX 100
#define TMAX 100
#define CMAX 10
using namespace std;
#define EPS 0.0001

struct Point{ int x, y;};

class Territory{
    public:
    int npoint;
    string cname;
    Point points[PMAX];
    Territory(){}
    Territory(string cname):cname(cname){
	npoint = 0;
    }

    void addPoint( int x, int y ){ 
	points[npoint].x = x;
	points[npoint++].y = y;
    }
};

int ncountry, nterritory;
Territory T[TMAX];
map<string, int> M; /* name to id */
bool G[CMAX][CMAX];

bool overlap( Point p1, Point p2, Point p3, Point p4 ){
    double dx1 = (double)p2.x - p1.x;
    double dy1 = (double)p2.y - p1.y;
    double dx2 = (double)p4.x - p3.x;
    double dy2 = (double)p4.y - p3.y;
    double dx3 = (double)p3.x - p1.x;
    double dy3 = (double)p3.y - p1.y;
    if ( dx1*dy2 != dy1*dx2 ) return false;
    if ( dx1*dy3 != dy1*dx3 ) return false;

    if ( p1.x != p2.x ){
	if ( max( p1.x, p2.x ) <= min( p3.x, p4.x ) ||
	     min( p1.x, p2.x ) >= max( p3.x, p4.x ) ) return false;
    }
    if ( p1.y != p2.y ){
	if ( max( p1.y, p2.y ) <= min( p3.y, p4.y ) ||
	     min( p1.y, p2.y ) >= max( p3.y, p4.y ) ) return false;
    }

    return true;
}

bool isAdj( Territory t1, Territory t2 ){
    for ( int i = 0; i < t1.npoint; i++ ){
	for ( int j = 0; j < t2.npoint; j++ ){
	    if ( overlap( t1.points[i], t1.points[(i+1)%t1.npoint],
			  t2.points[j], t2.points[(j+1)%t2.npoint] ) ){
		return true;
	    }
	}
    }
    return false;
}

void makeGraph(){
    for ( int i = 0; i < ncountry; i++ ){
	for ( int j = 0; j < ncountry; j++ ) G[i][j] = false;
    }

    for ( int i = 0; i < nterritory; i++ ){
	for ( int j = 0; j < nterritory; j++ ){
	    if ( T[i].cname == T[j].cname ) continue;
	    if ( isAdj( T[i], T[j] ) ){
		G[M[T[i].cname]][M[T[j].cname]] = true;
		G[M[T[j].cname]][M[T[i].cname]] = true;
	    }
	}
    }
}

int color[CMAX];
bool used[CMAX+1];
int mincolor;

void recursive( int pos, int ncolor ){
    if ( pos == ncountry ){
	mincolor = min( mincolor, ncolor );
	return;
    }

    if ( ncolor >= mincolor ) return;

    bool usedt;

    for ( int c = 1; c <= ncountry; c++ ){
	for ( int v = 0; v < ncountry; v++ ){
	    if ( G[pos][v] && color[v] == c ) goto nextcolor;
	}
	
	usedt = used[c];
	used[c] = true;
	color[pos] = c;
	recursive( pos + 1, usedt ? ncolor : ncolor+1);
	used[c] = usedt;

    nextcolor:;
    } 

}

void compute(){
    makeGraph();

    for ( int i = 0; i <= ncountry; i++ ) used[i] = false;
    for ( int i = 0; i < ncountry; i++ ) color[i] = -1;
    mincolor = ncountry;
    recursive(0, 0);
    cout << mincolor << endl;
}

bool input(){
    ncountry = 0;
    M = map<string, int>();
    string cname;
    int x, y;
    cin >> nterritory;
    if ( nterritory == 0 ) return false;
    for ( int i = 0; i < nterritory; i++ ){
	cin >> cname;
	if ( M.find(cname) == M.end() ) M[cname] = ncountry++;
	T[i] = Territory(cname);
	while( cin >> x, x != -1 ){
	    cin >> y;
	    T[i].addPoint(x, y);
	}
    }
    return true;
}

main(){
    while( input() ) compute();
}

Measured memory_bytes: 1300
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define ld long double
#define PI 3.141592653L
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll INF = (ll)1e18;
const int N = 2e5 + 5;
const ll MOD = 1e9+7;
 
int parent[N];
 
int gcd(int a, int b) { 
    if (a == 0) 
        return b;  
    return gcd(b%a, a);  
} 
   
int lcm(int a, int b) {  
    return (a*b)/gcd(a,b);  
} 
 
ll pow(ll x, ll y, ll p) {
    if(y == 0) return 1;
    ll res = 1;
    x %= p;
    if(x == 0) return 0LL;
    while(y > 0) {
        if(y & 1) res = (res*x) % p;
        y >>= 1;
        x = (x*x) % p;
    }
    return res;
}
 
int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}
 
void Union(int x, int y) {
    int xPar = find(x), yPar = find(y);
    if(xPar != yPar) parent[xPar] = yPar;
}
 
ll nCr(ll n, ll r) {
    ll res = 1;
    for(ll i=1;i<=r;i++) {
        res = res * (n - r + i) / i;
        // is different from
        // res *= (n -r + i) / i;
    }
    return res;
}
 
int ask(int i, int j) {
    cout << "? " << i + 1 << ' ' << j + 1 << endl;
    int v;
    cin >> v;
    return v;
}

void solve() {
    int h, w, ch, cw, dh, dw;
    cin >> h >> w >> ch >> cw >> dh >> dw;
    ch--, cw--, dh--, dw--;
    vector<int> dx = {-1, 0, 1, 0};
    vector<int> dy = {0, 1, 0, -1};
    vector<string> s;
    for(int i=0;i<h;i++) {
        string x;
        cin >> x;
        s.push_back(x);
    }
    vector<vector<int>> dist(h, vector<int>(w, INT_MAX));
    dist[ch][cw] = 0;
    deque<pair<int, int>> dq;
    dq.emplace_back(ch, cw);
    while(!dq.empty()) {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();
        int d = dist[x][y];
        for(int i=0;i<4;i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
            if(s[nextX][nextY] == '#') continue;
            if(dist[nextX][nextY] <= d) continue;
            dist[nextX][nextY] = d;
            dq.emplace_front(nextX, nextY);
        }
        for(int i=-2;i<=2;i++) {
            for(int j=-2;j<=2;j++) {
                int nextX = x + i;
                int nextY = y + j;
                if(nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
                if(s[nextX][nextY] == '#') continue;
                if(dist[nextX][nextY] <= d + 1) continue;
                dist[nextX][nextY] = d + 1;
                dq.emplace_back(nextX, nextY);
            }
        }
    }
    int res = dist[dh][dw];
    if(res == INT_MAX) res = -1;
    cout << res << endl;
    return;
} 
 
int main()
{
    IOS
    //int t;
    //cin >> t;
    //while(t--) 
    solve();
    return 0; 
}

Measured memory_bytes: 8640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e14;

signed
main(){
		int n;
		cin >> n;
		vector<ll> p(n+1);
		for(int i=0;i<n;i++)
		{
				cin >> p[i] >> p[i+1];
		}
		vector<vector<ll> > m(n+1,vector<ll>(n+1, INF));

		for(int i=1;i<=n;i++)	m[i][i] = 0;

		for(int sa=1;sa<n;sa++)
		{
				for(int fi=1;fi<=n-sa;fi++)
				{
						int la = fi + sa;
						for(int medi=fi;medi<=la-1;medi++)
						{
								m[fi][la] = min(m[fi][la],m[fi][medi] + m[medi+1][la] + p[fi-1]*p[medi]*p[la]  );
						}
						
				}
		}

		cout << m[1][n] << endl;
}


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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define dep(i, a, n) for(int i = a; i >= (n); i--)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll a, b, c;
  string result = "Close";
  cin >> a >> b >> c;
  if((a == 1 && b == 1) || c == 1) result = "Open";
  cout << result << endl;
	return 0;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" = "<<(x)<<endl
using vi = vector<int>;
using vvi = vector<vi>;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
using vb = vector<bool>;

int main(){
  int N,Q;
  cin>>N>>Q;
  vvi G(N);
  vi pt(N, 0);
  vb seen(N, false);
  for(int i=0; i<N-1; i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].pb(b);
    G[b].pb(a);
  }
  for(int i=0; i<Q; i++){
    int p,x;
    cin>>p>>x;
    p--;
    pt[p] += x;
  }

  queue<int> que;
  que.push(0);

  while(!que.empty()){
    int now = que.front();
    que.pop();
    seen[now] = true;

    for(int next: G[now]){
      if(seen[next])continue;
      pt[next] += pt[now];
      que.push(next);
    }
  }

  for(int x: pt){
    cout<<x<<endl;
  }
}

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

using namespace std;
using ll = long long;

#define rep(i,n) for(int i=0;i<(n);++i)
const int MOD = 1e9+7;

int main() {
  int N, M; cin >> N >> M;

  int S[N], T[M];
  rep(i, N) cin >> S[i];
  rep(i, M) cin >> T[i];
  ll dp[N+1][M+1];
  ll sum[N+2][M+2];

  memset(dp, 0, sizeof(dp));
  memset(sum, 0, sizeof(sum));
  int ans = 0;
  dp[0][0] = 1;
  sum[1][1] = 1;
  rep(i, N+1) {
    rep(j, M+1) {
      if (i == 0 && j == 0)
        continue;
      if (i >= 1 && j >= 1 && S[i-1] == T[j-1])
        dp[i][j] = sum[i][j];
      else
        dp[i][j] = 0;

      sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i][j] + MOD) % MOD;
    }
  }
  cout << sum[N+1][M+1] << endl;

  return 0;
}


Measured memory_bytes: 62848
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let s = read::<String>().chars().collect::<Vec<_>>();
    let mut k = read::<u32>();

    let mut ans = Vec::new();
    for i in 0..s.len() - 1 {
        let ch = s[i];
        let mut num = ch.to_digit(36).unwrap() - 10;
        if num != 0 && 26 - num <= k {
            k -= 26 - num;
            num = 0;
        }
        ans.push(std::char::from_digit(num + 10, 36).unwrap());
    }
    k %= 26;
    let num = s[s.len() - 1].to_digit(36).unwrap() - 10;
    ans.push(std::char::from_digit((num + k) % 26 + 10, 36).unwrap());
    for ch in ans {
        print!("{}", ch);
    }
    println!("");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
import java.util.*;
import java.io.PrintWriter;
public class Main{
	static ArrayList<Integer>[] list;
	static boolean[] visited;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		list=new ArrayList[n];
		visited=new boolean[n];
		int[] ans=new int[n];
		for(int i=0; i<n; i++){
			list[i]=new ArrayList<>();
		}
		for(int i=0; i<m; i++){
			int a=sc.nextInt()-1;
			int b=sc.nextInt()-1;
			list[a].add(b);
			list[b].add(a);
		}
		ArrayDeque<Integer> q=new ArrayDeque<>();
		q.add(0);
		visited[0]=true;
		while(!q.isEmpty()){
			int now=q.poll();
			for(int i:list[now]){
				if(!visited[i]){
					visited[i]=true;
					ans[i]=now;
					q.add(i);
				}
			}
		}
		System.out.println("Yes");
		for(int i=1; i<n; i++){
			System.out.println(ans[i]+1);
		}
	}
}


Measured memory_bytes: 77632
N, M = map(int, input().split())
A = [None] * N
B = [None] * N
C = [None] * N
for i in range(N):
  A[i], B[i] = map(int, input().split())
  C[i] = [A[i], B[i]]
C = sorted(C)

count = 0
price = 0
for i in range(N):
  price += C[i][0] * C[i][1]
  count += C[i][1]
  if (count >= M):
    break

price -= (count - M) * C[i][0]


print(price)

Measured memory_bytes: 59096
#include <bits/stdc++.h>
#define sz size
#define pb push_back
#define mper make_pair
#define PI 3.14159
#define fe first
#define se second
#define ll long long
//#define forik(i, a, b) for(ll i = a; i <= b; ++i)
#define vl vector<ll>
#define pll pair<ll, ll>
#define mal ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
using namespace std;

string s;

bool a, b, c, d;

int main() {

mal

cin >> s;

for(int i = 0; i < s.sz(); ++i) {

    if(s[i] == 'N') {a = 1;}
    else if(s[i] == 'S') {b = 1;}

    else if(s[i] == 'E') {c = 1;}

    else if(s[i] == 'W') {d = 1;}
}

if(a == b && c == d) cout << "Yes";
else cout << "No";

return 0;
}


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

#define D 6

void North(int dice[D]){
	int tmp=dice[0];
	dice[0]=dice[1];
	dice[1]=dice[5];
	dice[5]=dice[4];
	dice[4]=tmp;
}
void East(int dice[D]){
	int tmp=dice[0];
	dice[0]=dice[3];
	dice[3]=dice[5];
	dice[5]=dice[2];
	dice[2]=tmp;
}
void West(int dice[D]){
	int tmp=dice[0];
	dice[0]=dice[2];
	dice[2]=dice[5];
	dice[5]=dice[3];
	dice[3]=tmp;
}
void South(int dice[D]){
	int tmp=dice[0];
	dice[0]=dice[4];
	dice[4]=dice[5];
	dice[5]=dice[1];
	dice[1]=tmp;
}
void Right(int dice[D]){
	int tmp=dice[1];
	dice[1]=dice[2];
	dice[2]=dice[4];
	dice[4]=dice[3];
	dice[3]=tmp;
}
void Left(int dice[D]){
	int tmp=dice[1];
	dice[1]=dice[3];
	dice[3]=dice[4];
	dice[4]=dice[2];
	dice[2]=tmp;
}

int main(){
	int N;
	char command[10];
	int dice[D];
	int score=1;

	for(int i=0;i<D;i++){
		dice[i]=(i+1);
	}

	while(scanf("%d",&N)){
		if(N==0){break;}

		for(int i=0;i<D;i++){
			dice[i]=(i+1);
		}
		score=1;

		for(int i=0;i<N;i++){
			scanf("%s",&command);
			if(strcmp(command,"North")==0){
				North(dice);
			}else if(strcmp(command,"East")==0){
				East(dice);
			}else if(strcmp(command,"West")==0){
				West(dice);
			}else if(strcmp(command,"South")==0){
				South(dice);
			}else if(strcmp(command,"Right")==0){
				Right(dice);
			}else{
				Left(dice);
			}
			score+=dice[0];
		}
		printf("%d\n",score);
	}

	return 0;
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int h, w;
int dp[1001][1001];
char grid[1001][1001];
int main(){
    cin>>h>>w;

    for(int x=1;x<=h;x++){
        for(int y = 1; y<=w;y++){
            cin>>grid[x][y];
        }
    }
    dp[1][1] =1;
    for(int x=2;x<=w;x++)
        if(grid[1][x] == '.')
            dp[1][x] = dp[1][x-1];
    for(int x=2;x<=h;x++){
        for(int y=1;y<=w;y++){
            if(grid[x][y] == '#') continue;
            dp[x][y] += dp[x-1][y];
            dp[x][y] += dp[x][y-1];
            dp[x][y] %= mod;
        }
    }
    cout<<dp[h][w];


}


Measured memory_bytes: 8460
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

vint a, f;
int n;
ll k;

bool check(ll x) {
    ll ct = 0;
    rep(i,n) ct += max((ll)0,a[i]-x/f[i]);
    return ct <= k;
}

int main() {
    cin >> n >> k;
    a.resize(n); 
    f.resize(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> f[i];
    sort(rall(a));
    sort(all(f));
    ll l = -1;
    ll r = inf_l;
    while (r-l > 1) {
        ll mid = (l+r)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;
}

Measured memory_bytes: 4744
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;
int main(){
	int R[MAX],n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> R[i];
	int maxv = -2000000000;
	int minv = R[0];
	for (int i = 1; i < n; i++){
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}
	cout << maxv << endl;
	return 0;
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
#include <vector>
#include <string>
using namespace std;
#define FL(i,a,b) for(int i = a;i<b;i++)
typedef vector<int> vi;

const int inf = numeric_limits<int>::max();


int main(){
    long int n;
    cin>>n;
    int k;
    cin>>k;
    int arr[n];
    FL(i,0,n){
        cin>>arr[i];
    }
    int cost[n];
    FL(i,0,n){
        cost[i] = inf;
    }
    cost[0] = 0;
    
    cost[1] = abs(arr[1]-arr[0]);
    for(long int i = 2;i<n;i++){
        long int j = i-1;
        while ((i-j<=k)&&(j>=0)){
            cost[i] = min(cost[i],cost[j]+abs(arr[i]-arr[j]));
            j--;
        }
        
    }
    cout<<cost[n-1];
    
    
}

















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

def main():
    while True:
        tmp = input().strip()
        if tmp[0] == "#":
            break
        g, y, m, d = tmp.split()
        y = int(y)
        m = int(m)
        d = int(d)
        if y < 31:
            print(tmp)
        elif y == 31:
            if m <= 4:
                print(tmp)
            else:
                print("?", y-30, m, d)
        else:
            print("?", y-30, m, d)

if __name__ == "__main__":
    main()



Measured memory_bytes: 5636
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {


    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        main3(sc);
    }

    public static void main3(Scanner sc) {

    	int N = sc.nextInt();
        float[] all = new float[N];

        for (int i = 0; i < N; i++) {
        	all[i] = sc.nextFloat();
        }

        Arrays.sort(all);

        float value = (all[0] + all[1])/2;

        for (int i = 2; i < N; i++) {
        	value = (value + all[i])/2;
        }

        System.out.println(value);
    }

}

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

#define INF INT_MAX/2
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;

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

   string S;
   cin>>S;

   int black = 0;
   ll ans = 0;
   for(int i=0;i<S.size();i++){
      if(S[i]=='W'){
         ans += black;
      }
      else{
         black++;
      }
   }
   cout<<ans<<endl;
   return 0;
}


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

const int N = 100000;

int n, p;
int pre[N+1];

int find(int x)
{
    while (x != pre[x])
        x = pre[x];
    return x;
}

int main(void)
{
    while (scanf("%d%d", &n, &p) != EOF) {
        if (!n && !p) break;
        pre[1] = 1;
        for (int i = 2; i <= n; i ++)
            scanf("%d", &pre[i]);
        long long sum = 0;
        for (int i = 1; i <= p; i ++) {
            char s[2];
            int x;
            scanf("%s%d", s, &x);
            if (s[0] == 'M')
                pre[x] = x;
            else
                sum += find(x);
        }
        printf("%lld\n", sum);
    }

    return 0;
}


Measured memory_bytes: 3516
#include<bits/stdc++.h>
using namespace std;
#define pi 2.00*acos(0.00)
int main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	int loh,lom;
	cin>>loh>>lom;
	int h,m;
	cin>>h>>m;
	double mul=(double)h/(double)6+(double)m/(double)360-(double)m/(double)30;
	//cout<<"\n"<<pi/acos(((double)(loh*loh)+(double)(lom*lom)-(double)(4.56425719433005567605
//*4.56425719433005567605))/(2.00*(double)(loh*lom)))<<"\n";
	printf("%.20lf",sqrt((double)(loh*loh)+(double)(lom*lom)-2.00*(double)(loh*lom)*cos(pi*mul)));
	return 0;
}


Measured memory_bytes: 4172