akhauriyash/Code-Regression huggingface dataset:
n = gets.chomp.to_i
p = gets.chomp.gsub(" ", "")

answer = "YES"

(n - 1).times do |i|
  l = p[i].to_i
  r = p[i + 1].to_i

  if l > r
    answer = "NO"
    if p[l - 1].to_i == i + 1
      answer = "YES"
      break
    else
      answer = "NO"
      break
    end
  end
end

puts answer


Measured memory_bytes: 1788
#include <stdio.h>

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

  int a[1010], i;
  for(i = 0; i < n; ++i)
  {
    scanf("%d",&a[i]);
  }
  for(i = n-1; 0 <= i; --i)
  {
    if(i != 0){
      printf("%d ",a[i]);
    }
    else{
      printf("%d",a[i]);
    }
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 604
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Regular Triangle
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);

  if (a == b && b == c) puts("Yes");
  else puts("No");
  return 0;
}


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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    ll n, l;
    cin >> n >> l;
    vll a(n);
    rep(i, n) cin >> a[i];

    int idx = -1;
    rep(i, n - 1) {
        if (a[i] + a[i + 1] >= l) {
            idx = i;
            break;
        }
    }

    if (idx < 0) {
        cout << "Impossible" << endl;
        return 0;
    }

    vll ans;
    for (int i = idx; i < n - 1; i++) ans.push_back(i);
    for (int i = idx - 1; i >= 0; i--) ans.push_back(i);
    reverse(all(ans));

    cout << "Possible" << endl;
    rep(i, n - 1) {
        cout << ans[i] + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 2548
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;

int main()
{
	string s;
	cin>>s;
	if(s[2] == s[3] && s[4] == s[5])
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    s.replace(5, 1, " ");
    s.replace(13, 1, " ");
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
struct Point{
    double x,y;
};
void koch(int d,Point p1,Point p2){
    if(d==0) return;
    Point s,u,t;
    double th = M_PI * 60.0 / 180.0;
    s.x = (2*p1.x+1*p2.x)/3;
    s.y = (2*p1.y+1*p2.y)/3;
    t.x = (1*p1.x+2*p2.x)/3;
    t.y = (1*p1.y+2*p2.y)/3;
    u.x = (t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
    u.y = (t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;

    koch(d-1,p1,s);
    printf("%.8f %.8f\n",s.x,s.y);
    koch(d-1,s,u);
    printf("%.8f %.8f\n",u.x,u.y);
    koch(d-1,u,t);
    printf("%.8f %.8f\n",t.x,t.y);
    koch(d-1,t,p2);
}
int main()
{
    Point p1,p2;
    int d;
    scanf("%d",&d);
    p1.x = 0;
    p1.y = 0;
    p2.x = 100;
    p2.y = 0;
    printf("%.8f %.8f\n",p1.x,p1.y);
    koch(d,p1,p2);
    printf("%.8f %.8f\n",p2.x,p2.y);
    return 0;
}



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

int GCD(int x,int y){
  if(y == 0) return x;
  return GCD(y,x%y);
}

int main() {
  int n,x;
  cin >> n >> x;
  vector<int>data(n);
  for(int i = 0;i < n;i++){
    int a;
    cin >> a;
    data[i] = abs(a-x);
  }
  sort(data.begin(),data.end());
  int g = GCD(data[0],data[1]);
  for(int i = 2;i < n;i++) g = GCD(g,data[i]);
  cout << g << endl;
}


Measured memory_bytes: 640
import math


def main():
    A, B, H, M = map(int, open(0).read().split())

    H_rasian = (H + M / 60) / 12 * 2 * math.pi
    M_rasian = M / 60 * 2 * math.pi
    ans = math.sqrt(A**2 + B**2 - 2 * A * B * math.cos((H_rasian - M_rasian)))

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9504
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
cd=[list(map(int,input().split())) for i in range(m)]

for i in range(n):
    x=ab[i][0]
    y=ab[i][1]
    ans = [float('inf')] * 2
    for j in range(m):
        man=abs(x-cd[j][0])+abs(y-cd[j][1])
        if ans[0]>man:
            ans=[man,j+1]

    print(ans[1])


Measured memory_bytes: 3064
#include<stdio.h>
int main(){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    
    if (a==b && b==c){
        printf("%d", 1);
    }else if(a!=b && b!=c && c!=a){
        printf("%d", 3);
    }else{
        printf("%d", 2);
    }
    
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;cin>>S;
  cout << 700+100*((S[0]=='o')+(S[1]=='o')+(S[2]=='o'))<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val (N, X) = nextIntList()
    val A = nextLongList().toTypedArray()
    var ans = 0L
    for (i in 0 until N - 1) {
        val d = (A[i] + A[i + 1] - X).coerceAtLeast(0)
        ans += d
        A[i + 1] = (A[i + 1] - d).coerceAtLeast(0)
    }
    println(ans)
}

Measured memory_bytes: 74112
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int x,y,z;
  cin >> x >> y >> z;
  cout << (x-z)/(y+z) << "\n";
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a , b , c , d;
    cin>>a>>b>>c>>d;
    long long ar1 , ar2 ;
    ar1=a*b;
    ar2=c*d;
    if (ar1<=ar2)
    {
        cout<<ar2<<endl;
    }
    else
    {
        cout<<ar1<<endl;
    }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
#define all(a) (a).begin(),(a).end()
using namespace std;


signed main(){
    ios_base::sync_with_stdio(0);

    int n; 
    cin >> n;
    vector<int>arr(n);
    for(int& i:arr)
        cin >> i;

    sort(all(arr));
    reverse(all(arr));

    int ans = arr[0];
    if(n == 2){
        cout << ans << endl ;
        return 0;
    }
    int cnt = n-2;

    for(int i=1;i<n;i++){
        cnt -= 2;
        ans += 2*arr[i];
        if(cnt == 0) break;
        if(cnt < 0){
            ans -= arr[i];
            break;
        }
    }

    cout << ans << endl ;

    return 0;
}



Measured memory_bytes: 4840
#include<stdio.h>
#include<string.h>



int main() {

	int a, b, ans;
	char op;

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

	if (op == '+') {
		ans = a + b;
		printf("%d\n", ans);
	}
	else {
		ans = a - b;
		printf("%d\n", ans);
	}

	return 0;
}

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

int main(){
	int n;
	while( cin >> n , n ){
		vector<int> v;
		
		for(int i=0 ; i < n ; i++ ){
			int a;
			cin >> a;
			a = (a == 0)? 1 : -1 ;
			if( i == 0 ){
				v.push_back( a );
			}else if( i%2 && ((v[v.size()-1] < 0 && a > 0) || (v[v.size()-1] > 0 && a < 0)) ){
				if( v.size() >= 2 ){
					int t = v[v.size()-1];
					v.pop_back();
					v[v.size()-1] += -t + a;
				}else{
					v[v.size()-1] *= -1;
					v[v.size()-1] += a;
				}
			}else{
				if( (v[v.size()-1] > 0 && a > 0) || (v[v.size()-1] < 0 && a < 0) ){
					v[v.size()-1] += a;
				}else{
					v.push_back( a );
				}
			}
		}
		int ans = 0;
		for(int i=0 ; i < v.size() ; i++ ){
			if( v[i] > 0 )
				ans += v[i];
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 904
package main

import (
	"fmt"
)

func main() {
	var s string
	var k int
	fmt.Scan(&s, &k)

	for i, r := range s {
		if int(r-'0') != 1 {
			fmt.Println(string(r))
			return
		}
		if i == k-1 {
			fmt.Println(1)
			return
		}
	}
}


Measured memory_bytes: 1772
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n,a,d=map(int,input().split())
    if(d==0):
        if(a!=0):
            print(n+1)
        else:
            print(1)
        return

    if(d<0): a,d=-a,-d # d>0
    D=defaultdict(list)
    for k in range(n+1):
        q,r=divmod(k*a,d)
        L=q+k*(k-1)//2
        R=q+k*(2*n-k-1)//2
        D[r].append((L,1)) # 1 -> add
        D[r].append((R,2)) # 2 -> remove

    ans=0
    for arr in D.values():
        arr.sort()
        # print(arr)
        over=0
        for v,q in arr:
            if(q==1 and over==0):
                left=v
            over+=1 if(q==1) else -1
            if(over==0):
                ans+=v-left+1
    print(ans)
resolve()

Measured memory_bytes: 88148
/*

	????則???蔵???????????????2?????即?????????????則????????????????????????則???
	??蔵???S, ??即?????????L, a???????????即????????即????????????h????即?????????????????????????
	
	radian = degree * PI / 180 ????????????
	
	??蔵??? S = 2??? a*b * sin(c) /2	????????????	???sin(c)???c???????????蔵??????
	
	??即????????? L = a + b + sqrt(a^2 + b^2 - 2*a*b*cos(c))		????????????	???cos(c)???c???????????蔵??????


3:27 2013/11/02

Accepted.

?????????????????贈??????


*/



#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.14159265358979


//???????????贈?????卒??属???????????蔵????????????????????蔵??属
double toRadian(int degree);

int main(void){
	
	int a, b, c;
	
	double S, L, h;
	
	
	//??\???
	scanf("%d %d %d", &a, &b, &c);
	
	
	//??蔵???S = a*b*sin(c)/2
	S = a*b*sin(toRadian(c))/2;
	
	
	//??即?????????L = a+b+sqrt(a^2+b^2-(2ab*cos(c)))
	L = a + b + sqrt(pow((double)a, 2.0) + pow((double)b, 2.0) - 2*a*b*cos(toRadian(c)));
	
	
	//??????h = 2*S/a
	h = 2*S/a;
	
	printf("%f\n", S);
	printf("%f\n", L);
	printf("%f\n", h);
	
	return 0;
}



//????????蔵????????????????????蔵??属
double toRadian(int degree){
	
	return degree*PI/180.0;
	
}

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

double t[204], v[104], T = 0;
double ok(double t){
	return min(t, T-t);
}

double check(double x, int k){
	if(t[k-1] <= x && x <= t[k])return v[k];
	if(x < t[k])return (t[k-1]-x)+v[k];
	else return (x-t[k])+v[k];
	return 0;
}

int main(){
	int n;
	scanf("%d", &n);
	rrep(i,n)scanf("%lf", &t[i]);
	rrep(i,n)scanf("%lf", &v[i]);
	rrep(i,n)T += t[i];
	rrep(i,n)t[i+1] += t[i];
	
	double vec = 0, ans = 0;
	for(double t = 0;t <= T;t += 0.5){
		double res = (double)1e9;
		rrep(i,n)res = min(res, check(t, i));
		res = min(res, ok(t));
		ans += 0.5*vec+(res-vec)*0.5/2.0;
		vec = res;
	}
	
	printf("%lf\n", ans);
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    if(a.equals(b)){
      System.out.println("H");
    }else{
      System.out.println("D");
    }
  }
}

Measured memory_bytes: 21460
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from itertools import combinations_with_replacement
INF = float('inf')

def main():
    N, M, Q = map(int, readline().split())
    abcd = []

    for _ in range(Q):
        a,b,c,d = map(int, readline().split())
        abcd.append([a,b,c,d])

    As = combinations_with_replacement(range(1,M+1),N)
    ans = 0

    for A in As:
        score = 0
        for a,b,c,d in abcd:
            if A[b-1] - A[a-1] == c:
                score += d

        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9276
import Control.Monad
import Control.Applicative
import Data.List
import Data.Array

strToInt s = (read :: String -> Int)

acut :: Int -> Int -> Int
acut h w 
  | h `mod` 3 == 0 = 0
  | otherwise = w

bcut :: Int -> Int -> Int
bcut h w = minimum [bcutsub h w c | c <-[1..(h-1)]]


bcutsub :: Int -> Int -> Int -> Int
bcutsub h w l = maximum [abs(a-b),abs(b-c),abs(c-a)]
                where a = (h-l) * (w `div` 2)
                      b = w * (h-l) - a
                      c = w * l



main = do

    [h,w] <- (map read . words) <$> getLine
    
    print (minimum [(acut h w) , (bcut h w) , (acut w h) , (bcut w h)])
    

Measured memory_bytes: 1020
#include <stdio.h>
#include <string.h>

int main(void) {
	char str[201], tmp[101];
	char p[101];
	int slen, plen;
	int i, j, flag;
	
	scanf("%s %s", str, p);
	
	strcpy(tmp, str);
	strcat(str, tmp);
	
	slen = strlen(str);
	plen = strlen(p);
	
	flag = 0;
	for (i = 0; i < slen - plen; i++) {
		if (strncmp(&str[i], p, plen) == 0) flag = 1;
	}
	
	if (flag) puts("Yes");
	else puts("No");
	
	return 0;
}

Measured memory_bytes: 548
#include<stdio.h>
#include<stdlib.h>
int desc(const void *a, const void *b) { //クイックソート
  return *(int *)b - *(int *)a;
}
//qsort(配列,要素数,sizeof(intとかchar)、ascで昇順)
int main(){
    int n;
    scanf("%d",&n);
    int a[200002];
    int i;
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int tmp[200002];
    for(i=0;i<n;i++){
        tmp[i] = a[i];
    }
    qsort(a,n,sizeof(int),desc);
    for(i=0;i<n;i++){
        if(tmp[i]==a[0]){
            printf("%d\n",a[1]);
            
        }
        else{
            printf("%d\n",a[0]);
        }
    }
    return 0;
}

Measured memory_bytes: 3120
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1000000000

int N, Ma, Mb;
int M[40][3];

int dp[50][500][500];

void solve() {
    for (int i = 0; i <= 40; i++) {
        for (int j = 0; j < 500; j++) {
            for (int k = 0; k < 500; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

    dp[0][0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 500; j++) {
            for (int k = 0; k < 500; k++) {
                if (dp[i][j][k] == INF) continue;
                dp[i+1][j][k] = min(dp[i][j][k], dp[i+1][j][k]);
                dp[i+1][M[i][0]+j][M[i][1]+k] = min(dp[i+1][M[i][0]+j][M[i][1]+k], dp[i][j][k]+M[i][2]);  
            }
        }
    }

    int ans = INF;
    for (int i = 1; i < 500; i++) {
        for (int j = 1; j < 500; j++) {
            if(i*Mb==j*Ma) ans = min(ans, dp[N][i][j]);
        }
    }
    
    if(ans >= INF) cout << -1 << endl;
    else cout << ans << endl;
}

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

    for (int i = 0; i < N; i++) {
        cin >> M[i][0] >> M[i][1] >> M[i][2];
    }

    solve();
}

Measured memory_bytes: 41216
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
int main(void){
    char s[1001]={0};
    int sum=0;
    while(1){
        cin >>s;
        if(strcmp(&s[0], "0")==0){
            break;
        }
        for(int i=0; s[i]!='\0'; i++){
            sum+=(int)(s[i]-'0');
        }
        cout <<sum <<endl;
        sum=0;
    }
    return 0;
}

Measured memory_bytes: 3076
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int[][] price = new int[3][26];
		//
		for (int i = 0; i < 3; i++) {
			for (int j = 1; j < 26; j++) {
				switch (i) {
					case 0:
						if (j % 5 == 0) {
							price[i][j] = price[i][j - 1];
						} else {
							price[i][j] = price[i][j - 1] + 380;
						}
						break;
					case 1:
						if (j % 4 == 0) {
							price[i][j] = price[i][j - 1] + 220;
						} else {
							price[i][j] = price[i][j - 1] + 550;
						}
						break;
					case 2:
						if (j % 3 == 0) {
							price[i][j] = price[i][j - 1] + 544;
						} else {
							price[i][j] = price[i][j - 1] + 850;
						}
						break;
				}
			}
		}

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int n = Integer.parseInt(line);
			if (n == 0) {
				break;
			}
			int min = Integer.MAX_VALUE;
			for (int i = 0; i < n / 200 + 1; i++) {
				for (int j = 0; j < n / 300 + 1; j++) {
					for (int k = 0; k < n / 500 + 1; k++) {
						if (i * 200 + j * 300 + k * 500 == n) {
							int sum = price[0][i] + price[1][j] + price[2][k];
							if (sum < min) {
								min = sum;
							}
						}
					}
				}
			}
			System.out.println(min);
		}
	}
}

Measured memory_bytes: 18424
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>
#include <cstdint>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for(ll i = (ll)(n-1); i >= 0; i--)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rrepi(i,a,b) for(ll i=(ll)(b-1);i>=(ll)(a);i--)

#define all(x) (x).begin(),(x).end()

template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;


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

  ll x;cin>>x;
  if(k*500>=x){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;

  return 0;

}


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

int main(void){
        while(1){
                double n;
                scanf("%lf", &n);
                if(n==0) break;

                double sc[(int)n], ave = 0;
                for(int i=0; i<n; i++){
                        scanf("%lf", &sc[i]);
                        ave += sc[i];
                }
                ave /= n;

                double ans = 0;
                for(int i=0; i<n; i++) ans += (sc[i]-ave)*(sc[i]-ave);
                printf("%lf\n", sqrt(ans/n));
        }
        return 0;
}


Measured memory_bytes: 2064
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define ll long long
using namespace std;

int main(void){
    long long n, a, b;
    cin >> n >> a >> b;
    if(n == 1){
        if(a == b){
            cout << "1" << endl;
            return 0;
        }else{
            cout << "0" << endl;
            return 0;
        }
    }
    if(a > b){
        cout << "0" << endl;
        return 0;
    }

    long long ans = (a+b*(n-1)) - (a*(n-1)+b) + 1;
    
    cout << ans << endl;
    return 0;
}



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

int main() {
	int a, b,i;
		while (cin >> a >> b) {
			if (a > b)
				i = b;
			else
				i = a;
			for (; i > 0; i--) {
				if (b%i == 0 && a%i == 0) {
					cout << i << " ";
					break;
				}
				//if (i == 0)
					//cout << 1 << " ";
			}
			if (a > b)
				i = a;
			else
				i = b;
			if (a > b) {
				for (i = a; i%b; i += a);
				cout << i << endl;
			}
			else {
				for (i = b; i%a; i += b);
				cout << i << endl;
			}
		}
	return 0;
}


Measured memory_bytes: 2984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll x,y,z,k; cin>>x>>y>>z>>k;
    vector<ll> a(x),b(y),c(z);
    rep(i,x) cin>>a[i];
    rep(i,y) cin>>b[i];
    rep(i,z) cin>>c[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    //k番目に美味しい組み合わせの美味しさを求める
    //d以上の美味しさの組み合わせがk以上であるようなdの最大値
    ll upper=1e11, under=0;
    while(upper-under>1){
        ll mid=(upper+under)/2;
        ll cnt=0;
        rep(i,x){
            rep(j,y){
                //mid-a[i]-b[j]>=c[k]なるkをカウント
                auto Iter=lower_bound(c.begin(),c.end(),mid-a[i]-b[j]);
                cnt+=c.end()-Iter; //key以上の要素の個数
            }
        }
        if(cnt>=k) under=mid;
        else upper=mid;
    }
    vector<ll> res={};
    rep(i,x){
        rep(j,y){
            auto Iter=lower_bound(c.begin(),c.end(),under-a[i]-b[j]);
            ll cnt=c.end()-Iter;
            rep(k,cnt) res.push_back(a[i]+b[j]+c[z-1-k]);
        }
    }
    sort(res.begin(),res.end(),greater<ll>());
    rep(i,k) cout<<res[i]<<endl;
    return 0;
}

Measured memory_bytes: 133344
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Math.min;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void solve() throws Exception {
		int n = scanInt();
		long a[] = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = scanInt();
		}
		long trees[][] = new long[n - 1][];
		for (int i = 0; i < n - 1; i++) {
			trees[i] = new long[(1 << i) + 1];
			trees[i][0] = trees[i][1 << i] = 1;
			for (int j = 2; j < 1 << i; j += 2) {
				trees[i][j] = trees[i - 1][j >> 1];
			}
			for (int j = 1; j < 1 << i; j += 2) {
				trees[i][j] = trees[i][j - 1] + trees[i][j + 1];
			}
		}
		long tt[] = new long[1 << (n - 2)];
		for (int i = 1; i < 1 << (n - 2); i++) {
			int l = 31 - Integer.numberOfLeadingZeros(i);
			tt[i] = trees[l + 1][((i ^ (1 << l)) << 1) + 1];
		}
		long dyn[][][] = new long[n][n][1 << (n - 1)];
		for (int i = n - 1; i > 0; i--) {
			for (int j = i + 1; j < n; j++) {
				for (int k = 1; k < 1 << (n - 1 - (j - i)); k++) {
					long v = Long.MAX_VALUE;
					for (int l = i; l < j; l++) {
						v = min(v, dyn[i][l][k << 1] + a[l] * tt[k] + dyn[l + 1][j][(k << 1) + 1]);
					}
					dyn[i][j][k] = v;
				}
			}
		}
		out.print(a[0] + dyn[1][n - 1][1] + a[n - 1]);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 468772
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int alphabetCount = 26;          // a to z = 26 
	string  S;
	string answer = "None";
	
	bool existFlag[alphabetCount];
	for (int i = 0; i < alphabetCount; i++)
		existFlag[i] = false;

	cin >> S;
			
	for (int j = 0; j < S.size()  ; j++)
		existFlag[S.at(j) - 'a'] = true;
	
	for (int i = 0; i < alphabetCount; i++) {
		if (existFlag[i] == false ) {
			answer =  (char) ( i + 'a' ) ;
			break;
		}	
	}
	
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 512
// LNU_Algotesters
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include <fstream>
#include <complex>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = 2*INF * (LL) INF;

const int MAX = 200 * 1000 + 47;
const int MOD = INF;


VI G[MAX];
char A[MAX];
int S[MAX];
int D[MAX];
LL ans = 0;

void dfs(int v, int p = -1)
{
    S[v] = (A[v] == '1');
    D[v] = 0;
    FOR(i, 0, SZ(G[v]))
    {
        int to = G[v][i];
        if (to == p)continue;
        dfs(to, v);
        S[v] += S[to];
        D[v] = max(D[v], D[to] + 1);
    }
}

void DFS(int v, int p = -1, int x = 0)
{
    int mn = INF;
    int mx = max(x, 0), mx2 = 0;
    
    if (A[v] == '1')mn = 0;
    if (S[0] != S[v])mn = min(x, mn);
    
    FOR(i, 0, SZ(G[v]))
    {
        int to = G[v][i];
        if (to == p)continue;
        
        if (D[to] + 1 > mx)
            mx2 = mx, mx = D[to] + 1;
        else mx2 = max(mx2, D[to] + 1);
        
        if (S[to] != 0)mn = min(mn, D[to] + 1);
    
    }
    
    ans += max(0, min(mx-1, mx2+1) - mn + 1);
    
    FOR(i, 0, SZ(G[v]))
    {
        int to = G[v][i];
        if(to == p)continue;
        if (D[to] + 1 == mx)
            DFS(to, v, mx2 + 1);
        else
            DFS(to, v, mx + 1);
    }
}


int main()
{
    int n;
    scanf("%d", &n);
    FOR(i, 0, n-1)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        --x, --y;
        G[x].PB(y);
        G[y].PB(x);
    }
    scanf("%s", A);
    dfs(0);
    DFS(0);
    ++ans;
    printf("%lld\n", ans);
}


Measured memory_bytes: 24832
# D - Double Dots

from collections import deque

n, m = map(int, input().split())
adj = {u: [] for u in range(1, n+1)}
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# BFS
parent = {}
queue = deque()
queue.append((1, 1))

while len(queue) > 0:
    p, q = queue.popleft()
    if q in parent: # 訪問済
        continue
    parent[q] = p
    for v in adj[q]:
        queue.append((q, v))

if all(u in parent for u in range(2, n+1)):
    print('Yes')
    for u in range(2, n+1):
        print(parent[u])
else:
    print('No')


Measured memory_bytes: 67716
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int a[3];
    rep(i, 3) { cin >> a[i]; }
    sort(a, a + 3);

    cout << a[0] + a[1] << endl;
    return 0;
}

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

ll gcd(ll a, ll b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
ll f[maxn];
ll p[maxn];
ll pows(ll a,ll b)
{
     ll re=1;
     while(b)
     {
        if(b&1)
        re=re*a%mod;
            a=a*a%mod;
            b/=2;
     }
     return re%mod;
}
void inint()
{
    f[0]=p[0]=1;
    for(int i=1;i<=maxn;i++)
        f[i]=f[i-1]*i%mod,p[i]=pows(f[i],mod-2)%mod;
}
ll C(ll n,ll m)
{
    ll ans=(ll)f[n]*p[n-m]%mod*p[m]%mod;
 //   cout<<f[n]<<' '<<p[n-m]<<' '<<p[m]<<' '<<ans<<endl;
 //cout<<ans<<endl;
     return ans;
}
ll solve(ll n,ll m,ll k)
{
       ll ans=0;
       for(int i=1;i<n  ;i++)
       {
           ans=(ans+C(n*m-2,k-2)*(n-i)%mod*m%mod*m%mod*i%mod)%mod;
          // cout<<ans<<endl;
       }

       return ans%mod;
}
int main()
{
    ll n,m,k;
     cin>>n>>m>>k;
     inint();
     ll ans=(solve(n,m,k)+solve(m,n,k))%mod;
     printf("%lld\n",ans);
    return 0;
}


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

int main() {
	int n, l; cin >> n >> l;
	vector<string> s(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	sort(s.begin(), s.end());

	for (string & t : s) {
		cout << t;
	}
	
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<map>
#include <cstring>
#include<string.h>
#include<stdio.h>

using namespace std;
#define ll long long int


int main()
{
   
 ll n=0,l=0,t;
 string a,b;
 cin>>a>>b;
 if(a==b)
 {
 	n=stoi(a);
 	while(n--)
 		cout<<a;
 }
 else
 {
 n=min(stoi(a),stoi(b));

 if(n==stoi(a))
 {
 	n=stoi(b);

 	while(n--)
 		cout<<a;
 }
 else
 {
 	n=stoi(a);

 	while(n--)
 		cout<<b;
 }
 }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = 1000000007;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef pair<int,int> P;
typedef long long ll;
 
int main(){
    string S;
    cin >> S;
 
    cout << S.substr(0, 4) << " " << S.substr(4) << endl;
    return 0;
}


Measured memory_bytes: 256
N = input()
S = raw_input()
flag1 = 0
a = 0
count = [0,0]
count2 = []
count3 = []
for c in S:
	if(c == "#"):
		if(flag1 == 1):
			flag1 = 0
			count2.append(count[0])
			count3.append(count[1])
		count[0] += 1
	else:
		count[1] += 1
		flag1 = 1
countf = []
for i in range(len(count2)):
	countf.append(count2[i] + count[1] - count3[i])
countf.append(N - count[0])
countf.append(N - count[1])
print(min(countf))

Measured memory_bytes: 15488
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

// debug methods
// usage: debug(x,y);
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {rep(i, sz(vec)) os << vec[i] << (i+1==sz(vec)? "" : ", "); return os; }
void print() { cout << endl; }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << ((sizeof...(tail)!=0)?" ":""); print(forward<Tail>(tail)...); }
template <class T> void print(vector<T> &vec) { for (auto& a : vec) { cout << a << ((&a!=&vec.back())?" ":""); } cout << endl; }
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec); } }
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,a5,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#define debug_6(x1,x2,x3,x4,x5,x6) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<", "#x6<<": "<<x6<<endl
#define debug(...) CHOOSE((__VA_ARGS__,debug_6,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)

int main() {
	int n, k; cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	int ans = 0;
	rep(i, k) ans += a[i];
	cout << ans << endl;
}

Measured memory_bytes: 3624
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

if __name__ == '__main__':
    n, x = map(int, input().split())
    count =n
    list=[]
    for i in range(n):
        a = int(input())
        list.append(a)
    x -=sum(list)
    list.sort()
    count += x//list[0]
    print(count)


Measured memory_bytes: 13312
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
n,m=map(int,input().split())
l=[-1]*n
z=n*(n-1)//2
b=tuple(input().split() for _ in range(m))
c=[0]*m+[z]
def r(s):
  t=l[s]
  if t<0:
    return s
  else:
    l[s]=r(t)
    return l[s]
def f(s):
  return r(int(s)-1)
for i in range(m-1,0,-1):
  x,y=map(f,b[i])
  if x!=y:
    s,t=l[x],l[y]
    z-=s*t
    if s>t:
      l[x]=y
      l[y]+=s
    else:
      l[y]=x
      l[x]+=t
  c[i]=z
for x in c[1:]:
  print(x)

Measured memory_bytes: 40272
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, K = mi()
ma = mi = 0
mod = 10**9+7
for i in range(K-1):
    ma += N-i
    mi += i
ans = 0

#mi = (K * (K-1))//2
for i in range(K-1, N+1):
    ma += N-i
    mi += i
    ans = (ans + (ma-mi+1))%mod
print(ans)


Measured memory_bytes: 9236
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<Pi>xy(N);
    vector<ll>pxy(N);
    vector<ll>mxy(N);
    rep(i,N){
        ll x,y;
        cin>>x>>y;
        xy[i].first=x+y;
        xy[i].second=x-y;
        pxy[i]=x+y;
        mxy[i]=x-y;
    }
    sort(all(pxy));
    sort(all(mxy));


    cout << max(pxy[N-1]-pxy[0],mxy[N-1]-mxy[0]) << endl;


    return 0;
    

}

Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i, n) ;for (int i = 0;i < (int)(n);i++)
#define rep2(i, s, n) ;for (int i = s; i < (int)(n);i++)
#define ALL(vec)  (vec).begin(),(vec).end()
#define pi 3.1415926535897932384626433832795
#define MAX_INF 9223372036854775807
#define MIN_INF (922337203685477587+1)
#define sosuu 1000000007

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

  if(a/d>c/b)
    cout << "Yes" << endl;
  else if (a/d<c/b){
    if(a%d!=0&&a/d+1==c/b){
      if(c%b==0)
      cout << "Yes" << endl;
    else
    cout << "No" << endl;
    }
    
    else
    cout << "No" << endl;
  }
  else
  {
    if(a%d==0){
    if(c%b==0){
    cout << "Yes" << endl;
    }
      else
        cout << "No" << endl;
    }
    else
      cout << "Yes" << endl;
  }

}

Measured memory_bytes: 3676
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=200003;
int main(){
  bool a[10101],b[10101];
  int n;
  cin>>n;
  
  for(int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    fill(b,b+10101,false);
    for(int j=0;j<10001;j++){
      if(a[j]){
        b[j]=true;
        b[j+tmp]=true;
      }
    }
    b[tmp]=true;
    swap(a,b);
  }
  for(int i=10000;i!=-1;i--){
    if(a[i] and i%10!=0){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m; i < n; i++) 
#define mod 1000000007
typedef long long ll;
int main(){
    string S;
    cin>>S;
    if(S[2]==S[3]&&S[4]==S[5]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define T top()
#define E end()
#define PS push
#define Q queue
#define PP pop()
#define L0 (LL)0
#define V vector
#define ST stack
#define FI first
#define MAX 4e18
#define MIN -MAX
#define DQ deque
#define RE rend()
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define SE second
#define DL double
#define G getline
#define IN insert
#define endl "\n"
#define EM empty()
#define EE emplace
#define RB rbegin()
#define MD 1000000007
#define PSB push_back
#define PI acos(-1.00)
#define PPB pop_back()
#define PSF push_front
#define ub upper_bound
#define lb lower_bound
#define PPF pop_front()
#define EB emplace_back
#define LL long long int
#define PQ priority_queue
#define N cout<<"NO"<<endl
#define Y cout<<"YES"<<endl
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define UOSMOY v.C;w.C;ww.C;uu.C;uo.C;vo.C;vu.C;ab.C;bc.C;cc.C;uuu.C;a.C;b.C;c.C;u.C
V<LL>v;
V<LL>w,ab,bc;
set<LL>uo;
map<LL,LL>ww,cc,u;
V<pair<LL,LL> >uu;
map<LL,V<LL> >uuu;
map<pair<LL,LL>,LL> vo;
map<pair<LL,LL>,LL> vu;
LL dxx[]= {-1,0,1,0};
LL dyy[]= {0,1,0,-1};
LL dx[]= {2,1,-1,-2,-2,-1,1,2};
LL dy[]= {1,2,2,1,-1,-2,-2,-1};
int main()
{
//  BRR;
//  file;
    FAST;
    char ch;
    string a,b,c;
    DL x,y,d,e,f,g,h;
    LL n,m,i,j,k,p,q,o,l,s,tt=1,t,z,aa,r=0;
//    cin>>tt;
    while(tt--)
    {
        UOSMOY;
        cin>>n>>m;
        for(i=0;i<m;i++)
        {
            cin>>p>>q;
            uuu[p].PSB(q);
            uuu[q].PSB(p);
        }
        l=0;
        k=0;
        for(i=1;i<=n;i++)
        {
            if(u[i]==0)
            {
                l++;
                stack<LL>an;
                an.PS(i);
                u[i]=l;
                ww[l]++;
                k=max(k,ww[l]);
                while(!an.EM)
                {
                    o=an.T;
                    an.PP;
                    for(j=0;j<uuu[o].SZ;j++)
                    {
                        if(u[uuu[o][j]]==0)
                        {
                            an.PS(uuu[o][j]);
                            u[uuu[o][j]]=l;
                            ww[l]++;
                                            k=max(k,ww[l]);
                        }
                    }
                }
            }
        }
        cout<<k<<endl;

    }
    return 0;
    //IN
    //AL
}


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

struct compare1 { 
    bool operator()(const pair<int, int>& value,  
                                const int& key) 
    { 
        return (value.first < key); 
    } 
    bool operator()(const int& key,  
                    const pair<int, int>& value) 
    { 
        return (key < value.first); 
    } 
}; 

int main()
{
    int N, D, A, temp, bom;
    long ans;
    vector<pair<int, int>> XH(200005);
    int b[200005];
    int out[200005];
    cin >> N >> D >> A;
    REP(i, N)
        cin >> XH[i].first >> XH[i].second;
    sort(XH.begin(), XH.begin() + N);
    REP(i, N){
        if(binary_search(XH.begin(), XH.begin() + N, XH[i].first + 2 * D, compare1()))
            b[i] = (int)(lower_bound(XH.begin(), XH.begin() + N, XH[i].first + 2*D, compare1()) - XH.begin());
        else
            b[i] = (int)(lower_bound(XH.begin(), XH.begin() + N, XH[i].first + 2*D, compare1()) - XH.begin()) - 1;
    }
    temp = 0;
    ans = 0;
    REP(i, N)
        out[i] = 0;
    REP(i, N){
        temp -= out[i];
        if((XH[i].second - temp) > 0){
            if((XH[i].second - temp) % A == 0)
                bom = (XH[i].second - temp) / A;
            else
                bom = (XH[i].second - temp) / A + 1;
            ans += (long)bom;
            temp += bom * A;
            out[b[i]+1] += bom * A;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3328
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
    vector<LLONG> ps(A), qs(B), rs(C);
    for (auto &i : ps) cin >> i; sort(ps.rbegin(), ps.rend());
    for (auto &i : qs) cin >> i; sort(qs.rbegin(), qs.rend());
    for (auto &i : rs) cin >> i;
    vector<LLONG> usedApples = rs;
    for (int i = 0; i < X; ++i) usedApples.push_back(ps[i]);
    for (int i = 0; i < Y; ++i) usedApples.push_back(qs[i]);
    sort(usedApples.rbegin(), usedApples.rend());
    cout << accumulate(usedApples.begin(), usedApples.begin() + X + Y, 0LL) << endl;
}


Measured memory_bytes: 6896
n = int(input())
a = []
for i in range(n):
	a.append(input().split())
for i in range(len(a)-2):
	if(a[i][0] == a[i][1] and a[i+1][0] == a[i+1][1] and a[i+2][0] == a[i+2][1]):
		print("Yes")
		exit()
print("No")

Measured memory_bytes: 9188
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = unsigned long long;
const int MOD = 1e9 + 7;
int main() {
    ll N;
    vector<ll> A;
    cin >> N;
    REP(i, N) {
        ll a;
        cin >> a;
        A.push_back(a);
    }

    ll ans;
    REP(i, 63) {
        ll zc, oc;
        zc = oc = 0;
        REP(j, N) {
            if (A[j] % 2 == 0) {
                zc++;
            } else {
                oc++;
            }
            A[j] /= 2;
        }
        zc %= MOD;
        oc %= MOD;

        ans = (ans + (((zc * oc) % MOD * ((1LL << i) % MOD)) % MOD)) % MOD;
    }

    cout << ans << endl;

    return 0;
}


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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<bool> prime(200000, true);
    prime[0] = prime[1] = false;
    for(int i = 2; i <= 1000; i++){
        for(int j = i; j < 200000; j+=i){
            if(j == i){
                if(prime[j]) continue;
                else break;
            }
            prime[j] = false;
        }
    }

    int ruiseki[100001] = {};
    vector<bool> similar(100000, false);

    for(int i = 1; i <= 100000; i+=2){
        if(prime[i] & prime[(i+1)/2]) similar[i] = true; 
    }
    for(int i = 1; i < 100000; i++){
        if(similar[i]) ruiseki[i+1] = ruiseki[i]+1;
        else ruiseki[i+1] = ruiseki[i];
    }

    int Q; cin >> Q;
    rep(i, Q){
        int l, r; cin >> l >> r;
        cout << ruiseki[r+1] - ruiseki[l] << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
  int s;
  cin >> s;
  int ans = 0;
  for(int i = 0;i < 3;i++){
    if(s % 10 == 1)ans += 9*pow(10,i);
    else ans += pow(10,i);
    s /= 10;
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int MAXN = 210000;

string s;
int cc[100];
int cc2[100];
int tp[MAXN];
vector<pair<int, int>> vl;
vector<pair<int, int>> vr;
map<pair<int, int>, int> mm;
int a[MAXN];
int fv[MAXN];
ll ans = 0;
int cct[MAXN];

int get(int x) {
	int ans = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1)
		ans += fv[x];
	return ans;
}

void add(int x) {
	for (; x < vr.size(); x |= (x + 1))
		fv[x] += 1;
}

int main() {
	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		++cc[s[i] - 'a'];
	}
	int fl = 0;
	for (int i = 0; i < 26; ++i) {
		if (cc[i] % 2 == 1)
			++fl;
	}
	if (fl >= 2) {
		cout << -1 << "\n";
		return 0;
	}
	for (int i = 0; i < s.size(); ++i) {
		int c = s[i] - 'a';
		++cc2[c];
		if (cc[c] % 2 == 1 && cc2[c] * 2 - 1 == cc[c])
			tp[i] = 1;
		else if (cc2[c] * 2 <= cc[c])
			tp[i] = 0;
		else
			tp[i] = 2;
		for (int j = 2; j > tp[i]; --j)
			ans += cct[j];
		++cct[tp[i]];
		if (tp[i] == 0)
			vl.push_back(make_pair(c, cc2[c] - 1));
		else if (tp[i] == 2)
			vr.push_back(make_pair(c, cc[c] - cc2[c]));
	}
	reverse(vr.begin(), vr.end());
	for (int i = 0; i < vl.size(); ++i)
		mm[vl[i]] = i;
	for (int i = 0; i < vr.size(); ++i)
		a[i] = mm[vr[i]];
	for (int i = (int)vr.size() - 1; i >= 0; --i) {
		ans += get(a[i]);
		add(a[i]);
	}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 9848
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
if b.count(0)==n:
    print("Yes")
elif n%3==0:
    if b.count(0)==n//3 and b.count(b[n-1])==n-(n//3):
        print("Yes")
    elif b[0]^b[n//3]^b[n-1]==0 and b.count(b[0])==n//3 and b.count(b[n//3])==n//3 and b.count(b[n-1])==n//3:
        print("Yes")
    else:
        print("No")
else:
    print("No")


Measured memory_bytes: 85520