akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,K,Q = inputIL()
A = inputILs(Q)

d = [K-Q for i in range(N)]
for i in A:
  d[i-1] += 1
  
for i in d:
  if i > 0:
    print("Yes")
  else:
    print("No")


Measured memory_bytes: 75480
h,w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))

ans = []
for i in range(n):
  for _ in range(a[i]):
    ans.append(i+1)
  
for i in range(h):
  if i%2 == 0: print(*ans[i*w:(i+1)*w])
  else: print(*reversed(ans[i*w:(i+1)*w]))

Measured memory_bytes: 9536
#include<stdio.h>
int main(){
	char c;
	int a=0,color,now=0,i,k=0;
	long int s[a];
	for(;;){
		scanf("%c",&c);
		if(c=='J'){color=1;}
		else if(c=='O'){color=2;}
		else if(c=='I'){color=3;}
		else if(c==10){break;}
		if(now==0){
			if(color==1){s[0]=1;now=1;}
		}
		else if(now==1){
			if(color==1){s[0]++;}
			else if(color==2){now=2;s[1]=1;}
			else if(color==3){now=0;}
		}
		else if(now==2){
			if(color==1){s[0]=1;now=1;}
			else if(color==2){s[1]++;}
			else if(color==3){
				now=3;s[2]=1;
				if(s[0]>=s[1] && s[1]<=s[2] && k<s[1]){k=s[1];}
			}
		}
		else if(now==3){
			if(color==1){s[0]=1;now=1;}
			else if(color==2){now=0;}
			else if(color==3){s[2]++;}
			if(s[0]>=s[1] && s[1]<=s[2] && k<s[1]){k=s[1];}
		}
	}
	printf("%d\n",k);
	return 0;
}

Measured memory_bytes: 360
#include <iostream>
using namespace std;
int main(void){
    int x,h,m,s;
    cin >> x;
    
    h = x/3600;
    m = ((x-(h*3600))/60);
    s = (x - h*3600 - m*60);
    
    cout << h << ":" << m << ":" << s << endl;
    return 0;
    
    
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
int main(){
  ll n,k;
  cin>>n>>k;
  vll x(n);
  ll ans=0;
  for (ll i=0;i<n;i++) {
    cin >> x[i];
    ans += min(k-x[i],x[i]);
  }
  cout << 2*ans;
}

Measured memory_bytes: 256
#include<iostream>
#include <string>
#include<vector>
typedef long long ll;

using namespace std;
int main()
{
	string kotae = "Yes";

	string s,t;
	cin >> s;
	cin >> t;
	vector<char> dict(26,'@');
	vector<char> dict2(26,'@');

	for (int i = 0; i < s.size(); i++) {
		for (int j = 0; j < 26; j++) {
			if (dict[j] == '@') {
				dict[j] = s[i];
				dict2[j] = t[i];
				break;
			}
			if (dict[j] == s[i]|| dict2[j] == t[i]) {
				if (dict2[j] != t[i]) {
					kotae = "No";
				}
				if (dict[j] != s[i]) {
					kotae = "No";					
				}
				break;
			}
		}
	}
	cout <<kotae << endl;
	return 0;
}

Measured memory_bytes: 776
#include <stdio.h>
#include <string.h>
int main()
{
	int a;
	int c=0,w=0,t=0,r=0;
	scanf("%d",&a);
	char b[a][81];
	for(int i=0;i<a;i++)
	{
		scanf("%s",b[i]);
		getchar();
	}
		for(int j=0;j<a;j++)
	{
		if(b[j][0]=='A')
		c=c+1;
		else if(b[j][0]=='W')
		w=w+1;
		else if(b[j][0]=='T')
		t=t+1;	
		else if(b[j][0]=='R')
		r=r+1;
	}
	printf("AC x %d\n",c);
		printf("WA x %d\n",w);
			printf("TLE x %d\n",t);
				printf("RE x %d\n",r);
	return 0;
 } 

Measured memory_bytes: 9636
a, b, k = map(int, input().split())
i, x = 0, 0

while a+i <= b and i < k:
    x = a + i
    print(x)
    i += 1

i = k - 1
while b-i <= b:
    y = b - i
    if y <= x:
        i -= 1
        continue
    print(y)
    i -= 1


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

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	int mx = *max_element(a.begin(), a.end());
	int k = mx / 2;
	int r, dist = 2e9;
	for (int i = 0; i < n; ++i)
		if (a[i] != mx && dist > abs(a[i] - k))
			dist = abs(a[i] - k), r = a[i];
	printf("%d %d\n", mx, r);
  return 0;
}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = set(map(int, [input() for _ in range(m)]))
dp = [0] * (n+1)

#`dp[i] = i段目にいる通り数`
if not 0 in a:
    dp[0] = 1
if not 1 in a:
    dp[1] = 1
    
for i in range(2,n+1):
    if i in a:
        dp[i] = 0
    else: 
        dp[i] += (dp[i-1] + dp[i-2]) % (10 ** 9 + 7)

print(dp[-1])


Measured memory_bytes: 18332
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define L(i,u) for (int i=head[u]; i!=0; i=nxt[i])
#define rep(i,a,b) for (register int i=a; i<=b; i++)
#define per(i,a,b) for (register int i=a; i>=b; i--)
typedef long long ll;
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
int n,a[233333],f[233333];
int main() {
	read(n);rep(i,1,n)read(a[i]);int mx=0;
	rep(i,1,n)f[a[i]]=f[a[i]-1]+1;rep(i,1,n)mx=max(mx,f[i]);
	cout<<n-mx;
	return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long h = Integer.parseInt(sc.next());
		long w = Integer.parseInt(sc.next());
		long max = (h + 2) / 3 * w;
		long min = h / 3 * w;
		long diff = max - min;
		max = (w + 2) / 3 * h;
		min = w / 3 *  h;
		diff = Math.min(diff, max - min);
		for (int i = 1; i < h; i++) {
			max = Math.max(i * w, (w + 1) / 2 * (h - i));
			min = Math.min(i * w, w / 2 * (h - i));
			diff = Math.min(diff, max - min);
		}
		for (int i = 1; i < w; i++) {
			max = Math.max(i * h, (h + 1) / 2 * (w - i));
			min = Math.min(i * h, h / 2 * (w - i));
			diff = Math.min(diff, max - min);
		}
		System.out.println(diff);
	}
}

Measured memory_bytes: 23124
#n=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

s=list(input())

if s[2]==s[3] and s[4]==s[5]:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define INF 93193111451418101
using namespace std;
int main()
{
	double a, b;
	cin >> a >> b;
	a = (a + b) / 2;
	a += 0.5;
	cout << (int)a << endl;
}

Measured memory_bytes: 256
n = int(input())


def 約数(n):
	count = 0
	for i in range(1,n+1):
		if n%i == 0:
			count += 1
	if count == 8:
		return True
	else:
		return
if n == 105:
	print(1)
elif n < 105:
	print(0)
else:
	ans = 1
	for i in range(106,n+1):
		if i%2 !=0:
			if 約数(i):
				ans += 1


	print(ans)


Measured memory_bytes: 3192
#![allow(unused_imports)]
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;
use std::str::FromStr;
use std::cmp::Reverse;

#[allow(dead_code)]
type Error = Box<dyn std::error::Error>;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

struct Scanner {
    buff: Vec<String>,
    pos: usize,
}

#[allow(dead_code)]
impl Scanner {
    pub fn new() -> Self {
        Scanner {
            buff: Vec::new(),
            pos: 0,
        }
    }

    pub fn next<T: FromStr>(&mut self) -> T {
        while self.buff.len() <= self.pos {
            self.pos = 0;
            self.buff = read_line().split_whitespace().map(|s| s.to_owned()).collect();
        }

        let result = self.buff[self.pos].parse::<T>();
        self.pos += 1;
        result.ok().unwrap()
    }

    pub fn next_line(&mut self) -> String {
        let result  = read_line().trim().to_owned();
        self.buff.clear();
        self.pos = 0;

        result
    }

    pub fn next_vec<T: FromStr>(&mut self) -> Vec<T> {
        self.buff.clear();
        self.pos = 0;
        read_line().trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect()
    }
    
    pub fn next_line_chars(&mut self) -> Vec<char> {
        let result  = read_line().trim().chars().collect();
        self.buff.clear();
        self.pos = 0;

        result
    }
}

const MOD: u64 = 998_244_353;

fn main() {
    let mut sc = Scanner::new();

    let a: usize = sc.next();
    let b: usize = sc.next();
    let c: usize = sc.next();
    let d: usize = sc.next();

    let mut memo = vec![vec![0u64; d+10]; c+10];
    memo[a][b] = 1;
    memo[a+1][b] = b as u64;
    memo[a][b+1] = a as u64;

    for i in a..c {
        memo[i+1][b] = (memo[i][b] * b as u64) % MOD;
    }
    for i in b..d {
        memo[a][i+1] = (memo[a][i] * a as u64) % MOD;
    }

    for i in a..c {
        for j in b..d {
            let x = i as u64;
            let y = j as u64;
            memo[i+1][j+1] += memo[i+1][j] * (x+1);
            memo[i+1][j+1] %= MOD;
            memo[i+1][j+1] += memo[i][j+1] * (y+1);
            memo[i+1][j+1] %= MOD;
            memo[i+1][j+1] += MOD - memo[i][j] * x * y % MOD;
            memo[i+1][j+1] %= MOD;
        }
    }

    println!("{}", memo[c][d]);
}


Measured memory_bytes: 72892
a, b, c = gets.chomp.split("\s")
a, b, c = a.to_i, b.to_i, c.to_i

if a > b
 n = a
 a = b
 b = n
end

if a > c
	print(c, " ", a, " ", b, "\n")
elsif b > c
	print(a, " ", c, " ", b, "\n")
else
	print(a, " ", b, " ", c, "\n")
end

Measured memory_bytes: 6096
N,M = map(int,input().split())
S = list(map(int,input()))

S.reverse()

#後ろから貪欲に

a = 0  #合計何マス進んだか
A = []  #何マスずつ進んでいるか

while a < N:
    if N-a <= M:
        A.append(N-a)
        a = N
    else:
        for i in range(M,0,-1):
            if S[a+i] == 0:
                A.append(i)
                a += i
                break
        else:
            print(-1)
            exit()

A.reverse()
print(*A)

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

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert_tree(int num){
    Node *find = root;
    Node *tmp_parent = NIL;
    Node *obj;

    obj = new Node;
    obj->key = num;
    obj->left = NIL;
    obj->right = NIL;

    while (find != NIL){
        tmp_parent = find;
        if(find->key > obj->key){
            find = find->left;
        }
        else{
            find = find->right;
        }
    }
    obj->parent = tmp_parent;

    if(tmp_parent == NIL){
        root = obj;
    }
    else{
        if(tmp_parent->key > obj->key){
            tmp_parent->left = obj;
        }
        else{
            tmp_parent->right = obj;
        }
    }
}

void inorder(Node *node){

    if(node == NIL){
        return;
    }
    inorder(node->left);
    cout << " " << node->key;
    inorder(node->right);
}

void preorder(Node *node){

    if(node == NIL){
        return;
    }
    cout << " " << node->key;
    preorder(node->left);
    preorder(node->right);
}

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

    string command;
    rep(i, n){
        cin >> command;
        if(command == "insert"){
            int num;
            cin >> num;
            insert_tree(num);
        }
        else if(command == "print"){
            inorder(root);
            cout << "\n";
            preorder(root);
            cout << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 26568
def gcd(a,b)
  return a if b == 0
  gcd(b,a%b)
end

def lcm(a,b)
  a * b / gcd(a,b)
end

MOD=1000000007

N=gets.to_i
a=gets.chomp.split.map(&:to_i)

l=1
a.each do |v|
  l = lcm(l,v)
end
ans=0
a.each do |v|
  ans += l / v
end


p ans%MOD

Measured memory_bytes: 56840
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
map<string, int> cache;
bool same(string seq){
  for(int i = 0; seq[i+1] != '\0'; ++i){
    if(seq[i] != seq[i+1]){
      return false;
    }
  }
  return true;
}
int dls(string seq, int depth){
  if(depth<0){
    return false;
  }
  if(same(seq)){
    return true;
  }
  if(cache.find(seq) != cache.end()){
    if(cache[seq] >= depth){
      return false;
    }
    cache[seq] = depth;
  }
  else{
    cache[seq] = depth;
  }
  for(int i = 0; seq[i+1] != '\0'; ++i){
    char t = seq[i];
    char n = seq[i+1];
    if(t != n){
      if((t + n) == ('r' + 'b')){
        seq[i] = seq[i+1] = 'g';
      }
      else if((t + n) == ('r' + 'g')){
        seq[i] = seq[i+1] = 'b';
      }
      else{
        seq[i] = seq[i+1] = 'r';
      }
      if(dls(seq, depth-1)){
        return true;
      }
      seq[i] = t;
      seq[i+1] = n;
    }
  }
  return false;
}
void iddfs(string seq){
  cache = map<string, int>();
  for(int depth = 0;depth <= 20; ++depth){
    if(dls(seq, depth)){
      cout << depth << endl;
      return;
    }
  }
  cout << "NA" << endl;
}
int main(){
  char seq[11];
  while(true){
    cin >> seq;
    if(seq[0] == '0'){
      break;
    }
    iddfs(seq);
  }
  return 0;
}

Measured memory_bytes: 2496
#include<stdio.h>
int main(void){
  long long int n;
  scanf("%lld",&n);
  int a[100000],i;
  for(i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
 
  for(i=0;i<n-1;i++){
    if(a[i]<a[i+1]){
      a[i+1]-=1;
    }
  }
  for(i=0;i<n-1;i++){
    if(a[i]>a[i+1]){
      printf("No");
    return 0;
    }
  }
  printf("Yes");
  return 0;
}


Measured memory_bytes: 512
n = int(input())
s = [input() for i in range(n)]

f = [a for a in s if a.startswith('M')]
g = [b for b in s if b.startswith('A')]
h = [c for c in s if c.startswith('R')]
i = [d for d in s if d.startswith('C')]
j = [e for e in s if e.startswith('H')]

k = len(f)*len(g)*len(h)
l = len(f)*len(g)*len(i)
m = len(f)*len(g)*len(j)
n = len(f)*len(h)*len(i)
o = len(f)*len(h)*len(j)
p = len(f)*len(i)*len(j)
q = len(g)*len(h)*len(i)
r = len(g)*len(h)*len(j)
s = len(g)*len(i)*len(j)
t = len(h)*len(i)*len(j)

sum = k+l+m+n+o+p+q+r+s+t
print(sum)

Measured memory_bytes: 10540
def f(s, i, d):
  if len(d) == 0:
    return "-1"
  if len(s) == i:
    d.sort()
    return d[0]
  d.remove(s[i])
  r = f(s, i+1, d)
  if r == "-1":
    d.sort()
    for j in d:
      if s[i] < j:
        return j
    d.append(s[i])
    return "-1"
  return "".join([s[i], r])

def main():
  d = list("abcdefghijklmnopqrstuvwxyz")
  t = input()
  r = f(t, 0, d)
  print(r)

main()


Measured memory_bytes: 3064
#include<stdio.h>

#define MAX 1000000000000000000

int main(void){
    unsigned long int x,y;
    unsigned long int i;
    scanf("%lu %lu", &x, &y);
    for(i = x; i <= MAX; i += x ){
        if(i % y == 0){
            printf("-1");
            return 0;
        }
        else{
            printf("%lu", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}


Measured memory_bytes: 128
/**	epsileer 12 January 2020  17:59:13  **/	
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TEST int t = 1; while(t--) solve()

vector<pair<int,int>> gp[1000];

void solve(){
	int n,m; cin>>n>>m;
	vector<vector<char>> mat(n, vector<char>(m));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mat[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(mat[i][j] == '.'){
				int p = i*m+j;
				if(i-1 >= 0){
					if(mat[i-1][j] == '.')
						gp[p].push_back({1,(i-1)*m+j});
				}
				if(i+1 < n){
					if(mat[i+1][j] == '.')
						gp[p].push_back({1,(i+1)*m+j});
				}
				if(j-1 >= 0){
					if(mat[i][j-1] == '.')
						gp[p].push_back({1,i*m+j-1});
				}
				if(j+1 < m){
					if(mat[i][j+1] == '.')
						gp[p].push_back({1,i*m+j+1});
				}
			}
		}
	}

	// for(int i=0;i<m*n;i++){
	// 	cout<<i<<" : ";
	// 	for(auto j: gp[i]){
	// 		cout<<j.second<<" ";
	// 	}
	// 	cout<<endl;
	// }

	int ans = 0;

	for(int i=0;i<m*n;i++){
		int x = i/m, y = i%m;
		if(mat[x][y] != '.'){
			continue;
		}
		int s = i;
		priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
		vector<int> visited(n*m+1,0),dist(n*m+1,INT_MAX);
		dist[s] = 0;
		pq.push(make_pair(0, s));
		while(!pq.empty()){
			pair<int,int> u = pq.top(); pq.pop();
			visited[u.second] = 1;
			for(auto v: gp[u.second]){
				if(!visited[v.second] && dist[u.second]+v.first < dist[v.second]){
					dist[v.second] = dist[u.second] + v.first;
					pq.push(make_pair(dist[v.second], v.second));
				}
			}
		}
		for(int i=0;i<n*m;i++){
			if(dist[i] != INT_MAX)
				ans = max(ans, dist[i]);
		}
	}

	cout<<ans;
}

signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); TEST; return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
 
int main(){
  int N,A,B,num,total = 0;
  cin >> N >> A >> B;
  for(int i = 1;i <= N;i++){
    num = i / 10000 + (i % 10000) / 1000 + (i % 1000) / 100 + (i % 100) / 10 + (i % 10);
    if(A <= num && num <= B)total += i;
  }
  cout << total << endl;
}

Measured memory_bytes: 256
def main():
    C = [list(map(int, input().split())) for _ in range(3)]
    ok = True
    for i in (1, 2):
        if C[i][0] - C[i-1][0] != C[i][1] - C[i-1][1] or \
            C[i][1] - C[i-1][1] != C[i][2] - C[i-1][2]:
            ok = False
        if C[0][i] - C[0][i-1] != C[1][i] - C[1][i-1] or \
            C[1][i] - C[1][i-1] != C[2][i] - C[2][i-1]:
            ok = False
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()


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

auto clk=clock();
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define Mod 987654319 
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define all(x) x.begin(),x.end()


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n ; cin>>n;
    cout<<(n-1)/2<<"\n";
    cerr<<"\n"<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<"\n";
    return 0;
}


Measured memory_bytes: 256
N, Y = map(int, input().split())
for x in range(N+1):
    for y in range(N-x+1):
        z = N-x-y
        if 0 <= z <= 2000 and 10000*x+5000*y+1000*z == Y:
            print(x, y, z)
            exit()
print(-1, -1, -1)

Measured memory_bytes: 9172
N = int(input())
A = list(map(int,input().split()))
A.sort()
k = N - 2
a = A.pop()
ans = a
n = k // 2
for i in range(n):
    a = A.pop()
    ans += 2*a
if k - 2*n == 1:
    ans += A[-1]

print(ans)

Measured memory_bytes: 31436
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const int INF = 1e9 + 5;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin>>n;
    int A,B,C,a,b,c,A_,B_,C_;
    for(int i=0;i<n;i++){
		cin>>a>>b>>c;
		if(i==0){
			A = a;
			B = b;
			C = c;
		}
		else{
			A_ = a + max(B,C);
			B_ = b + max(A,C);
			C_ = c + max(A,B);
			A = A_;
			B = B_;
			C = C_;
		}
		//cout<<A<<" "<<B<<" "<<C<<"\n";
	}
    cout<<max({A,B,C});
    return 0;
}









Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<math.h>

using namespace std;

int main(){

    //unsigned long long int x;
    long double x;
    cin >> x;

    long long int c=0;
    //unsigned long long  int a=100;
    long double a=1;

    while(a<x/100){
        a=a*101/100;
        a=floor(100*a)/100;
        c++; 
    }


    cout << c << endl;    
    


}

Measured memory_bytes: 3548
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

Int N;
vector<Int> a;
vector<vector<Int>> dp;



Int solve(Int i, Int j) {
	if (dp[i][j]!=-1) {
		return dp[i][j];
	}

	if (i==j) {
		return dp[i][j] = 0;
	}

	//先手
	if ((j-i)%2==N%2){
		return dp[i][j] = max(a[i] + solve(i + 1, j), a[j - 1] + solve(i, j - 1));
	}

	//後手
	else {
		return dp[i][j] = min(-a[i] + solve(i + 1, j), -a[j - 1] + solve(i, j - 1));
	}
}

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	cin >> N;
	a.resize(N);
	for (Int i = 0; i < N; i++) {
		cin >> a[i];
	}

	dp.resize(N+1);
	for (Int i = 0; i < N+1; i++) {
		dp[i].resize(N + 1,-1);
	}

	cout << solve(0,N) << "\n";

}


Measured memory_bytes: 70912
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long

using namespace std;

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

	int sum = 0;
	for (int ii = 0; ii < N.size(); ++ii){
		sum += N[ii] - '0';
	}

	if (sum % 9 == 0){
	cout << "Yes" << "\n";
	} else {
	cout << "No" << "\n";		
	}


	return 0;
}


Measured memory_bytes: 3724
N = int(input())
count = 0
max = 0
ans = 1
for i in range(1, N+1, 1):
    count = 0
    n = i
    while 1:

        if n%2!=0:
            break
        n = n //2
        count = count + 1
    if max<count:
        max = count
        ans = i
print(ans)

Measured memory_bytes: 3060
def main():
	# s = int(input())
	# s = str(input())
	a,b = map(int,input().split())
	#1行R列
	# a = list(map(int,input().split()))
	#R行1列
	# l = [str(input()) for i in range(n)]
	#R行C列
	# qu = [list(map(str,input().split())) for x in range(q)]
	# print(' '.join(map(str,)))
	import math
	def combinations_count(n, r):
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

	if a <= 1 and b > 1:
		print(combinations_count(b,2))
	elif a <= 1 and b <= 1:
		print(0)
	elif a > 1 and b <= 1:
		print(combinations_count(a,2))
	else:
		print(combinations_count(a,2) + combinations_count(b,2))


if __name__ == '__main__':
	main()

Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N; cin >> N;
    map<int,int> mp;

    vector<int> A(N);
    for(auto& it : A){
        cin >> it;
    }

    for(int i=0; i<N; i++){
        mp[A.at(i)] += 1;
    }

    long long cnt = 0;
    for(auto it = mp.begin(); it != mp.end(); it++){
        long long n = it->second;
        cnt += n*(n-1)/2;
    }

    for(int i=0; i<N; i++){
        long long ans = cnt;
        ans -= mp[A.at(i)]-1;
        cout << ans << endl;
    }


}

Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
#define forn(i,p,n); for(long long i=p;i<n;++i)
#define pb push_back
void solve(){
	int n;
	cin >> n;
	vector<ll> a(n);
	forn(i,0,n) cin >> a[i];
	int ans = 0;
	map<int,int> mp;
	forn(i,0,n) mp[a[i]]++;
	auto itr = mp.begin();
	for(;itr!=mp.end();++itr){
		auto itr2=itr;
		++itr2;
		for(;itr2!=mp.end();++itr2){
			auto itr3  =itr2;
			++itr3;
			for(;itr3!=mp.end();++itr3){
				int a,b,c;
				a = itr->first;
				b = itr2->first;
				c = itr3->first;
				if((a+b)>c){
					ans+=itr->second*itr2->second*itr3->second;			
				}
			}
		}
	}
	cout<<ans;
	return ;
}
 
int main()
{
	fast;
	// int test;
	// cin >> test;
	// while(test--){
		solve();
	// 	cout<<"\n";
	// }
}

Measured memory_bytes: 3664
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
	if (a<b) { return gcd(b, a); }
	else if (a%b) { return gcd(b, a%b); }
	else { return b; }
}
int main() {
	ll N, M;
	cin >> N;
	string s;
	string t;
  	map<string, ll>mp;
	for (ll i = 0; i < N; i++) {
		cin >> s;
        mp[s]++;
	}
	cin >> M;
	for (ll i = 0; i < M; i++) {
		cin >> t;
      	mp[t]--;
    }
  	ll ans=0;
	for (auto p : mp) {
      	ll x=p.second;
		ans=max(ans,x);
	}
	cout << ans << endl;

}








Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define Rep(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll,vector<ll>,greater<ll>> SMALLPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
const int inf=1000000007;
const int mod=1000000007;
void chmin(auto &a,auto b){if(b<a)a=b;}
void chmax(auto &a,auto b){if(a<b)a=b;}
int wa(int a){
  int sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
int main(){
  int n,ans=inf;cin>>n;
  for(int i=1;i<=n/2;i++){
    int j=n-i;
    chmin(ans,wa(i)+wa(j));
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
H,W,M=map(int,input().split())
R=[list(map(int,input().split())) for i in range(M)]
import sys
listH=[]
for i in range(H):
  listH.append(0)
for i in range(M):
  listH[R[i][0]-1]+=1
maxH=0
listHmax=[]
jH=0
for i in range(H):
  if listH[i]>maxH:
    maxH=listH[i]
    listHmax=[]
    listHmax.append(i)
    jH=1
  elif listH[i]==maxH:
    listHmax.append(i)
    jH+=1

listW=[]
for i in range(W):
  listW.append(0)
for i in range(M):
  listW[R[i][1]-1]+=1
maxW=0
listWmax=[]
jW=0
for i in range(W):
  if listW[i]>maxW:
    maxW=listW[i]
    listWmax=[]
    listWmax.append(i)
    jW=1
  elif listW[i]==maxW:
    listWmax.append(i)
    jW+=1

T=0
for i in range(M):
  if (listH[R[i][0]-1]==maxH and listW[R[i][1]-1]==maxW):
    T+=1
  else:
    continue
if T==jH*jW:
  print (maxH+maxW-1)
else:
  print (maxH+maxW)



Measured memory_bytes: 92172
import sys
sys.setrecursionlimit(10000)

N=int(input())
count=[]
F=[list(map(int,input().split())) for i in range(N)]
P=[list(map(int,input().split())) for i in range(N)]
INF=10**9

def dfs(s):
    if len(s)==10:
        if "1" not in s:
            val=-INF
        if "1" in s:
            val=0
            c=[0 for i in range(N)]
            for i in range(N):
                #F1 F2
                count=0
                for j in range(10):
                    
                    if int(int(s[j])*F[i][j]):
                        c[i]+=1
                    #print("count",count)

            for i in range(N):
                val+=P[i][c[i]]
        return val
    else:
        return max(dfs(s+"0"),dfs(s+"1"))
print(dfs(""))

Measured memory_bytes: 3064
d,g=map(int,input().split())
p=[]
c=[]
for i in range(d):
    P,C=map(int,input().split())
    p.append(P)
    c.append(C)
ans=sum(p)
for i in range(2**d):
    z=i
    x=[]
    for j in range(d):
        x.append(z%2)
        z=z//2
    po=0
    m=0
    for j in range(d):
        if x[j]==1:
            po+=100*(j+1)*p[j]+c[j]
            m+=p[j]
    q=[[] for j in range(d)] #残りp、c
    s=0
    for j in range(d):
        if x[j]==0:
            q[s].append(100*(j+1))
            q[s].append(p[j])
            s+=1
    q=[q[j] for j in range(d) if q[j]!=[]]
    q=sorted(q,reverse=True)
    w=len(q)
    for j in range(w):
        q[j][1]-=1
    if po>=g:
        ans=min(ans,m)
    else:
        for j in range(w):
            if po+q[j][0]*q[j][1]>=g:
                m+=(g-po+q[j][0]-1)//q[j][0]
                ans=min(ans,m)
                break
            else:
                po+=q[j][0]*q[j][1]
                m+=q[j][1]
print(ans)


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

public class Main{

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] strArr = br.readLine().split("\\s");
			int a = Integer.parseInt(strArr[0]); // 底辺
			int b = Integer.parseInt(strArr[1]); // 斜辺
			int C = Integer.parseInt(strArr[2]); // 斜辺と底辺に挟まれた角度
			
			double h = b * Math.sin(Math.toRadians(C)); // 高さ
			double S = a * h / 2; // 三角形の面積
			// 三角形の周の長さ
			double L = a + b + Math.sqrt(a * a + b * b -2 * a * b * Math.cos(Math.toRadians(C)));
			
			System.out.println(S);
			System.out.println(L);
			System.out.println(h);
			
		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		} 
	}

}



Measured memory_bytes: 24744
#include <iostream>
#include <cmath>

#define EPS (1e-10)

using namespace std;

int n;
double hx, hy, dx, dy, cx[20], cy[20];
bool got[20];

double Dist( double xx, double yy )
{
	return sqrt(xx*xx + yy*yy);
}

bool search( int count, double t )
{
	if(count == n) return true;
	for(int i=0; i < n; ++i) {
		if(got[i]) continue;
		double dist = (Dist(hx-cx[i], hy-cy[i]) + t);
		if((Dist(dx-cx[i], dy-cy[i]) <= dist + EPS)) return false;
	}
	bool hit = false;
	double tx = hx, ty = hy;
	for(int i=0; i < n && !hit; ++i) {
		if(got[i]) continue;
		got[i] = true;
		hx = cx[i]; hy = cy[i];
		hit |= search(count + 1, (Dist(tx-cx[i], ty-cy[i]) + t));
		got[i] = false;
	}
	return hit;
}

int main( void )
{
	while(cin >> n >> hx >> hy >> dx >> dy) {
		if((int)(n + hx + hy + dx + dy) == 0) break;
		for(int i=0; i < n; ++i) {
			cin >> cx[i] >> cy[i];
			got[i] = false;
		}
		if(search(0, 0))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 948
#include<stdio.h>
#define INF 100000001
int n,m;
int i,j,k;
int t[100][100];
int r,a,b,c;
bool used[100];
int d[100];
int ans;

int min(int a,int b){
	if(a<=b)return a;
	else return b;
}

int solve(int a,int b){
	int v;
	while(1){
		v=-1;
		for(k=0;k<n;k++)if(!used[k]&&(v==-1||d[k]<d[v]))v=k;
		if(d[v]==INF||v==-1)break;
		used[v]=true;
		for(k=0;k<n;k++){
			if(t[v][k]!=INF)d[k]=min(d[k],d[v]+t[v][k]);
		}
	}
	return d[b];
}
int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)return 0;
		for(i=0;i<n;i++)for(j=0;j<n;j++)t[i][j]=INF;
		for(i=0;i<m;i++){
			scanf("%d",&r);
			if(r==1){
				scanf("%d %d %d",&a,&b,&c);
				t[a-1][b-1]=min(t[a-1][b-1],c);
				t[b-1][a-1]=min(t[b-1][a-1],c);
			}
			if(r==0){
				scanf("%d %d",&a,&b);
				for(j=0;j<n;j++){
					used[j]=false;
					d[j]=INF;
				}
				d[a-1]=0;
				ans=solve(a-1,b-1);
				if(ans==INF)printf("-1\n");
				else printf("%d\n",ans);
			}
		}
	}
}

Measured memory_bytes: 1080
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a)) 
#define ff fflush(stdout)
using namespace std;
pll st[55];
pll chk[55];
int main () { 
	ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%lld %lld", &a, &b);
	for (i = 1; i <= a; i++) {
		scanf("%lld %lld", &st[i].fi, &st[i].se);
	}
	for (i = 1; i <= b; i++) {
		scanf("%lld %lld", &chk[i].fi, &chk[i].se);
	}
	for (i = 1; i <= a; i++) {
		c = 1e18; f = -1;
		for (j = 1; j <= b; j++) {
			d = abs(st[i].fi - chk[j].fi) + abs(st[i].se - chk[j].se);
			if (d < c) c = d, f = j;
		}
		printf("%lld\n", f);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    int n;cin >> n;
    ll ans = 1;
    vector<ll> a(n);
    rep(i,n) {
        cin >> a[i];
        if(a[i]==0) {
            cout << 0 << endl;
            return 0;
        }
    }
    rep(i,n) {
        if(ans<=1000000000000000000/a[i]){
            ans*=a[i];
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 4052
S = list(input())[::-1]
T = list(input())[::-1]

for n in range(0, len(S) - len(T) + 1):
	for i, t in enumerate(T):
		if "?" == S[n + i]:
			continue
		if t != S[n + i]:
			break
	else:
		S[n:n + len(T)] = T
		print("".join(S[::-1]).replace("?", "a"))
		break
else:
	print("UNRESTORABLE")


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

typedef long long int64;

const int N = 2e5, POW10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int n, cnt[10][45][20], sum[10][45][20];

int main() {
	scanf("%d", &n);
	int64 ans = 0;
	for (int i = 1; i <= n; i++) {
		int64 x;
		scanf("%lld", &x);
		int dgt = 0;
		if (getchar() == '.') {
			char str[10];
			int y;
			scanf("%s", str);
			dgt = strlen(str);
			sscanf(str, "%d", &y);
			x = x * POW10[dgt] + y;
		}
		int cnt2 = 0, cnt5 = 0;
		for (; x % 2 == 0; x /= 2, cnt2++);
		for (; x % 5 == 0; x /= 5, cnt5++);
		cnt[dgt][cnt2][cnt5]++;
		ans -= std::min(cnt2, cnt5) >= dgt;
	}
	for (int i = 0; i <= 9; i++) {
		for (int j = 43; j >= 0; j--) {
			for (int k = 18; k >= 0; k--) {
				sum[i][j][k] = cnt[i][j][k] + sum[i][j + 1][k] + sum[i][j][k + 1] - sum[i][j + 1][k + 1];
			}
		}
	}
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int p = 0; p <= 43; p++) {
				for (int q = 0; q <= 18; q++) {
					ans += (int64)cnt[i][p][q] * sum[j][std::max(0, i + j - p)][std::max(0, i + j - q)];
				}
			}
		}
	}
	printf("%lld\n", ans / 2);
	return 0;
}

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

int h, w, a, b;

int main()
{
    cin >> h >> w >> a >> b;
    int mat[h][w];
    rep(i, h)
    {
        rep(j, w)
        {
            mat[i][j] = ((j < a) ^ (i < b));
        }
    }
    rep(i, h) { rep(j, w) cout << mat[i][j]; cout << endl; }
    
    return 0;
}

Measured memory_bytes: 5120
n = int(input())
llist = [int(l) for l in input().split()]

maxl = 0
for l in llist:
    maxl = max(l, maxl)

suml = 0
maxl_checker = maxl
for l in llist:
    if l == maxl_checker:
        maxl_checker = -1
        continue
    suml += l

print('Yes' if maxl < suml else 'No')



Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stdlib.h>
#define ll long long
#define MOD_P 1000000007
using namespace std;

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

int main()
{
	int n;
	int sum = 0;
	cin >> n;
	int g;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			g = gcd(i, j);
			for (int k = 1; k <= n; k++) {
				if (i == j) {
					sum += gcd(g, k);
				} else {
					sum += 2 * gcd(g, k);
				}
			}
		}
	}

	printf("%d", sum);

	return 0;
}

Measured memory_bytes: 3696
import numpy as np

N = int(input())
d = []
for i in range(N):
    d.append(list(map(int, input().split())))

flag = 0
tmp = [7, 7]
for l in d:
    if l[0] == l[1]:
        flag += 1
    else:
        flag = 0
    if flag==3:
        break

if flag==3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 27088
N=int(input())
A=[int(input()) for i in range(N)]
B=sorted(A)[::-1]
x=B[0] 
y=B[1]
if x==y:
  for i in range(N):
    print(x)
else:
  z=A.index(x)
  for i in range(z):
    print(x)
  print(y)
  for i in range(N-z-1):
    print(x)

Measured memory_bytes: 14136
import itertools

n = int(input())
num = []
for i in range(3, 10):
    for j in itertools.product("357", repeat = i):
        if "3" in j and "5" in j and "7" in j:
            num.append("".join(j))
count = 0
for i in num:
    if int(i) <= n:
        count += 1
print(count)

Measured memory_bytes: 4980
import heapq
import sys
input = sys.stdin.readline
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

def solve():
  n = int(input())
  query = []
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery = sorted(xquery)
  yquery = sorted(yquery)
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    heapq.heappush(query,(cost,place,place2))
    
    ty,tx,place = yquery[i]
    ty2,tx2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    heapq.heappush(query,(cost,place,place2))
  ct = 0
  uf = UnionFind(n)
  while len(query) > 0:
    cost,place1,place2 = heapq.heappop(query)
    if uf.same_check(place1,place2):
      continue
    else:
      uf.union(int(place1),int(place2))
      ct += cost
  print(ct)
      

solve()

Measured memory_bytes: 57952
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>

int main(){
  std::string s,t;
  std::cin >> s >> t;

  std::unordered_map<char, std::vector<int>> smap;
  for(int i = 0; i < s.size(); i++){
    const char& c = s[i];
    smap[c].push_back(i);
  }
  int n = 0, k = -1;
  bool fail = false;
  for(int i = 0; i < t.size(); i++){
    const char& c = t[i];
    auto it = std::upper_bound(smap[c].begin(), smap[c].end(), k);
    if(it == smap[c].end()){
      if(smap[c].size() == 0){
        fail = true;
        break;
      }
      n += 1;
      it = smap[c].begin();
    }
    k = *it;
  }

  if(fail){
    std::cout << -1 << std::endl;
  }else{
    std::cout << n*s.size()+k+1 << std::endl;
  }

  return 0;
}



Measured memory_bytes: 1216
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {

	Scanner sca = new Scanner(System.in);
	long h = sca.nextLong();
	long times = 1L;
	long ans = 0L;

	while(h != 0) {
		ans += times;
		h = h / 2;
		times *= 2;
	}
	System.out.println(ans);

	// 後始末
	sca.close();
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
typedef vector<vector<ll>> Graph ;

void Main()
{
    ll n, m;
    cin >> n >> m;

    vector<ll> A(m), B(m);
    rep(i, m) cin >> A[i] >> B[i];
    rep(i, m) {
        A[i]--;
        B[i]--;
    }
    
    Graph G(n);
    rep(i, m) {
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }

    queue<ll> que;
    que.push(0);

    vector<ll> d(n, -1);
    d[0] = 0;

    while (!que.empty()) {
        ll v = que.front();
        que.pop();
        for (ll next: G[v]) {
            if (d[next] < 0) {
                d[next] = v + 1;
                que.push(next);
            }
        }
    }

    if (*min_element(all(d)) < 0) {
        put("No");
    }

    put("Yes");
    repi (i, n) {
        put(d[i]);
    }
}
signed main(){ Main();return 0;}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> dp(N+1, -1000000000);
    dp[0] = 0;
    vector<int> A(M, 0);
    const int num[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    for (int i = 0; i < M; i++) cin >> A[i];
    sort(A.begin(), A.end(), greater<int>());
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            if (i-num[A[j]]>=0) dp[i] = max(dp[i], dp[i-num[A[j]]]+1);
        }
    }
    string ans;
    long long rem = N;
    for (int i = 0; i < dp[N]; i++) {
        for (int j = 0; j < M; j++) {
            if (rem - num[A[j]] >= 0 && dp[rem-num[A[j]]] == dp[rem] -  1) {
                ans += to_string(A[j]);
                rem -= num[A[j]];
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int arr[105];

int main(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int happy = 0;
	int rl = 0;
	int lr = 0;
	int l = 0;
	int r = 0;
	
	for(int i=1; s[i]; i++){
		if(s[i]==s[i-1]) happy++;
		else{
			if(s[i]=='R') lr++;
			else rl++;
		}
	}
	int two = min(lr,rl);
	lr-=two;
	rl-=two;
	int one = lr+rl;
	
	happy+=2*min(k,two);
	k-=two;
	if(k>0) happy+=min(k,one);
	cout<<happy;
}

Measured memory_bytes: 3716
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <iomanip>
using namespace std;

long long fact(long long a, long long b) {
  if (a == 0 || a == 1 || a == b) {
    return 1;
  }
  return a * fact(a - 1, b);
}

long long comb(long a, long b) {
  if (a < 2) {
    return 0;
  }
  return fact(a, a - b) / fact(b, 1);
}

int main(){
  long long N;
  cin >> N;
  long long tmp = 0, ret = 0, a[N + 1], b[N + 1], c[N + 1], d[N + 1];
  memset(&a, 0, sizeof(a));
  memset(&b, 0, sizeof(b));
  memset(&c, 0, sizeof(c));
  memset(&d, -1, sizeof(d));
  for (long long i = 0; i < N; ++i) {
    long long t;
    cin >> t;
    a[t]++;
    b[i] = t;
  }
  for (long long i = 0; i <= N; ++i) {
    tmp += comb(a[i], 2);
  }
  for (long long i = 0; i < N; ++i) {
    long long ii = b[i];
    if (d[ii] > -1) {
      cout << d[ii] << endl;
      continue;
    }
    ret = tmp;
    ret -= comb(a[ii], 2);
    ret += comb(a[ii] - 1, 2);
    cout << ret << endl;
    d[ii] = ret;
  }
  return 0; 
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100;
const int INF=1e9+7;
const ll LINF=1e18;

int main()
{
	int t1,t2,t3;
	cin>>t1>>t2>>t3;
	t1-=t2;
	t3-=t1;
	printf("%d\n",max(t3,0));

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	int mornint_start,morning_end,lunch_start,lunch_end,dinner_start,dinner_end;
};

int calc(int hour,int minute){
	return 60*hour+minute;
}

int main(){

	int N;
	scanf("%d",&N);

	Info info[N];

	vector<int> MORNING,LUNCH,DINNER;

	int m_st_h,m_st_m,m_ed_h,m_ed_m,l_st_h,l_st_m,l_ed_h,l_ed_m,d_st_h,d_st_m,d_ed_h,d_ed_m;
	for(int i = 0; i < N; i++){
		scanf("%d %d %d %d %d %d %d %d %d %d %d %d",&m_st_h,&m_st_m,&m_ed_h,&m_ed_m,&l_st_h,&l_st_m,&l_ed_h,&l_ed_m,&d_st_h,&d_st_m,&d_ed_h,&d_ed_m);

		info[i].mornint_start = calc(m_st_h,m_st_m);
		info[i].morning_end = calc(m_ed_h,m_ed_m);
		MORNING.push_back(info[i].mornint_start);
		MORNING.push_back(info[i].morning_end);

		info[i].lunch_start = calc(l_st_h,l_st_m);
		info[i].lunch_end = calc(l_ed_h,l_ed_m);
		LUNCH.push_back(info[i].lunch_start);
		LUNCH.push_back(info[i].lunch_end);

		info[i].dinner_start = calc(d_st_h,d_st_m);
		info[i].dinner_end = calc(d_ed_h,d_ed_m);
		DINNER.push_back(info[i].dinner_start);
		DINNER.push_back(info[i].dinner_end);
	}

	sort(MORNING.begin(),MORNING.end());
	sort(LUNCH.begin(),LUNCH.end());
	sort(DINNER.begin(),DINNER.end());

	int ans = 0,tmp;

	for(int a = 0; a < MORNING.size(); a++){
		for(int b = 0; b < LUNCH.size(); b++){
			for(int c = 0; c < DINNER.size(); c++){
				tmp = 0;
				for(int i = 0; i < N; i++){
					if(info[i].mornint_start <= MORNING[a] && info[i].morning_end >= MORNING[a] &&
					   info[i].lunch_start <= LUNCH[b] && info[i].lunch_end >= LUNCH[b] &&
					   info[i].dinner_start <= DINNER[c] && info[i].dinner_end >= DINNER[c]){
						tmp++;
					}
				}
				if(tmp > ans){
					ans = tmp;
				}
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 3268