akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n;  cin >> n;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long a;    cin >> a;
        long long tmp = 0;
        while (a % 2 == 0) {
            a /= 2;
            tmp++;
        }
        ans += tmp;
    }
    cout << ans << endl;

    return 0;
}

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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N, u, v;
int A[110000], B[110000];
vint G[110000];
int dist_A[110000], dist_B[110000];;
void dfs_A(int cur, int prev) {
    dist_A[cur] = dist_A[prev] + 1;
    rep(i, G[cur].size()) {
        if (G[cur][i] == prev) { continue; }
        dfs_A(G[cur][i], cur);
    }
}
void dfs_B(int cur, int prev) {
    dist_B[cur] = dist_B[prev] + 1;
    rep(i, G[cur].size()) {
        if (G[cur][i] == prev) { continue; }
        dfs_B(G[cur][i], cur);
    }
}
signed main() {
    cin >> N >> u >> v;
    u--, v--;
    rep(i, N - 1) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    dfs_A(u, -1);
    dfs_B(v, -1);
    int ans = 0;
    rep(i, N) {
        if (dist_A[i] < dist_B[i]) { chmax(ans, dist_B[i]); }
    }
    ans -= 2;
    cout << ans << endl;
}

Measured memory_bytes: 13056
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
//l={1,2,3,4}
//greater<int>()
//sort(l,l+N)

int main(void)
{
	long long x, y;
	cin >> x >> y;
	long long a = -1;
	if (x%y == 0)
		cout << a << endl;
	else {
		for (int i = 2;; i++) {

			if ((x*i)%y != 0) {
				a = (x*i);
				break;
			}
		}
		cout << a << endl;
	}

}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

#define maxn 200010
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

typedef long long ll;
const ll inf = ~0ULL >> 1;
int a[maxn];
ll sum[maxn];
int main()
{
	int n; scanf("%d", &n); ll ans = inf;
	for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum[i] = sum[i - 1] + a[i];
	for (int i = 2; i <= n - 2; ++i)
	{
		ll hsum = sum[i] / 2;
		int pos1 = std::upper_bound(sum + 1, sum + n + 1, hsum) - sum - 1;
		hsum = (sum[n] - sum[i]) / 2 + sum[i];
		int pos2 = std::upper_bound(sum + 1, sum + n + 1, hsum) - sum - 1;
//		printf("%d %d %d\n", pos1, i, pos2);
		for (int j = 0; j < 2; ++j)
		{
			int np1 = pos1 + j;
			if (np1 == i) break;
			for (int k = 0; k < 2; ++k)
			{
				int np2 = pos2 + k;
				if (np2 == n) break;
				ll minn = inf, maxx = -inf;
				cmin(minn, sum[np1]);
				cmin(minn, sum[i] - sum[np1]);
				cmin(minn, sum[np2] - sum[i]);
				cmin(minn, sum[n] - sum[np2]);
				
				cmax(maxx, sum[np1]);
				cmax(maxx, sum[i] - sum[np1]);
				cmax(maxx, sum[np2] - sum[i]);
				cmax(maxx, sum[n] - sum[np2]);
				
				cmin(ans, maxx - minn);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2560
import sys
sys.setrecursionlimit(1000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
INF = 500000
mod = 10**9+7

S = deque(input())
Q = int(input())
flg = 0
for i in range(Q):
    query = input().split()
    if len(query) == 1:
        flg ^= 1
    else:
        F, C = int(query[1])-1, query[2]
        if F^flg:
            S.append(C)
        else:
            S.appendleft(C)
if flg:
    S.reverse()
print(''.join(S))


Measured memory_bytes: 8436
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1000000007,N=100000;
const double pi=acos(-1.0);
typedef long long ll;
struct node{
	int u,v,w;
}sq[100100];

bool operator < (const node &p,const node &q)
{
	return p.w<q.w;
}

int n,m,fa[100100],cnt[100100],p[100100],ans=0;
ll sum[100100];

int read()
{
	int x=0,f=1;char ch=getchar();
	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
	return x*f;
}

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

int main()
{
	n=read();m=read();int i;
	for (i=1;i<=n;i++) {p[i]=read();sum[i]=p[i];}
	memset(cnt,0,sizeof(cnt));
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++)
	{
		sq[i].u=read();sq[i].v=read();sq[i].w=read();
	}
	sort(sq+1,sq+1+m);
	for (i=1;i<=m;i++)
	{
		int x=sq[i].u,y=sq[i].v,
	    	fx=find(x),fy=find(y);
		if (fx!=fy)
		{
			cnt[fx]+=(cnt[fy]+1);
			sum[fx]+=sum[fy];
			cnt[fy]=0;sum[fy]=0;
			fa[fy]=fx;
		}
		else cnt[fx]++;
		if (sum[fx]>=sq[i].w)
		{
			ans+=cnt[fx];
			cnt[fx]=0;
		}
	}
	printf("%d",m-ans);
	return 0;
}



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

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B && A == C) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> table(H, vector<char>(W));
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> table[i][j];
    }
  }
  
  for(int j = 0; j < W; j++){
    for(int i = 0; i < H; i++){
      if(table[i][j] == '#'){
        break;
      }
      else if(i == H - 1){
        for(int k = 0; k < H; k++){
          table[k][j] = '\0';
        }
      }
    }
  }
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(table[i][j] == '#'){
        break;
      }
      else if(j == W - 1){
        for(int k = 0; k < W; k++){
         table[i] = {};
        }
      }
    }
  }
  

  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(table[i].size() == 0)
        break;
      else if(table[i][j] != '\0')
        cout << table[i][j];
    }
    if(table[i].size() != 0)
      cout << endl;
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define repl(i,a,b) for(int (i)=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)

vector<vector<ll>> fold(vector<vector<ll>> tile, pair<ll,ll> way){
  ll dir = way.first;
  ll dist = way.second;
  if(dir==2){
    int H = max(dist, (int)tile.size()-dist);
    int W = tile[0].size();
    vector<vector<ll>> res(H,vector<ll>(W,0));

    rep(h,H)rep(w,W){
      // way1
      int tgth = dist - h - 1;
      if(0<=tgth && tgth < tile.size()){
        res[h][w]+=tile[tgth][w];
      }
      tgth = h+dist;
      if(0<=tgth && tgth < tile.size()){
        res[h][w]+=tile[tgth][w];
      }
    }
    return res;
  }
  else{
    int H = tile.size();
    int W = max(dist, (int)tile[0].size()-dist);
    vector<vector<ll>> res(H,vector<ll>(W,0));

    rep(h,H)rep(w,W){
      int tgtw = dist - w - 1;
      if(0<=tgtw && tgtw < tile[0].size()){
        res[h][w]+=tile[h][tgtw];
      }
      tgtw = w+dist;
      if(0<=tgtw && tgtw < tile[0].size()){
        res[h][w]+=tile[h][tgtw];
      }
    }
    return res;
  }
}

int main(){
  while(1){
    ll n,m,t,p;
    cin>>n>>m>>t>>p;
    if(n==0 && m==0)break;
    vector<pair<ll,ll>> dc(t), xy(p);
    rep(i,t)cin >> dc[i].first>>dc[i].second;
    rep(i,p)cin>>xy[i].first>>xy[i].second;

    vector<vector<ll>> tile(m,vector<ll>(n,1));
    for(auto p:dc){
      tile = fold(tile,p);
    }
    for(auto p:xy){
      cout << tile[p.second][p.first] << endl;
    }
  }

}



Measured memory_bytes: 3164
from collections import deque

S = deque(input())
Q = int(input())
count = 0
for i in range(Q):
    input_list = input().split()
    if input_list[0] == "1":
        count += 1
        continue

    if count % 2 == 0:  # even
        if input_list[1] == "1":
            S.appendleft(input_list[2])
        else:
            S.append(input_list[2])
    else:
        if input_list[1] == "2":
            S.appendleft(input_list[2])
        else:
            S.append(input_list[2])

if count % 2 == 0:
    ans = ''.join(S)
    print(ans)
else:
    S.reverse()
    ans = ''.join(S)
    print(ans)


Measured memory_bytes: 74200
import java.util.Scanner;
import java.util.ArrayList;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    ArrayList<String> list = new ArrayList<String>();
    String str = sc.next();
    for(int i=0;i<str.length();i++){
      if(str.charAt(i)=='0'){
        list.add("0");
      }else if(str.charAt(i)=='1'){
        list.add("1");
      }else if(str.charAt(i)=='B'){
        if(!list.isEmpty()){
          list.remove((list.size()-1));
        }
      }
    }
    for(int i=0;i<list.size();i++){
      System.out.print(list.get(i));
    }
  }
}


Measured memory_bytes: 21972
from itertools import accumulate

N = input()

A = [1 if n=='R' else -1 for n in N]

m = len(N)
for i in range(1, m):
	if A[i-1] == 1 and A[i] == -1:
		A[i-1] = 0
		A[i] = 0

ans = [1 if a==0 else 0 for a in A]


flag=False
s = 0
for i in range(m-1):
	if A[i] == 1:
		flag=True
		s += 1
	if flag and A[i]==0:
		ans[i] += s//2
		ans[i+1] += s - s//2
		flag = False
		s = 0

flag=False
s = 0
for i in range(1, m)[::-1]:
	if A[i] == -1:
		flag=True
		s += 1
	if flag and A[i]==0:
		ans[i] += s//2
		ans[i-1] += s - s//2
		flag = False
		s = 0

for i in range(m-1):
	print(ans[i], end=' ')
print(ans[m-1])

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

int main()
{
   int n;
   cin>>n;
   int a[n],min=INT_MAX,c=0;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
       if(a[i]<min)
       {
           c++;
           min=a[i];
       }
   }
   cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
input=sys.stdin.readline
n=int(input())
P=tuple(map(float,input().split()))
DP=[[0]*(n+1) for _ in range(n+1)]
DP[0][0]=1
for i in range(1,n+1):
    DP[i][0]=DP[i-1][0]*(1-P[i-1])
for i in range(1,n+1):
    for j in range(1,i+1):
        DP[i][j]=DP[i-1][j-1]*P[i-1]+DP[i-1][j]*(1-P[i-1])
ans=0
for i in range(n//2+1,n+1):
    ans+=DP[-1][i]
print(ans)

Measured memory_bytes: 311176
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <queue>
#include <set>
#include <cassert>
using namespace std;
using ll = long long;
using plong = pair<ll,ll>;
ll MOD=998244353;

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; }

int main(){
    ll H,W,A,B;
    cin>>H>>W>>A>>B;
    for(ll i=0;i<B;i++){
        for(ll i=0;i<A;i++){
            cout<<0;
        }
        for(ll i=0;i<W-A;i++){
            cout<<1;
        }
        cout<<"\n";
    }
    for(ll i=0;i<H-B;i++){
        for(ll i=0;i<A;i++){
            cout<<1;
        }
        for(ll i=0;i<W-A;i++){
            cout<<0;
        }
        cout<<"\n";
    }


}

Measured memory_bytes: 1280
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

K,N = parseMap(split(readline()))
A = parseMap(split(readline()))

function main()
    
before_a = 0
shortest_aida = -100000
for a in A
    aida = a - before_a
    before_a  = a
    if aida > shortest_aida
        shortest_aida = aida
    end
end

if A[1] + (K - A[N]) > shortest_aida
    shortest_aida = A[1] + (K - A[N])
end

println(K - shortest_aida)
end

main()

Measured memory_bytes: 194012
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n,K; cin>>n>>K;
    vector<int> p(n),q(n,0);
    rep(i,n) cin>>p[i];
    rep(i,min(K,50)){
        rep(j,n){
            int a=max(0,j-p[j]), b=min(n-1,j+p[j]);
            //cout<<a<<" "<<b<<endl;
            q[a]++;
            if(b!=n-1) q[b+1]--;
        }
        rep(j,n-1) q[j+1]=q[j+1]+q[j];
        p=q;
        q=vector<int>(n,0);
    }
    rep(i,n) cout<<p[i]<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 5652
#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;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll a, b;
    cin >> a >> b;
    if(b == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    for(ll i = 1; i <= 20; i++)
    {
        if(i * a - (i - 1) >= b)
        {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

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

int main() {
    vector<int> a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K; cin >> K;
    cout << a[K-1] << endl;
}


Measured memory_bytes: 256
from collections import defaultdict

n = int(input())
x = defaultdict(int)
for i in range(2, n + 1):
    k = i
    for j in range(2, i + 1):
        while(k % j == 0):
            k = k // j
            x[j] += 1

y = defaultdict(int)
for i in x.values():
    for j in [2, 4, 14, 24, 74]:
        if i >= j:
            y[j] += 1

ans = 0
ans += y[4] * max(0, y[4] - 1) * max(0, y[2] - 2) // 2
ans += y[14] * max(0, y[4] - 1)
ans += y[24] * max(0, y[2] - 1)
ans += y[74]
print(ans)


Measured memory_bytes: 3316
#include<cstdio>
#include<algorithm>
#include<vector>
int numrec[100002]={};
int main(){
    int n,cmax,s,t,c;
    scanf("%d%d",&n,&cmax);
    std::vector<std::pair<int,int>> v[31];
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&s,&t,&c);
        v[c].push_back({s,t});
    }
    for(int i=1;i<=cmax;i++){
        std::sort(v[i].begin(),v[i].end());
        for(int j=1;j<v[i].size();j++){
            if(v[i][j-1].second==v[i][j].first)v[i][j].first=v[i][j-1].first;
            else v[0].push_back(v[i][j-1]);
        }
        if(v[i].size()>0)v[0].push_back(v[i].back());
    }
    for(auto itr=v[0].begin();itr!=v[0].end();itr++){
        numrec[itr->first]++;
        numrec[1+itr->second]--;
    }
    int ans=0,nowrec=0;
    for(int i=0;i<=100000;i++){
        nowrec+=numrec[i];
        if(ans<nowrec)ans=nowrec;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 2676
from bisect import bisect_left, bisect_right
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for i in range(len(B)):
    selectA = bisect_left(A, B[i])
    selectB = len(C) - bisect_right(C, B[i])
    ans += selectA * selectB
print(ans)


Measured memory_bytes: 23232
s = input()
t = input()

def count_mismatch(a, b):
    ans = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            ans += 1

    return ans

lt = len(t)
ans = len(s)
for i in range(len(s)-lt+1):
    part = (s[i:i+lt])
    tmp_ans = count_mismatch(part, t)
    ans = min(ans, tmp_ans)

print(ans)




Measured memory_bytes: 9132
H, W = map(int, input().split())
M = [["." for i in range(W)] for j in range(H)]
S = [input() for i in range(H)]

start = (0, 0, 0)
queue = [start]
white = 0
isGoal = False
depth = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            white+=1

while(len(queue)):
    i, j, d = queue.pop(0)
    if i < 0 or i >= H or j < 0 or j >= W or S[i][j] == "#" or M[i][j] == "#":
        continue
    elif i == H - 1 and j == W - 1:
        isGoal = True
        depth = d
        break
    M[i][j] = "#"
    for ni, nj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        queue.append((i+ni, j+nj, d+1))

print(white-d-1 if isGoal else -1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
  long int A, B, K;
  cin >> A >> B >> K;
  if (A >= K) {
    cout << A - K << endl;
    cout << B << endl;
  }
  else if (A + B >= K) {
    cout << 0 << endl;
    cout << A + B - K << endl;
  }
  else {
    cout << 0 << endl;
    cout << 0 << endl;
  }
}

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

int main() {
  int x[3];
  cin >> x[0] >> x[1] >> x[2];
  sort(x, x + 3);
  int ans = x[0] + x[1] + x[2] * 10;
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
INF = 10**18
cnt = 0
for i in range(n):
  if a[i] == 0:
    cnt += 1
if cnt > 0:
  print(0)
else:
  mul = 1
  flg = True
  for i in range(n):
    mul *= a[i]
    if mul > INF:
      flg = False
      break
  if flg:
    print(mul)
  else:
    print(-1)

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

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll a, b, n;
    cin >> a >> b >> n;
    cout << (a*min(n, b-1))/b;
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <list>
#include <stack>
#include <queue>
#include <utility>

using namespace std;

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

bool compare_by_second(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
}



int main()
{
    int n,m;
    cin >> n >> m;
    vector<ll> a(n);

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    ll b;
    ll c;
    sort(a.begin(),a.end());
    vector<pair<ll,ll> > pairs;

    for (int i = 0; i < m; i++)
    {
        pair<ll,ll> mypair;
        cin >> b;
        cin >> c;
        mypair = make_pair(b,c);
        pairs.push_back(mypair);
    }
    sort(pairs.begin(),pairs.end(),compare_by_second);
    /*for (int i = 0; i < m; i++)
    {
        cout << pairs[i].first << " " <<  pairs[i].second << endl;
    }*/

    vector<ll> changer(n);
    for (int i = 0; i < n; i++)
    {
        changer[i] = 0;
    }
    
    
    int index = 0;
    int pair_index = 0;
    while (index < n && pair_index < m)
    {
        while (pairs[pair_index].first > 0 && index < n)
        {
            changer[index] = pairs[pair_index].second;
            pairs[pair_index].first--;
            index++;
        }
        pair_index++;
    }

    index = 0;
    int index_changer = 0;


    while(index < n && index_changer < n)
    {
        if(a[index]<changer[index_changer])
        {
            a[index] = changer[index_changer];
            index++;
            index_changer++;
        }else{
            index++;
        }
    }

    
    
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 3440
#include<iostream>
using namespace std;
int main(){
	int r, c, list[100][100] = { 0 },sum;
	cin >> r >> c;
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			cin >> list[i][j];
		}
	}
	for (int i = 0; i < r; i++){
		sum = 0;
		for (int j = 0; j < c; j++){
			cout << list[i][j] << " ";
			sum += list[i][j];
		}
		cout << sum<<endl;
	}
	int sumList[100] = { 0 };
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			sumList[j] += list[i][j];
		}
	}
	sum = 0;
	for (int i = 0; i < c; i++){
		cout << sumList[i] << " ";
		sum += sumList[i];
	}
	cout << sum << endl;
}


Measured memory_bytes: 3152
#include <iostream>

using namespace std;

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

int main()
{
	int a, b, k;
	cin >> a >> b >> k;

	int gcd = GCD(a, b);

	int ans = 0;

	for (int i = gcd; i >= 1; i--)
	{
		if (a % i == 0 && b % i == 0)
		{
		 	k--;
		}

		if (a % i == 0 && b % i == 0 && k == 0)
		{
			cout << i << endl;
		}
	}
}


Measured memory_bytes: 256
#include<string>
#include<sstream>
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<ios>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<type_traits>
#include<random>
#include<vector>
#include<map>

using namespace std;

	

int main()
{
	int N;
	cin >> N;
	vector<int> b(N);
	for(int i=0;i<N;i++)
	{
		cin >> b[i];
	}
	vector<int> ans(N,0);
	bool judge_i = 0;
	for(int i=0;i<N && judge_i == 0;i++)
	{
		bool judge_j = 0;
		for(int j=0;j<b.size() && judge_j == 0;j++)
		{
			if(b[b.size()-j-1]==b.size()-j)
			{
				judge_j = 1;
				ans[N-i-1] = b[b.size()-j-1];
				b.erase(b.begin()+b.size()-j-1);
			}
		}
		if(judge_j==0)
		{
			judge_i = 1;
		}
	}
	if(judge_i==1)
	{
		int x = -1;
		cout << x << endl;
	}
	else
	{
		for(int i=0;i<N;i++)
		{
			cout << ans[i] << endl;
		}
	}
				
}


Measured memory_bytes: 256
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a


def cul(n,x):
    l=len(x)
    b=[x[i] for i in range(l)]
    b.pop(n)
    tmp=b[0]
    for i in range(1,l-1):
        tmp=gcd(tmp,b[i])
    return tmp

import sys
import math
p=100
N=int(input())
a=list(map(int,input().split()))
if N<=p:
    ans=0
    
    for i in range(N):
        tmp=cul(i,a)        
        if tmp>ans: ans=tmp
    print(ans)
    sys.exit()
        
M=a[0]
for i in range(1,p):
    M=gcd(M,a[i])

ans=0


R=a[p]
for i in range(p,N):
    r=gcd(R,a[i])

if r>ans:
    for i in range(p):
        s=gcd(cul(i,a[:p]),R)
        if s>ans: ans=s

print(ans)


Measured memory_bytes: 14588
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			long n = sc.nextLong();
			long k = sc.nextLong();

			if(n == 0) {
				System.out.println(0);
			} else {
				long mod = n % k;
				long ans = Math.abs(mod - k);
				System.out.println(Math.min(mod, ans));
			}
		}

	}

}


Measured memory_bytes: 21972
#include<iostream>
using namespace std;
int main()
{
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    
    long long lcm, cc, dd;
    cc = c;
    dd = d;
    while (cc != dd) {
      if (cc > dd) {
        cc -= dd;
      } else {
        dd -= cc;
      }
    }
    lcm = c * d / cc;
  
    a--;
    cout << (b-b/c-b/d+b/lcm) - (a-a/c-a/d+a/lcm) << endl;
    return 0;
}


Measured memory_bytes: 256
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [li[0] for li in LIST]
    if any(num > k for num in tmp):
        return h * w
    for j in range(1, w):
        cal = [t + li[j] for t, li in zip(tmp, LIST)]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [li[j] for li in LIST]
        else:
            tmp = cal
    return CNT


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)


Measured memory_bytes: 76588
import java.io.*;
 
class Main {
    public static void main(String[] args) {
        BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
        try {
 
            String[] str = kb.readLine().split( " " );
            int n = Integer.parseInt( str[0] );
            int m = Integer.parseInt( str[1] );
            int l = Integer.parseInt( str[2] );
                         
            int[][] matrixA = new int[n][m];
            int[][] matrixB = new int[m][l];
            for( int i=0; i<n; i++ ) {
                str = kb.readLine().split( " " );
                for( int j=0; j<m; j++ ) {
                    matrixA[i][j] = Integer.parseInt( str[j] );
                }
            }
            for( int i=0; i<m; i++ ) {
                str = kb.readLine().split( " " );
                for( int j=0; j<l; j++ ) {
                    matrixB[i][j] = Integer.parseInt( str[j] );
                }
            }
            StringBuilder output = new	StringBuilder( 400+1 );	
 			long c;
            for( int i=0; i<n; i++ ) {
                for( int j=0; j<l; j++ ) {
                	c = 0;
	                for( int k=0; k<m; k++ ) {
                        c += ( matrixA[i][k] * matrixB[k][j] );
                    }
                    output.append( c );
                    output.append( " " );
                }
                output.deleteCharAt( output.lastIndexOf( " " ) );
                output.append( "\n" );
            }
             
            System.out.print( output );
             
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

Measured memory_bytes: 27128
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#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 trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define M   1000000007 // 1e9 + 7
//#define int long long
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

int32_t main(){
 fastio;
 string s;
 cin>>s;
 int n =s.size();
 for(int i=0;i<n;i++){
  if(i%2==0){
    if(s[i]=='L'){
      cout<<"No"<<endl;
      return 0;
    }
  }else{
    if(s[i]=='R'){
      cout<<"No"<<endl;
      return 0;
    }
  }

 }
 cout<<"Yes"<<endl;

  // Math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

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

using namespace std;

int main() {
	string a, b, c;
	int counta = 0, countb = 0, countc = 0;
	int turn = 1;
	cin >> a >> b >> c;
	while (1) {
		if (turn == 1) {
			counta++;
			if (a[counta - 1] == 'a')turn = 1;
			else if (a[counta - 1] == 'b') turn = 2;
			else if(a[counta-1]=='c')turn = 3;
			else break;
		}
		else if (turn == 2) {
			countb++;
			if (b[countb - 1] == 'a') turn = 1;
			else if (b[countb - 1] == 'b') turn = 2;
			else if(b[countb - 1] == 'c')turn = 3;
			else break;
		}
		else {
			countc++;
			if (c[countc - 1] == 'a') turn = 1;
			else if (c[countc - 1] == 'b') turn = 2;
			else if(c[countc - 1] == 'c')turn = 3;
			else break;
		}
	}
	if (counta-1 == a.size())cout << 'A' << endl;
	else if (countb-1 == b.size())cout << 'B' << endl;
	else cout << 'C' << endl;
	return 0;
}




Measured memory_bytes: 256
import collections

n=int(input())
str_list = [input() for _ in range(n)]
c = collections.Counter(str_list)



print('AC' + ' x ' + str(c['AC']))
print('WA' + ' x ' + str(c['WA']))
print('TLE' + ' x ' + str(c['TLE']))
print('RE' + ' x ' + str(c['RE']))

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

#define BUF_SIZE 20000

int* fget_array(int *arr, int size, char *line) {
  char *tmpbuf = line;
  int i;
  for(i = 0; i < size; i++) {
    char *tmp = strtok(tmpbuf, " ");
    arr[i] = strtol(tmp, NULL, 10);
    tmpbuf = NULL;
  }
  return arr;
}

int main(void) {
  FILE *fp = stdin;
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  int num;
  sscanf(line, "%d", &num);
  int *arr = malloc(sizeof(int)*num);
  if(!fgets(line, BUF_SIZE, fp)) return 0;
  fget_array(arr, num, line);

  if(!fgets(line, BUF_SIZE, fp)) return 0;
  int queries;
  sscanf(line, "%d", &queries);

  int i, j;
  for(i = 0; i < queries; i++) {
    if(!fgets(line, BUF_SIZE, fp)) return 0;
    int begin, end, k;
    sscanf(line, "%d %d %d", &begin, &end, &k);
    int cnt = 0;
    for(j = begin; j < end; j++) {
      if(arr[j] == k) cnt++;
    }
    printf("%d\n", cnt);
  }

  return 0;
}


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

N = int(input())

Ret = [0 for _ in range(10**5)]

for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            r = i**2 + j**2 + k**2 + i*j + j*k + i*k
            Ret[r] += 1

for r in Ret[1:N+1]:
    print(r)




Measured memory_bytes: 10084
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin>>S;
  int next;
  if(S=="SUN")next=7;
  if(S=="MON")next=6;
  if(S=="TUE")next=5;
  if(S=="WED")next=4;
  if(S=="THU")next=3;
  if(S=="FRI")next=2;
  if(S=="SAT")next=1;
  cout<<next;
  
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	long i,n,m,ans=1,a=0,aa=-1,mod=1e9+7,f[114514];
	cin>>n>>m;
	f[0]=f[1]=1;
	for(i=2;i<114514;i++)f[i]=(f[i-1]+f[i-2])%mod;
	for(i=0;i<m;i++)
	{
		cin>>a;
		if(a-aa==1)
		{
			cout<<0<<endl;
			return 0;
		}
		ans=(ans*f[a-aa-2])%mod;
		aa=a;
	}
	a=n;
	ans=(ans*f[a-aa-1])%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
struct edge {int from,to, cost;};
vector<edge> G(0);
vector<bool> reachableFrom1;
vector<bool> reachableToN;
void dfs(int v) {
    if(reachableFrom1[v] == true) return;
    reachableFrom1[v] = true;
    for(edge e: G) {
        if(e.from==v) dfs(e.to);
    }
    return;
}
void rdfs(int v) {
    if(reachableToN[v] == true) return;
    reachableToN[v] = true;
    for(edge e: G) {
        if(e.to == v) rdfs(e.from);
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m,p;
    cin >> n >> m >> p;
    rep(i,n) {
        reachableToN.resize(n,false);
        reachableFrom1.resize(n,false);
    }
    rep(i, m) {
        int a,b,c;
        cin >> a >> b >> c;
        G.push_back({a-1,b-1,c-p});
    }
    //dfs
    dfs(0);
    rdfs(n-1);
    vector<bool> ok_v(n);
    rep(i,n) ok_v[i] = reachableFrom1[i]&reachableToN[i];
    //bellman ford
    const int INF = INT32_MAX>>3;
    vector<int> d(n, -INF);
    d[0] = 0;
    rep(i, n) {
        bool end = true;
        for(edge e: G) {
            if(ok_v[e.from] == false || ok_v[e.to] == false) continue;
            if(d[e.from] == -INF) continue;
            if(d[e.from] + e.cost > d[e.to] ) {
                d[e.to] = d[e.from] + e.cost;
                end = false;
                if(i == n-1) {
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
        if(end) break;
    }
    if(d[n-1] < 0) cout << 0 << endl;
    else cout << d[n-1] << endl;
}

Measured memory_bytes: 512
package main

import (
	"fmt"
	"strings"
)

func include7(a []string) bool {
	for _, v := range a {
		if v == "7" {
			return true
		}
	}
	return false
}

func main() {
	var n string

	fmt.Scan(&n)
	s := strings.Split(n, "")

	if include7(s) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1820
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    ll N, W; cin >> N >> W;
    ll w[111], v[111];
    vector<ll> item[4];
    for(int i=0;i<N;++i) cin >> w[i] >> v[i];
    ll minw = w[0];
    for(int i=0;i<N;++i) w[i] -= minw;
    for(int i=0;i<N;++i) item[w[i]].push_back(v[i]);
    for(int i=0;i<4;++i) {
        sort(item[i].rbegin(), item[i].rend());
        for(int j=0; j < item[i].size(); ++j) item[i][j+1] += item[i][j];
    }


    ll ans = 0;
    for(int i=0; i <= item[0].size(); ++i) {
        for(int j=0; j <= item[1].size(); ++j) {
            for(int k=0; k <= item[2].size(); ++k) {
                for(int l=0; l <= item[3].size(); ++l) {
                    ll sumw = 0, sumv = 0;
                    if(i > 0) sumw +=  minw    * i, sumv += item[0][i-1];
                    if(j > 0) sumw += (minw+1) * j, sumv += item[1][j-1];
                    if(k > 0) sumw += (minw+2) * k, sumv += item[2][k-1];
                    if(l > 0) sumw += (minw+3) * l, sumv += item[3][l-1];
                    
                    if(sumw <= W) ans = max(ans, sumv);
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int l = a+b, r = c+d;
  if (r == l) cout << "Balanced" << endl;
  else if (r < l) cout << "Left" << endl;
  else cout << "Right" << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
G = [[] for i in range(H*W)]
S = [list(input()) for i in range(H)]
rs = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        rs += 1
        if h < H-1 and S[h+1][w] == "#" :
            j = (h+1)*W + w
            G[i].append(j)
        if w < W-1 and S[h][w+1] == "#" :
            j = h*W + w+1
            G[i].append(j)

def bfs(s, g) :
    dist = [-1 for _ in range(H*W)]
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for next in G[now] :
            if dist[next] != -1 :
                continue
            else :
                dist[next] = dist[now] + 1
                q.append(next)
    return dist[g]

if bfs(0,H*W-1) == rs-1 :
    print("Possible")
else :
    print("Impossible")


Measured memory_bytes: 38512
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N,X; cin>>N>>X;
    int g=0;
    REP(i,N){
        int x; cin>>x;
        g=__gcd(g,abs(X-x));
    }
    cout<<g<<endl;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードを示す。負は自身が親ということ。親だった場合は−(その集合のサイズ)
        self.parent = [-1] * N

    def root(self, A):
        # Aがどのグループに属しているか調べる
        # ノード番号を受けとって一番上の親ノードの番号を返す
        # print(A)
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        # 自分のいるグループの頂点数を調べる
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # AとBをくっつける
        # AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  # すでにくっついてるからくっつけない

        if self.size(A) < self.size(B):
            # 大きい方(A)に小さいほう(B)をくっ付けたい
            # 大小が逆だったらひっくり返しちゃう。
            A, B = B, A

        # Aのサイズを更新する
        self.parent[A] += self.parent[B]
        # Bの親をAに変更する
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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


uf = UnionFind(N)
frd = [0] * N  # 友達の数
blk = [[] for _ in range(N)]  # ブロック関係。隣接リスト
ans = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frd[a] += 1
    frd[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blk[a].append(b)
    blk[b].append(a)
for i in range(N):
    ans[i] = uf.size(i) - 1 - frd[i]
    for j in blk[i]:
        if uf.same(i, j):
            ans[i] -= 1 # 同じグループ内でのblock関係を引く
print(*ans)



Measured memory_bytes: 31832
import java.util.Scanner;


public class Main {

	static int[] par;
	static int[] rank;

	static void initUF(int n) {
		par = new int[n];
		rank = new int[n];
		for (int i=0;i<n;i++){
			par[i] = i;
			rank[i] = 1;
		}
	}
	
	static int root(int n) {
		if (par[n]==n) {
			return n;
		} else {
			return (par[n] = root(par[n]));
		}
	}
	
	static boolean same(int i, int j) {
		return root(i)==root(j);
	}

	static void unite(int i, int j) {
		int x = root(i);
		int y = root(j);
		
		if (rank[x]>rank[y]) {
			par[y] = x;
		} else {
			par[x] = y;
			if (rank[x]==rank[y]) rank[x]++;
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int q = scan.nextInt();
		
		initUF(n);
		for (int i=0;i<q;i++) {
			int com = scan.nextInt();
			int x = scan.nextInt();
			int y = scan.nextInt();
			if (com==0) {
				unite(x, y);
			} else {
				System.out.println(same(x, y) ? 1 : 0);
			}
		}
		
	}
	
}

Measured memory_bytes: 101292
#include <iostream>
#include <stack>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

#define rep(i,n) for(int i=0; i < n; i++)
using ll =  long long;
using namespace std;
#define pi 3.14159265358979

// 回文チェック関数

bool Pal(string a)
{
	int size = a.length();
	rep(i, size / 2) if (a[i] != a[size - i - 1]) return false;
	return true;
}

int main()
{
	int a, b, count = 0;
	cin >> a >> b;

	for (int i = a; i < b + 1; i++) if (Pal(to_string(i))) count++;

	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include<iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int a,b;
    cin >> a >> b;
    cout << 6-a-b << "\n";
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdint>
#include <bitset>
#include <vector>
#include <thread>
#include <stack>
#include <map>


using namespace std;

int main()
{
	int a = 0, b = 0, c;
	for (int i = 0; i < 3; i++)
	{
		cin >> c;
		if (c == 5) a++;
		else if (c == 7) b++;
	}
	if (a == 2 && b == 1) printf("YES");
	else printf("NO");
}

Measured memory_bytes: 3220
#include <iostream>
#include <vector>

using namespace std;
int n;
int x[1000];
int y[1000];
int d[40];

int main(){
    cin >> n;
    int mx = 0;
    int k = -1;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        if (k != -1 && k != abs(x[i] + y[i]) % 2) {
            //cout << i << endl;
            //cout << k << endl;
            cout << "-1" << endl;
            return 0;
        }
        k = abs(x[i] + y[i]) % 2;
        mx = max(abs(x[i] + y[i]), mx);
    }

    int m = 1;
    while(mx != 0) {
        mx /= 2;
        m++;
    } 
    long long d[40];
    d[m - 1] = 1;
    d[m - 2] = 1;
    for (int i = (k == 0 ? m - 3: m - 2); i >= 0; --i) {
        d[i] = d[i + 1] * 2;
    }
    cout << m << endl;
    cout << d[0];
    for (int i = 1; i < m; ++i) {
        cout << " " << d[i];
    }
    cout << endl;

    for (int ni = 0; ni < n; ++ni) {
        int xc = 0;
        int yc = 0;
        for (int i = 0; i < m; ++i) {
            int dx = x[ni] - xc;
            int dy = y[ni] - yc;
            int u = dx + dy;
            int v = - dx + dy;
            char mode = 'a';
            if (u >= 0 && v >= 0) {
                mode = 'U';
                yc += d[i];
            } else if (u >= 0 && v < 0) {
                mode = 'R';
                xc += d[i];
            } else if (u < 0 && v >= 0) {
                mode = 'L';
                xc -= d[i];
            } else if (u < 0 && v < 0) { 
                mode = 'D';
                yc -= d[i];
            }
            cout << mode;
        }
        if (xc != x[ni] || yc != y[ni]) {
            cout << x[ni] << ", " << y[ni] << " " << xc << ", " << yc << endl;
        }
        cout << endl;
    }


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
 
struct UnionFind
{
  vector< int > data;
 
  UnionFind(int sz) : data(sz, -1) {}
 
  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
 
  int size(int k)
  {
    return (-data[find(k)]);
  }
};
 
 
int main()
{
  int N, C[100000], M;
  vector< int > g[100000];
  vector< pair< int, int > > beet[100000];
  int dp[100000];
 
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    scanf("%d", &C[i]);
  }
  scanf("%d", &M);
 
  UnionFind tree(N);
  for(int i = 0; i < M; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    if(C[a] > C[b]) swap(a, b);
    if(C[a] == C[b]) tree.unite(a, b);
    else g[a].push_back(b);
    beet[a].emplace_back(C[b], b);
    beet[b].emplace_back(C[a], a);
  }
 
  for(int i = 0; i < N; i++) {
    sort(begin(beet[i]), end(beet[i]));
    for(int j = 1; j < beet[i].size(); j++) {
      auto &pv = beet[i][j - 1], cr = beet[i][j];
      if(pv.first == cr.first) tree.unite(pv.second, cr.second);
      else g[pv.second].push_back(cr.second);
    }
  }
 
  vector< int > order;
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) {
      order.push_back(i);
      dp[i] = 1;
    } else {
      copy(begin(g[i]), end(g[i]), back_inserter(g[tree.find(i)]));
      g[i].clear();
    }
  }
 
  sort(begin(order), end(order), [&](int a, int b)
  {
    return (C[a] < C[b]);
  });
 
  long long ret = 0;
  for(int idx : order) {
    for(int to : g[idx]) dp[tree.find(to)] = max(dp[tree.find(to)], dp[idx] + 1);
    ret += 1LL * dp[idx] * tree.size(idx);
  }
 
  printf("%lld\n", ret);
}

Measured memory_bytes: 19396
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;
  int B;
  int C;
  int K;
  cin >> A;
  cin >> B;
  cin >> C;
  cin >> K;
  if ( K <= A ) {
    cout << K << endl;
  }
  else if ( K <= ( A + B ) ) {
    cout << A << endl;
  }
  else {
    cout << ( A - ( K - A - B ) ) << endl;
  }
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j;
	cin>>n;
	double arr[n],ans=0,dp[n+1],p;
	for(i=1;i<=n;i++)
		dp[i]=0.0;
	dp[0]=1.0;
	for(i=0;i<n;i++)
	{
		cin>>p;
		for(j=(n);j>0;j--)
			dp[j]=dp[j-1]*p + dp[j]*(1.0-p);//instead of using two array and iterating from 0 we use one array and iterate from last
		dp[0]=dp[0]*(1.0-p);
	}
	for(i=(n/2+1);i<=n;i++)
		ans+=dp[i];
	cout<<fixed;
	cout<<setprecision(10);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int a = sc.nextInt();
			String op = sc.next();
			int b = sc.nextInt();
			int ans;
			if (op.equals("?")) {
				break;
			} else {
				if (op.equals("+")) {
					ans = a + b;
				} else if (op.equals("-")) {
					ans = a - b;
				} else if (op.equals("/")) {
					if (b == 0) {
						break;
					}
					ans = a / b;
				} else {
					ans = a * b;
				}
				System.out.println(ans);
			}
		}
		sc.close();
	}
}



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

int main()
{
    long long int n,t,sum=0,rem;
    scanf("%lld",&n);
    t=n;
    while(t>0)
    {
        rem=t%10;
        sum+=rem;
        t=t/10;
    }
    if(n%sum==0)
        printf("Yes");
    else
        printf("No");
    return 0;
}

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

#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    string S; cin >> S;
    
    sort(ALL(S));
    Yes(S[0] == S[1] && S[2] == S[3] && S[1] != S[2]);
}


Measured memory_bytes: 256
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reads f = stdin.ReadLine().Split() |> Array.map f

[<EntryPoint>]
let main argv =
    let [|hh;ww|] = reads int
    let [|h;w|] = reads int
    printfn "%i" ((hh - h) * (ww - w))
    0

Measured memory_bytes: 14044
while True:
    a,op,b=input().split()
    a,b=map(int,(a,b))
    if op=='?':
        break
    elif op=='+':
        print(str(int(a+b)))
    elif op=='-':
        print(str(int(a-b)))
    elif op=='*':
        print(str(int(a*b)))
    else:
        print(str(int(a//b)))

Measured memory_bytes: 7724
#include <iostream>
#include <string>
#include <functional>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

using i64 = int64_t;

void shit(i64 x) {
	cout << x << endl;
	exit(0);
}

int main() {
	i64 k, a, b;
	cin >> k >> a >> b;
	if (a >= b || b == a + 1) {
		shit(k + 1);
	}
	if (k <= a - 1) {
		shit(k + 1);
	}
	i64 t = (k - a + 1) / 2ll;
	i64 fuck = (k - a + 1) % 2ll;
	shit(a + t * (b - a) + fuck);
    return 0;
}

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

int main(){
    int A,B,C;
    cin >> A >> B >> C;
    if(A+B+C > 21)cout << "bust";
    else cout <<"win";
    return 0;
}

Measured memory_bytes: 256
import Control.Monad
import Data.List

solve  :: [Double] -> Double
solve [] = 0
solve (a:as) | as == [] = a
             | otherwise = solve ([(a + (head as)) / 2] ++ (tail as))

main = do
    n <- readLn :: IO Int
    vi <- map (\x -> fromRational $ toRational $ (read x) :: Double)  . words <$> getLine
    print $ solve (sort vi)


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

int main() {
  
  char c;
  cin >> c;
  
  if(c == 'a' ){
    
    cout << "vowel" << endl;
    
  }
  
  else if(c == 'e'){
    
    cout << "vowel" << endl;
    
  }
  
  else if(c == 'i'){
    
    cout << "vowel" << endl;
    
  }
  
   else if(c == 'o'){
    
    cout << "vowel" << endl;
    
  }
  
   else if(c == 'u'){
    
    cout << "vowel" << endl;
    
  }
  
  else{
    
    cout << "consonant" << endl;
  }
  
}

Measured memory_bytes: 256