akhauriyash/Code-Regression huggingface dataset:
def main
  # n = $stdin.gets.to_i
  # ↑rspec側で$stdinをすげ替えているので明示的にそれを読み込ませる
  #   ただし、このようにしてしまうとスクリプト引数に入力ファイルを指定してもそれを読み込んではくれなくなる。
  n = ARGF.gets.to_i
  # ↑rspec側でARGFをStringIOに置き換えれば、specも正しく動作する上に、
  #   通常実行時 標準入力からの入力でも、入力ファイルからの入力でも正しく動作する。
  puts("Error") if n <= 0

  # 前に存在していた点
  lx = ly = 0
  # 前に存在していた点にいた時刻
  lt = 0

  n.times do
    t, x, y = ARGF.gets.split.map(&:to_i)

    # 前に存在していた点からの距離（道のり）
    distance = (x - lx).abs + (y - ly).abs

    # 前に存在していた点にいた時刻からの経過時刻
    dt = t - lt

    if dt < distance
      puts 'No'
      return    # 入力をgetsするのを途中でやめても大丈夫かな？
    end

    # 経過時刻が偶数なら距離も偶数じゃなければならない。奇数でも同様。
    if dt.even? != distance.even?
      puts 'No'
      return
    end

    lt = t
    lx = x
    ly = y
  end

  puts 'Yes'
end

if __FILE__ == $0
  main
end


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

using namespace std;

int A, B, C, X, Y;
int main(){
    cin >> A >> B >> C >> X >> Y;
    int  mincost = 200000 * C;
    for (int c = 0; c < 200000; c += 2) {
        int a = max(X - c / 2, 0);
        int b = max(Y - c / 2, 0);
        int cost = A * a + B * b + C * c;
        mincost = min(mincost, cost);
    }

    cout << mincost << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void)
{
	int a,b,c,d,e,f,g,A;
	cin>>a>>b>>c>>d>>e;
	if (b%d!=0) f=b/d+1;
	else f=b/d;
	if (c%e!=0) g=c/e+1;
	else g=c/e;
	if (g>f) A=a-g;
	else A=a-f;
	cout<<A<<endl;
}
	
	

Measured memory_bytes: 3084
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("POSSIBLE")
    elif q == 0:print("IMPOSSIBLE")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

#n = ip()                                     #入力整数1つ
n,m,x,y= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!

print((n*m)/2,end =' ')
if n == 2*x and m == y*2:
    print(1)
else: print(0)


Measured memory_bytes: 13660
#include <iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
int main(){
    int n,dp[100010][3]={};
    cin>>n;
    dp[0][0]=dp[0][1]=dp[0][2]=0;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        dp[i][0]=a+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=b+max(dp[i-1][0],dp[i-1][2]);
        dp[i][2]=c+max(dp[i-1][0],dp[i-1][1]);
    }
    int ans=max(dp[n][0],max(dp[n][1],dp[n][2]));
    cout<<ans<<endl;
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {

    static int mod = 1000000000 + 7;
    static int max = 1000000 * 2 / 3 + 1;

    static long[] fact = new long[max];
    static long[] modinv = new long[max];
    static long[] factinv = new long[max];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = Integer.parseInt(scan.next());
        int y = Integer.parseInt(scan.next());
        scan.close();

        if ((x + y) % 3 != 0) {
            System.out.println(0);
            return;
        }

        int limit = (x + y) / 3;
        if (x < limit || y < limit) {
            System.out.println(0);
            return;
        }

        initCombi();
        System.out.println(combi(limit, x - limit));

    }

    private static void initCombi() {
        fact[0] = 1;
        fact[1] = 1;
        modinv[1] = 1;
        factinv[0] = 1;
        factinv[1] = 1;

        for (int i = 2; i < max; i++) {
            fact[i] = fact[i - 1] * i % mod;
            modinv[i] = mod - modinv[mod % i] * (mod / i) % mod;
            factinv[i] = factinv[i - 1] * modinv[i] % mod;
        }
    }

    private static long combi(int n, int k) {
        return fact[n] * (factinv[k] * factinv[n - k] % mod) % mod;
    }

}


Measured memory_bytes: 48340
A,B,C,X,Y = map(int,input().split())
ans = float("inf")
MAX = max(X,Y)*2
for i in range(0,MAX+1,2): #ABハーフを何枚買うか？必ず偶数枚
  #print(i,X-i//2,Y-i//2)
  temp = A*max((X-i//2),0)+B*max((Y-i//2),0)+C*i
  ans = min(temp,ans)
print(ans)
  

Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6+10 , OO = 0x3f3f3f3f ;
const int mod = 1e9 + 7;
 
#define clr(arr,val) memset(arr , val , sizeof (arr))
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define rloop(i,n) for(int i = int(n)-1;i >= 0;i--)
#define xloop(i,a,b) for(int i = int(a);i <= int(b);i++)
#define range(vec) for(auto &x : vec) cin >> x;
#define ALL(v) ((v).begin()) , ((v).end())
#define SZ(v)  ((int)((v).size()))
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

int x , n;

int main()
{
   // startTime = (double)clock();
    #ifndef ONLINE_JUDGE
        //freopen("in.in", "r", stdin);
        //freopen("out.in", "w", stdout);
    #endif
	//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    scanf("%d %d", &x , &n);
    if(n == 0)
        return printf("%d\n" , x) , 0;

    set < int > st;
    for(int i = 0 ; i < n ; ++i){
        int rkm;
        scanf("%d" , &rkm);
        st.insert(rkm);
    }
    int mnleft = 0 , mnRight = 0;
    for(int i = x ; i >= -105 ; --i){
        if(!st.count(i)){
            mnleft = i;
            break;
        }
    }
    for(int i = x ; i <= 105 ; ++i){
        if(!st.count(i)){
            mnRight = i;
            break;
        }
    }
    //printf("mnL = %d , mnR = %d\n" , mnleft , mnRight);

    if(x - mnleft < mnRight - x)
        printf("%d\n" , mnleft);
    else if(mnRight - x < x - mnleft)
        printf("%d\n" , mnRight);
    else 
        printf("%d\n", mnleft);
    
    //printf("%d\n" , min(x - mnleft , mnRight - x));

    return 0;
}

Measured memory_bytes: 3764
using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

namespace AOJ2
{
    class Program
    {
        class Member
        {
            public int Number { get; set; }
            public long Uriage { get; set; }

            public Member(int Number, long Uriage)
            {
                this.Number = Number;
                this.Uriage = Uriage;
            }
        }

        static void Main(string[] args)
        {
            List<string> resultList = new List<string>();

            while (true)
            {
                int num = int.Parse(Console.ReadLine());
                if (num == 0)
                {
                    break;
                }

                List<Member> memberList = new List<Member>();

                for (int i = 0; i < num; i++)
                {
                    long[] records = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
                    if (memberList.Where(s => s.Number == records[0]).Count() == 0)
                    {
                        memberList.Add(new Member((int)records[0], records[1] * records[2]));
                    }
                    else
                    {
                        memberList.Where(s => s.Number == records[0]).ToList()[0].Uriage += records[1] * records[2];
                    }
                }


                if (memberList.Where(s => s.Uriage >= 1000000).Count() == 0)
                {
                    resultList.Add("NA");
                }
                else
                {
                    foreach (Member m in memberList.Where(s => s.Uriage >= 1000000).ToArray())
                    {
                        resultList.Add(m.Number.ToString());
                    }
                }

            }


            foreach (string s in resultList)
            {
                Console.WriteLine(s);
            }


        }

    }
}

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

int main(){
    int a,b;
    cin >> a >> b;
    if(a==b||a-1==b||a==b-1){
        cout << a+b << endl;
    }else if(a>b){
        cout << a*2-1 << endl;
    }else{
        cout << b*2-1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

int main(int argc, const char * argv[]) {
    int a,b;
    cin >> a >> b;
    int ans = 0;
    ans += a;
    if(b < a){
        ans--;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
use proconio::input;
const MODN:i128 = 1000000007;

fn main() {
    input!{
        n:i128,
        k:i128,
    }
    let mut ans = 0;
    for sel in k..=n+1{
        ans = ((ans as i128) % MODN + (((2*n-(sel-1)) * sel / 2 - (sel-1) * sel / 2 + 1_i128)) % MODN) as i32;
    }
    println!("{}",ans);
}

Measured memory_bytes: 2176
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val AB = (1..N).map { readLine()!!.split(" ").map { it.toInt() } }.sortedBy { it[1] }
    var t = 0
    for ((a, b) in AB) {
        t += a
        if (t > b) {
            println("No")
            return
        }
    }
    println("Yes")
}

Measured memory_bytes: 131848
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
#define ALL(x) (x).begin(), (x).end()
#define LBi(x, n) lower_bound(ALL(x), n) - (x).begin()
#define ZIP(x) (x).erase(unique(ALL(x)), (x).end())
#define Pi pair<int, int>
#define Vi vector<int>

#define rep(n) for(int i = 0; i < n; i++)

string s = "";
char ch[10];
int a, b, c, d, x, m[5];

int main() {
	rep(9)cin >> ch[i];
	cout << s + ch[0] + ch[4] + ch[8] << endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.IllegalArgumentException
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val s = sc.nextLine()
    if (s == s.toLowerCase()) {
        println("a")
    } else {
        println("A")
    }
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 34272
#include <stdio.h>
int main (){
	int a,b,x;
	// x adalah alamat rumah pembeli
	scanf ("%d %d %d", &x, &a, &b);
	int i = x-a;
	int j = x-b;
	if (i<0){
		i*=(-1);}
	if (j<0){
		j*=(-1);}
i<j ? printf("A"):printf("B");
return 0;
}


Measured memory_bytes: 1644
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		long x = scan.nextLong();
		long y = scan.nextLong();
		scan.close();
		
		int ans = 0;
		while(x <= y) {
			ans++;
			x *= 2;
		}
		System.out.println(ans);
	}
}

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

int n;
const int maxn = 1e5 + 5;

bool check(vector<int> v){
    for(int i = 1, j = 1;i <= v.size();i = j + 1, j = i){
        while(j + 1 <= v.size() and v[j] == v[i - 1])
            j++;
        int l1 = (i == 1) ? 0 : v[i - 2];
        int r1 = v[i - 1];
        int l2 = v.size() - j;
        int r2 = v.size() - i + 1;
        if(l2 >= r1 or l1 >= r2)
            continue;
        int v = max(l1, l2);
        int v1 = r1 - v;
        int v2 = r2 - v;
        if((v1 & 1) == (v2 & 1))
            return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    vector<int> a;
    for(int i = 1;i <= n;i++){
        int v;
        cin >> v;
        a.push_back(v);
    }
    sort(a.begin(), a.end());
    if(!check(a)){
        cout << "Second" << endl;
        return 0;
    }
    vector<int> b = a;
    b.pop_back();
    if(!check(b)){
        cout << "First" << endl;
        return 0;
    }
    vector<int> c(0);
    for(auto v : a){
        if(v > 1){
            c.push_back(v - 1);
        }
    }
    if(!check(c)){
        cout << "First" << endl;
        return 0;
    }
    cout << "Second" << endl;
    return 0;
}


Measured memory_bytes: 1912
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> PII;
#define MOD (1000000007ll)

ll t[225816][2];

ll powmod(ll num,ll idx){
	int i=0;
	ll ans=1ll,pw=num;
	while((1ll<<i)<=idx){
		if(((1ll<<i)&idx)>0){
			ans *= pw;
			ans %= MOD;
		}
		pw *= pw;
		pw %= MOD;
		i++;

	}
	return ans;
}

ll comb(ll lf,ll rg){
	ll ans;
	ans = t[lf][0];
	ans *= t[rg][1];
	ans %= MOD;
	ans *= t[lf-rg][1];
	ans %= MOD;
	return ans;
}

int main(void){
	ll w,h,a,b,ans=0ll,x,y,tmp=1ll,i;
	t[0][0] = 1ll;
	t[0][1] = 1ll;
	for(i=1ll; i<=222222ll; i++){
		t[i][0] = i;
		t[i][1] = powmod(i,MOD-2);
	}
	for(i=1ll; i<=222222ll; i++){ 
		t[i][0] *= t[i-1][0];
		t[i][0] %= MOD;
		t[i][1] *= t[i-1][1];
		t[i][1] %= MOD;
	}
	cin >> h >> w >> a >> b;
	w--;
	h--;
	x = h-a;
	y = b;
	while(x>=0 && y<=w){
		tmp = comb(x+y,x);
		tmp *= comb(h+w-x-y,h-x);
		tmp %= MOD;
		ans += tmp;
		ans %= MOD;
		x--;
		y++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN=1e2+10;
const int MAXK=1e5+10;
const int MOD=1e9+7;
int n,k;
int a[MAXN];
ll dp[MAXN][MAXK],sum[MAXN][MAXK];
int add(int x,int y){
	return (x+y)%MOD;
}
int sub(int x,int y){
	return (x-y+MOD)%MOD;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=0;i<=k;i++){
		sum[0][i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			if(j-a[i]<=0) dp[i][j]=add(dp[i][j],sum[i-1][j]);
			else dp[i][j]=add(dp[i][j],sub(sum[i-1][j],sum[i-1][j-a[i]-1]));
			if(!j) sum[i][j]=dp[i][j];
			else sum[i][j]=add(dp[i][j],sum[i][j-1]);
		}
	}
	cout<<dp[n][k]<<"\n";
	return 0;
}

Measured memory_bytes: 162048
n = int(input())
c0 = 0
c1 = 0
c2 = 0
c3 = 0

for i in range(n):
    s = input()
    if s == 'AC':
        c0 += 1
    elif s == 'WA':
        c1 += 1
    elif s == 'TLE':
        c2 += 1
    else:
        c3 += 1

print('AC x',c0)
print('WA x',c1)
print('TLE x',c2)
print('RE x',c3) 


Measured memory_bytes: 9056
from bisect import bisect_left

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

INF = 10 ** 9 + 1

stx.sort(key=lambda x: x[2])

nxt = [-1] * q
ans = [-1] * q

for s, t, x in stx:
    l = bisect_left(d, s - x)
    r = bisect_left(d, t - x)

    while l < r:
        if nxt[l] == -1:
            ans[l] = x
            nxt[l] = r
            l += 1
        else:
            l = nxt[l]

print(*ans, sep="\n")


Measured memory_bytes: 77328
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        char[]f=new char[26],t=new char[26];
        char[]a=s.next().toCharArray(),b=s.next().toCharArray();
        
        for(int i=0;i<a.length;++i){
            if((t[a[i]-'a']!=0&&t[a[i]-'a']!=b[i])
                ||(f[b[i]-'a']!=0&&f[b[i]-'a']!=a[i])){
                System.out.println("No");
                return;
            }
            t[a[i]-'a']=b[i];
            f[b[i]-'a']=a[i];
        }
        System.out.println("Yes");
    }
}


Measured memory_bytes: 29912
from itertools import product
while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    a = [[0]*(w+2)] + [[0]+list(map(int, input().split()))+[0] for _ in [0]*h] + [[0]*(w+2)]
    visited = [[0]*(w+2) for _ in [0]*(h+2)]
    ans = 0
    for y in range(1, h+1):
        for x in range(1, w+1):
            if visited[y][x] or not a[y][x]:
                continue
            ans += 1
            visited[y][x] = 1
            q = [(x, y)]
            pop, append = q.pop, q.append
            while q:
                _x, _y = pop()
                for dx, dy in product(range(-1, 2), range(-1, 2)):
                    nx, ny = _x+dx, _y+dy
                    if not visited[ny][nx] and a[ny][nx]:
                        visited[ny][nx] = 1
                        append((nx, ny))
    print(ans)


Measured memory_bytes: 5800
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <string.h>
#include <stdlib.h>

using namespace std;
// vector push_back push front top empty pop make_pair long long insert begin end  
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair <int,int> > vpi;
typedef vector<long long> vll;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define B begin()
#define RB rbegin()
#define E end()
#define RE rend()
#define Z size()
#define REP(i,a,b) for (int i = a; i < b; i++)
#define L length()
#define show(a) cerr << " *** " << a << endl;
#define show1(a) cerr << " /// " << a << endl;
#define valid(a,b,c) (a >= b && a < c ? 1 : 0)
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int mod = (int)1e9 + 7;
void ads(ll &a, ll b){a += b;if (a >= mod)a -= mod;}
void mis(ll &a, ll b){a -= b;if (a >= mod)a -= mod; if (a < 0)a += mod;}
ll gcd(ll a, ll b) {return (b==0? a:gcd(b,a%b));}
ll egcd(ll a, ll b, ll & x, ll & y) {if (a == 0){x = 0;y = 1;return b;}ll x1, y1;ll d = egcd(b % a, a, x1, y1);x = y1 - (b / a) * x1;y = x1;return d;}
ll mbinp(ll a, ll b){a %= mod;if (b == 0)return 1;ll ans = mbinp(a, b/2);ll tmp = (ans * ans) % mod;if (b % 2)return ((tmp * a) % mod);return ((tmp) % mod);}
ll binp(ll a, ll b){if (b == 0)return 1;ll ans = binp(a, b/2);ll tmp = (ans * ans);if (b % 2)return ((tmp * a));return ((tmp));}

const int maax = 404;
ll dp[maax][maax];
ll inf = (ll)(1e18) + 5;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vll all(n);
	vll pre(n,0);
	REP(i,0,n)cin>>all[i];
	REP(i,0,n)pre[i] = all[i];
	REP(i,1,n)pre[i]+=pre[i-1];
	for (int i = n-1; i >= 0;i--)
	{
		for (int j = i; j <n; j++)
		{
			if (i == j)
				dp[i][j] = 0;
			else
			{
				dp[i][j] = inf;
				ll sum = pre[j]-(i == 0 ? 0 :pre[i-1]);
				for (int x = i; x < j; x++)
					dp[i][j] = min(dp[i][j], dp[i][x] + dp[x+1][j] + sum);
			}
		}
	}
	cout << dp[0][n-1];
}


Measured memory_bytes: 1536
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    String str = "";
    if(a==b&&b==c&&a==c)str = "Yes";
    else str = "No";
    System.out.println(str);
  }
}

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

typedef pair< int,int > P;
int N;
vector< vector< int > > Edge;
vector< int > Csum;

void bfs(){
  Csum.assign(N+1,-1);
  queue< P > que;
  que.push(P(0,0));
  Csum[0] = 0;
  while(!que.empty()){
    int now = que.front().second;
    int cost = que.front().first;
    que.pop();
    for(int i=0;i<Edge[now].size();i++){
      if(Csum[Edge[now][i]] != -1) continue;
      Csum[Edge[now][i]] = cost+1;
      que.push(P(cost+1,Edge[now][i]));
    }
  }
}

int main(){
  cin >> N;
  Edge.resize(N+1);
  for(int i=0;i<N;i++){
    int u,k; cin >> u >> k;
    for(int j=0;j<k;j++){
      int e; cin >> e; e--;
      Edge[i].push_back(e);
    }
  }
  bfs();
  for(int i=0;i<N;i++){
    cout << i+1 << " " << Csum[i] << endl;
  }
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int  main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; ++i) cin >> a[i];

  sort(a.rbegin(), a.rend());
  int alice = 0, bob = 0;
  for(int i=1; i<=n; ++i){
    if(i%2==1) alice+=a[i-1];
    if(i%2==0) bob+=a[i-1];
  }
  cout << abs(alice - bob) << endl;
 return 0;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
        self.rank=[0]*n

    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return 

        if self.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def are_same(self,x,y):
        return self.find(x)==self.find(y)

    def element_count(self,x):
        x=self.find(x)
        return -self.parents[x]

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    a=[0]*m
    b=[0]*m
    for i in range(m):
        a[i],b[i]=map(lambda x:int(x)-1,readline().split())

    uf=UnionFind(n)
    cnt=[0]*m
    now=n*(n-1)//2
    j=-1
    for i in range(m-1,-1,-1):
        cnt[j]=now
        if uf.are_same(a[i],b[i])==False:
            now=max(0,now-uf.element_count(a[i])*uf.element_count(b[i]))
            uf.union(a[i],b[i])
        j-=1

    for i in range(m):
        print(cnt[i])

if __name__=="__main__":
    main()

Measured memory_bytes: 17712
def initSquare(H, W):
    square = []
    for r in range(H):
        row = []
        row_string = input()
        for letter in row_string:
            row.append(letter)
        square.append(row)
    return square

def rowChecker(square):
    delete_row_indexes = []
    for i, row in enumerate(square):
        if "#" not in row:
            delete_row_indexes.append(i)            
    return delete_row_indexes

def columnChecker(square):
    delete_column_indexes = []
    for c in range(W):
        column = []
        for r in range(H):
            column.append(square[r][c])
        if "#" not in column:
            delete_column_indexes.append(c)            
    return delete_column_indexes

def generateNewSquare(square, delete_row_indexes,delete_column_indexes):
    new_square = []
    for r, row in enumerate(square):
        if r not in delete_row_indexes:
            new_row = []
            for c, column in enumerate(row):
                if c not in delete_column_indexes:
                    new_row.append(column)
            new_square.append(new_row)
    return new_square

H, W = [int(i) for i in input().split()]

square = initSquare(H, W)
delete_row_indexes = rowChecker(square)
delete_column_indexes = columnChecker(square)
new_square = generateNewSquare(square, delete_row_indexes,delete_column_indexes)

for row in new_square:
    row_string = ''.join(row)
    print(row_string)

Measured memory_bytes: 3188
//Inbornhandsome
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define endl '\n'
#define int long long

const int N = 1e5 + 7;

int arr[N][3], ans[N][3], n;

int dp(int a, int b, int k)
{

    if(a == n) return arr[n][b];

    if(a > n) return -1e10;

    if(ans[a][k] != 0) return ans[a][k];

    ans[a][k] = max(arr[a][b] + dp(a+1, (b+1) % 3, (k+1) % 3), arr[a][b] + dp(a+1, (b+2) % 3, (k+2) % 3));

    return ans[a][k];
    
}

int32_t main()
{
    IOS; //FIO;

    cin >> n;

    memset(ans, 0, N);

    for(int i = 1; i <= n; i ++)
    cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    ans[0][0] = max(dp(1,0,0), max(dp(1,1,1), dp(1,2,2)));

    cout << ans[0][0];

    return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<char> S(N);
  
  for(int i = 0;i<N;i++){
    cin >> S.at(i);
  }
  
  int answer = 0;
  
  for(int i = 0;i<N;i++){
    if(S.at(i) == 'Y'){
      answer = 1;
      break;
    }
  }
  
  if(answer == 1){
    cout << "Four" << endl;
  }
  else if(answer == 0){
    cout << "Three" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h> 
//compiling code: g++ test.cpp(file) -o script(output) -std=c++11(version) -O2(make it 2x faster)
using namespace std;
int N;
string S[200005];
vector<string> ans;

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

    sort(S, S+N);
    int maxcount = 1;
    int count = 1;
    for (int i=1; i<N; i++){
        if(S[i] == S[i-1]){
            count += 1;
        } else{
            if (count == maxcount) {
                ans.push_back(S[i-1]);
                count = 1;
            }
            else if(count > maxcount){
                maxcount = count;
                ans.clear();
                ans.push_back(S[i-1]);
                count = 1;
            } else{
                maxcount = maxcount;
                count = 1;
            }
        }
    }
    if (count == maxcount) {
        ans.push_back(S[N-1]);
        count = 1;
    }
    else if(count > maxcount){
        maxcount = count;
        ans.clear();
        ans.push_back(S[N-1]);
        count = 1;
    }

    for(int i=0; i<ans.size(); i++){
        cout << ans[i] << endl;
    }
    
}

Measured memory_bytes: 15988
import math

A,B,H,M = map(int,input().split())

omega_h = 360/720
omega_m = 360/60

min = H * 60 + M

theta_h = omega_h * min
theta_m = (omega_m * min) % 360
theta = theta_h - theta_m


print( math.sqrt( A*A + B*B -2*A*B*math.cos(math.radians(theta)) ) )


Measured memory_bytes: 9504
#include<bits/stdc++.h>
using  namespace std;
main(){
int i,j,k,l;
while(cin>>l>>k){
 j=0;
 for(i=0;i<k;i++){
    int a; cin>>a;
    j+=a;
 }
 if(j>l)cout<<"-1"<<endl;
 else cout<<l-j<<endl;
} return 0;
}


Measured memory_bytes: 3632
n = int(input())
dict_s = {}
for i in range(n):
    s = input()
    dict_s[s] = dict_s.get(s, 0) + 1

m = int(input())
dict_t = {}
for i in range(m):
    t = input()
    dict_t[t] = dict_t.get(t, 0) + 1

ans = 0
for k, v in dict_s.items():
    add = v
    add -= dict_t.get(k, 0)
    ans = max(ans, add)

print(ans)

Measured memory_bytes: 3064
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    int N;
    cin >> N;

    map<ll, int> mp;
    FOR(i, 0, N){
        ll a;
        cin >> a;
        mp[a]++;
    }

    int num = 0;
    for(auto a : mp){
        int count = a.second;
        if(count%2==1){
            num++;
        }
    }

    p(num);

    return 0;
}

Measured memory_bytes: 6528
// Last Change:                     11/19/2018 23:13:54.
//教科書の写し
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

#include <cstdio>
#include <cstdlib>

#include <cstring>

using namespace std;
using ll = long long;

struct Node {
  int key;
  Node *prev, *next;
};

Node *nil;

void Init() {
  nil       = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void Insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node)); //指定したサイズのメモリを確保
  x->key  = key;
  x->next = nil->next;
  //この書き方によって、最初のNodeが最後尾としてnil->prevに入る
  //末尾Node->nextにnilを入れることで、末尾消去の際nil->prevを更新できる
  nil->next->prev = x;
  nil->next       = x;
  x->prev         = nil;
}

Node *ListSearch(int key) {
  Node *cur = nil->next;
  while (cur != nil && cur->key != key) { // cur==nilのとき、終端にいる
    cur = cur->next;
  }
  return cur;
}

void DeleteNode(Node *t) {
  if (t == nil) {
    return;
  }
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void DeleteFirst() {
  DeleteNode(nil->next);
}

void DeleteLast() {
  DeleteNode(nil->prev);
}

void DeleteKey(int key) {
  DeleteNode(ListSearch(key));
}

void PrintList() {
  Node *cur = nil->next;
  int isf   = 0;
  while (1) {
    if (cur == nil) {
      break;
    }
    if (isf++ > 0) { //最初だけSpace出さない
      printf(" ");
    }
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

int main() {
  int key, n;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  Init();
  for (int i = 0; i < n; i++) {
    scanf("%s%d", com, &key);
    if (com[0] == 'i') {
      Insert(key);
      np++;
      size++;
    } else if (com[0] == 'd') {
      if (strlen(com) > 6) {
        if (com[6] == 'F') {
          DeleteFirst();
        } else if (com[6] == 'L') {
          DeleteLast();
        }
      } else {
        DeleteKey(key);
        nd++;
      }
      size--;
    }
  }
  PrintList();
}



Measured memory_bytes: 34460
import java.util.*;
public class Main {

	private boolean isPrime(int n){
		for(int i=2; i * i <= n; i++){
			if(n % i == 0){
				return false;
			}
		}
		return true;
	}

	public void doIt(){
		Scanner sc = new Scanner(System.in);

		//ツエツδ可トツスツテツネツスツづ個づ督づゥツつ「
		final int MAX = 999999;
		boolean [] prime = new boolean[MAX + 1];
		for(int i=2; i < prime.length; i++){
			prime[i] = true;
		}
		for(int i=2; i * i < MAX; i++){
			if(isPrime(i)){
				for(int j = i + i; j <= MAX; j += i){
					prime[j] = false;
				}
			}
		}

		while(true){
			int n = sc.nextInt();
			if(n == 0){
				break;
			}
			int prePrimeInd = 0;
			for(int i = n;;i--){
				if(prime[i]){
					//ツ催渉可づ按づァpreツづ可禿シツづェツづゥ
					if(prePrimeInd == 0){
						prePrimeInd = i;
						continue;
					}
					//ツ催渉可出ツづ按つ「ツづ按づァツ、indexツづ個債キツつェツ２ツつゥツづつ、ツつゥ
					if(prePrimeInd - i == 2){
						System.out.println(i + " " + prePrimeInd);
						break;
					}
					else{
						prePrimeInd = i;
					}
				}
			}
		}

	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doIt();

	}

}

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

using namespace std;

using ll = int_fast64_t;
constexpr ll llmax = INT_FAST64_MAX; // std::numeric_limits<int_fast64_t>::max()
constexpr ll llmin = INT_FAST64_MIN; // std::numeric_limits<int_fast64_t>::min()
using ull = uint_fast64_t;
constexpr ull ullmax = UINT_FAST64_MAX; // std::numeric_limits<uint_fast64_t>::max()

#define FOR(i, b, e) for (int i = (b); i < (e); ++i)
#define RFOR(i, b, e) for (int i = ((e) - 1); (b) <= i; --i)
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define RREP(i, N) for (int i = ((N) - 1); 0 <= i; --i)
#define scanInt(x) int x; scanf("%d", &(x)); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &(x)); getchar();
#define scanVecInt(A, N) vector<int> A(N); REP(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); REP(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    using T = pair<int, int>;
    vector<T> V; V.reserve(N);
    REP(n, N){
        scanInt(Ai);
        scanInt(Bi);
        V.emplace_back(Ai, Bi);
    }
    sort(V.begin(), V.end(), [](T& l, T& r){return l.second < r.second;});
    // for (auto& e : V){
    //     cout << e.first << " " << e.second << endl;
    // }
    int tsum = 0;
    for (auto& e : V){
        auto& Ai = e.first;
        auto& Bi = e.second;
        tsum += Ai;
        if (Bi < tsum){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  int ans = 0, res = inf, seg = 1;
  rep(i, n) {
    if (a[i] == res) continue;
    else if (a[i] > res) {
      if (seg == 0) seg = 1;
      else if (seg == -1) {
        ans++;
        seg = 0;
      }
    }
    else {
      if (seg == 0) seg = -1;
      else if (seg == 1) {
        ans++;
        seg = 0;
      }
    }
    res = a[i];
  }
  cout << ans << '\n';




  
  return 0;
}

Measured memory_bytes: 640
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace ARC074C
{
    public class Program
    {
        void Solve(StreamScanner ss, StreamWriter sw)
        {
            //---------------------------------
            var H = ss.Next(long.Parse);
            var W = ss.Next(long.Parse);

            var ans = Math.Min(GetAns(H, W), GetAns(W, H));
            sw.WriteLine(ans);
            //---------------------------------
        }

        long GetAns(long h, long w)
        {
            var min = long.MaxValue;

            for (var h1 = 0; h1 <= h; h1++)
            {
                var h2 = h - h1;
                var h21 = h2 / 2;
                var h22 = (h2 + 1) / 2;
                min = Math.Min(min, GetMinDiff(h1 * w, h21 * w, h22 * w));

                var w1 = w / 2;
                var w2 = (w + 1) / 2;
                min = Math.Min(min, GetMinDiff(h1 * w, h2 * w1, h2 * w2));
            }

            return min;
        }
        
        long GetMinDiff(params long[] areas)
        {
            return areas.Max() - areas.Min();
        }

        static void Main()
        {
            var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput()));
            var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            new Program().Solve(ss, sw);
            sw.Flush();
        }

        static readonly Func<string, string> String = s => s;
    }

    public class StreamScanner
    {
        static readonly char[] Sep = {' '};
        readonly Queue<string> buffer = new Queue<string>();
        readonly TextReader textReader;

        public StreamScanner(TextReader textReader)
        {
            this.textReader = textReader;
        }

        public T Next<T>(Func<string, T> parser)
        {
            if (buffer.Count != 0) return parser(buffer.Dequeue());
            var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries);
            foreach (var nextString in nextStrings) buffer.Enqueue(nextString);
            return Next(parser);
        }
    }
}

Measured memory_bytes: 17588
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define debout cout
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define debout cerr
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

template<class T> inline T sqr(T x) {return x*x;}

LL dp[2][100001] = {};

void resolve() {
    int n;
    cin >> n;
    VI a(n), b(n), c(n);
    REP(i,0,n) cin >> a[i];
    REP(i,0,n) cin >> b[i];
    REP(i,0,n) cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    VI u,m,l;
    u.push_back(a[0]);
    m.push_back(b[0]);
    l.push_back(c[0]);
    REP(i,1,n) {
        u.push_back(a[i]);
        m.push_back(b[i]);
        l.push_back(c[i]);
    }
    for (int i = m.size()-1; i >= 0; --i) {
        dp[1][i] = dp[1][i+1] + l.size() - (lower_bound(all(l), m[i]+1) - begin(l));
    }
    for (int i = u.size()-1; i >= 0; --i) {
        dp[0][i] = dp[0][i+1] + dp[1][lower_bound(all(m), u[i]+1) - begin(m)];
    }
    cout << dp[0][0] << endl;

}

int main() {
    resolve();
    
    return 0;
}

Measured memory_bytes: 4460
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 1; i <= 1000000; ++i) {
        if (a * i % b == c) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
    return 0;
}

Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

int main() {
  std::string S;
  std::cin >> S;
  const unsigned int mod = 2019;

  std::vector<unsigned int> dp(S.size());
  unsigned int pow = 10;
  for (unsigned int i = S.size(); i > 0; --i) {
    if (i == S.size()) {
      dp.at(i - 1) = S[i - 1] - '0';
    } else {
      dp.at(i - 1) = (dp.at(i) + (S[i - 1] - '0') * pow) % mod;
      pow = (pow * 10) % mod;
    }
  }

  std::unordered_map<unsigned int, unsigned long> map;
  map.emplace(0, 1);
  for (unsigned int i = 0; i < S.size(); ++i) {
    if (map.count(dp.at(i)) == 0) {
      map.emplace(dp.at(i), 1);
    } else {
      map.at(dp.at(i)) += 1;
    }
  }

  unsigned long ans = 0;
  for (const auto& x : map) {
    const unsigned long num = x.second;
    ans += num * (num - 1) / 2;
  }

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


Measured memory_bytes: 4384
#include<bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ff first 
#define ss second
#define mod 1000000007
#define lim 100005
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main()
{
	int i,j,n; double p[3001], dp[3001] = {}, ans = 0.0;
	cin>>n;
	for(i=1; i<=n; i++) cin>>p[i];

	dp[0] = 1.0;
	for(i=1; i<=n; i++){
		for(j=i; j; j--)
			dp[j] = dp[j]*(1-p[i]) + dp[j-1]*p[i];
		dp[0] *= (1-p[i]);
	}

	for(i=(n+1)/2; i<=n; i++) ans += dp[i];
	printf("%.10lf",ans);
}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 998244353
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li a[100100];
li n;

int main() {
    cin >> n;
    set<li> st;
    rin{
        cin >> a[i];
        st.insert(a[i]);
    }
    if (sz(st) > 2) {
        puts("No");
        return 0;
    }
    if (sz(st) == 1) {
        if (a[0] == n - 1) {
            puts("Yes");
            return 0;
        }
        cout << (a[0] * 2 <= n ? "Yes" : "No") << endl;
        return 0;
    }

    map<li, li> cnt;
    rin{
        cnt[a[i]]++;
    }
    vector<PI> v;
    for (auto && kv : cnt) {
        v.pb({kv.F, kv.S});
    }
    if (v[0].F + 1 != v[1].F) {
        puts("No");
        return 0;
    }
    if (v[0].F < v[0].S) {
        puts("No");
        return 0;
    }
    li req_num = v[0].S + (v[0].F - v[0].S + 1) * 2;
    cout << (req_num <= n ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fuck signed
long long pw[21];
long long solve(int sum,int len,bool first) {
    if (len == 0) return (sum == 0);
    if (len == 1) return (sum == 0) * 10;
    int coef = pw[len - 1] - 1;
    int cur = sum / coef;
    long long ret = 0;
    if (first) {
        int new_sum = sum - cur * coef;
        if (new_sum % 10 == 0) ret += max(0ll, 9ll - cur) * solve(new_sum / 10, len - 2, 0);
        new_sum = (cur + 1) * coef - sum;
        if (new_sum % 10 == 0) ret += max(0ll, 8 - cur) * solve(new_sum / 10, len - 2, 0);
    }
    else {
        int new_sum = sum - cur * coef;
        if (new_sum % 10 == 0) ret += max(0ll, 10 - cur) * solve(new_sum / 10, len - 2, 0);
        new_sum = (cur + 1) * coef - sum;
        if (new_sum % 10 == 0) ret += max(0ll, 9 - cur) * solve(new_sum / 10, len - 2, 0);
    }
    return ret;
}

fuck main() {
    ios_base::sync_with_stdio(false);
    int d; cin >> d;
    pw[0] = 1; for (int i = 1; i <= 19; ++i) pw[i] = pw[i - 1] * 10;
    long long ans = 0;
    for (int i = 1; i <= 19; ++i) ans += solve(d, i, 1);
    cout << ans << '\n';
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <set>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;
typedef long long LL;
#define ALL(a) (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IFOR(v,it) for(VI::iterator it=(v).begin();it!=(v).end();++it)


// あるiに対して
// - iより左が白
// - iより右(i含む)が黒
// になるようにする問題。
//
// 各iに対して、iより左の黒の数 + iより右(iを含む)の白の数をカウントして最小化する。
// iより左の黒の累積和をとればいい
int main() {
  int N;
  cin >> N;

  int black_count[N+1];
  black_count[0] = 0;
  REP(i, N) {
    char c;
    cin >> c;
    black_count[i+1] = black_count[i];
    if (c == '#')
      ++black_count[i+1];
  }

  // black_count[1] = 1番目が黒なら1
  // black_count[2] = 2番目までの黒の数

  int min_count = N + 1;
  REP(i, N+1) {
    int left_white = i - black_count[i]; // iより左の白の数
    int right_black = black_count[N] - black_count[i];
    min_count = min(min_count, (i - left_white) + (N - i - right_black));
  }
  cout << min_count << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
using namespace std;
char s[10002];
int J,I;
int main()
{
while(scanf("%s",s)!=EOF){
 J=0; I=0;
 for(int i=0;i<strlen(s)-2;i++){
 if(s[i]=='J'&&s[i+1]=='O'&&s[i+2]=='I') J++;
 if(s[i]=='I'&&s[i+1]=='O'&&s[i+2]=='I') I++;
}
 printf("%d\n%d\n",J,I);
}}

Measured memory_bytes: 976
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define ar array<int,2>
#define inf 1000000000000000000 
int mod=1e9+7;
int min(int a,int b){return (a<b)?a:b;}
int max(int a,int b){return (a>b)?a:b;}
int fp(int a,int b){if(b==0) return 1;int x=fp(a,b/2);x=(x*x)%mod;if(b&1) x=(x*a)%mod;return x;}


const int N=2e5+5;
struct node
{
  int p,mx;
  node()
  {
    p=0;
    mx=0;
  }
}; 
node merge(node a,node b)
{
  node c;
  return c;
}
 
vector<node> bit(4*N);

void propagate(int id)
{
  bit[2*id].p+=bit[id].p;
  bit[2*id+1].p+=bit[id].p;
  bit[2*id].mx+=bit[id].p;
  bit[2*id+1].mx+=bit[id].p;
  bit[id].p=0;
} 

 
int get(int id,int l,int r,int L,int R)
{
  if(R<l||r<L){
    return INT_MIN;
  }
  if(L<=l&&r<=R)
  {
    return bit[id].mx;
  }
  propagate(id);
  int mid=(l+r)/2;
  
 int ans=max(get(2*id,l,mid,L,R),get(2*id+1,mid+1,r,L,R));
  bit[id].mx=max(bit[2*id].mx,bit[2*id+1].mx);
 return ans;
}


void upd(int id,int l,int r,int L,int R,int v)
{
  if(R<l||r<L)
    return;
  if(L<=l&&r<=R)
  {
    bit[id].p+=v;
    bit[id].mx+=v;
    return;
  }
  propagate(id);
  int mid=(l+r)/2;
  upd(2*id,l,mid,L,R,v);
  upd(2*id+1,mid+1,r,L,R,v);
  bit[id].mx=max(bit[2*id].mx,bit[2*id+1].mx);
  //bit[id]=merge(bit[2*id],bit[2*id+1]);
}
 
 

signed main() {
 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

 
 int n,m;
 cin>>n>>m;

 int a[m+1][3];
 vector<int> v[n+1];
 for(int i=1;i<=m;i++)
 {
  cin>>a[i][0]>>a[i][1]>>a[i][2];
  v[a[i][1]].push_back(i);
 }

 for(int i=1;i<=n;i++)
 {
  int x=max(0,get(1,1,n,1,n-1));
  upd(1,1,n,i,i,x);
  for(auto j:v[i])
  {
    upd(1,1,n,a[j][0],a[j][1],a[j][2]);
  }
 }
 // for(int i=1;i<=n;i++)
 // {
 //  cout<<i<<" "<<get(1,1,n,1,i)<<endl;
 // }

 int ans=max(0,get(1,1,n,1,n));
 cout<<ans;



} 

Measured memory_bytes: 31436