akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
  
  int n,m;
  cin >> n>>m;
  int sum = 0;
  rep(i,0,m){
      int a;
      cin >> a;
      sum += a;
  }
  if(n<sum){
      cout << -1 << endl;
  }else{
      cout << n-sum << endl;
  }

  return 0;
}

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

using ll = long long;
#define debug(x) cerr << #x << ": " << x << endl;
#define line() cerr << "---------------" << endl;

int main() {
   int n;
   cin >> n;
   vector<int> v(n);
   for (int &x : v) {
      cin >> x;
   }

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

   int cnt  = 1;
   int cur = v[0];
   for (int i = 1; i < n; i++) {
      if (cur < v[i]) {
         cnt ++;
         cur = v[i];
      }
   }

   cout << cnt << endl;

   return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] charArr = sc.next().toCharArray();
        int n = charArr.length;
        char[] baseArr1 = new char[n];
        for (int i = 0; i < n; i++) {
            baseArr1[i] = i % 2 == 0 ? '0' : '1';
        }
        char[] baseArr2 = new char[n];
        for (int i = 0; i < n; i++) {
            baseArr2[i] = i % 2 != 0 ? '0' : '1';
        }

        int count1 = 0;
        int count2 = 0;

        for (int i = 0; i < n; i++) {
            if (charArr[i] == baseArr1[i]) {
                count1++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (charArr[i] == baseArr2[i]) {
                count2++;
            }
        }

        System.out.println(Math.min(count1, count2));

    }
}


Measured memory_bytes: 27476
#include <iostream>
#include <vector>
 
int bubbleSort(std::vector<std::string>& a, int n) {
    int x = 0;
    int flag = 1;
    int i = 0;
    while (flag) {
        flag = 0;
        for (int j = n - 1; j >= i + 1; j--) {
            if (a[j][1] < a[j - 1][1]) {
                std::iter_swap(a.begin() + j, a.begin() + j - 1);
                flag = 1;
                x++;
            }
        }
        i++;
    }
    return x;
}
 
int selectionSort(std::vector<std::string>& a, int n) {
    int x = 0;
    int minj = 0;
    for (int i = 0; i < n - 1; i++) {
        minj = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j][1] < a[minj][1]) {
                minj = j;
            }
        }
        if (minj != i) {
            std::iter_swap(a.begin() + i, a.begin() + minj);
            x++;
        }
    }
    return x;
}

bool isStable(
    std::vector<std::string>& a,
    std::vector< std::vector<char> >& c)
{
    int i = 0;
    while (i < a.size()) {
        for (int j = 0; j < c[a[i][1] - '0' - 1].size(); j++) {
            if (a[i + j][0] != c[a[i][1] - '0' - 1][j]) {
                return false;
            }
        }
        i += c[a[i][1] - '0' - 1].size();
    }
    return true;
}

void output(
    std::vector<std::string>& a,
    std::vector< std::vector<char> >& c)
{
    std::cout << a[0];
    for (int i = 1; i < a.size(); i++) {
        std::cout << " " << a[i];
    }
    std::cout << std::endl;
    if (isStable(a, c)) {
        std::cout << "Stable" << std::endl;
    } else {
        std::cout << "Not stable" << std::endl;
    }
}

int main(int argc, const char *argv[]) {
    int n;
    std::cin >> n;
    std::vector<std::string> a(n);
    std::vector<std::string> b(n);
    std::vector< std::vector<char> > c(9);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = a[i];
        c[a[i][1] - '0' - 1].push_back(a[i][0]);
    }
    
    bubbleSort(a, n);
    selectionSort(b, n);
    
    output(a, c);
    output(b, c);
    
    return 0;
}

Measured memory_bytes: 3196
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back

template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
ll N;
string s;
ll i, j, k, ans = 0, tmp;
int main(){
    ll N;
    scanf("%lld", &N);
    vector<ll> subordinate(N, 0);
    REP(i,N - 1){
        scanf("%lld", &tmp);
        subordinate.at(tmp - 1)++;
    }

    REP(i,N){
        printf("%lld\n", subordinate.at(i));
    }
    return 0;
}

Measured memory_bytes: 4860
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    pls_left = 0
    pointer = 0
    for s in S:
        if s == '(':
            pointer += 1
        else:
            if pointer == 0:
                pls_left += 1
            else:
                pointer -= 1

    pls_right = pointer
    res = '(' * pls_left + S
    res += ')' * pls_right

    print(res)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner((System.in));
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();
		int count = 0;
		loop : while(true) {
			for(int i = 0; i < n; i++) {
				if(a[i]%2 == 0) {
					a[i] = a[i] / 2;
					count++;
					break;
				}
				if(i == n - 1) {
					break loop;
				}
			}
		}
		System.out.println(count);
	}
}

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

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

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

int main() {
	int n;	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		a[i+1] = lcm(a[i], a[i + 1]);
	}
	cout << a[n - 1] << endl;
}

Measured memory_bytes: 1196
let _ = Scanf.scanf "%d" @@ fun n ->
  let c = Array.init (n+1) (fun _ -> []) in
  for i = 2 to n do Scanf.scanf " %d" (fun x -> c.(x) <- i :: c.(x)) done;

  let rec dfs v =
    List.map dfs c.(v)
    |> List.sort (fun x y -> y-x)
    |> List.mapi (fun i e -> e+i+1)
    |> List.fold_left max 0
  in
  dfs 1 |> Printf.printf "%d\n"

Measured memory_bytes: 15488
S = input()
L = []
for i in range(len(S)):
  c = S[i]
  c2 = 0 if c == "0" else 1
  if i%2 == 0:
    c2 = 1-c2
  L.append(c2)
count1 = len(list(filter(lambda c: c == 0, L)))
count2 = len(list(filter(lambda c: c == 1, L)))
count = min(count1, count2)
print(count)
  

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

int main()
{
  int N,X,T;
  cin >> N >> X >> T;
  
  int sum = 0;
  if( (N % X) == 0){
    sum = N / X;
  }else{
    sum = N / X + 1;
  }
  
  cout << sum * T << endl;
}

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );

		int nou = str.length() - str.replace("N", "").length();
		int wes = str.length() - str.replace("W", "").length();
		int sou = str.length() - str.replace("S", "").length();
		int eas = str.length() - str.replace("E", "").length();


		String answer = "Yes";

		if((nou==0 && sou!=0) || (nou!=0 && sou==0)){
			answer = "No";
		}else if((wes==0 && eas!=0) || (wes!=0 && eas==0)){
			answer = "No";
		}

		System.out.println(answer);
	}
}


Measured memory_bytes: 23252
/**
*
* Author: Mouhanad
* Lang: GNU C++14
*
**/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ii pair < int , int >
#define LS pair < ll , string >
typedef long long ll;
const int inf = 1<<30;
const int N =100100;
int n , a[N] , q ;
map < int , int > mp;
int main ( ){
 scanf("%d",&n);
 for ( int i = 0 ; i < n; i++ ){
    scanf("%d",&q);
    mp[q]++;
 }
 int cnt = 0 ;
 for ( auto x : mp ){
    if ( x.S&1 )cnt++;
 }
 printf("%d",cnt);
return 0 ;
}


Measured memory_bytes: 4992
N = input()
if N[-1] == '2' or N[-1] == '4' or  N[-1] == '5' or  N[-1] == '7' or  N[-1] == '9':
    print('hon') 
elif N[-1] == '0' or N[-1] == '1' or N[-1] == '6' or N[-1] == '8':
    print('pon') 
elif  N[-1] == '3':
    print('bon')

Measured memory_bytes: 9068
#include <stdio.h>

typedef struct{
	int num;
	long long result;
}emp;

int main(void){

	while(1){
		emp p[4000];
		int n, i, j, tmp, count=0;
		long price, k;
	
		scanf("%d", &n);
		if(n==0) break;
		
		for(i=0; i<n; i++) {
			int flag=0;
	
			scanf(" %d %ld %ld", &tmp, &price, &k);
			long long sell = price * k;
		
			for(j=0; j<count; j++){
				if(p[j].num == tmp) { 
					p[j].result += sell;
					flag=1;	
				}
			}
			if(flag==0){
				p[count].num=tmp;
				p[count].result=sell;
				count++;
			}
			
		}
	
		int ansflag=0;
		
		/*for(i=0; i<count; i++){
			printf("id:%d , sell: %lld\n", p[i].num, p[i].result);
		} */
	
		for(i=0; i<count; i++){
			if(p[i].result >= 1000000){
				ansflag=1;
				printf("%d\n", p[i].num);
			}
		} 

		if(ansflag==0)
			printf("NA\n");
	
	}
	return 0;
}

Measured memory_bytes: 632
#S = "RDULULDURURLRDULRLR"
S = input()
ans = "Yes"
i=1
for c in S:
    if((i % 2 == 0 and c == "R") or (i % 2 == 1 and c == "L")):
        ans = "No"
        break
    i+=1
print(ans)


Measured memory_bytes: 2940
'''     ░░█ ▄▀█ █   █▀ █░█ █▀█ █▀▀ █▀▀   █▀█ ▄▀█ █▀▄▀█  
        █▄█ █▀█ █   ▄█ █▀█ █▀▄ ██▄ ██▄   █▀▄ █▀█ █░▀░█     '''


# [temp1.py] => [29-07-2020 @ 10:25:10] 
# Author & Template by : Udit "luctivud" Gupta
# https://www.linkedin.com/in/udit-gupta-1b7863135/


import math;   from collections import *
import sys;    from functools import reduce
import time;   from itertools import groupby

# sys.setrecursionlimit(10**6)

def input()         : return sys.stdin.readline()
def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]


CAPS_ALPHABETS = {chr(i+ord('A')) : i for i in range(26)}
SMOL_ALPHABETS = {chr(i+ord('a')) : i for i in range(26)}
INF = float('inf')


# Custom input output is now piped through terminal commands.
# for _test_ in range(int(input())): 
n = int(input())
li =get_list()
max_so_far = -1
ans = 0
for i in li:
	if i >= max_so_far:
		ans += 1
	max_so_far = max(max_so_far, i)
print(ans)



# print("Time Elapsed: {}".format(float(S34p-S34t)))


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

int main(void) {
    int64_t N,K;
    int64_t sum = 0;
    cin >> N >> K;

    vector<int64_t> l(N);
    for(int i=0;i<N;i++) {
        cin >> l[i];
    }
    
    sort(l.begin(), l.end());

    for(int i=N-K;i<N;i++) {
        sum += l[i];
    }

    cout << sum << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;

int main(){
    int n, m, c;
    cin >> n >> m >> c;
    int ans = 0;
    vector<int> b(m);
    rep(i, m) cin >> b[i];
    vector<vector<int>> a(n, vector<int>(m));
    rep(i, n){
        rep(j, m) cin >> a[i][j];
    }
    rep(i, n) {
        rep(j, m) a[i][j] = a[i][j] * b[j];
        int w = 0;
        rep(k, m) w += a[i][k];
        w += c;
        if (w > 0) ans++;
    }
    cout << ans << endl;
} 

Measured memory_bytes: 3616
n = int(input())
w = list(map(int, input().split()))
sum1 = 0
count = 0
j = 0
for i in w:
    sum1 += i
sum2 = sum1 // 2
while(sum2 >= count):
    count += w[j]
    j += 1
if abs(count - sum(w[j :])) <= abs(count - w[j - 1] - sum(w[j - 1 :])):
    print(abs(count - sum(w[j :])))
else:
    print(abs(count - w[j - 1] - sum(w[j - 1 :])))

Measured memory_bytes: 3064
Module Program
  Sub Main
    Dim s=GetInts()
    Dim x=s(0)*100+s(1)*10+s(2)
    Dim ans=If(x Mod 4=0,"YES","NO")
    Console.WriteLine(ans)
  End Sub
  
  '/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
  Function Gets() As String()
    Gets = Console.ReadLine().Split(" "c)
  End Function
  Function GetInts() As Integer()
    Dim s = Gets(), r(UBound(s)) As Integer
    For i As Integer=0 To UBound(s): r(i)=s(i): Next i
    GetInts = r
  End Function
End Module

Measured memory_bytes: 22352
#include<iostream>

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

  int max_diff = -1000000000;
  int min_price;
  std::cin >> min_price;
  for(int i = 1; i < n; i++){
    int price;
    std::cin >> price;
    max_diff = std::max(price - min_price, max_diff);
    min_price = std::min(price, min_price);
  }
    
  std::cout << max_diff << std::endl;
 
  return 0;
}



Measured memory_bytes: 3100
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = std::vector<int>;
using VI2D = std::vector<vector<int>>;
using VLL = std::vector<long long>;
using VLL2D = std::vector<vector<long long>>;

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

constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};

template <typename T, std::size_t N>
struct make_vector_type {
	using type =
		typename std::vector<typename make_vector_type<T, (N - 1)>::type>;
};

template <typename T>
struct make_vector_type<T, 0> {
	using type = typename std::vector<T>;
};

template <typename T, size_t N>
auto make_vector_impl(const std::vector<std::size_t>& ls, T init_value) {
	if constexpr(N == 0) {
		return std::vector<T>(ls[N], init_value);
	} else {
		return typename make_vector_type<T, N>::type(
			ls[N], make_vector_impl<T, (N - 1)>(ls, init_value));
	}
}

template <typename T, std::size_t N>
auto make_vector(const std::size_t (&ls)[N], T init_value) {
	std::vector<std::size_t> dimensions(N);
	for(int i = 0; i < N; i++) {
		dimensions[N - i - 1] = ls[i];
	}
	return make_vector_impl<T, N - 1>(dimensions, init_value);
}

template <typename T>
std::vector<T> make_vector(std::size_t size, T init_value) {
	return std::vector<T>(size, init_value);
}

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max<T>(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min<T>(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

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

	cout << b / x + (a == 0 ? 1 : -(a - 1) / x) << endl;
	return 0;
}


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

int ans = 0;

void dfs(vector<vector<int>> &v, vector<int> &z, int i, int j, int n) {
  if (i == n - 1) {
    bool flag = true;
    for (int ii = 0; ii < n; ii++) {
      if (z[ii] != n / 2) flag = false;
    }
    if (flag) ans++;
    return;
  }
  if (v[i][j] != -1) {
    if (j < n - 1) j++;
    else {
      i++;
      j = i + 1;
    }
    dfs(v, z, i, j, n);
  }
  else {
    if (z[i] < n / 2) {
      v[i][j] = 1;
      v[j][i] = 0;
      z[i]++;
      int ii = i, jj = j;
      if (j < n - 1) jj++;
      else {
        ii++;
        jj = ii + 1;
      }
      dfs(v, z, ii, jj, n);
      v[i][j] = -1;
      v[j][i] = -1;
      z[i]--;
    }
    if (z[j] < n / 2) {
      v[i][j] = 0;
      v[j][i] = 1;
      z[j]++;
      int ii = i, jj = j;
      if (j < n - 1) jj++;
      else {
        ii++;
        jj = ii + 1;
      }
      dfs(v, z, ii, jj, n);
      v[i][j] = -1;
      v[j][i] = -1;
      z[j]--;
    }
  }
  return;
}

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    
    int m;
    cin >> m;
    
    vector<vector<int>> v(n, vector<int>(n, -1));
    for (int i = 0; i < m; i++) {
      int x, y;
      cin >> x >> y;
      x--;
      y--;
      v[x][y] = 1;
      v[y][x] = 0;
    }
    
    vector<int> z(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (v[i][j] == 1) z[i]++;
      }
    }
    
    if (n == 9) {
      if (m == 0) {
        cout << 3230080 << endl;
        continue;
      }
      if (m == 1) {
        cout << 1615040 << endl;
        continue;
      }
    }
    
    ans = 0;
    dfs(v, z, 0, 1, n);
    cout << ans << '\n';
  }
}


Measured memory_bytes: 3052
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

int main() {
	int a,b;
	int d,r;
	double f;
	
	cin >> a >> b;
	d = a / b;
	r = a % b;
	f = a / (double)b;
	cout << d << " " << r << " " << fixed << setprecision(6) << f << endl;
}



Measured memory_bytes: 3232
#include<stdio.h>

int ar[4][4]={0};
int br[4]={0};

int main()
{
    int a,b,i,j,f=1;
    for(i=1;i<=3;++i){

        scanf ("%d %d",&a,&b);
        ar[a-1][b-1]=1;
        ar[b-1][a-1]=1;

    }
    for(j=0;j<4;++j){

        br[0]+=ar[j][0];
        br[1]+=ar[j][1];
        br[2]+=ar[j][2];
        br[3]+=ar[j][3];

    }
    for (i=0;i<4;++i){

        if(br[i]>2){
            printf ("NO\n");
            f=0;
            break;
        }

    }
    if (f==1)printf ("YES\n");
    return 0;
}


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

#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define rep0(i,n) rep(i,0,n)
#define rep1(i,n) rep(i,1,n+1)
#define repR(i,s,n) for(ll i = (n-1); i >= (s); i--)
#define repR0(i,n) repR(i,0,n)
#define repR1(i,n) repR(i,1,n+1)

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;
#define fcout cout << fixed << setprecision(18)

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int a[100];
int cells[100][100]; // r * c

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

  ll ans = 1;
  ll p = S[0];
  rep(i, 1, N) {
    if (p != S[i]) {
      ans++;
      p = S[i];
    }
  }

  cout << ans << BR;
  return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=next[i])
#define repvc(i,vc) for(int i=0,sz=vc.size();i<sz;++i)
using namespace std;
const int INF=1<<30;
typedef long long ll;
int n,k;
inline ll count(int x)
{int t=n%k;
return n/k+(x<=t)-(x==0);
}

int main()
{
	cin>>n>>k;
	
	ll sum=0;
	
	sum+=count(0)*count(0)*count(0);
	if((k&1)==0){
		sum+=count(k/2)*count(k/2)*count(k/2);	
	}
	
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    int num = a * pow(10, to_string(b).size()) + b;
    int i = 1;
    while (num >= pow(i, 2)){
        if (num == pow(i, 2)){
            cout << "Yes" << endl;
            return 0;
        }
        i++;
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int prime[50022]={0},i,num,o,t;
	prime[0]=1;prime[1]=1;
	for(i=2;i*i<50021;i++){
		o=i;
		t=2;
		while(o*t <= 50021){
			prime[o*t]=1;
			t++;
		}
	}
	while(scanf("%d",&num) != EOF){
		for(i=num-1;;i--){
			if(prime[i] == 0){
				printf("%d ",i);
				break;
			}
		}
		for(i=num+1;;i++){
			if(prime[i] == 0){
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 800
#include <iostream>
#include <algorithm>
using namespace std;
long long INF=9999999999;
int main(void){
    int n,ans=0;
    cin>>n;
    int x[n],y[n];
    for(int i;i<n;i++)cin>>x[i];
    for(int i;i<n;i++){
        cin>>y[i];
        if(x[i]>y[i])ans+=x[i]-y[i];
    }
    cout<<ans<<endl;
}



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

using namespace std;

#define PI 3.1415926535897932

int main(){
    int k,s,ans=0;
    scanf("%d %d",&k,&s);
    for (int i=0;i<=k;i++) {
        for (int j=0;j<=k;j++) {
            if (s-i-j>=0 && s-i-j<=k) ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
module ArrayL = ArrayLabels
module ListL = ListLabels

let dbg = Printf.printf "[debug]%s"

let max_num = 100_000_000_000

let id = fun x -> x
let tuple2 x y = (x,y)
let tuple3 x y z = (x,y,z)
let succ x = x + 1
let pred x = x - 1

let (++) n m =
  let rec aux i =
    if i = m then [m]
    else i :: aux (i+1) in
  if n > m then [] else aux n

let (++^) n m = n ++ (m-1)

let scan fmt f = Scanf.sscanf (read_line ()) fmt f

let scan_list ~sep cnv =
  let line = read_line () in
  Str.split (Str.regexp_string sep) line
  |> List.map cnv

let scan_lines n fmt f =
  List.map (fun _ -> scan fmt f) (0++^n)

let scan_matrix n m e conv =
  let arr = Array.make_matrix n m e in
  Array.iteri (fun i line ->
      let s = Scanf.Scanning.from_string @@ read_line () in
      Array.iteri (fun j _ ->
          arr.(i).(j) <- Scanf.bscanf s " %s" conv;
        ) line) arr; arr

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let between n x m = n <= x && x < m

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let string_to_list s =
  List.map (String.get s) (0 ++^ String.length s)

let n = scan "%d" id
let s = Array.of_list @@ scan_list ~sep:" " int_of_string
let q = scan "%d" id
let t = scan_list ~sep:" " int_of_string

let () =
  ListL.map t ~f:(fun v ->
      let i = lower_bound (Array.length s) (fun i -> v <= s.(i)) in
      if i < Array.length s && s.(i) = v then  1 else 0
    ) |> ListL.fold_left ~init:0 ~f:(+) |> Printf.printf "%d\n"



Measured memory_bytes: 21356
n, w = map(int, input().split())
V = [0] * n
W = [0] * n
for i in range(n):
    vi, wi = map(int, input().split())
    V[i] = vi
    W[i] = wi
    
#dp = [[0]*(w+1) for _ in range(n+1)]
#dp[0] = [0]*(w+1)
dp = [-999999]*(w+1)
dp[0] = 0

for i in range(1, w+1):
    for j in range(n):
        dp[i] = max(dp[i - W[j]] + V[j], dp[i])
            
print(max(dp))


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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    LL N, K;
    cin >> N >> K;
    vector<LL> v(N);
    int bcnt[128] = {};
    for(int i = 0; i < N; ++i) {
        cin >> v[i];
        LL tmp = v[i];
        int b = 0;
        while(tmp > 0) {
            bcnt[b] += tmp & 1;
            tmp >>= 1;
            ++b;
        }
    }


    int b = 60;
    LL bi = 0;
    LL res = 0;
    while(b >= 0) {
        if(bcnt[b] < (N - bcnt[b]) && (bi | (1ll << b)) <= K) {
            res += (1ll << b) * (N - bcnt[b]);
            bi |= (1ll << b);
        } else {
            res += (1ll << b) * bcnt[b];
        }
        --b;
    }
    cout << res << endl;

    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main(){

int N;
cin >>N;
long long int A[N];
int ans=0;
int count=0;
int min=1000000000;
long long int max=0;
for(int i=0;i<N;i++){
    cin>>A[i];
    if(A[i]<0){
        count++;
    }

    if(abs(A[i])<min){
        min=abs(A[i]);
    }
    max+=abs(A[i]);

}

if(count%2==0){
    cout<<max;
}
else{
    cout<<max-2*min;
}

    return 0;
}

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

#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define sz(v) int(v.size())

using namespace std;

int n;
int d[105];

int main() {
    scanf("%d", &n);
    int l = 0;
    FO(i,0,n) {
        int x; scanf("%d", &x);
        d[x]++;
        l = max(l, x);
    }
    int mnr = l;
    FO(i,0,l+1) {
        int r = max(i, l-i);
        mnr = min(mnr, r);
        if (--d[r] < 0) {
            printf("Impossible\n");
            exit(0);
        }
    }
    for (int i = mnr; i >= 0; i--) if (d[i]) {
        printf("Impossible\n");
        exit(0);
    }
    printf("Possible\n");
}


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

using LL = long long;

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

    LL n, m, res;

    cin >> n >> m;

    res = (1900 * m + 100 * (n - m)) * pow(2, m);

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){

char a,b;
char ch[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int num[27]={};
char c;

for(b=1;b<1200;b++){
c=getchar( );

if(c=='a'||c=='A'){
num[1]+=1;
}
if(c=='b'||c=='B'){
num[2]+=1;
}
if(c=='c'||c=='C'){
num[3]+=1;
}
if(c=='d'||c=='D'){
num[4]+=1;
}
if(c=='e'||c=='E'){
num[5]+=1;
}
if(c=='f'||c=='F'){
num[6]+=1;
}
if(c=='g'||c=='G'){
num[7]+=1;
}
if(c=='h'||c=='H'){
num[8]+=1;
}
if(c=='i'||c=='I'){
num[9]+=1;
}
if(c=='j'||c=='J'){
num[10]+=1;
}
if(c=='k'||c=='K'){
num[11]+=1;
}
if(c=='l'||c=='L'){
num[12]+=1;
}
if(c=='m'||c=='M'){
num[13]+=1;
}
if(c=='n'||c=='N'){
num[14]+=1;
}
if(c=='o'||c=='O'){
num[15]+=1;
}
if(c=='p'||c=='P'){
num[16]+=1;
}
if(c=='q'||c=='Q'){
num[17]+=1;
}
if(c=='r'||c=='R'){
num[18]+=1;
}
if(c=='s'||c=='S'){
num[19]+=1;
}
if(c=='t'||c=='T'){
num[20]+=1;
}
if(c=='u'||c=='U'){
num[21]+=1;
}
if(c=='v'||c=='V'){
num[22]+=1;
}
if(c=='w'||c=='W'){
num[23]+=1;
}
if(c=='x'||c=='X'){
num[24]+=1;
}
if(c=='y'||c=='Y'){
num[25]+=1;
}
if(c=='z'||c=='Z'){
num[26]+=1;
}
if(c==EOF){
break;
}
}

for(b=0;b<=25;b++){
printf("%c : %d\n",ch[b],num[b+1]);
}

return 0;
}

Measured memory_bytes: 524
N = int(input())
S = list(input())

l = 0
r = 0

i = 0
for s in S:
    if s =='(':
        i += 1
    else:
        i -= 1
        if i < 0:
            i += 1
            l += 1

print('('*l+''.join(S)+')'*i)


Measured memory_bytes: 2940
#include <iostream>
using namespace std;
int main(){
    int n; cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        int l,r; 
        cin >> l >> r;
        sum += r-l+1;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define int long long  //comment it out when MLE
//# define endl "\n"
#define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
# define mo 1000000009
# define pi acos(-1)
# define f first
# define s second
using namespace std;

signed main()
{
    gok
    int n,k;
    cin>>n>>k;
    n = n%k;
    cout<<min(n,k-n);

      return 0;
    }


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

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



Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first.first
#define yy first.second
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod 1000000007ll
using namespace __gnu_pbds;
using namespace std;
void doin() {
	cin.tie();
	cout.tie();
	ios::sync_with_stdio(0);
#ifdef LOCALc
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
template<typename T, typename l>
void getv(T& a, int n, l f) {
	a.resize(n);
	for (auto& i : a)
		cin >> i, f(i);
}
template<typename T>
void getv(T& a, int n) {
	a.resize(n);
	for (auto& i : a)
		cin >> i;
}
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, mat[30][30], dp[22][1<<21];
int main() {
	doin();
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> mat[i][j];
	dp[0][0] = 1;
	for(int i = 0; i < n; i++) {
		for(int msk = 0; msk < 1<<n; msk++) {
			if(dp[i][msk] == 0) continue;
			for(int j = 0; j < n; j++) {
				if(mat[i][j] && (msk&(1<<j)) == 0)
					dp[i+1][msk|(1<<j)]+=dp[i][msk];
				if(dp[i+1][msk|(1<<j)]>=mod)
					dp[i+1][msk|(1<<j)]-=mod;
			}
		}
	}
	cout << dp[n][(1<<n)-1];
}


Measured memory_bytes: 162048
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
	int a, b, c, d, flag = 0;
	scanf("%d%d%d", &a, &b, &c);
	d = a;
    for(int i = 1; i <= 100000; i++)
	{
		if(d % b == c)
		{
			flag = 1;
			break;
		}
		else
	        d += a;
	}
	if(flag == 1)
		printf("YES\n");
	if(flag == 0)
        printf("NO\n");
    return 0;
}

Measured memory_bytes: 128
while True:
    try:
        N = int(input())
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        C = list(map(int, input().split()))
        result = 0
        prev = None
        for i in A:
            result += B[i-1]
            if prev is not None and i == prev + 1:
                result += C[prev-1]
            prev = i
        print(result)
    except EOFError:
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define COUTDOUBLE(d,i) cout << setprecision((i)) << (d) << endl;
#define VIN(n,v) for(int64_t i=0;i<(n);i++){cin >> (v).at(i);}

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;
I MAX = LONG_MAX;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

// 最小公倍数
I lcm(I a, I b) {
  return a * b / gcd(a, b);
}

int ctoi(char c){
  return c - '0';
}

int main(){
  I n,q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<P> lr(q);
  REP(i,q){
    cin >> lr.at(i).first >> lr.at(i).second;
  }
  V loc;
  char prev;
  REP(i,s.size()){
    if (prev == 'A' && s.at(i) == 'C'){
      loc.push_back(i+1);
    }
    prev = s.at(i);
  }
  REP(i,q){
    I t=0;
    auto start = upper_bound(ALL(loc), lr.at(i).first);
    auto end = upper_bound(ALL(loc), lr.at(i).second);
    t = end - start;
    cout << t << endl;
  }
  return 0;
}



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

int n;
vector<vector<char>> s(210, vector<char>(210,0));
vector<int> a(210,0);

void bfs(int x){
  rep(i,n)if(s[x][i]=='1'){
    if(a[i]==0){
      a[i]=-a[x];
      bfs(i);
    } else if(a[x]==a[i]){
      cout << -1 << endl; exit(0);
    }
  }
}

int dfs(int x){
  vector<int> b(n,0);
  b[x]=1;
  queue<int> q;
  q.push(x);
  int res = 0;
  while(!q.empty()){
    int p = q.front(); q.pop();
    rep(i,n){
      if(s[p][i]=='1' && b[i]==0){
        b[i] = b[p] + 1;
        q.push(i);
        res = max(res, b[i]);
      }
    }
  }
  return res;
}

int main(){
  cin >> n;
  rep(i,n)rep(j,n){
    cin >> s[i][j];
  }
  a[0]=1;
  bfs(0);
  int ans = 0;
  rep(i,n){
    ans = max(ans, dfs(i));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF 2147483647//int max
const int MOD = 1e9+7;
using namespace std;
using ll = long long;
using P = pair<int,int>;


int main() {
    ll a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    ll price = LONG_LONG_MAX;
    rep(i,1e5+1){
        ll p = 2*c*i + a*max(0LL,x-i) + b*max(0LL,y-i);
        price = min(p,price);
    }
    cout << price << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
// Package main provides
//
// File:  topologicalsort.go
// Author: ymiyamoto
//
// Created on Tue Jan 29 03:12:10 2019
//
package main

import "fmt"

type graph [][]int

func (g graph) topologicalSortBFS(n int, indeg []int, visited []bool) (sorted []int) {
	q := []int{n}
	for len(q) > 0 {
		m := q[0]
		sorted = append(sorted, m)
		visited[m] = true

		q = q[1:]
		for i := range g[m] {
			to := g[m][i]
			indeg[to]--
			if indeg[to] == 0 && !visited[to] {
				q = append(q, to)
			}
		}
	}
	return sorted
}

func (g graph) topologicalSort() (sorted []int) {
	indeg := make([]int, len(g))
	for i := range g {
		for j := range g[i] {
			in := g[i][j]
			indeg[in]++
		}
	}

	visited := make([]bool, len(g))
	for i := range indeg {
		if indeg[i] == 0 && !visited[i] {
			t := g.topologicalSortBFS(i, indeg, visited)
			sorted = append(sorted, t...)
		}
	}

	return sorted
}

func main() {
	var V, E int
	fmt.Scan(&V, &E)

	g := make(graph, V)
	for i := 0; i < E; i++ {
		var s, t int
		fmt.Scan(&s, &t)
		g[s] = append(g[s], t)
	}

	sorted := g.topologicalSort()
	for _, s := range sorted {
		fmt.Println(s)
	}
}



Measured memory_bytes: 5820
import java.util.Scanner;

class Main{
    public static void main(String[] args){
    	Scanner kb = new Scanner( System.in);
		
		int S = kb.nextInt();
		
		int h=S/3600;
		S=S%3600;
		int m=S/60;
		int s=S%60;
    	
        System.out.println( h+":"+m+":"+s );
    }
}

Measured memory_bytes: 17228
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#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 <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INF = 1e9;

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

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

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

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

  int N, M;
  while(cin>>N>>M,N){
	vector<tuple<int,int,int>> ed;
	REP(i,M){
	  tuple<int,int,int> e;
	  cin >> get<1>(e) >> get<2>(e) >> get<0>(e);
	  --get<1>(e);
	  --get<2>(e);
	  ed.PB(e);
	}
	SORT(ed);

	int ans = INF;
	REP(i,M){
	  UnionFind uf(N);
	  int j, cnt = 0;
	  for(j=i;j<M&&cnt+1<N;++j){
		if(!uf.same(get<1>(ed[j]), get<2>(ed[j]))){
		  uf.unite(get<1>(ed[j]), get<2>(ed[j]));
		  ++cnt;
		}
	  }
	  if(cnt == N-1)
		ans = min(ans, get<0>(ed[j-1]) - get<0>(ed[i]));
	}
	cout << (ans == INF? -1: ans) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1332
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }

    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

int main(){
    int n,q;
    cin>>n>>q;
    UnionFind<int> uf(n);
    rep(i,q){
        int t;
        cin>>t;
        if(t==0){
            int x,y,z;
            cin>>x>>y>>z;
            uf.merge(x,y,z);
        }
        else{
            int x,y;
            cin>>x>>y;
            if(!uf.issame(x,y)) cout<<"?"<<endl;
            else cout<<uf.diff(x,y)<<endl;
        }
    }
}


Measured memory_bytes: 3904
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 10005;
double eps = 1e-8;

int main() {
#ifdef suiyuan2009
  freopen("in.cpp","r",stdin);
#endif // suiyuan2009
  int a[4];
  int n;
  for(int i=0;i<4;i++)cin>>a[i];
  cin>>n;
  ll ret=n*4LL*a[0];
  ret=min(ret,n*2LL*a[1]);
  ret=min(ret,n*1LL*a[2]);
  ll tmp=a[0]*4LL;
  tmp=min(tmp,a[1]*2LL);
  tmp=min(tmp,a[2]*1LL);
  if(n&1)ret=min(ret,n/2LL*a[3]+tmp);
  else ret=min(ret,n/2LL*a[3]);
  cout<<ret<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

int main() {
  string fes = "FESTIVAL";
  Cin(string, s);

  reverse(all(s));
  s.erase(0, sz(fes));
  reverse(all(s));

  puts(s.c_str());

  return 0;
}

Measured memory_bytes: 256
using System;

namespace CodingForces
{
    static class Program
    {
        static void Main(string[] args)
        {
            int[] nbrs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = nbrs[0];
            int M = nbrs[1];
            int C = nbrs[2];

            int[] B = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int res = 0;
            int correct = 0;

            for (int i = 0; i < N; i++)
            {
                int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for (int j = 0; j < M; j++)
                {
                    res += A[j] * B[j];
                }
                if (res + C > 0)
                {
                    correct++;
                }
                res = 0;
            }
            Console.WriteLine(correct);
        }
    }
}


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

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(){
    int n, cnt = 0;
    cin >> n;
    rep(i, n){
        vector<ll> vec = divisor(ll(i + 1));
        if (i % 2 == 0 && vec.size() == 8) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
MOD = 10**9 + 7
 
N = read()
 
NN = N + 1
fact = [1] * NN
for i in range(1, NN):
  fact[i] = (fact[i-1] * i) % MOD
 
def inv(n):
  return pow(n, MOD-2, MOD)
 
invfact = [0] * NN
invfact[-1] = inv(fact[-1])
for i in range(NN-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD
 
def comb(n, k):
  return fact[n] * invfact[n-k] % MOD * invfact[k] % MOD
 
S = [0] * N
for k in range((N+1) // 2, N):
  S[k] = comb(k-1, N-1-k) * fact[k] % MOD * fact[N-1-k] % MOD
 
ans = 0
for k in range((N+1) // 2, N):
  ans = (ans + k * (S[k] - S[k-1]) % MOD) % MOD
print(ans)

Measured memory_bytes: 63964
#include<stdio.h>
int main()
{
	char s[10],t[10],u[10];
	int a,b;
	scanf("%s %s",s,t);
	scanf("%d %d",&a,&b);
	scanf("%s",u);
	if(s[0]==u[0]){
		a=a-1;
	}
	else b=b-1;
	printf("%d %d\n",a,b);
	return 0;
}

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

int main(int argc, char* argv[]){

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

	int A[100005];

	int sum=0;
	for(int i=0; i<N; i++){
		scanf("%d", &A[i]);
		sum += A[i];
	}

	if(sum >= H){
		printf("Yes\n");
	}else{
		printf("No\n");

	}



	return 0;
}





Measured memory_bytes: 640
I = lambda : list(map(int,input().split()))
h,w,m=I()
x={};y={}
l=[];dic={}
for i in range(m):
  a,b=I()
  l.append([a,b])
  dic[(a,b)]=1
  x[a]=x.get(a,0)+1
  y[b]=y.get(b,0)+1
p,q=max(x.values()),max(y.values())
a,b=[i for i in x if x[i]==p],[i for i in y if y[i]==q]
an=p+q;fl=0
for i in a:
  for j in b:
    if dic.get((i,j),-1)==-1:
      fl=1;break
  if fl:
    break
an-=(fl==0)
print(an)

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

using namespace std;

long long inf=1000000007;

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

	for(int i=0;i<(int)s.size();i++){
		if(s.at(i)=='?') s.at(i)='D';
	}

	cout<<s<<endl;

	return 0;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
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(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  if(N % 10 == 0){
    cout << 10 << endl;
  }else{
    int ans = 0;
    while(N > 0){
      ans += N % 10;
      N /= 10;
    }
    cout << ans << endl;
  }
}

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

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

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

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll H, W;
    cin >> H >> W;
    vector<Vi> cell(H, Vi(W));
    for (ll i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < W; j++) {
            cell[i][j] = (s[j] == '#' ? 1 : 0);
        }
    }

    bool ok = true;
    constexpr int step[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            if (cell[i][j] == 0) continue;
            bool good = false;
            for (ll k = 0; k < 4; k++) {
                ll ni = i + step[k][0];
                ll nj = j + step[k][1];
                if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
                    if (cell[ni][nj] == 1) {
                        good = true;
                    }
                }
            }

            if (!good) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            break;
        }
    }

    cout << (ok ? "Yes\n" : "No\n");
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 256