akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define rep(N) for(int i=0;i<N;i++)
#define repj(N) for(int j=0;j<N;j++)
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define For(I,N) for(int I=0;I<N;I++)
#define cinone(N) int N;cin>>N;
#define scanfone(N) int N;cin>>N;
#define cinng(N,M) int N[M];for(int yiuytvnm=0;yiuytvnm<M;yiuytvnm++) cin>>N[yiuytvnm];
#define scanfng(N,M) int N[M];for(int qrwuoiq=0;qrwuoiq<M;qrwuoiq++) scanf("%d",&N[qrwuoiq]);
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
ll dp[105][105][305];
ll n,w;
ll a[105],v[105],we[105];

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>v[i];
		we[i]=a[i]-a[1];
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0][0]=0;
//	dp[1][1][we[1]]=v[1];
//	dp[1][0][0]=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=300;k++)
			{
				dp[i+1][j+1][k+we[i+1]]=max(dp[i+1][j+1][k+we[i+1]],dp[i][j][k]+v[i+1]);
				dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
			}
		}
	}
	ll res=0;
//	for(int i=1;i<=n;i++)
//	{
	
//	for(int j=0;j<=n;j++)
//	{
//		for(int k=0;k<=6;k++)
//		{
//			cout<<dp[i][j][k]<<' ';
//		}
//		cout<<endl;
//	}
//	cout<<endl;
//}
	for(int j=0;j<=n;j++)
	{
		for(int k=0;k<=300;k++)
		{
			if(j*a[1]+k>w) continue;
			res=max(res,dp[n][j][k]);
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 26496
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n,i,m=0,f=1,a[101];
	cin >> n;
	for(i=0;i<n;i++) {
		cin >> a[i];
	}
	sort(a,a+n);
	for(i=n-1;i>=0;i--)	{
		m+=f*a[i];
		f=-f;
	}
	cout << m << endl;
	return 0;
}


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

int main() {
	int	N;
	cin >> N;
	set<int> s;
	rep(i, N)
	{
		int	a, b;
		cin >> a >> b;
		if (a == 0)
		{
			s.insert(b);
			cout << s.size() << endl;
		}
		else
			cout << (s.find(b) != s.end()) << endl;
	}
}



Measured memory_bytes: 12456
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define pi acos(-1.0)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

string s, inv;

int main(){
    cin >> s;
    
    for(int i = 0; i < s.length(); i++){
        inv.push_back(s[s.length() - 1 - i]);
    }
    
    int i = 0;
    while(true){
        if(i == inv.length()){
            cout << "YES" << endl;
            return 0;
        }
        
        if(inv.substr(i, 5) == "maerd"){
            i+=5;
        }else if(inv.substr(i, 5) == "esare"){
            i+=5;
        }else if(inv.substr(i, 6) == "resare"){
            i+=6;
        }else if(inv.substr(i, 7) == "remaerd"){
            i+=7;
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }
    
    
    return 0;
}










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

int main() {
  int n;
  cin>>n;
  if(n<105)cout<<"0"<<endl;
  if(105<=n && n<135)cout<<"1"<<endl;
  if(135<=n && n<165)cout<<"2"<<endl;
  if(165<=n && n<189)cout<<"3"<<endl;
  if(189<=n && n<195)cout<<"4"<<endl;
  if(195<=n )cout<<"5"<<endl;

}
  


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <tuple>
#include <string.h>
#include <map>
#include <iomanip>
#include <time.h>
using namespace std;
typedef long long ll;

double square(pair<int, int> p) {
    return p.first * p.first + p.second * p.second;
}

pair<int, int> add(pair<int, int> p, pair<int, int> q) {
    return make_pair(p.first + q.first, p.second + q.second);
}

double dot(pair<int, int> p, pair<int, int> q) {
    return p.first * q.first + p.second * q.second;
}

int main() {
    int x1, y1, x2, y2, q;
    cin >> x1 >> y1 >> x2 >> y2;
    pair<int, int> a = make_pair(x2 - x1, y2 - y1);

    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;

        pair<int, int> b = make_pair(x - x1, y - y1);
        double r = dot(a, b) / square(a);

        double cx = x1 + r * (x2 - x1), cy = y1 + r * (y2 - y1);
        cout << setprecision(16) << cx << " " << cy << endl;


    }
}


Measured memory_bytes: 3292
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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


int main() {
    std::cout<<std::fixed<<std::setprecision(10);
    
    ll A, B; cin >> A >> B;
    ll lcm = A*B/gcd(A, B);
    cout << lcm << endl;
    return 0;
}

Measured memory_bytes: 256
def acinput():
    return list(map(int,input().split(" ")))


L,R=acinput()

minv=10**5
for i in range(L,min(R+1,L+2019)):
    for j in range(i+1,min(R+1,L+2019)):
        tmp=(i*j)%2019
        #print(tmp)
        if minv>tmp:
            minv=tmp
    
print(minv)


Measured memory_bytes: 3064
from collections import deque, defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))

Si_m_i = [0]
total = 0
temp = 0
for i in range(N):
    total += A[i]
    temp = (total-i-1) % K
    Si_m_i.append(temp)

ret = 0
d = defaultdict(deque)
for i in range(N+1):
    pair = Si_m_i[i]
    temp = d[pair]
    while temp and i-temp[0] >= K:
        temp.popleft()
    ret += len(temp)
    d[Si_m_i[i]].append(i)

print(ret)




Measured memory_bytes: 162080
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Stack, Queue, PriorityQueue, Set}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val X = in.next().toLong

  //
  def f(a: Int): Long = {
    val b = a.toLong
    b*b*b*b*b
  }

  var A = 0L
  var B = 0L
  breakable{
    for (a <- -1000 to 1000;b <- -1000 to 1000) {
      if (f(a) == X + f(b)) {
        A = a; B = b
      }
    }
  }

  println(s"$A $B")
}

object Sub {
  def print2DimArray[A](mat: Array[Array[A]]): Unit = {
    mat.foreach(lin => println(lin.toList))
  }
}

class InputReader(stream: InputStream) {
  private[this] val reader = new BufferedReader(new InputStreamReader(stream))
  private[this] var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 54884
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static boolean solve() {
		int n = in.nextInt();
		int m = in.nextInt();
		if (n + m == 0) return false;

		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i=1; i<=n; i++) {
			list.add(i);
		}

		int p = 0;
		while (list.size() > 1) {
			int idx = (p + m - 1)%list.size();
			list.remove(idx);
			p = idx;
		}

		out.println(list.get(0));

		return true;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		while(solve());
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26532
s = input()
k = int(input())
import math

if len(set(list(s))) == 1:
    print(len(s) * k // 2)
    exit()

ans=0
last=s[0]
length=1
change=0
for i in range(1,len(s)):
    if s[i] == last:
        length+=1
    else:
        change += math.floor(length/2)
        length=1
    last=s[i]

change += math.floor(length/2)
ans=change*k
if s[0] != s[-1]:
    print(ans)
    exit()
    
    
l_length=1
last=s[0]
for i in range(1,len(s)):
    if s[i] == last:
        l_length+=1
    else:
        break
r_length=1
last=s[-1]
for i in range(len(s)-2,-1,-1):
    if s[i] == last:
        r_length+=1
    else:
        break

if l_length%2==1 and r_length%2==1:
    print(ans+k-1)
    exit()

print(ans)

Measured memory_bytes: 3064
n = int(input())
ans = float('inf')
for i in range(n+1):
    result = 0
    t = i
    while t > 0:
        result += t % 6
        t = t // 6
    s = n - i
    while s > 0:
        result += s % 9
        s = s // 9
    ans = min(ans, result)
print(ans)

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

int n;
vector<int> a;
bool solve(int i, int m) {
  if(m == 0) {
    return true;
  }

  if(i > n) {
    return false;
  }
  bool res = solve(i + 1, m) || solve(i + 1, m - a[i]);
  return res;
}

int main() {
  
  cin >> n;
  a = vector<int>(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int q;
  cin >> q;
  bool flag;
  for(int i; i < q; i++) {
    int m;
    cin >> m;
    flag = solve(0, m);
    if(flag) cout << "yes" << endl;
    else cout << "no" <<endl;
  }
}




Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
void solotion()
{
    int n;
    cin>>n;
    string s;
    map<string,int> mp;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;
}
int main()
{
    solotion();
    return 0;
}


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

#define endl '\n'
#define ll  long long
#define modd(a,b) ((a+2*b)%b)
#define ioso ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug(a) cout << #a << ": " << (a) << "\n"
#define ffe freopen("input.txt","r",stdin), freopen("output.txt","w",stdout)

int main() {
	ioso;
	#ifndef ONLINE_JUDGE
	ffe;
	#endif

	ll n,k,l;cin >> n >> k;
	int cn[10001]={0};
	for(int i=0;i<k;i++) {
		cin >> l;
		for(int j=0;j<l;j++) {
			int a;cin >> a;
			cn[a]++;
		}
	}
	int v=0;
	for(int i=1;i<=n;i++) {
		if(cn[i]==0) {v++;}
	}
	cout << v << endl;
}

Measured memory_bytes: 3656
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}
struct multi {
  ll i;
  ll s;
  ll t;
  ll c;
};
bool multicomp(const multi &a, const multi &b) {
  if (a.t == b.t)
    return a.s < b.s;
  return a.t < b.t;
}
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, C;
  cin >> N >> C;
  vvl S = VVL(C, 200002, 0);
  REP(i, N) {
    ll s, t, c;
    cin >> s >> t >> c;
    S[c - 1][s * 2 - 1]++;
    S[c - 1][t * 2]--;
  }
  FOR(i, 1, 200002) { REP(j, C) S[j][i] += S[j][i - 1]; }
  ll ans = 0;
  REP(i, 200002) {
    ll a = 0;
    REP(j, C) if (S[j][i] >= 1) a++;
    ans = max(ans, a);
  }

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


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

int N,T,S;
int A[3010],B[3010];
int dp[3010][3010];

int solve(int cnt,int now){
  if(cnt == N) return 0;
  if(dp[cnt][now] != -1) return dp[cnt][now];
  int ret = 0;
  ret = max(ret,solve(cnt+1,now));
  if(now+B[cnt] <= S){
    ret = max(ret,solve(cnt+1,now+B[cnt])+A[cnt]);
  }
  else if(now >= S && now+B[cnt] <= T){
    ret = max(ret,solve(cnt+1,now+B[cnt])+A[cnt]);
  }
  else if(now < S && S+B[cnt] <= T) {
    ret = max(ret,solve(cnt+1,S+B[cnt])+A[cnt]);
  }
  return dp[cnt][now] = ret;
}

int main(){
  cin >> N >> T >> S;
  for(int i=0;i<N;i++){
    cin >> A[i] >> B[i];
  }
  memset(dp,-1,sizeof(dp));
  cout << solve(0,0) << endl;
}

Measured memory_bytes: 36720
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	while(true){
		int n;
		cin >> n;
		if(n == 0){
			break;
		}
		int student[n];
		for(int i = 0; i < n; i++){
			cin >> student[i];
		}
		std::sort(student,student + n);
		int defference[n-1];
		for(int i = 0; i < n-1; i++){
			defference[i] = student[i+1] - student[i];
		}
		std::sort(defference, defference + (n-1));
		cout << defference[0] << endl;
  		
	}
return 0;
}


Measured memory_bytes: 3092
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;


int main()
{
	string a;
	cin >> a;
	for (int i = 0; i < 3; i++) {
		if (a.substr(i, 1) == "1")a.replace(i, 1, "9");
		else a.replace(i, 1, "1");

	}
	cout<<a<<endl;
    return 0;
}

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

using namespace std;

int main(){
    int a,b;
    char c;
    cin>>a>>c>>b;
    
    if(c=='+') cout<<a+b<<endl;
    else cout<<a-b<<endl;
    
    return 0;
}

Measured memory_bytes: 256
import sys


def main():
    N = int(input())

    for a in range(N // 4 + 1):
        for b in range(N // 7 + 1):
            if a * 4 + b * 7 == N:
                print("Yes")
                sys.exit()

    print("No")


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include "iostream"
#include<stdio.h>
using namespace std;

int main()
{
	int a, b, c,d;
	while (1)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)break;
		d = a + b; if (a == -1 || b == -1 || d < 30) {
			cout << 'F' << endl;
		}
		else {
			if (d >= 80)cout << 'A' << endl;
			if (80 > d &&d>= 65)cout << 'B' << endl;
			if (65 > d&&d >= 50)cout << 'C' << endl;
			if (50 > d &&d >= 30 && c < 50)cout << 'D' << endl;
			if (50 > d &&d >= 30 && c >= 50) { cout << 'C' << endl; }

		}
	}
	return 0;
}

Measured memory_bytes: 3108
import sys

def solve(N: int, p: "List[float]"):
    #dp[i][j]: i枚投げて、j枚表の確率
    dp=[[0]*(N+1) for _ in range(N+1)]

    dp[0][0]=1

    # dp[1][0]=dp[0][0]*p[1]
    # dp[1][1]=dp[0][0]*(1-p[1])

    # dp[2][0]=dp[1][0]*p[2]
    # dp[2][1]=dp[1][0]*(1-p[2])
    # dp[2][1]+=dp[1][1]*p[2]
    # dp[2][2]=dp[1][2]*(1-p[2])
    for i in range(1,N+1):
        for j in range(i):
            dp[i][j]+=dp[i-1][j]*p[i-1]
            dp[i][j+1]+=dp[i-1][j]*(1-p[i-1])
            #print("#",i,j,dp)

    ans=0
    for j in range(-(-N//2)):
        ans+=dp[N][j]

    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [float(next(tokens)) for _ in range(N)]  # type: "List[float]"
    solve(N, p)

if __name__ == '__main__':
    main()


Measured memory_bytes: 263176
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
#a.sort()
ans=0
#print(a)
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      if a[i]+a[j]>a[k] and a[j]+a[k]>a[i] and a[i]+a[k]>a[j]:
        if a[i]!=a[j] and a[j]!=a[k] and a[k]!=a[i]:  
          ans+=1
print(ans)
    

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


struct Point{
	double x,y;
};
Point point[16];

struct Data{
	double slope;
	int count;
};
Data data[8];

enum Type{
	FROM,
	TO,
};

int M;
int ans = 0;

double calc_slope(int a,int b){

	if(point[a].x == point[b].x){
		return DBL_MAX;
	}else{
		return (point[b].y-point[a].y)/(point[b].x-point[a].x);
	}
}

void recursive(int array[16],int pair[8][2],int num,Type type){

	if(num == M/2){

		int index = 0;
		double tmp_slope;

		bool FLG;

		for(int i = 0; i < M/2; i++){
			tmp_slope = calc_slope(pair[i][0],pair[i][1]);

			FLG = false;
			for(int k = 0; k < index; k++){
				if(fabs(data[k].slope-tmp_slope) < EPS){
					data[k].count++;
					FLG = true;
					break;
				}
			}
			if(FLG)continue;

			data[index].slope = tmp_slope;
			data[index].count = 1;
			index++;
		}

		int tmp_count = 0;
		for(int i = 0; i < index; i++){
			tmp_count += (data[i].count*(data[i].count-1))/2;
		}

		ans = max(ans,tmp_count);

		return;
	}

	if(type == FROM){
		for(int i = 0; i < M; i++){
			if(array[i] == -1){
				int next_array[16];
				for(int k = 0; k < M; k++)next_array[k] = array[k];
				next_array[i] = 1;
				int next_pair[8][2];
				for(int k = 0; k < num; k++){
					next_pair[k][0] = pair[k][0];
					next_pair[k][1] = pair[k][1];
				}
				next_pair[num][0] = i;
				recursive(next_array,next_pair,num,TO);
				break;
			}
		}
	}else{ //type == TO
		for(int i = 0; i < M; i++){
			if(array[i] == -1){
				int next_array[16];
				for(int k = 0; k < M; k++)next_array[k] = array[k];
				next_array[i] = 1;
				int next_pair[8][2];
				for(int k = 0; k <= num; k++){
					next_pair[k][0] = pair[k][0];
					next_pair[k][1] = pair[k][1];
				}
				next_pair[num][1] = i;
				recursive(next_array,next_pair,num+1,FROM);
			}
		}
	}
}


int main(){

	scanf("%d",&M);

	for(int i = 0; i < M; i++){
		scanf("%lf %lf",&point[i].x,&point[i].y);
	}

	int first_array[16],first_pair[8][2];
	for(int i = 0; i < M; i++)first_array[i] = -1;

	recursive(first_array,first_pair,0,FROM);

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

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

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

Measured memory_bytes: 3692
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    char s[100][101];
    
    rep(i, 3){
        scanf("%s", s[i]);
    }
    
    printf("A%cC", s[1][0]);
    
    return 0;
}



Measured memory_bytes: 1648
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 300005
#define mod 998244353
#define inf 1000000


int main()
{
    fastio;
    lli n,d;
    cin>>n>>d;
    lli ans=0;
    for(int i=0;i<n;i++){
        lli x,y;
        cin>>x>>y;
        if(x*x+y*y<=d*d)
        ans++;
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

LL calc(LL H, LL W) {
    LL res = LLINF;
    if (W >= 3) {
        LL one = W / 3;
        LL two = (W - one) / 2;
        LL three = W - one - two;
        VL v{one * H, two * H, three * H};
        chmin(res, *max_element(ALL(v)) - *min_element(ALL(v)));
    }
    FOR(w, 1, W / 2 + 2) {
        LL one = w * H;
        LL nokoriW = W - w;
        LL two = (H / 2)  * nokoriW;
        LL three = (H - (H / 2)) * nokoriW;
        VL v{one, two, three};
        chmin(res, *max_element(ALL(v)) - *min_element(ALL(v)));
    }
    return res;
}

int main(void) {
    LL H, W;
    cin >> H >> W;
    if (H % 3 == 0 || W % 3 == 0) {
        cout << 0 << endl;
        return 0;
    }
    cout << min(calc(H, W), calc(W, H)) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>

#define ll long long

using namespace std;

size_t N;
int M;
vector<int> pass1, passN;

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

    int a, b;

    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        if (a == 1) {
            pass1.push_back(b);
        } else if (b == N) {
            passN.push_back(a);
        }
    }

    sort(pass1.begin(), pass1.end());
    sort(passN.begin(), passN.end());

    size_t p1, pN;
    p1 = pN = 0;

    while (p1 < pass1.size() && pN < passN.size()) {
        if (pass1[p1] == passN[pN]) {
            cout << "POSSIBLE" << endl;
            return 0;
        } else if (pass1[p1] < passN[pN]) {
            p1++;
        } else {
            pN++;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 1276
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner stdIn=new Scanner(System.in);
		long a=stdIn.nextLong();
		long b=stdIn.nextLong();
		long x=stdIn.nextLong();
		long count=0;
		for(int i=0;i<=(b/x);i++){
			if((a<=x*i)&&(x*i<=b)){
			count++;
			count+=((b-x*i)/x);
			break;
		}
		}
		System.out.print(count);
	}
}

Measured memory_bytes: 9300
//C
#include <cassert>
//#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//ここまで標準include

using namespace std;

long aCb(long a, long b) {
	long out = 1;
	for (long i = 1; i <= b; i++) {
		out = out * (a + 1 - i) / i;
	}
	return out;
}

int main() {
	int n, a;
	cin >> n >> a;
	n %= 500;
	if (n <= a) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

int main(){
  int N,Q,l,r;
  string S;
  cin>>N>>Q>>S;
  int count;
  vector<int> vec(N);
  for(int i=1;i<N;i++){
    vec.at(i)+=vec.at(i-1);
    if(S.at(i-1)=='A'&&S.at(i)=='C')
      vec.at(i)++;
  }
  for(int i=0;i<Q;i++){
  	cin>>l>>r;
    cout<<vec.at(r-1)-vec.at(l-1)<<endl;
  }
}

Measured memory_bytes: 1408
#include<iostream>
using namespace std;
#define MAX 100000  // defineは文字列を指定した文字で置き換える。constは変数を格納している。
// 2分接点の各情報を出力する
int parent(int i) { return i / 2;}
int left(int i) { return 2 * i;}
int right(int i) { return 2 * i + 1;}

int main() {
  int H, i, A[MAX+1];  // 1-オリジンのため +1する

  cin >> H;
  for (i =1; i <= H; i++) cin >> A[i];

  for (i = 1;i <= H; i++) {
    cout << "node " << i << ": key = " << A[i] << ", ";
    // <<はストリームへの入力
    if (parent(i) >= 1 ) cout << "parent key = " << A[parent(i)] << ", ";
    if (left(i) <= H ) cout << "left key = " << A[left(i)] << ", ";
    if (right(i) <= H ) cout << "right key = " << A[right(i)] << ", ";
    cout << endl;
  }
}




Measured memory_bytes: 3100
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
void solve()
{
    string s;
    cin>>s;
    if(s[1]=='B')
    cout<<"ARC";
    else
    cout<<"ABC";
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_C 40
#define MAX_N 510

ll N, C;
ll D[MAX_C][MAX_C] = {};
ll Cm[MAX_N][MAX_N] = {};

// i を j にするコスト
ll dp[3][MAX_C] = {};

signed main()
{
    cin >> N >> C;
    REP(i, C) {
        REP(j, C) {
            cin >> D[i][j];
        }
    }
    REP(i, N) {
        REP(j, N) {
            cin >> Cm[i][j];
        }
    }

    // コスト事前計算
    REP(to, C) {
        REP(i, N) {
            REP(j, N) {
                ll pat = (i+j+2) % 3;
                ll from = Cm[i][j]-1;
                if(from != to) { dp[pat][to] += D[from][to]; }
            }
        }
    }

    // 全パターン試す
    ll ans = LLINF;
    for(ll zero = 1; zero <= C; ++zero) {
        for(ll one = 1; one <= C; ++one) {
            if(zero == one) { continue; }
            for(ll two = 1; two <= C; ++two) {
                if(two == zero || two == one) { continue; }
                ll cand = dp[0][zero-1] + dp[1][one-1] + dp[2][two-1];
                ans = min(ans, cand);
            }
        }
    }

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


Measured memory_bytes: 2304
#include <cstdio>

int n;
int a[100];
long long int s[100][21];

int main() {
	scanf("%d", &n);
	
	for(int i=0;i<n;i++) {
		scanf("%d", &a[i]);
	}
	
	for(int i=0;i<21;i++) {
		s[0][i] = 0;
	}
	
	s[0][a[0]] = 1;
	
	for(int i=1;i<n-1;i++) {
		for(int j=0;j<21;j++) {
			s[i][j] = 0;
			if(j+a[i]<=20) {
				s[i][j] += s[i-1][j+a[i]];
			}
			if(j-a[i]>=0) {
				s[i][j] += s[i-1][j-a[i]];
			}
		}
	}
	
	printf("%lld\n", s[n-2][a[n-1]]);
	
	return 0;
}

Measured memory_bytes: 1044
#include<stdio.h>

typedef struct{
  char mark;
  int number;
}Card;

int main(){
  int a,b,i,j,minj,num_card,stable1=1,stable2=1;
  Card card1[36],card2[36],check[36],swap;

  //??\???
  scanf("%d",&num_card);
  for(i = 0;i < num_card; i++){
    scanf(" %c%d",&card1[i].mark,&card1[i].number);
	}

  for(i = 0;i < num_card; i++){
    check[i] = card2[i] = card1[i];
 
	}

  //??????(BubbleSort)
  for(i = 0; i < num_card; i++){
    for(j = num_card-1; j > i; j--){
      if(card1[j].number < card1[j-1].number){

	swap = card1[j];
	card1[j] = card1[j-1];
	card1[j-1]= swap;
      } 
    }
  }
  for(i = 0; i < num_card; i++){
    for(j = i+1; j < num_card; j++){
      for(a = 0; a < num_card; a++){
	for(b = a+1; b < num_card; b++){
	  if(check[i].number == check[j].number && check[i].number == card1[b].number && check[i].mark == card1[b].mark && check[j].number == card1[a].number && check[j].mark == card1[a].mark){
	    stable1 = 0;
	  }
	}
      }
    }
  }
  //??????
  for(i = 0; i < num_card-1; i++){
    printf("%c%d ",card1[i].mark,card1[i].number);
  }
  printf("%c%d\n",card1[i].mark,card1[i].number);
  if(stable1 == 1){
    printf("Stable\n");
  }else{
    printf("Not stable\n");
  }
  

  //??????(SelectionSort)
  for(i = 0; i < num_card; i++){
    minj = i;
    for(j = i; j < num_card; j++){
      if(card2[j].number < card2[minj].number){
	minj = j;
      }
    }
    swap = card2[i];
    card2[i] = card2[minj];
    card2[minj] = swap;
      
   
  }
  
  for(i = 0; i < num_card; i++){
    for(j = i+1; j < num_card; j++){
      for(a = 0; a < num_card; a++){
	for(b = a+1; b < num_card; b++){
	  if(check[i].number == check[j].number && check[i].number == card2[b].number && check[i].mark == card2[b].mark && check[j].number == card2[a].number && check[j].mark == card2[a].mark){
	    stable2 = 0;
	  }
	}
      }
    }
  }

  //??????
  for(i = 0; i < num_card-1; i++){
    printf("%c%d ",card2[i].mark,card2[i].number);
  }
  printf("%c%d\n",card2[i].mark,card2[i].number);
  if(stable2 == 1){
    printf("Stable\n");
  }else{
    printf("Not stable\n");
  }

  return 0;
 
}

Measured memory_bytes: 1036
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#define int long long
using namespace std;

int countDivisibles(int A, int B, int M) { 
    int counter = 0; 
    for (int i = A; i <= B; i++) 
        if (i % M == 0) 
            counter++; 
  
    return counter; 
} 

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int l, r, d;
    cin >> l >> r >> d;
    cout << countDivisibles(l, r, d);

    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define PRINT(s) cout << s << endl;
#define FOR(i, a, b) for (unsigned int i = (a); i < (b); i++)
#define REP(i, n) FOR((i), 0, (n))

int contestsCount = 26;
int d;
vector<long long> c(contestsCount, 0);
vector<vector<long long>> s;
vector<int> t;
vector<int> lastDate(contestsCount, 0);

long long lastDateScore(int currentDate) {
    long long score = 0;
    REP(i, contestsCount) {
        score += c[i] * (currentDate - lastDate[i]);
    }
    return score;
}

long long scoring(int currentDateIndex, int contestNumber) {
    return s[currentDateIndex][contestNumber] - lastDateScore(currentDateIndex + 1);
}

int main() {
    cin >> d;
    REP(i, contestsCount) {
        cin >> c[i];
    }
    REP(i, d) {
        vector<long long> score(contestsCount);
        REP(j, contestsCount) {
            cin >> score[j];
        }
        s.push_back(score);
    }
    t = vector<int>(d);
    REP(i, d) {
        cin >> t[i];
    }
    long long totalScore = 0;
    REP(i, d) {
        lastDate[t[i] - 1] = i + 1;
        totalScore += scoring(i, t[i] - 1);
        PRINT(totalScore);
    }
}


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

#define F first
#define S second
#define pb push_back
#define ld  double
#define ll long long
#define int long long


using namespace std;

const int MAXN = 101 * 1001  , MOD = 1e9 + 7 , sq = 333  ;

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

    string s ;
    cin >> s;
    int n = s.size() , ans = 0 ;
    for(int l = 0 ; l < n ; l ++ )
    {
        for(int r = l ; r < n ; r ++ )
        {
            int x = 0 ;
            for(int i = l ; i <= r ; i ++)
                x = 10 * x + s[i]-'0' ;
            int L = 1 , R = 1 ;
            if(l>1)
                L = (1LL<<(l-1)) ;
            int w = n - r - 1 ;
            if(w>1)
                R = (1LL<<(w-1)) ;
            ans += x * L *  R ;
        }
    }
    cout<<ans;


}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;

int main(){
	int a,b;
	while(~scanf("%d %d",&a,&b)){
		if(a==b && b==0) break;

		int X,Y;
		if(a>=b){
			X = a;
			Y = b;
		}
		else{
			X = b;
			Y = a;
		}

		int count = 0;
		while(Y!=0){
			X = X % Y;
			swap(X,Y);
			count++;
		}

		printf("%d %d\n",X,count);
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <float.h>
using namespace std;

#define N 200000
 
int n;
int a[N];
int b[N];
int mb[N];

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

	for( int i = 0; i < 29; i++ ) {
		for( int j = 0; j < n; j++ ) {
			mb[j] = b[j] % (2 << i);
		}
		sort(mb, mb + n);
		int t = 1 << i;

		int cnt = 0;
		for( int j = 0; j < n; j++ ) {
			int ma = a[j] % (2 << i);
			cnt += lower_bound(mb, mb + n, 2 * t - ma) - lower_bound(mb, mb + n, t - ma);
			cnt += lower_bound(mb, mb + n, 4 * t - ma) - lower_bound(mb, mb + n, 3 * t - ma);
		}

		if (cnt % 2) {
			ans |= 1 << i;
		}
	}

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


Measured memory_bytes: 2560
H, W = map(int, raw_input().split())
# case 1
h1 = H / 3
h2 = (H - H / 3) / 2
h3 = H - h1 - h2
s = [h1 * W, h2 * W, h3 * W]
cand1 = max(s) - min(s)

# case 2
w1 = W / 3
w2 = (W - W / 3) / 2
w3 = W - w1 - w2
s = [w1 * H, w2 * H, w3 * H]
cand2 = max(s) - min(s)

# case 3
h1 = (W * H / 3) / W
h2 = H - h1
s = [h1 * W, h2 * W / 2, h2 * (W / 2 + W % 2)]
cand3 = max(s) - min(s)

# case 3'
h1 = (W * H / 3) / W + min(1, (W * H / 3) % W)
h2 = H - h1
s = [h1 * W, h2 * (W / 2), h2 * (W / 2 + W % 2)]
cand3d = max(s) - min(s)

# case 4
w1 = (W * H / 3) / H
w2 = W - w1
s = [w1 * H, w2 * (H / 2), w2 * (H / 2 + H % 2)]
cand4 = max(s) - min(s)

# case 4'
w1 = (W * H / 3) / H + min(1, (W * H / 3) % H)
w2 = W - w1
s = [w1 * H, w2 * (H / 2), w2 * (H / 2 + H % 2)]
cand4d = max(s) - min(s)

print min(cand1, cand2, cand3, cand3d, cand4, cand4d)

Measured memory_bytes: 2696
N = int(input())
pyramid_height = []
for _ in range(N):
    val = list(map(int, input().split()))
    pyramid_height.append(val)

pyramid_height.sort(key=lambda x: x[2], reverse=True)

for x in range(101):
    for y in range(101):
        tmp_h = pyramid_height[0][2] + abs(x - pyramid_height[0][0]) + abs(y - pyramid_height[0][1])
        for i in range(1, N):
            if pyramid_height[i][2] != max(tmp_h - abs(x - pyramid_height[i][0]) - abs(y - pyramid_height[i][1]), 0):
                break
        else:
            print(x, y, tmp_h)
            exit()




Measured memory_bytes: 9140
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
typedef pair<int, int> P;
typedef pair<P, int> PP;
const int MAX_N = 100010;

int par[MAX_N];
int Rank[MAX_N];
int size;

void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        Rank[i] = 0;
    }
    size = n;
}

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

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

    size--;
    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);
}
struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

const int MAX_E = 200020;

edge es[MAX_E];
int V, E;                   // 頂点数と辺数

int kruskal() {
    sort(es, es + E, comp); // edge.costが小さい順にソートする
    init(V);                 // Union-Findの初期化
    int res = 0;
    rep(i, E) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    PP p1[100010];
    rep(i, N) cin >> p1[i].first.first >> p1[i].first.second;
    rep(i, N) p1[i].second = i;
    sort(p1, p1 + N);
    V = N;
    E = (N - 1) * 2;
    rep(i, N - 1) {
        es[i].u = p1[i].second;
        es[i].v = p1[i + 1].second;
        es[i].cost = min(abs(p1[i].first.first - p1[i + 1].first.first), abs(p1[i].first.second - p1[i + 1].first.second));
    }
    rep(i, N) swap(p1[i].first.first, p1[i].first.second);
    sort(p1, p1 + N);
    rep(i, N - 1) {
        es[N - 1 + i].u = p1[i].second;
        es[N - 1 + i].v = p1[i + 1].second;
        es[N - 1 + i].cost = min(abs(p1[i].first.first - p1[i + 1].first.first), abs(p1[i].first.second - p1[i + 1].first.second));
    }
    cout << kruskal() << endl;



    
    return 0;
}


Measured memory_bytes: 8832
S=str(input())
T=str(input())
x=[]
y=[]
dic={}

for i in range(len(S)):
    x.append(S[i])
    y.append(T[i])
    
for s,t in zip(x,y):
    if s in dic:
        if dic[s]!=t:
            print("No")
            exit()
    else:
        dic[s]=t

if len(dic)!=len(set(dic.values())):
    print("No")   
else:
    print("Yes")             
            
        



Measured memory_bytes: 6716
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
struct UnionFind{
	int par[210],rank[210];
	void init(){
		for(int i=0;i<210;i++){par[i]=i;rank[i]=0;}
	}
	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[y]=x;
		else{
			par[x]=y;
			if(rank[x]==rank[y])rank[y]++;
		}
		return;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
}uf;
struct edge{
	int from,to,cost;
	edge(){}
	edge(int from,int to,int cost):from(from),to(to),cost(cost){}
	bool operator < (const edge& a) const{
		return cost < a.cost;
	}
};
int n,m,k;
vector<edge> A,B;
int cost,use_a_max,use_a_min,use;
void check(int x){
	uf.init();
	int p = 0,q = 0;
	cost = 0;
	use_a_max = 0;
	use = 0;
	while(p<A.size()||q<B.size()){
		edge e;
		bool flag = false;
		if(p==A.size())e = B[q++];
		else if(q==B.size()){
			e = A[p++];
			flag = true;
		}else{
			if(A[p].cost+x<=B[q].cost){
				e = A[p++];
				flag = true;
			}else e = B[q++];
		}
		if(!uf.same(e.from,e.to)){
			uf.unite(e.from,e.to);
			cost += e.cost;
			if(flag)use_a_max++;
			use++;
		}
	}
	uf.init();
	p = 0,q = 0;
	cost = 0;
	use_a_min = 0;
	use = 0;
	while(p<A.size()||q<B.size()){
		edge e;
		bool flag = false;
		if(p==A.size())e = B[q++];
		else if(q==B.size()){
			e = A[p++];
			flag = true;
		}else{
			if(A[p].cost+x<B[q].cost){
				e = A[p++];
				flag = true;
			}else e = B[q++];
		}
		if(!uf.same(e.from,e.to)){
			uf.unite(e.from,e.to);
			cost += e.cost;
			if(flag)use_a_min++;
			use++;
		}
	}
	return;
}
bool solve(){
	cin >> n >> m >> k;
	if(n==0&&m==0&&k==0)return false;
	A.clear();
	B.clear();
	for(int i=0;i<m;i++){
		int u,v,c;
		char l;
		cin >> u >> v >> c >> l;
		if(l=='A')A.pb(edge(u,v,c));
		else B.pb(edge(u,v,c));
	}
	sort(all(A));
	sort(all(B));
	for(int i=-105;i<=105;i++){
		check(i);
		//cout << i << ' ' << use_a_min << ' ' << use_a_max << ' ' << cost << endl;
		if(use_a_min<=k&&k<=use_a_max&&use==n-1){
			printf("%d\n",cost+i*use_a_min-i*k);
			return true;
		}
	}
	printf("-1\n");
	return true;
}
int main(){
	while(solve()){}
	return 0;
}


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

n, m = [int(x) for x in input().split()] 
g = [[] for _ in range(n)] 

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n 
    d[u] = 0
    pre = [-1] * n
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
                pre[i] = v + 1 
                
    return pre

d = bfs(0)
if all([i != None for i in d]):
    print("Yes")
    for i in range(1,n):
        print(d[i])
else:
    print("No")


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

public class Main{

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

  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      String[] lines = in.readLine().split(" ");
      int n = Integer.parseInt(lines[0]);
      int k = Integer.parseInt(lines[1]);

      // String line = in.readLine();
      // int offset=0,next=0;
      // char regx = ' ';
      int[] ax = new int[n];
      // for(int i=0; i<n; i++) {
      //   if((next = line.indexOf(regx,offset)) == -1)
      //     next = line.length();
      //   ax[i] = Integer.parseInt(line.substring(offset, next));
      //   offset = ++next;
      // }

      lines = in.readLine().split(" ");
      int m = 0;
      for (String s : lines) {
        ax[m++] = Integer.parseInt(s);
      }

      int min = Integer.MAX_VALUE;
      int sumF=0, sumB=0, sum=0;
      for(int i=0; i<n-k+1; i++) {
        sumF = Math.abs(ax[i]) + Math.abs(ax[i+k-1] - ax[i]);
        sumB = Math.abs(ax[i+k-1] + Math.abs(ax[i+k-1]) - ax[i]);
        sum = Math.min(sumF, sumB);
        if(i == 0 || sum < min) min = sum;
      }

      System.out.println(min);
    }
    catch(IOException e) {
      System.out.println(e);
    }
  }
}

Measured memory_bytes: 38228
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

signed main(){
    int h, w, d;
    cin >> h >> w >> d;

    vector<vector<int>> a(h+1, vector<int>(w+1));
    map<int, P> b;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
            b.insert(make_pair(a[i][j], make_pair(i, j)));
        }
    }

    vector<int> dist(h*w+1);
    for(int i = 1; i <= h*w; i++){
        if(i <= d){
            continue;
        }
        P p1 = b.at(i);
        P p2 = b.at(i-d);
        dist[i] = dist[i-d] + abs(p1.first - p2.first) + abs(p1.second - p2.second);
    }

    int q;
    cin >> q;

    rep(i, q){
        int l, r;
        cin >> l >> r;

        if(l == r){
            cout << 0 << endl;
            continue;
        }
        cout << dist[r] - dist[l] << endl;
    }
    return 0;
}


Measured memory_bytes: 9344