akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

int min(int a, int b)
{
    return a < b ? a : b;
}

int solution(int *h, int n)
{
  int *memo = (int *)malloc(sizeof(int)*n);
  memo[0] = 0;
  memo[1] = abs(h[1] - h[0]);
  int i;
  for (i = 2; i < n; i++)
  {
    memo[i] = min(abs(h[i] - h[i-1]) + memo[i-1], abs(h[i] - h[i-2]) + memo[i-2]);
  }
  return memo[n-1];
}

int main(int argc, char **argv)
{
  int n;
  scanf("%d", &n);
  
  int *h = (int *)malloc(sizeof(int)*n);
  int i;
  for (i = 0; i < n; i++)
  {
    scanf("%d", h+i);
  }
  int best = solution(h, n);
  printf("%d\n", best);
}

Measured memory_bytes: 896
#!/usr/bin/env python3
N = int(input())
A = [None] * N
B = [None] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = [[A[i] + B[i], i] for i in range(N)]
C.sort(reverse=True)
ans = 0
for i in range(N):
    if i % 2 == 0:
        ans += A[C[i][1]]
    else:
        ans -= B[C[i][1]]
print(ans)


Measured memory_bytes: 28076
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par; 
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i; 
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d,e, H, W;
long long A[2][200005] = {};
long long B[200005] = {};
long long C[200005] = {};
bool f, ff;
string S;
set <long long>sll;
pl bufpl;
vector <long long>vl[100005];
vector <pl>vpl[20];
vector <string> vs[20];
set<ll> llset;

struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;
bool fr[100004] = {};

int main() {


	cin >> N >> M;
	a = 1;
	
	for (int i = 1; i <= N; i++) {
		B[i]=1;
		fr[i] = false;
	}
	fr[1] = true;

	for (int i = 0; i < M; i++) {
		cin >> b >> c;

		B[b]--;
		B[c]++;
		if (fr[b]) {
			if (B[b] == 0) {
				fr[b] = false;
			}

			fr[c] = true;
		}


	}

	a = 0;


	for (int i = 1; i <= N; i++) {
		if (fr[i]) {
			a++;
		}
	}

	cout << a << endl;
	
	return 0;

}


Measured memory_bytes: 6528
K, N = map(int, input().split())
A = [int(s) for s in input().split()]

ans = 10**9
for i in range(N):
	right = A[i-1] - A[i]
	right += K if right < 0 else 0
	left = A[i] - A[0] if i == N - 1 else A[i] + K - A[i+1]
	ans = min(ans, min(right, left))

print(ans)

Measured memory_bytes: 26444
def solve(N, Ss):
    d = {}
    _max = 0
    for s in Ss:
        d.setdefault(s, 0)
        d[s] += 1
        _max = max(_max, d[s])

    d = [x[0] for x in d.items() if x[1] == _max]
    d.sort()
    for s in d:
        print(s)


if __name__ == '__main__':
    N = int(input())
    Ss = [input() for _ in range(N)]
    solve(N, Ss)


Measured memory_bytes: 35220
#!/usr/bin/env python3

def main():
    N, W = map(int, input().split())
    V = N * 10**3
    INF = 10**12
    dp = [INF] * (V+1)# dp[i]: 価値の総和をiにするための重さの最小値
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(V,-1,-1):
            if j-v >= 0:
                dp[j] = min(dp[j],dp[j-v]+w)
    # print(dp)
    ans = -1
    for i in range(V+1):
        if dp[i] <= W:
            ans = i
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 68588
local a = {}
a[1] = io.read("*n")

local function f(n)
    local x
    if n%2==0 then
        return n/2
    else
        return 3*n+1
    end
end

for i = 2, 1000000 do
   a[i] = f(a[i-1])
end

for i = 1, 1000000 do
    if a[i]==1 or a[i]==2 or a[i]==4 then
        print(i+3)
        break
    end
end

Measured memory_bytes: 17392
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;
typedef long long LL;

int ans;
bool check(char num[],int len)
{
    if(len == 1) return 1;
    for(int i=len-1; i>0; i--)
    {
        if(num[i] != '9')
            return 0;
    }
    return 1;
}

int main()
{
    char num[20];
    while(scanf("%s",num) != EOF)
    {
        int len = strlen(num);
        if(check(num,len))
            ans = 9 * (len-1) + num[0]-'0';
        else ans = 9 * (len-1) + num[0]-'0'-1;

        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
/*---------------------------------------------------------------------*/
/*                   -------------------------------------             */
/*                   -----------MEHEDI HASAN--------------             */
/*                   -----CSE,JAHANGIRNAGAR UNIVERSITY----             */
/*                   -------------------------------------             */
/*---------------------------------------------------------------------*/
#include<bits/stdc++.h>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
/*---------------------------------------------------------------------*/
#define FAST        ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define cc(x)       cout<<#x<<"="<<x<<" ";
#define ccc(x)      cout<<#x<<"="<<"("<<x.ff<<" "<<x.ss<<") ";
#define CC(x)       cout<<"["<<#x<<"] = ";for(auto xx: x) cout<<xx<<" ";
#define CCC(x)      cout<<"["<<#x<<"] = ";for(auto xx: x) cout<<"("<<xx.ff<<" "<<xx.ss<<") ";
#define MARK(x)     cout<<x<<" ";
#define ee          cout<<"\n";
#define OK          cout<<"Ok till line "<<__LINE__<<"\n";
/*---------------------------------------------------------------------*/
#define ff          first
#define ss          second
#define ll          long long
#define ull         unsigned long long
#define pii         pair<int,int>
#define mp          make_pair
#define ps          push
#define psb         push_back
#define psf         push_front
#define pp          pop
#define ppb         pop_back
#define ppf         pop_front
#define all(x)      x.begin(),x.end()
#define TESTS       int t;cin>>t;for(int tcase=1;tcase<=t;tcase++)
#define ordered_set tree< int, null_type, less_equal< int >, rb_tree_tag, tree_order_statistics_node_update>
/*---------------------------------------------------------------------*/
#define MAX (ll)(1e6)
#define MOD (ll)(1e9+7)

int main()
{
    FAST
    ll n;cin>>n;
    ll gcd=0;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            for(ll k=1;k<=n;k++)
            {
                gcd+=(ll)__gcd(i,__gcd(j,k));
            }
        }
    }
    cout<<gcd<<endl;






    return 0;

}
/*--------------------------------------------------------------------*/
/*
>Check Corner Cases (n==1 or T==1)
>Overflow issues?
>LB / UB !!not found!! check?
*/
/*--------------------------------------------------------------------*/
/* ---INPUT---
--------(1)------

-------(2)-------


-------(3)-------


-------(4)-------



--------------
*/
/*--------------------------------------------------------------------*/



//https://codeforces.com/contest/466/problem/C try again


Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#define _USE_MATH_DEFINES
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<map>
#include<unordered_map>
#include<set>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::set;
using std::vector;
using std::pair;
using std::make_pair;
using std::priority_queue;

typedef unsigned long long ull;
typedef long long ll;

#define Prime1 1000000007
#define Prime2 9999973

#define INF 0x7fffffffffffffff

ull i, j, k, l, m, n;
ull H, W, Q;
ull a, b, c, x, y;
ull K, L, N, M;
string str;

ull GCD;

ull gcd(ull x, ull y)
{
	if (y==0)return x;
	return gcd(y, x%y);
}



ull count(ull x, ull c, ull d)
{
	return x + x / (c*d / GCD) - x / (c) - x / (d);
}

int main()
{
	ull A, B,C,D;
	cin >> A >> B >> C >> D;

	GCD = gcd(C, D);

	cout << count(B, C, D) - count(A - 1, C, D);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

count = b[a[0]-1]
for i in range(1,n):
  count += b[a[i]-1]    
  if a[i]-a[i-1]==1:
    count += c[a[i-1]-1]
    
print(count)

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k, s;
	cin >> n >> k >> s;
	for(int i = 0; i < k; i++){
		cout << s << " ";
	}
	for(int i = k; i < n; i++){
		if(s == 1000000000) cout << 1 << " ";
		else cout << 1000000000 << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1280
h, w = gets.chomp.split.map(&:to_i)
a = []
h.times do
  a << gets.chomp.split.map(&:to_i)
end

cnt=0
ans=[]

h.times do |i|
  w.times do |j|
    next if i == h - 1 && j == w - 1
    j = w - j - 1 if i.odd?

    if a[i][j].odd?
      cnt += 1

      a[i][j] -= 1



      if i.odd?
        if j == 0
          a[i+1][j] += 1
          ans << [i+1, j+1, i+2, j+1]
        else
          a[i][j - 1] += 1
          ans << [i+1, j+1, i+1, j]
        end
      else
        if j == w-1
          a[i+1][j] += 1
          ans << [i+1, j+1, i+2, j+1]
        else
          a[i][j + 1] += 1
          ans << [i+1, j+1, i+1, j+2]
        end
      end


    end
  end
end

p cnt

ans.each do |row|
  puts row.join(' ')
end

Measured memory_bytes: 26492
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
using pq = priority_queue<int>;
using q = queue<int>;

int main() {
    int a,b,c,k;
    cin >> a >> b >> c >> k;
 int xa = min(a,k);
 k -= xa;
 int xb = min(b,k);
 k -= xb;
 int xc = k;
int ans = xa - xc;

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


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

using namespace std;

#define si(a) scanf("%d",&a)
#define f first
#define s second
#define mp(a,b) make_pair(a,b)
#define MAX 100005

vector<pair<int,int> > graph[MAX];
int val_node[MAX][16],ans[MAX],allval[100005];

int solve(int now,int from,int ed)
{
    if(graph[now].size()==1 && from!=-1){
        if(ed){
            val_node[now][ed]=1;
            ans[now]=1;
        }
        return ans[now];
    }
    for(int i=0;i<graph[now].size();i++){
        int to=graph[now][i].f,w=graph[now][i].s;
        if(to==from)continue;
        solve(to,now,w);
        ans[now]+=ans[to];
        for(int j=0;j<16;j++){
            if(val_node[to][j]){
                val_node[now][j]^=1;
                if(!val_node[now][j])ans[now]--;
            }
        }
    }
    int xorval=0;
    for(int i=0;i<16;i++)if(val_node[now][i])xorval^=i;
    xorval^=ed;
    if(from!=-1 && xorval){
        val_node[now][xorval]^=1;
        if(val_node[now][xorval])ans[now]++;
    }
    return ans[now];
}

void precal(void)
{
    int tot=1<<16;
    for(int msk=0;msk<tot;msk++){
        for(int i=0;i<16;i++)if(msk&(1<<i))allval[msk]^=i;
    }
}

int dp[100005];

int calc(int msk)
{
    int &ret=dp[msk];
    if(ret!=-1)return ret;
    ret=0;
    for(int submask=msk;submask>0;submask=(submask-1)&msk){
        int xorval=allval[submask];
        if(!xorval)ret=max(ret,1+calc(msk^submask));
    }
    return ret;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int n,i;
    si(n);
    for(i=1;i<n;i++){
        int u,v,w;
        si(u);si(v);si(w);
        graph[u].push_back(mp(v,w));
        graph[v].push_back(mp(u,w));
    }
    precal();
    int ans=solve(0,-1,0);
    int msk=0;
    for(i=0;i<16;i++)if(val_node[0][i])msk^=(1<<i);
    memset(dp,-1,sizeof(dp));
    cout<<ans-calc(msk)<<endl;
    return 0;
}


Measured memory_bytes: 21888
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

A, B, N = map(int, read().split())

ans = 0
x = min(B - 1, N)
ans = (A * x // B) - A * (x // B)

print(ans)


Measured memory_bytes: 9112
from copy import copy

N = int(input())
A = list(map(int, input().split()))
S,r,m = [0]*N,0,1000000007

for i in range(len(A)-1):
    S[N-2-i] = S[N-1-i] + A[N-1-i] 

for a,s in zip(A,S):
    r += (a*s)%m
    r %= m

print(r)

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

import sys
import os
import math

for s in sys.stdin:
    s = s.strip()
    answer = []
    i = 0
    while i < len(s):
        if s[i] == '@':
            num = int(s[i+1])
            c = s[i+2]
            answer.append(c * num)
            i += 3

        else:
            answer.append(s[i])
            i += 1

    print(''.join(answer))

Measured memory_bytes: 7564
#include<iostream>
using namespace std;
int main() {
	int a[100][100], b[100],c[100], m, n, i,ans,j,q,e,w,r;
	cin >> n >> m;
	for (r = 0; r < 100; r++) {
		c[r] = 0;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (e = 0; e < m; e++) {
		cin >> b[e];
	}
	for (q = 0; q < n; q++) {
		for (w = 0; w < m; w++) {
			c[q] += a[q][w] * b[w];
			
		}
		cout << c[q] << endl;
	}

	return 0;
}

Measured memory_bytes: 3144
n = gets.to_i
ary = gets.chomp.split.map(&:to_i)

def partition(ary, p, r)
    x = ary[r]
    i = p - 1
    p.upto(r - 1) do |j|
        if ary[j] <= x then
            i += 1
            tmp = ary[i]
            ary[i] = ary[j]
            ary[j] = tmp
        end
    end
    tmp = ary[i + 1]
    ary[i + 1] = ary[r]
    ary[r] = tmp
    return i + 1
end

q = partition(ary, 0, ary.size - 1)
ary[q] = "[#{ary[q]}]"
puts ary.join(' ')


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

int main() {
  string S;
  int64_t K;
  cin>>S>>K;
  for(int64_t i=0;i<K;i++){
    if(S.at(i)!='1'){
      cout<<S.at(i)<<endl;
      break;
    }
    else if(i==K-1){
      cout<<'1'<<endl;
    }
  }
}

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

using namespace std;
using LL = long long;

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

	int n;
	cin >> n;

	vector< int> pos(n);
	for (int i = 0; i < n; i ++) {
		int x;
		cin >> x;
		x --;
		pos[x] = i;
	}

	LL ans = 0;
	multiset< int> used;
	used.insert(-1); used.insert(-1);
	used.insert(n); used.insert(n);

	LL result = 0;
	for (int i = n - 1; i >= 0; i --) {
		used.insert(pos[i]);
		auto it = prev(used.find(pos[i]));
		int s1 = *it;
		int s2 = *prev(it);
		it = next(used.find(pos[i]));
		int e1 = *it;
		int e2 = *next(it);

		LL cur_value = i + 1;
		LL numPos = 0;
		numPos += (s2 - s1) * 1LL * (pos[i] - e1);
		numPos += (s1 - pos[i]) * 1LL * (e1 - e2);
		result += cur_value * numPos;
	}

	cout << result << endl;
}

Measured memory_bytes: 5376
N,M=map(int,input().split())
ans=[999]*N
    
for _ in range(M):
    s,c=map(int,input().split())
    if ans[s-1]==999:
        ans[s-1]=c
    elif ans[s-1]==c:
        continue
    else:
        ans=-1

if ans==-1:
    print(ans)
    exit()
if N>1 and ans[0]==999:
    ans[0]=1
elif N>1 and ans[0]==0:
    print(-1)
    exit()

for i in range(N):
    if ans[i]==999:
        ans[i]=0

print(*ans,sep="")


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

int main(){
  int N, M;
  int64_t K;

  while(std::cin >> N >> M >> K){
    std::vector<int64_t> A(N);
    std::vector<int64_t> B(M);

    for(int i = 0; i < N; ++i) std::cin >> A[i];
    for(int i = 0; i < M; ++i) std::cin >> B[i];

    std::vector<int64_t> SA(N+1), SB(M+1);

    for(int i = 0; i < N; ++i) SA[i+1] = SA[i] + A[i];
    for(int i = 0; i < M; ++i) SB[i+1] = SB[i] + B[i];

    int ans = 0;    

    for(int i = 0; i <= N; ++i){
      int64_t r = K - SA[i];
      
      if(K >= 0){
        auto it = std::upper_bound(SB.begin(), SB.end(), r);

        if(it != SB.begin()){
          int j = it - SB.begin() - 1;
          ans = std::max(ans, i + j);
        }
      }
    }

    std::cout << ans << "\n";
  }

  return 0;
}


Measured memory_bytes: 9592
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    string N;
    cin >> N;
    if(N.at(0) == '7' || N.at(1) == '7' ||N.at(2) == '7')cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5 + 100;
string s;
int ans = 0;
int main() {
	
	cin >> s;
	
	int tmp = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
			tmp++;
			ans = max(ans, tmp);
		}else tmp = 0;
	}
	
	cout << ans << endl;
	return 0;	
} 

Measured memory_bytes: 3148
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int[] l = new int[2*n];
		for (i = 0; i < l.length; i++) {
			l[i] = parseInt(sc.next());
		}
		sc.close();
		Arrays.parallelSort(l);
		int cnt = 0;
		for (i = 0; i < n; i++) {
			cnt += Math.min(l[i*2], l[i*2+1]);
		}
		out.println(cnt);
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int n;
void dfs(string ans, char mx){
  if(ans.size() == n){
    cout << ans << endl;
    return;
  }
  for(char c = 'a'; c <= mx+1; c++){
    dfs(ans+c,max(mx,c));
  }
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  cin >> n;
  dfs("",'a'-1);
  // cout << "\n";
  return 0;
}


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

int main() {
  int n; cin >> n;
  int x = 0, y = 0, time = 0;
  bool ok = true;
  rep(i,n) {
    int t,tmpx, tmpy;
    cin >> t >> tmpx >> tmpy;
    time = t - time;
    x = abs(tmpx - x);
    y = abs(tmpy - y);
    if (time >= x+y && time%2==(x+y)%2) {
      ok = true;
    } else {
      ok = false;
      cout << "No" << endl;
      return 0;
    }
  }
  if (ok) cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)
//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

int cnt = 0;

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int len = s.size();
    char tmp;
    tmp = s[0];
    FOR(i, 1, len){
        if(tmp != s[i]){
            cnt++;
            tmp = s[i];
        }
    }
    cout << cnt << endl;
}

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

int par[10000], high[10000];
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 (high[x] > high[y])par[y] = x;
	else {
		par[x] = y;
		if (high[x] == high[y])high[y]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int main() {
	int n, q; scanf("%d%d", &n, &q);
	rep(i, n)par[i] = i;
	rep(i, q) {
		int com, x, y; scanf("%d%d%d", &com, &x, &y);
		if (com)cout << same(x, y) << endl;
		else unite(x, y);
	}
}

Measured memory_bytes: 3272
import sys
input = sys.stdin.readline


n, m, l = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
    a, b, cost = info[i]
    if cost > l:
        continue
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))


def warshall_floid(graph):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(|N|^3)
    """
    n = len(graph)
    INF = 10**18
    dp = [[INF]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost
            dp[j][i] = cost

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    return dp

def warshall_floid_matrix(matrix):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    matrix[i][j] := 頂点iから頂点jへの距離（頂点iから頂点jへ到達できないときはINFを代入しておく）
    計算量: O(|N|^3)
    """
    n = len(matrix)
    dp = matrix
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp

dp1 = warshall_floid(graph)
INF = 10**18
dp2 = [[INF]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if dp1[i][j] <= l:
            dp2[i][j] = 1
ans = warshall_floid_matrix(dp2)         

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
    a, b = query[i]
    a -= 1
    b -= 1
    if ans[a][b] == 10**18:
        print(-1)
    else:
        print(ans[a][b] - 1)


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

int main(){
    int x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vector<ll> p(a), q(b), r(c);
    for (int i = 0; i < a; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < b; ++i) {
        cin >> q[i];
    }
    for (int i = 0; i < c; ++i) {
        cin >> r[i];
    }
    sort(r.begin(), r.end(), greater<ll>());

    sort(p.begin(), p.end(), greater<ll>());
    sort(q.begin(), q.end(), greater<ll>());
    vector<ll> v(x+y);
    for (int i = 0; i < x; ++i) {
        v[i] = p[i];
    }
    for (int i = 0; i < y; ++i) {
        v[x+i] = q[i];
    }
    sort(v.begin(), v.end());

    int index = 0;
    for (int i = 0; i < x+y; ++i) {
        if(v[i] < r[index]){
            v[i] = r[index];
            index++;
        }
        if(index == c) break;
    }

    ll res = 0;
    for (int i = 0; i < x+y; ++i) {
        res += v[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 3968
#include<iostream>
using namespace std;
int main(){
	int n, ans = 0; cin >> n;
	int a[101], b[101];
	for (int i = 1; i <= n; i++){
		a[i] = false;
		b[i] = false;
	}
	int x; cin >> x;
	for (int i = 0; i < x; i++){
		int k; cin >> k; a[k] = true;
	}
	int y; cin >> y;
	for (int i = 0; i < y; i++){
		int k; cin >> k; b[k] = true;
	}
	int z; cin >> z;
	for (int i = 0; i < z; i++){
		int k; cin >> k;
		if (!a[k] || b[k])ans++;
	}
	cout << ans << endl;
}

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

int a[100][7];
int e=0;


//houkou,taishou
void move(char i,int o){
int b[7];
for(int n=1;n<7;n++){b[n]=a[o][n];}

if(i=='W'){
a[o][6]=b[4];
a[o][4]=b[1];
a[o][1]=b[3];
a[o][3]=b[6];
}

if(i=='N'){
a[o][6]=b[5];
a[o][5]=b[1];
a[o][1]=b[2];
a[o][2]=b[6];
}

if(i=='E'){
a[o][6]=b[3];
a[o][3]=b[1];
a[o][1]=b[4];
a[o][4]=b[6];
}

if(i=='S'){
a[o][6]=b[2];
a[o][2]=b[1];
a[o][1]=b[5];
a[o][5]=b[6];
}

if(i=='R'){
a[o][3]=b[2];
a[o][2]=b[4];
a[o][4]=b[5];
a[o][5]=b[3];
}}


//naniwouehe,taishou
void move2(int r,int p){
if(r==2){move('N',p);}
if(r==3){move('W',p);}
if(r==4){move('E',p);}
if(r==5){move('S',p);}
if(r==6){move('N',p); move('N',p);}
}


//nanito,naniga
void right(int o,int p){
for(int l=1;l<7;l++){
if(l==6 && a[o][l]==a[p][l]){e=1;}
if(a[o][l]==a[p][l]){continue;}
break;
}}




int main(){
int O;
cin>>O;
for(int h=0;h<O;h++){
for(int g=1;g<7;g++){
cin>>a[h][g];
}}




for(int P=0;P<O-1;P++){
for(int I=P+1;I<O;I++){


int da[7];
for(int h=1;h<7;h++){da[h]=a[P][h];}

for(int g=1;g<=7;g++){
for(int n=0;n<=4;n++){

right(P,I);

if(e==1){break;}
move('R',P);
}
if(e==1){break;}
for(int h=1;h<7;h++){a[P][h]=da[h];}
move2(g,P);
}


if(e==1){break;}
}
if(e==1){break;}
}

if(e==1){cout<<"No"<<endl;}
if(e==0){cout<<"Yes"<<endl;}

return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>
#include <set>

template<typename T> bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<typename T> bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}

using namespace std;
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=1001001000;
const ll LLMAX=1010010010010010000;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N;
    cin>>N;
    vll A(N);
    for(ll i=0;i<N;i++)cin>>A[i];
    
    vvll dp(N,vll(2));//j=0,not changed
    
    for(ll i=0;i<N;i++){
        if(i==0){
            dp[i][0]=A[i];
            dp[i][1]=-A[i];
        }else if(i==N-1){
            dp[i][0]=max(dp[i-1][0]+A[i],dp[i-1][1]-A[i]);
        }else{
            dp[i][0]=max(dp[i-1][0]+A[i],dp[i-1][1]-A[i]);
            dp[i][1]=max(dp[i-1][0]-A[i],dp[i-1][1]+A[i]);
        }
    }
    //for(int i=0;i<N;i++)printf("%lld,%lld\n",dp[i][0],dp[i][1]);
    
    cout<<dp[N-1][0]<<endl;
    
    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;
typedef map< pair<ll, ll>, int >::iterator mit;

const int M = 3000;
bool used[M];
vector<int> ps;
map< pair<ll, ll>, int > mp;

void first() {
    for (int i = 2; i < M; i++) {
        if (used[i]) continue;
        for (int j = i * i; j < M; j += i) {
            used[j] = true;
        }
    }
    for (int i = 2; i < M; i++) {
        if (!used[i]) ps.push_back(i);
    }
}

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

    first();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll x;
        cin >> x;
        ll g1 = 1, g2 = 1;
        for (int j = 0; j < int(ps.size()); j++) {
            ll p = ps[j];
            if (p * p * p > x) break;
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            e %= 3;
            if (e == 1) g1 *= p;
            else if (e == 2) g2 *= p;
        }
        ll r = sqrt(x);
        if (r * r == x) g2 *= r;
        else g1 *= x;
        mp[make_pair(g1, g2)]++;
    }

    int ans = 0;
    for (mit it = mp.begin(); it != mp.end(); it++) {
        ll x = it->first.first, y = it->first.second;
        if (x > y && mp[make_pair(y, x)]) continue;
        if (x == y) {
            ans++;
        } else {
            ans += max(mp[make_pair(x, y)], mp[make_pair(y, x)]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12800
import numpy as np
L = 10**5


def main():
    is_prime = np.full(L+1, True, dtype=bool)
    is_prime[0:2] = False
    for i in range(2, int(np.sqrt(L))+1):
        if is_prime[i] == False:
            continue
        is_prime[i+i:L+1:i] = False
    # ここまで素数判定
    # ここから2017に似た数を判定
    is_like_2017 = np.full(L+1, False, dtype=bool)

    for i in range(2, L+1):
        if 2*i-1 > L:
            break
        if is_prime[i]:
            is_like_2017[2*i-1] = True

    is_like_2017[2] = False

    is_like_2017 = np.logical_and(is_prime, is_like_2017)
    accumulate = np.cumsum(is_like_2017)

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        print(accumulate[r]-accumulate[l-1])


if __name__ == "__main__":
    main()


Measured memory_bytes: 28536
#include <iostream>
#include <cstdio>
#include <cstring>

#define MAX 100

using namespace std;
int main(){
  int n, q, m;
  int d[MAX], date;
  while(cin >> n >> q){
    if(n == 0 && q == 0) break;
    memset(d, 0, sizeof(d));

    while(n--){
      cin >> m;
      for(int i = 0 ; i < m ; i++){
	cin >> date;
	d[date]++;
      }
    }
    bool flag = 0;
    int ans = 0, tmp = 0;

    for(int i = 1 ; i < MAX ; i++){
      if(d[i] >= q){
	if(i >= ans && d[i] > tmp){
	  ans = i;
	  tmp = d[i];
	  flag = 1;
	}
      }
    }
    
    if(flag == 1) cout << ans << endl;
    else cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define INF 10**9+7
using namespace std;

bool check(long long a,long long b,long long c){
    return true;
}

int main(){
    long long N,M;
    long long a,b;
    
    cin >> N >> M;
    vector<vector<int> > graph(N);
    for(int i=0; i<M; i++){
        cin >> a >> b;
        graph.at(a-1).push_back(b-1);
        graph.at(b-1).push_back(a-1);
    }

    for(int node=0; node<graph.size(); node++){
        cout << graph.at(node).size() << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 1000000007;
using ll = int64_t;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int h, w;
    cin >> w >> h;
    h += 2; w += 2;
    vector<vector<int>> v(h+2, vector<int>(w+2, -1));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            v[i][j] = 0;
        }
    }
    for (int i = 2; i <= h-1; ++i) {
        for (int j = 2; j <= w-1; ++j) {
            cin >> v[i][j];
        }
    }
    int dys[] = {-1, -1, 0, 0, 1, 1};
    int dx_odd[] = {-1, 0, -1, 1, -1, 0};
    int dx_even[] = {0, 1, -1, 1, 0, 1};
    stack<pair<int, int>> q;
    q.emplace(1, 1);
    while(!q.empty()){
        int y, x; tie(y, x) = q.top(); q.pop();
        v[y][x] = 2;
        for (int i = 0; i < 6; ++i) {
            int dy = dys[i], dx = (y&1 ? dx_odd : dx_even)[i];
            if(v[y+dy][x+dx] == 0) q.emplace(y+dy, x+dx);
        }
    }
    int ans = 0;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            if(v[i][j] != 2) continue;
            for (int k = 0; k < 6; ++k) {
                int dy = dys[k], dx = (i&1 ? dx_odd : dx_even)[k];
                if(v[i+dy][j+dx] == 1) ans++;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3228
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <cctype>

using namespace std;

using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)



int main() {
	ll n;
	cin >> n;
	ll a[n];
	rep(i, n) {
		cin >> a[i];
	}
	if (a[0] != 0) {
		cout << -1 << endl;
		return 0;		
	}

	rep(i, n - 1) {
		if (a[i] + 1 < a[i + 1]) {
			cout << -1 << endl;
			return 0;
		}
	}
	ll ans = a[n - 1];

	for(int i = n - 2; i >= 0; i--) {
		if (a[i] + 1 == a[i + 1]) {
			continue;			
		}
		ans += a[i];
	}

	cout << ans << endl;

	return 0;
}


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

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

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

    vector<vector<int> > bfs(n);
    REP(i, m) {
        int a, b;
        cin >> a >> b;
        bfs[a - 1].push_back(b - 1);
    }

    bool ans = false;
    REP(i, bfs[0].size()) {
        REP(j, bfs[bfs[0][i]].size()) {
            if (bfs[bfs[0][i]][j] == n - 1)
                ans = true;
            if (ans) break ;
        }
        if (ans) break ;
    }

    if (ans) cout << "POSSIBLE" << '\n';
    else cout << "IMPOSSIBLE" << '\n';
    return 0;
}


Measured memory_bytes: 8576
import itertools

S = input()


def solve():
    ans = []
    ss = itertools.groupby(S)

    for key, groups in ss:
        groups = list(groups)
        groups_cnt = len(groups)
        nothing_cnt = [0] * (groups_cnt - 1)

        even_cnt = groups_cnt // 2
        odd_cnt = groups_cnt - even_cnt

        if key == 'R':
            tmp_ans = nothing_cnt + [odd_cnt]
            tmp_ans.append(even_cnt)
        elif key == 'L':
            ans[-1] += odd_cnt
            ans[-2] += even_cnt
            tmp_ans = nothing_cnt

        ans += tmp_ans

    return ' '.join(map(str, ans))


print(solve())


Measured memory_bytes: 12148
using System;
public class c
{
  public static void Main()
  {
    string[] A_B_K = Console.ReadLine().Split(' ');
    int A = int.Parse(A_B_K[0]);
    int B = int.Parse(A_B_K[1]);
    int K = int.Parse(A_B_K[2]);
    int n = A;
    int ans =0;
    if(n>B) n=B;
    for(int i=n;i>=1;i--)
    {
      if(A%i==0&&B%i==0)K--;
      if(K==0){ans=i;break;}
    }
    Console.WriteLine(ans);
    
  }
}

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

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

int main(){
  long long int a,b;
  cin >> a >> b;
  long long int s;
  s = a * b;
  //cout << s << '\n';
  long long int n;
  n = gcd(a, b);
  //cout << n << '\n';
  s = s / n;
  cout << s << '\n';
  return 0;
}


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

// 最大公約数(GCD:greatest common divisor) ユークリッドの互除法
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 最小公倍数(LCM:least common multiple)
// 公式 a * b = gcd(a, b) * lcm(a, b)
// a * b / gcd(a, b) = lcm(a, b)
// a, bはそれぞれ10^18なのでa*bするとTLEしちゃう。なので、 a / gcd(a,b)してから*b
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

int main() {
    int n;
    cin >> n;
    ll t, ans = 1;
    rep(i, n) {
        cin >> t;
        ans = lcm(ans, t); //入力の度に最小公倍数を探す
    }

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

Measured memory_bytes: 3560
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == 1)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T> void SORT_(vector<int>& v,bool GREATER = 0){if(GREATER == 0)sort(v.begin(),v.end());else{sort(v.begin(),v.end(),std::greater<T>());}}

//CODE
void solve(void)
{

  int N,D,X;
  cin>>N>>D>>X;
  int ANS = X;
  for (int i = 0; i < N; i++)
  {
    int A;
    cin>>A;
    ANS += (D-1)/A + 1;
  }
  cout<<ANS<<endl;
  
  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x)  x.begin(),x.end()
#define vi vector<int>
#define print(x) for(auto it=x.begin();it!=x.end();it++) cout<<*it<<' '; cout<<'\n';
#define in(x,n) for(int e=0;e<n;e++){int y;cin>>y;x.pb(y);}
#define lower(sl)  transform(sl.begin(), sl.end(), sl.begin(), ::tolower); 
//Available in Snips
#define fi(i, x, y)   for (__typeof(x) i = x; i < y; i ++)
#define fir(i, x, y)  for (__typeof(x) i = x; i > y; i --)
#define fv(x)   for (auto itr = x.begin(); itr != x.end(); itr ++)
#define fvr(x)  for (auto itr = x.end() - 1; itr != x.begin() - 1; itr --)

bool check(string s){
	int n = s.size();
	for(int i=0;i<n/2;i++){
		if(s[i]==s[n-1-i]){
			continue;
		} else {
			return false;
		}
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//code here
	string s;
	cin >> s;
	int n= s.size();
	string s1 = s.substr(0,(int)(n-1)/2);
	string s2 = s.substr((int)(n+3)/2-1,n);
	if (check(s) and check(s1) and check(s2)){
		cout << "Yes";
	} else {
		cout << "No";
	}
}


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

int main() {
 int a,b,c,d,e,f;
 cin >> a >> b >> c >> d;
 e = max(a,c);
 f = min(b,d);
 if(e < f) cout << f-e << endl;
 else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
int n, m;
int main(){
	scanf("%d%d", &n, &m);
	rep(i,m) printf("%d %d\n", i+1, n-i-(~n&1 && n<=i*4+2));
}

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

class UnionFind {
private:
  int sz;
  vector<int> par, size_;
public:
  UnionFind() {}
  UnionFind(int n) : sz(n), par(sz), size_(sz, 1) {
    iota(par.begin(), par.end(), 0);
  }
  int root(int x) {
    if (par.at(x) == x) return x;
    else return par.at(x) = root(par.at(x));
  }
  void unit(int x,int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    if (size_.at(x) < size_.at(y)) swap(x, y);
    par.at(y) = x;
    size_.at(x) += size_.at(y);
  }
  int size(int x) {
    x = root(x);
    return size_.at(x);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

template<typename T> class Kruskal {
public:
  struct edge {
    int u, v;
    T cost;
    bool operator < (const edge& another) const {
      return cost < another.cost;
    }
  };
  vector<edge> es;
  int V;
  Kruskal(int n) : V(n) {}
  void add(int u, int v, T cost) {
    es.push_back((edge) {u, v, cost});
  }
  T solve() {
    UnionFind UF(V);
    T res = 0;
    int cnt = 0;
    sort(es.begin(),es.end());
    for (edge &e : es) {
      if (!UF.same(e.u, e.v)) {
        UF.unit(e.u, e.v);
        res += e.cost;
        cnt++;
        if (cnt == V - 1) break;
      }
    }
    return res;
  }
};

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> X(N);
  vector<pair<int, int>> Y(N);
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    X.at(i) = {x, i};
    Y.at(i) = {y, i};
  }
  sort(X.begin(), X.end());
  sort(Y.begin(), Y.end());
  Kruskal<long> KR(N);
  for (int i = 0; i + 1 < N; i++) {
    KR.add(X.at(i).second, X.at(i + 1).second, abs(X.at(i).first - X.at(i + 1).first));
    KR.add(Y.at(i).second, Y.at(i + 1).second, abs(Y.at(i).first - Y.at(i + 1).first));
  }
  cout << KR.solve() << "\n";
}

Measured memory_bytes: 9052
# 入力割り当て
N = int(input())
A = list(map(int, input().split()))

# sort
A_sort = sorted(A, reverse=True)

# 変数定義
n = 0
m = 0
i = 0

# 降順に割り当て
for i in range(N):
	if i%2 == 0:
		n += A_sort[i]
	else:
		m += A_sort[i]

# 結果の表示
ans = n - m
print(ans)

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

ll isWinning(ll x, ll k){

	if(x<k)return 0;

    ll curr=x;

    ll toRem;
    ll cm;

    while(curr%k!=0){
        if(curr<k)break;

        cm=curr%k;

        toRem=(curr/k)+1;

        if((cm)%toRem == 0){
            return curr/k;
        }
        else{
            curr-=((cm/toRem)+1)*toRem;
        }

    }

    return curr/k;
}

int main() 
{ 

	#ifndef ONLINE_JUDGE
    	freopen("input", "r", stdin);
    	freopen("output", "w", stdout);
    	freopen("error", "w", stderr);
	#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // for(int i=1;i<40;i++){
    //     cerr<<i<<" "<<isWinning(i,3)<<endl;
    // }

    ll n;
    cin>>n;
    ll arr[n][2];
    ll winC=0;
    ll lossC=0;
    ll curr=0;
    for(int i=0;i<n;i++){
    	cin>>arr[i][0]>>arr[i][1];
    	curr^=(isWinning(arr[i][0],arr[i][1]));
    }

    if(curr){
        cout<<"Takahashi"<<endl;
    }
    else{
        cout<<"Aoki"<<endl;
    }
}

Measured memory_bytes: 3648
#!/usr/bin/env python
# -*- coding: utf-8 -*-

w = []
k = []

for _ in range(10):
    w.append(int(input()))

for _ in range(10):
    k.append(int(input()))

w_sum = sum(sorted(w)[7:])
k_sum = sum(sorted(k)[7:])

print(w_sum, k_sum)

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

int main() {
	int n;
	cin >> n;
	vector<int> perm(n);
	for (int i = 0; i < n; ++i)
		cin >> perm[i];
	sort(perm.begin(), perm.end());
	cout << perm[n / 2] - perm[n / 2 - 1] << endl;
	return 0;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=0;i<b;i++)
#define REP(i,a,b) for(int i=0;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout <<(f?"Yes":"No")<<endl//fが真の場合Yesを出力、偽の場合Noを出力
#define yes(f) cout <<(f?"yes":"no")<<endl
#define YES(f) cout <<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())

using namespace std;

const int mod=1e9+7;

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

    int ans;
    rep(i,4)
    {
        if(s[i]=='+')ans++;
        if(s[i]=='-')ans--;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
//
//  main.cpp
//  B - Frog 2
//
//  Created by Hashizo on 2019/06/12.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>

using namespace std;

#undef INT_MAX
#define INT_MAX 2147483647
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define REPLACE(s, f, t) regex_replace(s, regex(f), t)

int main(int argc, const char * argv[]) {
	int n,k;
	cin >> n >> k;

	
	int h[n],dp[n];
	
	REP(i, n) {
		cin >> h[i];
		dp[i]=INT_MAX;
	}
	
	dp[0]=0;
	
	FOR(i, 1, n) {
		FOR(j, 1, k+1){
			if((i-j) >= 0) {
				dp[i] = min(dp[i], (dp[i-j]+abs(h[i]-h[i-j])));
			}
		}
	}
	
	
	cout << dp[n-1] << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
using pint  = pair<int, int>;
using ppint = pair<pint, pint>;

int main() {
  int H, W;
  cin >> H >> W;

  vector<vector<int>> A(H, vector<int>(W, 0));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A[i][j];
    }
  }

  vector<ppint> ans;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W - 1; j++) {
      if (A[i][j] % 2 == 0)
        continue;
      A[i][j]--;
      A[i][j + 1]++;
      ans.push_back(ppint(pint(i, j), pint(i, j + 1)));
    }
  }
  for (int i = 0; i < H - 1; i++) {
    if (A[i][W - 1] % 2 == 0)
      continue;
    A[i][W - 1]--;
    A[i + 1][W - 1]++;
    ans.push_back(ppint(pint(i, W - 1), pint(i + 1, W - 1)));
  }

  cout << ans.size() << endl;
  for (auto p : ans) {
    cout << p.first.first + 1 << " " << p.first.second + 1 << " ";
    cout << p.second.first + 1 << " " << p.second.second + 1 << endl;
  }
  return 0;
}


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

bitset <5010> dp;
int n, k;
int a[5010];

bool check(int mid) {
	dp.reset(), dp.set(0);
	for (int i = 0; i < n; i++) {
		if (i != mid) dp = dp | dp << a[i];
	}
	for (int i = max(0, k - a[mid]); i < k; i++) {
		if (dp[i]) return 0;
	}
	return 1;
}

int main () {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	int l = -1, r = n - 1;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	printf("%d\n", l + 1);
	return 0;
}


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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define PI (acos(-1))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define MAXN 1123456
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;

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

  int n, x, y;
  cin >> n >> x >> y;

  vi ans(n+1);

  rep(i,2,n+1) {
    rep(j,1,i) {
      int d = min(i-j, min( abs(i-x)+abs(j-y)+1, abs(i-y)+abs(j-x)+1 ));
      ans[d]++;
    }
  }

  rep(i,1,n) cout << ans[i] << endl;
}

Measured memory_bytes: 256