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

#define lint long long
#define P pair<int, int>

int par[100000];
int ran[100000];
int num[100000];

void init(int n){
    for(int i = 0; i < n; ++i){
        par[i] = i;
        ran[i] = 0;
        num[i] = 1;
    }
}

int find(int x){
    if(par[x] == x){
        return  x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y){
        return;
    }
    
    if(ran[x] < ran[y]){
        par[x] = y;
        num[y] += num[x];
    } else {
        par[y] = x;
        num[x] += num[y];
        if(ran[x] == ran[y]){
            ran[x]++;
        }
    }
}

bool same(int x, int y){
    return  find(x) == find(y);
}

int main(){
    lint N, M;
    
    cin >> N >> M;
    
    int A[M], B[M];
    lint listans[M];
    
    init(N);
    
    for(int i = 0; i < M; ++i){
        int a, b;
        cin >> a >> b;
        A[i] = a - 1; B[i] = b - 1;
    }
    
    lint ans = N * (N - 1) / 2;
    
    for(int i = M - 1; i >= 0; --i){
        listans[i] = ans;
        lint a = num[find(A[i])];
        lint b = num[find(B[i])];
        if(!same(A[i], B[i])){
            ans -= (lint)a * b;
        }
        unite(A[i], B[i]);
        
        
    }
    
    for(int i = 0; i < M; ++i){
        cout << listans[i] << endl;
    }
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
long long int MOD = 1000000007;
long long int ruiseki[200001];
int ncrset(){
  ruiseki[0] = 1;
  for(int i=1;i<200001;i++){
    ruiseki[i] = (ruiseki[i-1] * i) % MOD;
  }
}

long long int powld(long long int x,long long int n){
  long long int ans = 1;
  while(n > 0){
    if((n&1) == 1){
      ans = (ans*x)  % MOD;
    }
    x = (x*x) % MOD;
    n >>= 1;
  }
  return ans % MOD;
}

int ncrgyaku(int n,int r){
  long long int gyakuk,gyakur;
  long long int res = 1,x,y,z;
  y = powld(ruiseki[r],MOD-2);
  z = powld(ruiseki[n-r],MOD-2);
  return (((ruiseki[n]*y) % MOD)*z) % MOD;

}
int main()
{
  ncrset();
  ll N,M,dp[100001],d=0,res=0,f=1;
  cin >> N >> M;
  ll D = M;
  dp[0] = 1;
  vector<int> soinsu;
  set<int> soin;
  for(int i=2;M != 1 && i*i <= D;i++){
    while(M % i == 0){
      soinsu.push_back(i);
      soin.insert(i);
      M /= i;
    }
  }
  if(M != 1){
    soinsu.push_back(M);
   	soin.insert(M); 
  }
  d += soinsu.size();
  for(auto itr=soin.begin();itr!=soin.end();itr++){
    f = (f*ncrgyaku(N-1+count(soinsu.begin(),soinsu.end(),*itr),N-1))%MOD;
  
  }
  cout << f << endl;
  return 0;
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}


Measured memory_bytes: 1792
def main():
    C=[]
    for i in range(3):
        C.append((input()))

    line = list(C[1])

    for i in range(int(C[0])):
        if line[i] != line[int(C[2])-1]:
            line[i] = "*"

    ans = ""
    for i in line:
        ans +=i

    return ans

print(main())

Measured memory_bytes: 3064
import math
N, K = map(int, input().split())

t = []

if K > N:
  max = N
  for i in range(max):
    t.append(math.ceil((math.log10(K) - math.log10(i+1))/math.log10(2)))
else:
  max = K
  for i in range(max):
    t.append(math.ceil((math.log10(K) - math.log10(i+1))/math.log10(2)))
  for i in range(N - K):
    t.append(0)

Answer_n = 0
for item in t:
  Answer_n += 0.5**item

Answer = Answer_n / N

print(Answer)


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

int main() {
    int a[4];
    int b[4] = {1, 4, 7, 9};
    for (int i = 0; i < 4; i++) {
        cin >> a[i];
    }
    sort(a, a+4);
    for (int i = 0; i < 4; i++) {
        if (a[i] != b[i]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

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

int main(){
	cin.tie(0);	
	cout.tie(0);	
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	bool val[n + 1] = {};
	val[0] = 1;
	vector<int> moves = {100, 101, 102, 103, 104, 105};
	for(int i = 0;i <= n;++i){
		if(val[i]){
			for(int x: moves){
				if(i + x <= n){
					val[i + x] = 1;
				}
			}
		}
	}
	cout << val[n] << '\n';
}


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


int main(){
	char s1[200],s2[200];
	scanf("%s%s",s1,s2);
	int n=strlen(s1);
	for(int i=0;i<n*2;i++){
		reverse(s1,s1+n-1);
		reverse(s1,s1+n);
		if(!strcmp(s1,s2)){
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
	return 0;
} 

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

int n;
class team {
public:
	string name;
	int win, lose;
	team()
		: win(0), lose(0)
	{
	}
};
bool teamComp(const team& x, const team& y) {
	if (x.win > y.win) return true;
	else if (x.win == y.win && x.lose < y.lose) return true;
	return false;
}

int main () {
	while (cin >> n, n) {
		team teams[n];
		for (int i = 0; i < n; i++) {
			cin >> teams[i].name;
			for (int j = 0; j < n - 1; j++) {
				int x;
				cin >> x;
				switch (x) {
				case 0:
					teams[i].win++;
					break;
				case 1:
					teams[i].lose++;
					break;
				}
			}
		}
		stable_sort(teams, teams + n, teamComp);
		for(team* it = teams; it != teams + n; it++) {
			cout << it->name << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
import std;

alias S = Tuple!(int, "a", int, "b", int, "c", int, "d");

int calc(int n, int m, S[] s) {
    int ans = 0;

    void rec(int last, int p, int[] buf) {
        if (p == buf.length) {
            int t = 0;
            foreach (e; s) {
                int x = buf[e.b - 1] - buf[e.a - 1];
                if (x == e.c) t += e.d;
            }
            ans = max(ans, t);
            return;
        }


        for (int i = last; i <= m; i++) {
            buf[p] = i;
            rec(i, p + 1, buf);
        }
    }

    auto buf = new int[n];
    rec(1, 0, buf);
    return ans;
}

void main() {
    int n, m, q; scan(n, m, q);
    S[] s;
    foreach (_; 0..q) {
        int a, b, c, d; scan(a, b, c, d);
        s ~= S(a, b, c, d);
    }
    writeln(calc(n, m, s));
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

ll gcd(ll a, ll b){
    return (b == 0) ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b){
    ll g = gcd(a, b);
    return (a / g) * (b / g);
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    ll T, A, nT, nA;
    cin >> T >> A;
    for (int i = 1; i < n; i++){
        cin >> nT >> nA;
        ll mul = max((T + nT - 1) / nT, (A + nA - 1) / nA);
        T = nT * mul;
        A = nA * mul;
    }
    cout << T + A << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
#define int long long
#define MOD 1000000007
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1e18
#define For(i,a,b) for (int i = a; i < b; i++)
#define Rep(i,a,b) for (int i = a; i <= b; i++)
#define ps(x,y) fixed << setprecision(y) << x 
#define pb push_back 
#define mp make_pair 

vector<pi> drinks;
 
int32_t main()
{
    fast;
    int n, m, a, b, cost = 0, cans = 0, idx = 0; cin >> n >> m;
    For(i, 0, n) {
        cin >> a >> b;
        drinks.pb({a, b});
    }
    sort(drinks.begin(), drinks.end());
    For(i, 0, n) {
        if(cans >= m) break;
        cans += drinks[i].second;
        idx = i;
    }

    
    For(i, 0, idx) {
        cost += drinks[i].first * drinks[i].second;
        m -= drinks[i].second;
    }

    cost += drinks[idx].first * (m);

    cout << cost << "\n";
     
    return 0;
}

Measured memory_bytes: 5264
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		
		int m =scanner.nextInt();
		String a = scanner.next();
		int n= a.length();
		
		char[] c = a.toCharArray();
		
		for(int i = 0 ;i<n;i++) {
			if(i>m-1) {
				if(n>m) {
				System.out.println("...");
				}
				break;
			}
			System.out.print(c[i]);
		}		
	}
}

Measured memory_bytes: 35596
#include <bits/stdc++.h>
using namespace std;
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define f first
	#define s second
	#define int long long 
	//using namespace std;
template<typename T> T gcd(T a, T b){ if(b == 0) return a; return gcd(b, a % b); }
	
	
	int gcd3(int a,int b,int c)
	{
		return gcd(gcd(a,b),c);
	}
	signed main()
	{
		std::ios::sync_with_stdio(false);
		int n;
		cin>>n;
		int sum = 0 ; 
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
		{
			for(int k=1;k<=n;++k)
		{
			sum += gcd3(i,j,k) ;
		}
		}
		}
		cout<<sum ; 
		return 0;
	}


Measured memory_bytes: 3612
import sys
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

s_list = [0]*(n+1)
s_list[1] = p[0]
for i in range(1, n+1):
    s_list[i] = p[i-1] + s_list[i-1]

for i in range(n-k+1):
    e = (s_list[i+k] - s_list[i] + k)/2
    if ans < e:
        ans = e
print(ans)

Measured memory_bytes: 71792
import math

def solve(x, a):
	low = 0
	high = len(a)-1
	while high >= low:
		t = (high+low)//2
		if x>a[t]:
			low = t+1
		else:
			high = t-1
	t = math.ceil((high+low)/2)
	return min(t, len(a)-t)
		
n,m,x = map(int, input().split())
a = list(map(int, input().split()))
print(solve(x,a))

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <vector>

using namespace std;

bool is_contradiction(int N,map<int, vector<map<string, int>>> T,vector<int> honest_flag) {
    for (int i = 1; i <= N; i++) {
        if (honest_flag.at(i) == false) continue;

        for (auto a : T[i]) {
            if (a["y"] != honest_flag.at(a["x"])) {
                return false;
            }
        }
    }

    return true;
}

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

    map<int, vector<map<string, int>>> T;
    for (int i = 1; i <= N; i++) {
        int A;
        cin >> A;

        vector<map<string, int>> a;
        for (int j = 1; j <= A; j++) {
            map<string, int> t;
            cin >> t["x"];
            cin >> t["y"];
            a.push_back(t);
        }
        T[i] = a;
    }

/*
    // test for input
    for (int i = 1; i <= N; i++) {
        cout << i << " : ";
        for (auto a : T[i]) {
            cout << a["x"] << " " << a["y"];
        }
        cout << endl;
    }
*/

    // 総当たりで矛盾がないか調べる
    int ans = 0;
    vector<int> honest_flag(N + 1);
    for (int bits = 1; bits < (1 << N); bits++) {
        int num_honest = 0;
        for (int i = 0; i < N; i++) {
            if (bits >> i & 1) {
                honest_flag.at(i + 1) = 1;
                num_honest++;
            } else {
                honest_flag.at(i + 1) = 0;
            }
        }

        // **** debug ****
        /*
        for (int i = 1; i <= N; i++) {
            cout << honest_flag.at(i) << ' ';
        }
        cout << endl;
        */

        if (num_honest <= ans) continue;

        if (is_contradiction(N, T, honest_flag)) {
            ans = num_honest;
        }
    }

    cout << ans << endl;

    return 0;
}

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

#define EPSILON 1e-6
#define ll long long
#define pii pair<int, int>

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, k;
  cin >> n >> k;

  string s;
  cin >> s;

  string ans = "";
  for (int i=0; i<n; i++) {
    if (i == k-1) ans += tolower(s[i]);
    else ans += s[i];
  }

  cout << ans << "\n";

  return 0;
}


Measured memory_bytes: 256
import itertools
import sys
 
def readline():
    return sys.stdin.readline()
 
def read_int_list():
    return list(map(int, readline().split()))
 
def read_int():
    return int(readline())
 
def main():
    N, M, R = read_int_list()
 
    r = [a-1 for a in read_int_list()]
 
    d = [[float('inf')]*N for _ in range(N)]
 
    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c
 
    for a in range(N):
        d[a][a] = 0
 
    res = float('inf')
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dd = d[i][k]+d[k][j]
                if dd < d[i][j]:
                    d[i][j] = min(d[i][j], dd)
 
    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)
 
    print(res)
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 4720
import java.util.Scanner;

public class Main {

    static boolean test(String s, String t) {
        if (t.length() != s.length() + 1) {
            return false;
        }
        for (int i=0;i<s.length();i++) {
            if (s.charAt(i) != t.charAt(i)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next(), t = in.next();
        System.out.println(test(s, t) ? "Yes" : "No");
    }
}


Measured memory_bytes: 35684
import sys, re
import math
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul	# 
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd	# 最大公約数
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# -*- coding: utf-8 -*-

a = INT() 
print(a * pi * 2)

Measured memory_bytes: 10580
#include <stdio.h>

int main (void)
{
  int a,b,c,d,e,k;
  int temp;
  int m1,m2,m3,m4,m5,m6,m7,m8,m9,m10;

  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &d);
  scanf("%d", &e);
  scanf("%d", &k);

  if(e > d){
     temp = d;
     d = e;
     e = temp;
   }
   if(d > c){
     temp = c;
     c = d;
     d = temp;
   }
   if(c > b){
     temp = b;
     b = c;
     c = temp;
   }
  if(b > a){
    temp = a;
    a = b;
    b = temp;
  }

  m1 = a - b;
  m2 = a - c;
  m3 = a - d;
  m4 = a - e;
  m5 = b - c;
  m6 = b - d;
  m7 = b - e;
  m8 = c - d;
  m9 = c - e;
  m10 = d - e;

  if(m1 > k) printf(":(");
  else if(m2 > k) printf(":(");
  else if(m3 > k) printf(":(");
  else if(m4 > k) printf(":(");
  else if(m5 > k) printf(":(");
  else if(m6 > k) printf(":(");
  else if(m7 > k) printf(":(");
  else if(m8 > k) printf(":(");
  else if(m9 > k) printf(":(");
  else if(m10 > k) printf(":(");
  else printf("Yay!");

}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int A,B;
int main(int argc, char const *argv[]) {
cin>>A>>B;
if(B%A==0){
  cout<<A+B<<endl;
}else{
  cout<<B-A<<endl;
}
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		String str = scan.next();
		for(int i = str.length() - 1; i >= 0; i--){
			char ch = str.charAt(i);
			System.out.printf("%c", ch);
		}
		System.out.printf("\n");
	}
}

Measured memory_bytes: 26048
#pragma region GNUC
//以下を参考にした
//https://yukicoder.me/wiki/auto_vectorization
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif
#pragma endregion

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>
#include <valarray>
//#include <array>//x C++ (G++ 4.6.4)

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <cassert>//assert();
#include <fstream>
#include <random>
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)

/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#define PII pair<int,int>
/////////
using namespace::std;
#pragma region Math
// 最大公約数
template<class T>
inline T gcd(T a, T b){return b ? gcd(b, a % b) : a;}
//inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}

// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a / gcd(a, b) * b;}
//inline T lcm(T a, T b){return a * b / gcd(a, b);}

template<class T>
T pow(T x,int n){
	T mul = x;
	T ans = (T)1;
	while(n){
		if(n&1){
			ans *= mul;
		}
		mul *= mul;
		n >>= 1;
	}
	return ans;
}
#pragma endregion //math

void solve(){
	string str;
	cin >> str;
	deque<char> ans;
	for(int i=0;i<(int)str.size();++i){
		switch(str[i]){
		case 'B':
			if( ans.empty() ) continue;
			ans.pop_back();
			break;
		default:
			ans.push_back(str[i]);
		}
	}
	while(!ans.empty()){
		cout << ans.front();
		ans.pop_front();
	}
}

signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	//std::cout << std::fixed;//小数を10進数表示
	//cout << setprecision(16);//小数点以下の桁数を指定
	
	solve();
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

int N, A[1<<20], neg = 0, minm = 1e9;
long long sum = 0;

int main() {
  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);

  cin >> N;
  for(int i = 0;i < N;i++) {
    cin >> A[i];
    sum += abs(A[i]);
    if(A[i] < 0) neg++;
    minm = min(minm, abs(A[i]));
  }

  cout << (((neg % 2) == 0) ? sum : (sum - 2*minm)) << endl;

  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int mod = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub_self(int &x, int y){x -= y; if(x < 0) x += mod;}
void mul(int &x, int y){x = x * 1LL * y % mod;}

int main(){

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

	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m, 0));
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			char x;
			cin >> x;
			a[i][j] = x == '#';
		}
	}

	vector<vector<int>> best(n, vector<int>(m, 1e9));
	vector<vector<bool>> vis(n, vector<bool>(m, false));
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	best[0][0] = a[0][0];
	while(!q.empty()){
		int x, y;
		tie(x, y) = q.front();
		q.pop_front();

		vis[x][y] = true;

		if(x + 1 < n && !vis[x + 1][y]){ // down
			int Xtra = (a[x][y] ^ a[x + 1][y] && a[x + 1][y]);
			if(best[x][y] + Xtra < best[x + 1][y]){
				best[x + 1][y] = best[x][y] + Xtra;
				if(Xtra)
					q.push_back({x + 1, y});
				else
					q.push_front({x + 1, y});
			}
		}
		if(y + 1 < m && !vis[x][y + 1]){ // right
			int Xtra = (a[x][y] ^ a[x][y + 1] && a[x][y + 1]);
			if(best[x][y] + Xtra < best[x][y + 1]){
				best[x][y + 1] = best[x][y] + Xtra;
				if(Xtra)
					q.push_back({x, y + 1});
				else
					q.push_front({x, y + 1});
			}
		}
	}

	cout << best[n - 1][m - 1] << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 105
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;

int main(){
    ll n,m;
    cin>>n>>m;
    map<int,int>w;
    for(int i=1;i*i<=m;i++){
        if(m%i==0){
            w[i]++;
            w[m/i]++;
        }
    }
    ll ans=0;
    for(auto p:w){
        if((ll)p.first*n<=(ll)m)ans=max(ans,(ll)p.first);
        else break;
    }
    OUT(ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long int llint;


const int MOD = 1000000007;

llint n, a, b;

//xのn乗を高速に求める
llint mod_pow(llint x, llint n, llint mod) {
	llint res = 1;
	while (n > 0) {
		if (n & 1) { res = res * x % mod; }
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

//start から end までをかける
llint mul(llint start, llint end, llint mod) {
	llint res = 1;
	for (llint i = start; i <= end; i++) {
		res *= i;
		res %= mod;
	}
	return res;
}

//nCa を計算
llint COM(llint n, llint a, llint mod) {
	llint up = mul(n - a + 1, n, mod);
	llint down = mul(1, a, mod);
	down = mod_pow(down, mod - 2, mod);
	return (up * down) % mod;
}

int main() {
	cin >> n >> a >> b;
	llint ans = mod_pow(2, n, MOD);
	ans += (MOD - COM(n, a, MOD)) % MOD;
	ans %= MOD;
	ans += (MOD - COM(n, b, MOD)) % MOD;
	ans %= MOD;
	ans = (ans + MOD - 1) % MOD;
	cout << ans << endl;
}

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

ans = 1e16
for s in (1, -1):
    res, acc = 0, 0
    for a in A:
        acc += a
        if acc * s <= 0:
            res += abs(acc-s)
            acc = s
        s *= -1
    ans = min(ans, res)

print(ans)


Measured memory_bytes: 14332
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>

//#include<bits/stdc++.h>





using namespace std;
int main() {

	int n;
	cin >> n;
	vector<int>p;
	int x = 0;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		x += t;
		p.push_back(t);
	}
	sort(p.begin(), p.end());
	if (x - p[n - 1] > p[n - 1])cout << "Yes" << endl;
	else cout << "No" << endl;


		
	

	return 0;
}


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

#define long long long

using namespace std;

int main() {
    int n;
    long k;
    cin >> n >> k;
    long a[n];
    for (auto &ai:a) cin >> ai;
    sort(a, a+n);
    int l = -1, r = n;
    while (r - l > 1) {
        int m = (l + r + 1) / 2;
        bool dp[k];
        fill(dp, dp+k, 0);
        dp[0] = true;
        for (int i=0; i<n; i++) {
            if (i == m) continue;
            for (long j=k-1-a[i]; j>=0; j--)
                dp[j+a[i]] |= dp[j];
        }
        long start = max(k-a[m], 0ll);
        if (any_of(dp+start, dp+k, [](bool b) { return b; }))
            r = m;
        else
            l = m;
    }
    cout << r << '\n';
    return 0;
}

Measured memory_bytes: 256
import sys, math, re
from functools import lru_cache
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    S = input()
    d = {}
    for i in range(N):
        if not S[i] in d:
            d[S[i]] = 1
        d[S[i]] += 1

    ans = 1
    for v in d.values():
        ans *= v
        ans %= MOD

    ans -= 1
    print(ans%MOD)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9908
#include<stdio.h>
#include<string.h>
int main(){
  char s[3];
  scanf("%s",s);
  char s1[]="abc";
  char s2[]="acb";
  char s3[]="bac";
  char s4[]="bca";
  char s5[]="cab";
  char s6[]="cba";
  if(strcmp(s,s1)==0){
    printf("Yes");
  }
  else if(strcmp(s,s2)==0){
    printf("Yes");
  }
  else if(strcmp(s,s3)==0){
    printf("Yes");
  }
  else if(strcmp(s,s4)==0){
    printf("Yes");
  }
  else if(strcmp(s,s5)==0){
    printf("Yes");
  }
  else if(strcmp(s,s6)==0){
    printf("Yes");
  }
  else{
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 128
//四則演算 #pragma GCC target("avx")
//並列計算 #pragma GCC optimize("O3")
//条件分岐を減らす #pragma GCC optimize("unroll-loops")
//浮動小数点演算 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(i) sort(i.begin(),i.end())
#define rSORT(i) sort(i.rbegin(),i.rend())
#define fSORT(i,a) sort(i.begin(),i.end(),a)
#define all(i) i.begin(),i.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
inline void print() { cout << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }

void dfs(         ) {

}

int main() {
    init();

    int a, b, c, d, k; cin >> a >> b >> c >> d >> k;
    int x = a * 60 + b, y = c * 60 + d;
    print(y - x - k);

    return 0;
}


Measured memory_bytes: 3648
N, M = map(int, input().split())
S = []
for _ in range(N):
  a, b = map(int, input().split())
  S.append((a, b))
S.sort()

p = 0
for a, b in S:
  if M <= b:
    # M個買う
    p += a * M
    break
  else:
    # b個買う
    p += a * b
    M -= b
print(p)

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

typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7;
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define pb push_back

ll N,M;

int main(){

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

cin>>N>>M;
ll time=1800*M+100*N;
ll ans=time*pow(2,M);
cout<<ans<<endl;

}
	


Measured memory_bytes: 256
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt() int {
  n, _ := strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Min(a, b int) int {
  if a < b { return a }
  return b
}

func main() {
  NM := NextIntVec()
  M := NM[1]
  A := NextIntVec()
  S := make([]int, M + 2)
  F := make([][]int, M)
  for i := range F {
    F[i] = make([]int, 0)
  }
  for i := range A { A[i]-- }
  for i, a := range A[1:] {
    F[a] = append(F[a], i + 1)
    S[A[i] + 2]++
    if M - 2 < A[i] { S[1]++ }
    S[a + 1]--
    if a < A[i] && A[i] < M - 1 { S[0]++ }
  }
  for i, s := range S[:M - 1] {
    S[i + 1] += s
  }
  cnt := 0
  for i, a := range A[1:] {
    cnt += (a + M - A[i]) % M
    if a < A[i] { cnt -= M - A[i] - 1 }
  }
  ans := cnt
  for i := 1; i < M; i++ {
    cnt -= S[i]
    for _, j := range F[i - 1] {
      cnt += (A[j] + M - A[j - 1]) % M - 1
    }
    ans = Min(cnt, ans)
  }
  Write(ans)
  Output()
}

Measured memory_bytes: 9088
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=105;
int s[N];
int n,ans;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n*2;i++)
		scanf("%d",s+i);
	std::sort(s,s+n*2);
	ans=0;
	for(int i=0;i<n*2;i+=2)
		ans+=s[i];
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define EPS 1e-9
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << a+b+c+d << endl;
}



Measured memory_bytes: 3116
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
//#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
#define puts(x) cout << x << endl
using namespace std;
int input() {
	int r;
	cin >> r;
	//scanf("%lld", &r);
	return r;
}
int f1(int a, int p) {
	if (p == 1)return a;
	if (p % 2)return f1(a, p - 1) * a % mod;
	else return f1(a * a % mod, p / 2) % mod;
}
int c[345678], n, a, b, k, ans;
signed main() {
	cin >> n >> a >> b >> k;
	c[0] = 1;
	for1(i, n)c[i] = c[i - 1] * (n - i + 1) % mod * f1(i, mod - 2) % mod;
	for0(i, n + 1) {
		if (a * i > k)break;
		if (b * n + a * i < k)continue;
		if ((k - (a * i)) % b == 0) ans += c[i] * c[(k - a * i) / b] % mod;
		ans %= mod;
	}puts(ans);
}

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

int P, R, T;

int res[300];
int need[300][300];
int rlog[200000][2];

bool check(int t){
	int state[300][300];
	for(int i = 0; i < P; i++){
		for(int j = 0; j < R; j++){
			state[i][j] = 0;
		}
	}
	int curres[300];
	for(int i = 0; i < R; i++){
		curres[i] = res[i];
	}

	for(int i = 0; i < t; i++){
		int p = rlog[i][0];
		int r = rlog[i][1];
		state[p][r]++;
		curres[r]--;
		if(state[p][r] == need[p][r]){
			bool flg = true;
			for(int j = 0; j < R; j++){
				if(state[p][j] < need[p][j]){
					flg = false;
					break;
				}
			}
			if(flg){
				for(int j = 0; j < R; j++){
					curres[j] += state[p][j];
					state[p][j] = 0;
				}
			}
		}
	}

	bool fin[300];
	for(int i = 0; i < P; i++){
		fin[i] = false;
	}
	bool flg = true;
	while(flg){
		flg = false;
		for(int i = 0; i < P; i++){
			if(!fin[i]){
				bool f2 = true;;
				for(int j = 0; j < R; j++){
					if(need[i][j] - state[i][j] > curres[j]){
						f2 = false;
						break;
					}
				}
				if(f2){
					for(int j = 0; j < R; j++){
						curres[j] += state[i][j];
						state[i][j] = 0;
					}
					fin[i] = true;
					flg = true;
				}
			}
		}
	}
	for(int i = 0; i < P; i++){
		if(!fin[i]) return false;
	}
	return true;
}


int main(){
	cin >> P >> R >> T;
	for(int i = 0; i < R; i++){
		cin >> res[i];
	}

	for(int i = 0; i < P; i++){
		for(int j = 0; j < R; j++){
			cin >> need[i][j];
		}
	}

	for(int i = 0; i < T; i++){
		cin >> rlog[i][0] >> rlog[i][1];
		rlog[i][0]--;
		rlog[i][1]--;
	}

	
	int l = 0;
	int r = T + 2;
	while(r - l > 1){
		int m = (l + r) / 2;
		if(check(m)){
			l = m;
		}else{
			r = m;
		}
	}
	if(l > T){
		cout << -1 << endl;
	}else{
		cout << (l+1) << endl;
	}
}

Measured memory_bytes: 5356
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
	        int H = sc.nextInt();
	        int N = sc.nextInt();
    
	        int x1 = sc.nextInt();
	        int y1 = sc.nextInt();
	        int z = 0;
	        for(int i = 1; i < N; i++) {
	            int xi = sc.nextInt();
	            int yi = sc.nextInt();
	            if((x1 > xi && y1 < yi) || (x1 < xi && y1 > yi)) {
	                z = z + Math.abs(x1 - xi) + Math.abs(y1 - yi);
		    }else {
		        z = z + Math.max(Math.abs(x1 - xi), Math.abs(y1 - yi));
		    }
		    x1 = xi;
		    y1 = yi;
		}
	        System.out.println(z);
	    }
        }

Measured memory_bytes: 25472
#include<bits/stdc++.h>
using namespace std;
typedef long long int T;

void knapsack(vector<pair<int,int>> items,int n,int w){

	T dp[n+1][w+1]; // i is items, j is capacity under consideration
	for(int i=0;i<=w;++i){
		dp[0][i] = 0; // no items under consideration
	}
	for(int i=0;i<=n;++i){
		dp[i][0] = 0; // capacity is 0
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=w;++j){
			// take or not take
		 if(items[i].first>j) dp[i][j] = dp[i-1][j];	
		 else dp[i][j] = max(items[i].second + dp[i-1][j-items[i].first],dp[i-1][j]);
		}
	}
/*	for(int i=0;i<=n;++i){
		for(int j=0;j<=w;++j) cout<<dp[i][j]<<" ";
		cout<<endl;
	}
*/
cout<<dp[n][w]<<endl;	
}
int main(){
	int N,W;
	cin>>N>>W;
	int n = N;
	vector<pair<int,int>> items;
	items.push_back(make_pair(0,0));
	while(n--){
		int w,v;
		cin>>w>>v;
		items.push_back(make_pair(w,v));
	}
	knapsack(items,N,W);
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,N-1,0)
#define RREPS(i,n) RFOR(i,N,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;

bool isprime(int x){
    int y=x;
    for(int i=2;i<=sqrt(x);i++){
        while(y%i==0)y/=i;
    }
    if(y==x)return true;
    return false;
}

signed main(){
    int N;cin>>N;
    int A[N];
    REP(i,N)cin>>A[i];
    int ans=INF;
    REP(i,201){
        int d=i-100;
        int cost=0;
        REP(j,N){
            cost+=(A[j]-d)*(A[j]-d);
            if(cost>1000000){
                cost=INF;
                break;
            }
        }
        chmin(ans,cost);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define debug(x)        cout<<#x<<" :"<<x<<endl;
#define ff              first
#define ar              array
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define f(i,n)          for(int i=0;i<n;i++)
#define MOD             1000000007
#define pi              3.14159265
#define umii            unordered_map<int,int>
#define umci            unordered_map<char,int>
#define umsi            unordered_map<string,int>

void k_007()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("ip1.txt", "r", stdin);
	freopen("op1.txt", "w", stdout);
#endif
}
bool sortbysec(const pair<int, int> &a,
               const pair<int, int> &b);
int gcd(int a, int b) ;
int prime(int n);
int power(int x, int y);
int lcm(int a, int b);
int maxf(int a, int b) {if (a > b) return a; else return b;}
int diff(int a, int b) {return abs(a - b);}
int mul(int a, int b) { return (a * b) % mod; }
int32_t main()
{
	k_007();
	int n;
	cin >> n;

	if (n & 1)
	{
		long double ans = (((n / 2) + 1) / (long double)n);
		cout << ps(ans, 10) << endl;
	}
	else
	{
		cout << ps((long double)(1 / (long double)2) , 10) << endl;
	}
}

bool sortbysec(const pair<int, int> &a, const pair<int, int> &b)
{
	return (a.second < b.second);
}
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int prime(int n) {
	int flag = 1;
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {flag = 0; break;}
	}
	return flag;
}
int power(int x, int y)
{
	if (y == 0)
		return 1;
	else if (y % 2 == 0)
		return ((power(x, y / 2) % MOD) * ( power(x, y / 2) % MOD)) % MOD;
	else
		return ((x % MOD) * (power(x, y / 2) % MOD) * (power(x, y / 2) % MOD)) % MOD;
}
int lcm(int a, int b)
{
	return (a * b) / gcd(a, b);
}

Measured memory_bytes: 3864
from collections import deque

H, W = map(int, input().split())
A = []
for _ in range(H):
    temp = list(map(int, input().split()))
    a = [t % 2 for t in temp]
    A.append(a)

operations = []

for i in range(H):
    y = i + 1
    if i % 2 == 0:
        for j in range(W):
            x = j + 1
            if A[i][j] == 1:
                if x != W:
                    operations.append((y, x, y, x+1))
                    A[i][j+1] = (A[i][j+1] + 1) % 2
                elif y != H:
                    operations.append((y, x, y+1, x))
                    A[i+1][j] = (A[i+1][j] + 1) % 2
    else:
        for j in reversed(range(W)):
            x = j + 1
            if A[i][j] == 1:
                if x != 1:
                    operations.append((y, x, y, x-1))
                    A[i][j-1] = (A[i][j-1] + 1) % 2
                elif y != H:
                    operations.append((y, x, y+1, x))
                    A[i+1][j] = (A[i+1][j] + 1) % 2

N = len(operations)
print(N)
if N != 0:
    for op in operations:
        print(*op, sep=' ')


Measured memory_bytes: 22832
a,b,c = list(map(int, input().split()))
a_init = a
b_init = b
c_init = c
a_temp = 0
b_temp = 0
c_temp = 0
count = 0
while a % 2 != 1 and b % 2 != 1 and c % 2 != 1:
    a_temp = a/2
    b_temp = b/2
    c_temp = c/2
    a = b_temp + c_temp
    b = c_temp + a_temp
    c = a_temp + b_temp
    count+= 1
    if a ==a_init and b == b_init and c == c_init:
        count = -1
        break
print(count)

Measured memory_bytes: 3316
fun main(args: Array<String>) {
    val (x, y) = readLine()!!.split(' ').map { it.toInt() }
    val ax = Math.abs(x)
    val ay = Math.abs(y)
    if (ax == ay) {
        if (x == y) println(0)
        else println(1)
    } else if (ax < ay) {
        var ans = ay - ax
        if (x < 0) ans += 1
        if (y < 0) ans += 1
        println(ans)
    } else {
        var ans = ax - ay
        if (x >= 0) ans += 1
        if (y > 0) ans += 1
        println(ans)
    }

}


Measured memory_bytes: 36460
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    int n;
    long long sum_1 = 0, sum_2 = 0, ans_1 = 0, ans_2 = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        sum_1 += a[i];
        sum_2 += a[i];
        if (i % 2 == 0) {
            if (sum_1 <= 0) {
                ans_1 += 1 - sum_1;
                sum_1 = 1;
            }
            if (sum_2 >= 0) {
                ans_2 += sum_2 + 1;
                sum_2 = -1;
            }
        }
        else {
            if (sum_1 >= 0) {
                ans_1 += sum_1 + 1;
                sum_1 = -1;
            }
            if (sum_2 <= 0) {
                ans_2 += 1 - sum_2;
                sum_2 = 1;
            }
        }
        //printf("%lld %lld %lld %lld\n", sum_1, sum_2, ans_1, ans_2);
    }
    printf("%lld\n", min(ans_1, ans_2));
    return 0;
}


Measured memory_bytes: 640
import sys
import collections
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

import math

N, K, Q = map(int, input().split())
init = [K] * N
res = [0] * N

for _ in xrange(Q):
    cur = int(input())
    res[cur-1] += 1

for i in xrange(N):
    init[i] -= (Q - res[i])
    print('No' if init[i] <= 0 else 'Yes')


Measured memory_bytes: 7156
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


Int gojo(Int)(Int a, Int b, out Int x, out Int y) {
  if (b != 0) { Int g = gojo(b, a % b, y, x); y -= (a / b) * x; return g; }
  x = 1; y = 0; return a;
}

Tuple!(Int, "b", Int, "m") modSol(Int)(Int b0, Int m0, Int b1, Int m1) {
  if (m0 < m1) {
    swap(b0, b1);
    swap(m0, m1);
  }
  Int b, m, x, y;
  const g = gojo(m0, m1, x, y);
  if ((b1 - b0) % g == 0) {
    b = b0 + m0 * ((x * (((b1 - b0) / g) % (m1 / g))) % (m1 / g));
    m = m0 * (m1 / g);
    if ((b %= m) < 0) {
      b += m;
    }
  }
  return Tuple!(Int, "b", Int, "m")(b, m);
}


void main() {
  try {
    for (; ; ) {
      const N = readLong();
      
      long n = 2 * N;
      long[] pes;
      for (long p = 2; p^^2 <= n; ++p) {
        if (n % p == 0) {
          long e;
          do {
            ++e;
            n /= p;
          } while (n % p == 0);
          pes ~= p^^e;
        }
      }
      if (n > 1) {
        pes ~= n;
      }
      const pesLen = cast(int)(pes.length);
      debug {
        writeln("pes = ", pes);
      }
      
      long ans = long.max;
      void dfs(int i, long b, long m) {
        if (i == pesLen) {
          debug {
            writeln(b, " ", m);
            foreach (j; 0 .. pesLen) {
              writeln("  ", pes[j], " ", b % pes[j]);
            }
          }
          chmin(ans, (b == 0) ? m : b);
        } else {
          foreach (r; [0, pes[i] - 1]) {
            const res = modSol(b, m, r, pes[i]);
            dfs(i + 1, res.b, res.m);
          }
        }
      }
      dfs(0, 0, 1);
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 3396
#include<iostream>
#include<sstream>

using namespace std;

int main(){
	ostringstream out;
	int coin[]={10,50,100,500},c[4];
	int pay,first=0;
	while(cin >> pay, pay){
		if(first++)
			out << endl;
		pay*=-1;
		for(int i=0;i<4;i++){
			cin >> c[i];
			pay+=coin[i]*c[i];
		}
		for(int i=3;i>=0;i--){
			if(pay/coin[i]==0)continue;
			c[i]-=pay/coin[i];
			pay=pay%coin[i];
		}
		for(int i=0;i<4;i++)
			if(c[i]>0)
				out << coin[i] << " " << c[i] << endl;
	}
	cout << out.str();
	return 0;
}

Measured memory_bytes: 1332