akhauriyash/Code-Regression huggingface dataset:
N = gets.to_i
R = N.times.map { gets.split.map(&:to_i) }

A = []
B = []

R.each do |a, b|
  A << a
  B << b
end

A.sort!
B.sort!

if N.odd?
  puts B[N / 2] - A[N / 2] + 1
else
  mb = (B[N / 2] + B[N / 2 - 1]) / 2.0
  ma = (A[N / 2] + A[N / 2 - 1]) / 2.0
  n = mb - ma + 1
  puts (2 * n - 1).to_i
end


Measured memory_bytes: 34492
#include <bits/stdc++.h>
#define ll long long
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e5 + 5;
ll mod = 1e9 + 7;
int  ans[N];
int main() {
	IO
	int n;
	cin >> n;
	int arr[n][3], ans[n][3];
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 3; j++){
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < 3; i++)
		ans[0][i] = arr[0][i];
	for (int i = 1; i < n; i++){
		ans[i][0] = max(ans[i - 1][1], ans[i - 1][2]) + arr[i][0];
		ans[i][1] = max(ans[i - 1][0], ans[i - 1][2]) + arr[i][1];
		ans[i][2] = max(ans[i - 1][0], ans[i - 1][1]) + arr[i][2];
	}
	cout << max(max(ans[n - 1][0], ans[n - 1][1]), ans[n - 1][2]);
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;
typedef long double ld;
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    int ans = 0;
    cin >> n >> m;
    vector<int> l(m);
    vector<int> r(m);
    for(int i = 0; i < m; i++)
    {
        cin >> l[i] >> r[i];
    }
    cout << max(0, *min_element(r.begin(), r.end()) - *max_element(l.begin(), l.end()) + 1);

    return 0;
}


Measured memory_bytes: 1024
a = dict()
b = list(input())
s1 = "random"
s2 = "random"
x = 0
y = 0
for i in b:
    if i == s1:
        x += 1
    elif i == s2:
        y += 1
    else:
        if s1 == "random":
            s1 = i
            x += 1
        elif s2 == "random":
            s2 = i
            y += 1
if x == 2 and y == 2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e3+7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int n, s;
ll a[maxn], dp[maxn];

int main() {
    n=read(), s=read();
    for(int i=1; i<=n; ++i) a[i]=read();
    ll res=0;
    for(int i=1; i<=n; ++i) {
        for(int j=s; j>=a[i]; --j) {
            if(j==a[i]) dp[j]=(dp[j]+i)%mod;
            else dp[j]=(dp[j]+dp[j-a[i]])%mod;
        }
        res=(res+dp[s])%mod;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
N = gets.to_i
last = [0, 0, 0]
readlines.each do |s|
  a = s.split.map(&:to_i)
  [1,2,0,1].each_cons(2).with_index do |(j,k),i|
    x, y = a[i] + last[j], a[i] + last[k]
    last << (x < y ? y : x)
  end
  last.shift(3)
end
puts last.max


Measured memory_bytes: 10620
#include <stdio.h> 

 #include <math.h> 
 
 
int main(){ 
     int a, b, angle; 
    double s, l, h; 
 
 
     scanf("%d %d %d", &a, &b, &angle); 
      h=b*sin(angle*M_PI/180.0); 
     s=a*h/2; 
     l=a+b+sqrt((a*a+b*b-2*a*b*cos(angle*M_PI/180.0))); 
printf("%f\n", s); 
     printf("%f\n", l); 
printf("%f\n", h); 

 
    return 0; 
 } 



Measured memory_bytes: 2104
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Console;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static StreamWriter sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
        static void Main(string[] args)
        {
            try
            {
                SetOut(sw);
                Solve.Answer();
                Out.Flush();
            }
            catch (Exception ex)
            {
                WriteLine(ex.ToString());
            }
        }
    }

    public class Solve
    {
        public static void Answer()
        {
            var nk = IO.RSLong;
            var ab = new Dictionary<long, long>();
            for (int i = 0; i < nk[0]; i++)
            {
                var work = IO.RSLong;
                if (ab.ContainsKey(work[0]))
                {
                    ab[work[0]] += work[1];
                }
                else
                {
                    ab[work[0]] = work[1];
                }
            }
            var sortab = ab.OrderBy(x => x.Key);
            foreach (var kvpair in sortab)
            {
                nk[1] -= kvpair.Value;
                if (nk[1] <= 0)
                {
                    WriteLine(kvpair.Key);
                    return;
                }
            }
        }
    }

    public class IO
    {
        #region Input
        public static int RInt => int.Parse(ReadLine());
        public static long RLong => long.Parse(ReadLine());
        public static double RDouble => double.Parse(ReadLine());

        public static string[] RSString => ReadLine().Split();
        public static int[] RSInt => ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        public static long[] RSLong => ReadLine().Split().Select(s => long.Parse(s)).ToArray();
        public static double[] RSDouble => ReadLine().Split().Select(s => double.Parse(s)).ToArray();
        #endregion

        #region Output
        public static void OutJoinSpace<T>(IEnumerable<T> list) => WriteLine(string.Join(" ", list));
        public static void WriteLineYes_or_No(bool flag) => WriteLine(flag ? "Yes" : "No");
        public static void WriteLineYES_or_NO(bool flag) => WriteLine(flag ? "YES" : "NO");
        #endregion
    }

    public class Mod
    {
        #region
        private readonly static long M = 1000000007;

        public static long Add(long a, long b) => (a * b) % M;
        public static long Sub(long a, long b) => (a - b) % M >= 0 ? (a - b) % M : (a - b) % M + M;
        public static long Multi(long a, long b) => (a * b) % M;
        #endregion
    }
}

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

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

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import copy
from fractions import gcd
# from math import gcd

a, b = map(int, input().split())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

base = gcd(a, b)

yakusu = make_divisors(base)
rest = copy.deepcopy(yakusu)

count = 0
ans = []
for v in yakusu:
    if v == 1:
        ans.append(1)
        continue
    if rest == []:
        break
    new_rest = []
    for r in rest:
        if r == 1:
            continue
        if r == v:
            ans.append(r)
            continue
        if r % v != 0:
            new_rest.append(r)
    rest = new_rest

print(len(set(ans)))

Measured memory_bytes: 5340
#include<iostream>
#include<algorithm>
#include<vector>
#include <queue>
#include<map>
using namespace std;
int main()
{
	long long int n, d;
	double x, y;
	long int num = 0;
	cin >> n >> d;
	for (long int i = 1; i <= n; i++)
	{
		cin >> x >> y;
		if (x * x + y * y <= d * d)
			num++;
	}
	cout << num << endl;
}






Measured memory_bytes: 3772
N = int(input())
A = [int(x) - 1 for x in input().split()]

S = {0}

for i, v in enumerate(A):
    S2 = set()
    for j in S:
        if v == i - j:
            S2.add(j)
        else:
            S2.add(j + 1)
    S = S2

ans = min(S)
if ans == N:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 77772
from collections import defaultdict
n, k = map(int, input().split())
dic = defaultdict(int)
for i in range(n):
    a, b = map(int, input().split())
    dic[a] += b

t = sorted(dic.keys())
for i in t:
    k -= dic[i]
    if k <= 0:
        print(i)
        break

Measured memory_bytes: 10848
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass : Scanner
{
    static int N;
    static long K;
    static long[] A;
    static long[] F;
    static void Main()
    {
        (N, K) = ReadStream<int, long>();
        A = RLongs();
        F = RLongs();
        Array.Sort(A);
        Array.Sort(F);
        Array.Reverse(F);

        long lb = -1, ub = 2000000000001;
        while (ub - lb > 1)
        {
            var mid = (lb + ub) / 2;
            if (comp(mid)) lb = mid;
            else ub = mid;
        }
        WriteLine(ub);
    }
    static bool comp(long mid)
    {
        long k = K;
        for (int i = 0; i < N; i++)
        {
            if (A[i] * F[i] > mid)
            {
                var dif = A[i] - mid / F[i];
                k -= Max(dif,0);
            }
        }
        return k < 0;
    }
}

class Scanner
{
    public static int RInt() => int.Parse(Console.ReadLine());
    public static long RLong() => long.Parse(Console.ReadLine());
    public static string RString() => Console.ReadLine();
    public static double RDouble() => double.Parse(Console.ReadLine());

    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static string[] RStrings() => Console.ReadLine().Split();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static T1 ReadStream<T1>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadStream<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadStream<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadStream<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[0], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[0], typeof(T4));
        return (r1, r2, r3, r4);
    }
}

Measured memory_bytes: 62296
#include <iostream>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

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

	int s = (x - a > 0) ? (x - a) : (a - x);
	int t = (x - b > 0) ? (x - b) : (b - x);

	cout << ((s < t) ? "A" : "B") << endl;

	return 0;
}

Measured memory_bytes: 256
import math
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
def cmbmod(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = result*int(numerator[k])%mod
    return result
N=int(input())
X = list(map(int,input().split()))
T=0
mod=10**9+7
pmod=0
A=math.factorial(N-1)%mod
for i in range(1,N):
 pmod+=powmod(i, mod - 2, mod)
 T+=(X[i]-X[i-1])*pmod
 T%=mod
print((A*T)%mod)

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

string n;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    long long int ans = 0;
    for (int i=0; i<n.length(); i++) {
        int a = (int)n[i]-48;
        ans += a;
    }
    if (ans % 9 == 0) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}


Measured memory_bytes: 3696
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	String str;
	long num;
	int sum=0;
	char c;

	while(true){
	    str = in.next();
	    if(str.equals("0"))break;
	    sum=0;
	    for(int i=0;i<str.length();i++){
		c = str.charAt(i);
		sum+=Character.getNumericValue(c);
	    }
	    System.out.println(sum);
	}
    }
}



Measured memory_bytes: 26092
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int SIZE=100001;
//int arr[SIZE]={};
//???????????§???????????¬
const int MAX_V=100001;
const int MAX_LOGV=32;
//??°???????????£??\???????????¨???????????????v??¨???????????£????????????????????\??£????????????
vector<int> G[MAX_V];
//??????2^k????????£????????????????????????
int parent[MAX_LOGV][MAX_V]={};
//??????????????±???
int depth[MAX_V]={};
//?????????????????????
int root=0;
void dfs(int v,int p,int d);
void init(int v);
int lca(int u,int v);
 
int main(){
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int k;
		cin>>k;
		for(int j=0;j<k;j++){
			int c;
			cin>>c;
			G[i].push_back(c);
			G[c].push_back(i);
		}
	}
	init(N);
	int Q;
	cin>>Q;
	for(int i=0;i<Q;i++){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}
 
//?????°v,p,d?????????????????§??±???????????¢?´¢?????????
void dfs(int v,int p,int d){
	//parent[0][v]????????????v??????1????????£??????????????????p?????£??\
	parent[0][v]=p;
	//depth[v]????????????v?????±?????????d?????£??\
	depth[v]=d;
	//G[v]??????????????????G[v][i]???p??§????????????
	//dfs(G[v][i],v,d+1)????????¶
	//?????????????????????????????????????????£?????°??????????????????????????§??????
	for(int i=0;i<G[v].size();i++){
		if(G[v][i]!=p){
			dfs(G[v][i],v,d+1);
		}
	}
}
//?????????
//V?????????????????°
void init(int V){
	//?????????dfs???????????????
	//????????????????????????????????????parent[0]??¨depth?????????
	dfs(root,-1,0);
	//parent????????????
	for(int k=0;k+1<MAX_LOGV;k++){
		for(int v=0;v<V;v++){
			if(parent[k][v]<0)
				parent[k+1][v]=-1;
			else
				parent[k+1][v]=parent[k][parent[k][v]];
		}
	}
}
//u??¨v???LCA????±???????
int lca(int u,int v){
	//u??¨v?????±??????????????????????????§????????????
	//u??¨v??????????????????????????????????????????????????????????????????
	if(depth[u]>depth[v])
		swap(u,v);
	for(int k=0;k<MAX_LOGV;k++){
		if(((depth[v]-depth[u])>>k)&1)
			v=parent[k][v];
	}
	//u=v??????????????????LCA??§????????????v?????????
	if(u==v)
		return v;
	//???????????????????????¢?´¢??§LCA????±???????
	//u,v???????????????????????§??????
	for(int k=MAX_LOGV-1;k>=0;k--){
		if(parent[k][u]!=parent[k][v]){
			u=parent[k][u];
			v=parent[k][v];
		}
	}
	return parent[0][u];
}

Measured memory_bytes: 27660
X = 998244353

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

def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

inv_cache = [1]
for i in range(1, K + 1):
	inv_cache.append(calc_inverse(i, X))

inv_f_cache = [1]
d = 1
for i in range(1, K + 1):
	d = (d * inv_cache[i]) % X
	inv_f_cache.append(d)

f_cache = [1]
c = 1
for i in range(N - 1, N - K - 1, -1):
	c = (c * i) % X
	f_cache.append(c)

#print(f_cache, inv_f_cache)

def C(n, m):
#	if m in f_cache:
#		c = f_cache[m]
#	else:
#		c = 1
#		for i in range(n - m + 1, n + 1):
#			c = (c * i) % X
#		f_cache[m] = c
#	d = 1
#	for i in range(1, m + 1):
#		d = (d * inv_cache[i]) % X
#	print(m)
	return (f_cache[m] * inv_f_cache[m]) % X


total = 0
for k in range(K + 1):
	total = (total + M * pow(M - 1, N - 1 - k, X) * C(N - 1, k)) % X
	
#	print(k, M * pow(M - 1, N - 1 - k, X))
	

print(total)


Measured memory_bytes: 106864
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
    int n,k;cin>>n>>k;
    int d[k];
    rep(i,k)cin>>d[i];
    rep2(i,n,100000){
        string s = to_string(i);
        bool f=true;
        rep(j,s.length()){
            rep(l,k){
                if(s[j]-'0'==d[l]){
                    f=false;
                    break;}
            }
        }
        if(f){
            cout<<i<<endl;
            return 0;
        }
    }
    }

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

X,Y = map(int,input().split())

#a+b=X
#2a+4b+Y
#2a+2b=2X
#a=(4X-Y)/2
#b=(Y-2X)/2

# if Y-2X=0; b=0; a=X; 2a=Y; print Yes
if Y%2!=0  :
  print("No")
  exit()

#if (Y-2*X) < 0 or (4*X-Y) < 0 or Y%2!=0  :
#  print("No")
#  exit()

b=int((Y-2*X)/2)
a=int(X-b)

# if a>=0 and b>=0 -> Yes, else -> No
if a >= 0 and b >= 0 :
  print("Yes")
else:
  print("No")


Measured memory_bytes: 9172
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>

#define int long

const int INF = 1000000009;
const long LINF = 1123456789012345678;

int n;
int a[100005], b[100005];
int score[100005];
int sum;

signed main(){
	scanf("%ld", &n);
	for(int i = 0; i < n; i++){
		scanf("%ld %ld", &a[i], &b[i]);
		score[i] = a[i] + b[i];
		sum += a[i];
	}
	std::sort(score, score+n, std::greater<int>());
	for(int i = 0; i < n; i++){
		if(i % 2 == 1){
			sum -= score[i];
		}
	}
	printf("%ld\n", sum);
	return 0;
}


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

#define ll long long

int main()
{
	ll N;
	cin>>N;
	
	vector< vector<ll> >vect;
	ll val;
	
	for(ll i=0;i<N;i++)
	{
		vector<ll>stuff;
		for(ll u=0;u<3;u++)
		{
			cin>>val;
			stuff.push_back(val);
		}

		vect.push_back(stuff);
	}
	
	ll dp[N+1][3];

	for(ll i=1;i<=N;i++)
	{
		for(ll act=0;act<3;act++)
		{
	 if(i==1)
	 {
	 	dp[i][act]=vect[i-1][act];
	 }
	 
	 else
	 {
	 	
		 if(act==0)
		 {dp[i][act]=vect[i-1][act]+max(dp[i-1][1],dp[i-1][2]);}
		 
		 else if(act==1)
		 {
		 	dp[i][act]=vect[i-1][1]+max(dp[i-1][0],dp[i-1][2]);
		 }
		 
		 else
		 {
		 	dp[i][act]=vect[i-1][2]+max(dp[i-1][0],dp[i-1][1]);
		 }
	 }
	
		}
	}
	
	cout<<max(dp[N][0],max(dp[N][1],dp[N][2]))<<endl;
	
}


Measured memory_bytes: 8752
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge>>;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int H,W;
int main(){
    cin >> H >> W;
    char fd[H+10][W+10];
    string s;
    rep(i,H){
        cin >> s;
        rep(j,W) fd[i][j] = s[j];
    }
    
    int ans[H+10][W+10];
    rep(i,H) rep(j,W) ans[i][j] = 0;
    
    
    rep(i,H){
        vector<int> ls = {};
        int ct = 0;
        rep(j,W){
            if(fd[i][j]=='#') ls.pb(ct), ct = 0;
            else if(j==W-1) ls.pb(ct+1);
            else ct++;
        }
        int ix = 0;
        rep(j,W){
            ans[i][j] += ls[ix];
            if(fd[i][j]=='#') ix++;
        }
    }
    
    rep(j,W){
        vector<int> ls = {};
        int ct = 0;
        rep(i,H){
            if(fd[i][j]=='#') ls.pb(ct), ct = 0;
            else if(i==H-1) ls.pb(ct+1);
            else ct++;
        }
        int ix = 0;
        rep(i,H){
            ans[i][j] += ls[ix];
            if(fd[i][j]=='#') ix++;
        }
    }
    

    
    int answer = 0;
    
    rep(i,H) rep(j,W) answer = max(answer,ans[i][j]);
    
    pr(answer-1);
}

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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;
    string S;
    cin>>S;
    int m = 0;


    rep(s_i,N){
        string str = S.substr(s_i,N-s_i);
        vector<int> A(str.size());
        A[0]= S.size();        
        int i=1,j=0;
        while(i<str.size()){
            while(i+j<str.size()&&str[j]==str[i+j]) ++j;
            A[i]=j;
            m = max(m,min(j,i));
            if(j==0){
                ++i;continue;
            }
            int k=1;
            while(i+k<str.size() && k+A[k]<j){
                A[i+k] = A[k];++k;
            }
            i+=k;j-=k;
        }
        // for(auto a:A){
        //     cout<<a;
        // }
        // cout<<"\n";
    }
    cout<<m<<"\n";
}




Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#define N 100005
typedef long long ll;
using namespace std;
ll n, s, x, y, a[5][100005];
int main() {
	int i, j;
	scanf("%lld", &n);
	for(i=0; i<3; i++) {
		for(j=0; j<n; j++) scanf("%lld", &a[i][j]);
		sort(a[i], a[i]+n);
	}
	for(i=0; i<n; i++) {
		x = lower_bound(a[0], a[0]+n, a[1][i]) - a[0];
		y = n - (upper_bound(a[2], a[2]+n, a[1][i]) - a[2]);
		s += x*y;
	}
	printf("%lld", s);
	return 0;
}

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

using namespace std;


string solve(int A, int B, int C, int D) {
	string S = "";

	if ((A + B + C + D) == 7) {
		S = to_string(A) + "+" + to_string(B) + "+" + to_string(C) + "+" + to_string(D) + "=7";
	}
	else if ((A + B + C - D) == 7) {
		S = to_string(A) + "+" + to_string(B) + "+" + to_string(C) + "-" + to_string(D) + "=7";
	}
	else if ((A + B - C + D) == 7) {
		S = to_string(A) + "+" + to_string(B) + "-" + to_string(C) + "+" + to_string(D) + "=7";
	}
	else if ((A - B + C + D) == 7) {
		S = to_string(A) + "-" + to_string(B) + "+" + to_string(C) + "+" + to_string(D) + "=7";
	}
	else if ((A - B - C + D) == 7) {
		S = to_string(A) + "-" + to_string(B) + "-" + to_string(C) + "+" + to_string(D) + "=7";
	}
	else if ((A - B + C - D) == 7) {
		S = to_string(A) + "-" + to_string(B) + "+" + to_string(C) + "-" + to_string(D) + "=7";
	}
	else if ((A + B - C - D) == 7) {
		S = to_string(A) + "+" + to_string(B) + "-" + to_string(C) + "-" + to_string(D) + "=7";
	}
	else if ((A - B - C - D) == 7) {
		S = to_string(A) + "-" + to_string(B) + "-" + to_string(C) + "-" + to_string(D) + "=7";
	}

	return S;
}

int main(void) {
	int N, A, B, C, D;


	cin >> N;
	A = N / 1000;
	B = (N - (A * 1000)) / 100;
	C = (N - ((A * 1000) + (B * 100))) / 10;
	D = N - ((A * 1000) + (B * 100) + (C * 10));

	cout << solve(A, B, C, D) << endl;


	return 0;
}

Measured memory_bytes: 256
// Package main provides
//
// File:  c.go
// Author: ymiyamoto
//
// Created on Sat Aug  4 04:37:06 2018
//
package main

import "fmt"

var N int
var arr []int

func main() {
	fmt.Scan(&N)
	arr = make([]int, N)

	count := 0
	for i := range arr {
		fmt.Scan(&arr[i])
		count += arr[i] - 1
	}

	fmt.Println(count)
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int n;
	double x[15],y[15];
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf %lf",&x[i],&y[i]);
	}
	double sum,m=0;
	int a[15];
	for(int i=1;i<=n;i++) a[i]=i;
	int k=0;
	do{
		sum=0;
		for(int i=2;i<=n;i++){
			sum+=sqrt((x[a[i-1]]-x[a[i]])*(x[a[i-1]]-x[a[i]])+(y[a[i-1]]-y[a[i]])*(y[a[i-1]]-y[a[i]]));
		}
		k++;
		m+=sum;
	}while(next_permutation(a+1,a+n+1));
	printf("%.10lf\n",m*1.0/k);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

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

  vector<ll> seenPos(m, -1);
  vector<ll> sum(m + 10, 0);
  ll cur = x, ans;
  seenPos[x] = 1;
  sum[1] = x;

  if (n == 1) {
    cout << x << endl;
    return 0;
  }

  FOR(i, 2, n + 1) {
    cur = (cur * cur) % m;
    if (i == n) {
      cout << sum[n - 1] + cur << endl;
      return 0;
    }
    if (seenPos[cur] == -1) {
      seenPos[cur] = i;
      sum[i] = sum[i - 1] + cur;
      continue;
    }
    sum[i] = sum[i - 1] + cur;
    // seenPos[cur]+1, ..., i でひとかたまり
    ll syuki = i - seenPos[cur];
    ll syukibun = sum[i] - sum[seenPos[cur]];
    ll rem = n - i;
    ll amariCnt = rem - syuki * (rem / syuki);
    ll amari = sum[seenPos[cur] + amariCnt] - sum[seenPos[cur]];
    // DUMP(syuki);
    // DUMP(syukibun);
    // DUMP(rem);
    // DUMP(amariCnt);
    // DUMP(amari);
    ans = sum[i] + syukibun * (rem / syuki) + amari;
    cout << ans << endl;
    break;
  }
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 1001001001;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

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

    vector<int> a(n);

    rep(i, n) {
        cin >> a[i];
    }
    int rsum = accumulate(a.begin(), a.end(), 0);
    int lsum = 0;
    int d = rsum;
    for (int i = 0; i < n; i++) {
        rsum -= a[i];
        lsum += a[i];
        int nd = abs(rsum - lsum);
        d = min(d, nd);
    }

    cout << d << endl;


}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

        
    
int main(){
  int n; cin >> n; int d[2][n];
  rep(i, n){
    cin >> d[0][i] >> d[1][i];
  }
  bool can = false;
  for(int i=0; i<=n-3; i++){
    if(d[0][i]==d[1][i] && d[0][i+1]==d[1][i+1] && d[0][i+2]==d[1][i+2]){
      can = true;
    }
  }
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3628
#include<stdio.h>

int main(){
	int x, y, r, w, h;
	scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);
	if((x-r)<0) printf("No\n");
	else if((y-r)<0) printf("No\n");
	else if((x+r)>h) printf("No\n");
	else if((y+r)>h) printf("No\n");
	else printf("Yes\n");
}


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

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

    if (b >= a)
        cout << a << endl;
    else
        cout << a - 1 << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
int isPrime(int);

int main(){
  int a[100000];
  int i,n,x;
  int count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    if(isPrime(x)){
      count++;
    }
  }
  printf("%d\n",count);
  return 0;
}

int isPrime(int x){
  int n,i;
  if(x==2){
    return 1;
  }
  if(x<2||x%2==0){
    return 0;
  }
  for(i=3;i*i<=x;i+=2){
    if(x%i==0){
      return 0;
    }
  }
  return 1;
}




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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

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

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

    int ma = I_INF;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ma = min(ma, A[i]);
        if (ma >= A[i]) ++ans;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>

int main(int argc, char const *argv[]) {
  int N, Y;
  scanf("%d %d", &N, &Y);
  int r;
  int c = 0;
  int x, y, z;
  for (int i = 0; Y >= 10000*i; i++) {
    int y1 = Y - 10000*i;
    for (int j = 0; y1 >= 5000*j; j++) {
      int y2 = y1 - 5000*j;
      if (y2 == (N - i - j)*1000) {
        printf("%d %d %d\n", i, j, (N - i - j));
        return 0;
      }
    }
  }
  printf("%d %d %d\n", -1, -1, -1);
  return 0;
}


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

int main()
{
    uint64_t n,m;
    uint64_t a=0,b=0;
    cin >> n;
     a = n/500;
     m = n % 500;
     b = m/5;

     cout << a*1000+b*5 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <utility>
#include <map> 
#include <queue>
#include <stack>
#include <iomanip>
#include <sstream>
#include <cstring>
#define MP make_pair
#define PB push_back
#define SZ size()
#define B begin()
#define E end()
#define ll long long
#define REP(i,a,n) for(ll i=a; i<n; ++i)
#define RED(i,n,a) for(ll i=n; i>=a; --i)
#define m9 1000000007
#define endl "\n"
#define F first
#define S second
#define ld long double
#define eps 0.00000000001
#define MAX 1000000007
#define vll vector <ll> 
#define pll pair <ll,ll> 

using namespace std;

ll gcd(ll a, ll b){
    if(a%b==0){
        return b;
    }
    else{
        return gcd(b, a%b);
    }
}
ll powc(ll a, ll b){
    if(b<0){
        return 0;
    }
    ll res=1;
    while(b>0){
        if(b&1){
            res*=a;
        }
        a*=a;
        res%=m9, a%=m9;
        b>>=1;
    }
    return res;
}



///target expert

int main(){
    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b, c, d; 
    cin>>a>>b>>c>>d;
    cout<<max(max(a*c,a*d),max(b*c,b*d));
}



Measured memory_bytes: 3648
while 1:
    n=int(input())
    if n==0:break
    now=0
    ans=0
    l=0
    r=0
    mt=list(map(str,input().split()))
    for i in mt:
        if i=="lu":l=1
        elif i=="ru":r=1
        elif i=="ld":l=0
        elif i=="rd":r=0
        if now==0:
            if l+r==2:
                ans+=1
                now=1
        elif now==1:
            if l+r==0:
                ans+=1
                now=0
    print(ans)


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> matrix;

void solve() {
  int n;
  set<int> s;
  cin >> n;
  while(n--) {
    int t;
    cin >> t;
    s.insert(t%2);
  }
  if(s.count(1) || s.size() == 2) cout << "first\n";
  else cout << "second\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL);
  solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
#include <cstdint>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long int ll;
typedef pair<int, int> P;
const vector<int> di = { -1, 0, 1, 0 };
const vector<int> dj = { 0, 1, 0, -1 };


int main() {

	ll x;
	cin >> x;

	ll ans = 0;

	if (x % 11 > 6) {
		ans = (x / 11) * 2 + 2;
	}
	else if (x % 11 > 0) {
		ans = (x / 11) * 2 + 1;
	}
	else {
		ans = (x / 11) * 2;
	}

	cout << ans << endl;
	
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e6 + 5;
int n;
vector<ii> p;

bool cmp(ii p1, ii p2) {
  return min(p1.second,p1.first+p2.second)
    > min(p2.second,p2.first+p1.second);
}

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

  cin >> n;
  string s;
  int tt = 0;
  for (int i = 0; i < n; ++i) {
    cin >> s;
    int cnt = 0;
    int mcnt = 0;
    for (auto cc : s) {
      if (cc == '(')
        ++cnt;
      else
        --cnt;
      mcnt = min(mcnt, cnt);
    }
    tt += cnt;
    p.push_back(ii(cnt, mcnt));
  }
  if (tt != 0) {
    cout << "No" << endl;
  } else {
    sort(p.begin(), p.end(), cmp);
    int cnt = 0;
    bool ok = true;
    for (auto it = p.begin(); it != p.end(); ++it) {
      if (it->second + cnt < 0) {
        ok = false;
        break;
      }
      cnt += it->first;
    }
    if (ok)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  
  return 0;
}


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

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	int ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = i; j < n; j += i) {
			ans++;
		}
	}
	cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3644
/* Author : Pranav Deshmukh
            PICT,Pune
   Stay Focused!
*/

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define int             long long
#define float           double
#define dip(type,var)   type var; cin>>var;
#define dipi(x)         int x; cin>>x;
#define dipi2(x,y)      int x,y; cin>>x>>y;
#define w(x)            int x; cin>>x; while(x--)
#define mka(type,arr,n) type *arr=new type[n];
#define fo(i,n)         for(int i=0;i<n;i++)
#define mod             pow(10,9)+7
#define inf             1e18
#define pi              3.141592653589793238
#define endl            "\n"
#define F               first
#define S               second
#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> >

void c_p_c()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.tie(0);
#ifndef ONLINE_JUDGE

	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main() {
	c_p_c();
	string s;
	cin >> s;
	if (s == "AAA" || s == "BBB")
		cout << "No";
	else
		cout << "Yes";
	return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>
#include <stdio.h>
#include <sstream>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll mod = 1e9 + 7;
const ll inf = 1LL << 60;
const long double pi = 3.14159265358979323846;

// ****************************************CODE***************************************//

ll n, h[100100];
ll dp[100100];

ll rec(ll i) {
    if(dp[i] != inf) return dp[i];
    if(i == 0) return 0;

    ll res = inf;
    res = min(res, rec(i-1) + abs(h[i] - h[i-1]));
    if(i>1) res = min(res, rec(i-2) + abs(h[i] - h[i-2]));

    return dp[i] = res;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    for(int i = 0; i < 100100; i++) dp[i] = inf;

    cout << rec(n-1) << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  int x,a,b,n;
  cin>>n>>a;
  if(n%500<=a) cout<<"Yes"<<'\n';
  else cout<<"No"<<'\n';
  return 0;
}


Measured memory_bytes: 256
// -*- coding:utf-8-unix -*-

#[macro_use]
extern crate lazy_static;
extern crate num_bigint; // 0.2.2
extern crate num_traits; // 0.2.8
use num_bigint::BigInt;
use num_traits::Pow;

// use proconio::derive_readable;
use proconio::fastout;
use proconio::input;
// use std::convert::TryInto;
use libm::*;
use std::cmp::*;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::io::*;
use std::ops::Range;
use std::str::FromStr;
use superslice::*;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//abc176-A
// #[fastout]
fn main() {
    input![n: i64, x: i64, t: i64];

    let is_remain = n % x != 0;
    println!("{}", t * (n / x + if is_remain { 1 } else { 0 }));
    // eprintln!("{:#015b}", ans);
    // println!("{}", ans);
}

// use lazy_static::lazy_static;
// use std::sync::Mutex;

// lazy_static! {
//     static ref VALUES: Mutex<Vec<i32>> = Mutex::default();
// }

// let mut values = VALUES.lock().unwrap();
// values.extend_from_slice(&[1, 2, 3, 4]);
// assert_eq!(&*values, &[1, 2, 3, 4]);

// -100000000
//  1000000000


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

struct Mod
{
    static const auto P = int(1e9+7);
    long long k;

    Mod() = default;
    Mod(const long long k) : k(k%P) {}
};

Mod operator*(const Mod a, const Mod b) { return a.k * b.k; }
Mod& operator*=(Mod& a, const Mod b) { return a = a*b; }
Mod power(const Mod a, const int k)
{
    if (k == 0) return 1;
    else if (k % 2 == 0) return power(a*a, k/2);
    else return a * power(a*a, k/2);
}
Mod inverse(const Mod a) { return power(a, Mod::P-2); }

struct DisjointSets
{
    int N;
    vector<int> representatives, sizes;

    DisjointSets(const int N) : N(N), representatives(N), sizes(N, 1)
    {
        iota(begin(representatives), end(representatives), 0);
    }

    int find(const int n)
    {
        if (representatives[n] != n)
            representatives[n] = find(representatives[n]);
        return representatives[n];
    }

    void merge(int n, int m)
    {
        n = find(n), m = find(m);
        if (n == m) return;
        representatives[n] = m;
        sizes[m] += sizes[n];
    }

    int size(const int n) { return sizes[find(n)]; }
};

int main()
{
    int N, X, Y; cin >> N >> X >> Y;

    struct Ball { int index, color, weight; };
    auto balls = vector<vector<Ball>>(N);
    for (auto i = 0; i < N; i++)
    {
        int c, w; cin >> c >> w;
        c--;
        balls[c].push_back({i, c, w});
    }

    for (auto& bs : balls) sort(begin(bs), end(bs), [](const Ball a, const Ball b) { return a.weight < b.weight; });
    const auto compare = [](const vector<Ball>& a, const vector<Ball>& b)
    {
        if (a.empty() && b.empty()) return false;
        else if (a.empty()) return false;
        else if (b.empty()) return true;
        else return a[0].weight < b[0].weight;
    };
    sort(begin(balls), end(balls), compare);

    auto components = DisjointSets(N);
    const auto add_edge = [&](const Ball a, const Ball b)
    {
        const auto bound = a.color == b.color ? X : Y;
        if (a.weight + b.weight <= bound)
            components.merge(a.index, b.index);
    };

    for (const auto& bs : balls) for (const auto b : bs)
    {
        add_edge(b, bs[0]);
        add_edge(b, balls[0][0]);
        if (N >= 2 && !balls[1].empty()) add_edge(b, balls[1][0]);
    }

    auto color_counts = vector<map<int, int>>(N);
    for (const auto& bs : balls) for (const auto b : bs)
        color_counts[components.find(b.index)][b.color]++;

    auto factorials = vector<Mod>(N+1);
    factorials[0] = 1;
    for (auto n = 1; n <= N; n++) factorials[n] = n * factorials[n-1];

    auto inverse_factorials = vector<Mod>(N+1);
    inverse_factorials[N] = inverse(factorials[N]);
    for (auto n = N; n >= 1; n--) inverse_factorials[n-1] = n * inverse_factorials[n];

    auto result = Mod(1);
    for (auto i = 0; i < N; i++) if (components.find(i) == i)
    {
        result *= factorials[components.size(i)];
        for (const auto kv : color_counts[i])
            result *= inverse_factorials[kv.second];
    }
    cout << result.k << endl;
}


Measured memory_bytes: 33024
#include <iostream>
#include <set>
using namespace std;
//abc073-c
int n;
set<int> a;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int t;
		cin>>t;
		if(a.count(t)){
			a.erase(t);
		}else{
			a.insert(t);
		}
	}
	cout<<a.size()<<endl;
	return 0;
}

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

int main(void){
    int n,m,flag,i;
    flag = 0;

    cin >> n >> m;

    vector<int> num(n+1,-1);  //guessing num
    vector<int> s(m),c(m);   //condition

    for(i=0; i<m; i++){
        cin >> s.at(i) >> c.at(i);
        
        if(num.at(s.at(i)) == -1){
            num.at(s.at(i)) = c.at(i);
        }else{
            if(num.at(s.at(i)) != c.at(i)){
                flag = 1;
            }
        }
    }


    if(n >= 2 && num.at(1)== 0){
        flag = 1;
    }


    if(n == 3 && flag == 0){
        if(num.at(1) == -1){
            num.at(1) = 1;
        }
        if(num.at(2) == -1){
            num.at(2) = 0;
        }
        if(num.at(3) == -1){
            num.at(3) = 0;
        }
    }

    if(n == 2 && flag == 0){
        if(num.at(1) == -1){
            num.at(1) = 1;
        }
        if(num.at(2) == -1){
            num.at(2) = 0;
        }
    }


    if(n == 1 && flag == 0){
        if(num.at(1) == -1){
            num.at(1) = 0;
        }
    }



    if(flag == 0){
        if(n == 1){
            cout << num.at(1) << endl;
        }else if(n == 2){
            cout << num.at(1) << num.at(2) << endl;
        }else if(n == 3){
            cout << num.at(1) << num.at(2) << num.at(3)  << endl; 
        }
    }else if(flag == 1){
        cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,M;
int A[100010],B[100010];
int num[100010];

signed main(){
	cin>>N>>M;
	REP(i,M){
		cin>>A[i]>>B[i];
		if(A[i]>B[i]){
			swap(A[i],B[i]);
		}
		num[A[i]-1]++,num[B[i]-1]--;
	}
	REP(i,N){
		num[i+1]+=num[i];
		DEB(num[i])END
	}
	REP(i,N-1){
		if(num[i]%2==1){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0;
}


Measured memory_bytes: 2560
extern crate core;

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = run(input.trim().to_string());
    println!("{}", output);
}

fn run(input: String) -> String {
    let list = input
        .split_whitespace()
        .map(|x| x.parse::<i64>().unwrap())
        .collect::<Vec<_>>();
    if list[0] + list[1] >= list[2] {
        "Yes"
    } else {
        "No"
    }.to_string()
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!(super::run($input.to_string()), $output.to_string());
                }
            )*
        }
    }
}

tests! {
    test1: "50 100 120" => "Yes",
    test2: "500 100 1000" => "No",
    test3: "19 123 143" => "No",
    test4: "19 123 142" => "Yes",
}


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

using namespace std;

int n, w, h;
int imosxadd[100003] = {0};
int imosxsub[100003] = {0};
int imosyadd[100003] = {0};
int imosysub[100003] = {0};

int main() {
    cin >> n >> w >> h;
    
    for (int i = 0; i < n; ++i) {
        int xi, yi, wi;
        cin >> xi >> yi >> wi;

        imosxadd[max(xi - wi, 0)]++;
        imosxsub[min(xi + wi + 1, w + 1)]++;
        imosyadd[max(yi - wi, 0)]++;
        imosysub[min(yi + wi + 1, h + 1)]++;
        //for (int j = 0; j < w + 1; ++j) {
        //    if (imosxadd[j] != 0 || imosxsub[j] != 0)
        //        cout << imosxadd[j] - imosxsub[j] << "(" << j << ") ";
        //}
        //cout << endl;
        //for (int j = 0; j < h + 1; ++j) {
        //    if (imosyadd[j] != 0 || imosysub[j] != 0)
        //        cout << imosyadd[j] - imosysub[j] << "(" << j << ") ";
        //}
        //cout << endl;
    }

    int xsum = 0;
    bool xans = imosxadd[0] != 0;
    for (int i = 0; i < w + 1; ++i) {
        xsum -= imosxsub[i];
        if (xsum <= 0 && i > 0) {
            xans = false;
            //break;
        }
        xsum += imosxadd[i];
    }
    int ysum = 0;
    bool yans = imosyadd[0] != 0;
    for (int i = 0; i < h + 1; ++i) {
        ysum -= imosysub[i];
        //cout << ysum << " ";
        if (ysum <= 0 && i > 0) {
            yans = false;
            //break;
        }
        ysum += imosyadd[i];
    }

    cout << (xans || yans ? "Yes" : "No") << endl;
}


Measured memory_bytes: 4684