akhauriyash/Code-Regression huggingface dataset:
strs = ARGF.read.split
strs.shift
strs.map!{|v|v.split(//)}
if strs.size == 0
  puts
elsif strs.size == 1
  puts strs[0].sort.join
else
  ans = strs.inject(nil) do |dst, item|
    if !dst
      item
    else
      ret = []
      dst_ = dst.dup
      item.each do |c|
        if dst_.include?(c)
          ret << c
          i = dst_.index(c)
          dst_ = dst_[0...i] + dst_[(i+1)..-1]
        end
      end
      ret
    end
  end
  puts ans.sort.join
end

Measured memory_bytes: 2428
#include <iostream>

using namespace std;

int ans( int n){
    int result = 0;

    if( n == 0 || n%1000 == 0){

        result = 0;      

    } else if(n > 1000){

        result = 1000- (n%1000);

    } else {
        
        result = 1000 - n;
    }

    return result;

};

int main (){

    int n;

    cin >> n;

    cout << ans(n);

    return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n, m;
int x[100000];
int dx[100000];

signed main() {
	int i;
	
	cin >> n >> m;
	rep(i, m) cin >> x[i];
	sort(x, x + m);
	
	rep(i, m - 1) {
		dx[i] = x[i + 1] - x[i];
	}
	sort(dx, dx + m - 1, greater<int>());
	
	int toku = 0;
	rep(i, min(m - 1, n - 1)) {
		toku += dx[i];
	}
	
	cout << x[m - 1] - x[0] - toku << endl;
	return 0;
}

Measured memory_bytes: 1792
# internationalization という英単語は、i18n と略されることがあります。 
# これは、先頭文字 i と末尾文字 n の間に 18 文字が挟まっていることに由来します。
# 長さ 3 以上の英小文字のみからなる文字列 s が与えられます。 
# 同様の規則によって sを略してください。
array = gets.chomp.split("")
idx = 1
while idx < array.size - 2
  idx += 1
end
puts "#{array.first}#{idx}#{array.last}"

Measured memory_bytes: 1788
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = nc2(N)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in reversed(ans):
    print(v)

Measured memory_bytes: 127020
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var a = int.Parse(line[1]);
        var b = int.Parse(line[2]);
        line = Console.ReadLine().Trim().Split(' ');
        var w = Array.ConvertAll(line, long.Parse);
        var res = 0L;
        var pre = w[0];
        for (int i = 1; i < n; i++)
        {
            var te = w[i] - pre;
            res += Math.Min(te * a, b);
            pre = w[i];
        }
        Console.WriteLine(res);
    }
}


Measured memory_bytes: 18912
import java.util.*;

public class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);

    int a = sc.nextInt();
    int b = sc.nextInt();

    int tap = 1;
    int ans = 0;
    while (tap < b) {
      tap += a - 1;
      ans++;
    }
    
    System.out.println(ans);
  }
}


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

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

  double a, b, h, m;
  scanf("%lf %lf %lf %lf", &a, &b, &h, &m);

  double angle;
  double angle_h = (h*30)+(m/2);
  double angle_m = m*6;
  if(angle_h>angle_m){
    angle = angle_h - angle_m;
  }else{
    angle = angle_m - angle_h;
  }
  if(angle > 180.0L) angle = 360 - angle;

  double p = 3.141592653589793238462643383279L;
  double c = sqrt((a*a)+(b*b)-2*(a*b*cos(angle*p/180.0)));
  printf("%.20lf\n", c);

  return 0;
}


Measured memory_bytes: 2540
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    A, B, Q = map(int, readline().split())
    S = [-INF] + [int(readline()) for _ in range(A)] + [INF]
    T = [-INF] + [int(readline()) for _ in range(B)] + [INF]
    X = [int(readline()) for _ in range(Q)]

    ans = [INF] * Q
    for i, x in enumerate(X):
        idx_s = bisect_left(S, x)
        idx_t = bisect_left(T, x)

        for s in (S[idx_s - 1], S[idx_s]):
            for t in (T[idx_t - 1], T[idx_t]):
                ans[i] = min(ans[i], abs(x - s) + abs(s - t), abs(x - t) + abs(t - s))

    print('\n'.join(map(str, ans)))

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 35464
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	
	int n;
	cin >> n;
	vector<int> r(n);
	rep(i, n) cin >> r[i];
	int mn = r[0];
	int ans = -1001001001;
	for(int i = 1; i < n; i++){
		if(ans < r[i] - mn) ans = r[i] - mn;
		if(mn > r[i]) mn = r[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char s[5005], Str[15];
int arr[5005], chk[10005];
int K;

int Hash(char *str)
{
    long long hap = 37;
    int length;
    length = strlen(str);
    for(int i = 0; i < length; i++)
    {
        hap = (hap * 1234731 + str[i] - 'a') % 10001;
    }
    return hap;
}

bool comp(int t, int u)
{
    if(s[t] == s[u])
    {
        for(int i = 1; i < 5; i++)
        {
            if(s[t + i] == s[u + i])
            {
                continue;
            }
            return s[t + i] < s[u + i];
        }
    }
    return s[t] < s[u];
}

int main()
{
    int length;
    scanf("%s %d", s, &K);
    length = strlen(s);
    s[length] = 100;
    for(int i = 0; i < length; i++)
    {
        arr[i] = i;
    }
    sort(arr, arr + length, comp);
    int count = 0, sidx = 0;
    for(int i = 0; i < length; i++)
    {
        if(count == K)
        {
            printf("%s", Str);
            break;
        }
        if(arr[i] + count < length)
        {
            Str[sidx++] = s[arr[i] + count];
            Str[sidx] = 0;
            if(chk[Hash(Str)] == 1)
            {
                K++;
            }
            chk[Hash(Str)] = 1;
            count++;
            i--;
        }
        else
        {
            K -= count;
            count = 0;
            sidx = 0;
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int compare_int(const void *a,const void *b){
  return *(int*)a-*(int*)b;
}
int main(void){
  int a[3];
  scanf("%d%d%d",&a[0],&a[1],&a[2]);
  qsort(a,3,sizeof(int),compare_int);
  if(a[0]==5&&a[1]==5&&a[2]==7)
    printf("YES\n");
  else
    printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
import queue

class BreadthFirstSearch:
    def __init__(self, h, w, start_xy, goal_xy, board):
        self.h, self.w = h, w
        (self.sx, self.sy) = start_xy
        (self.gx, self.gy) = goal_xy
        self.board = board
        self.hist = [[False] * w for i in range(h)]

    def get_step(self, wall="#"):
        q = queue.Queue()
        q.put((self.sx, self.sy))
        step = 0
        count = 1
        next_count = 1
        ans = 0
        # キューが空になるまで
        while not q.empty():
            x, y = q.get()
            count -= 1
            if count == 0:
                step += 1
                count = next_count
                next_count = 0
            # ゴールにたどり着くまでのステップ
            if x == self.gx and y == self.gy:
                ans = step
                break
            for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if not(0 <= x+i <= w - 1) or not(0 <= y+j <= h - 1):
                    continue
                if self.board[y+j][x+i] == wall:
                    continue
                if self.hist[y+j][x+i]:
                    continue
                self.hist[y+j][x+i] = True
                q.put((x+i, y+j))
                next_count += 1
        return ans

# 図の形
h, w = map(int, input().split())
# スタート地点
s_xy = (0, 0)
# ゴール
g_xy = (w - 1, h - 1)
# ボードの読み込み
board = [[i for i in list(str(input()))] for i in range(h)]
# 既に通ったかどうか
bfs = BreadthFirstSearch(h, w, s_xy, g_xy, board)
ans = bfs.get_step()
count_black = 0
for y in range(h):
    for x in range(w):
        if board[y][x] == "#":
            count_black += 1
if ans == 0:
    print("-1")
else:
    print(h * w - ans - count_black)


Measured memory_bytes: 44008
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;

int main(){

    int n, m;
    cin >> n >> m;
    
    cout << n*(n-1)/2 + m*(m-1)/2 << endl;
}


Measured memory_bytes: 256
#pragma warning (disable:4996)
#include<stdio.h>

int main(void) {
	long long n;
	long long ans = 0;

	scanf("%lld", &n);

	ans = n * (n - 1) / 2;

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

/*
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1

*/


Measured memory_bytes: 128
/*
author : nit1n
*/
#include<bits/stdc++.h>
#define int long long
using namespace std ;


signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ;

	int d , t, s ; 
	cin >> d >> t >> s; 
	if(d <= s*t)
		cout << "Yes" ;
	else
		cout << "No" ; 	 
}


Measured memory_bytes: 3636
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main(void) {
	string s,x;
	int x_int,temp;
	int res = 10000;
	cin >> s;

	for(int i = 0; i < s.length()-2; i++){
		x[0] = s[i];
		x[1] = s[i+1];
		x[2] = s[i+2];
		x_int = stoi(x);

		if(x_int <= 753) temp = 753-x_int;
		else temp = x_int -753;

		if (temp < res) res = temp;
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const ll mod = 1e9+7;

int a,b,c;

int main()
{
    cin >> a >> b >> c;
    if(a+b == c || c+b == a || a+c == b) puts("Yes");
    else puts("No");
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
    int N, M;
    cin >> N >> M;
    vector<int> v(N);
    while(M--) {
        int a, b;
        cin >> a >> b;
        if(a == 1) {
            v[b]++;
        } else if(b == N) {
            v[a]++;
        }
    }

    if(*max_element(v.begin(), v.end()) >= 2) {
        cout << "POSSIBLE" << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}


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

typedef long long ll;

const int INF = 1e9;

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    for (int i=0;i<M;i++) {
        int A;
        cin >> A;
        sum += A;
    }
    if (N < sum) cout << -1 << "\n";
    else cout << N - sum << "\n";

    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
int x, y;
while(1){
  scanf("%d %d", &x, &y);
  if(x == 0 && y == 0) break;

if(x == 0 && y == 0){

}else if(x < y){
  printf("%d %d\n", x, y);
}else{
  printf("%d %d\n", y, x);
} 
}
return 0;
}


Measured memory_bytes: 1980
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A,B,C,X,Y,XY,bestsum;
    cin >> A >> B >> C >> X >> Y;
    bestsum=A*X+B*Y;

    for(XY=0;X>=0||Y>=0;XY++,X--,Y--){
        if(X<0)X=0;
        if(Y<0)Y=0;
        if(bestsum>A*X+B*Y+C*XY*2)bestsum=A*X+B*Y+C*XY*2;
    }

    cout << bestsum << endl;

    return 0;
}

Measured memory_bytes: 3608
w=int(input())
n=int(input())
d=[list(map(int,input().split(',')))for i in range(n)]

結果=[0]*w
for j in range(w):
	現在位置 = j + 1
	for k1,k2 in d:
		if 現在位置==k1:
			現在位置 = k2
		elif 現在位置==k2:
			現在位置=k1
	結果[現在位置-1]=j+1
print(*結果,sep='\n')


Measured memory_bytes: 5700
import sys
import pdb
input = sys.stdin.readline

N, W = map(int, input().split())
ws = [0]
vs = [0]

for _ in range(N):
  w, v = map(int, input().split())
  ws.append(w)
  vs.append(v)

inf = sum(ws)+1
V = int(sum(vs))   # N * max(vs)
# V = int(100 * 1e3)   # N * max(vs)
# Weight[i番目までの品番][価値j]
Weight = [[inf for _ in range(V+1)] for __ in range(N+1)]

if ws[1] <= W:
  Weight[1][vs[1]] = ws[1]
  value_max = vs[1]
else:
  value_max = 0

for _ in range(N+1):
  Weight[_][0] = 0

# pdb.set_trace()

for num in range(2, N+1):
  for value in range(1, V+1):
    if value >= vs[num]:   # 新しい品物を入れられるとき
      Weight[num][value] = min(Weight[num][value], Weight[num-1][value], Weight[num-1][value-vs[num]] + ws[num])
      if Weight[num][value] <= W:
        value_max = max(value_max, value)
      else:
        Weight[num][value] = inf
    else:   # 新しい品物を入れられないとき
      # 重さを変えることはできない
      Weight[num][value] = Weight[num-1][value]
      # Weight[num][value] = max(Weight[num][value], Weight[num-1][value])

# print(Weight)
print(value_max)


Measured memory_bytes: 178040
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long int N,M;
    cin >> N >> M;
    vector<long long int> loads(N,0);

    long long int a,b;
    for (long long int i = 0; i < M; ++i) {
        cin >> a >> b;
        loads[a-1] += 1;
        loads[b-1] += 1;
    }

    for(auto load : loads){
        cout << load << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int k, s, r=0;
	cin >> k>>s;
	for (int y=0; y<=k; y++){
		for (int z=0;z<=k;z++){
			int op=s-y-z;
			if (op >= 0 && op <= k) r++;
		}
	}
	cout << r;
	
	return 0;	
}

Measured memory_bytes: 256
#include<cstdio>

int p[200000];

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d", &p[i]), p[i]--;

    int res=0;
    for(int i=0; i<n; i++)
        if(p[i]==i)
            p[i+1] = p[i], res++;
    printf("%d\n", res);

    return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        int res = 0;
        if (k <= a) {
            System.out.println(k);
            return;
        }
        
        if (a + b >= k) {
            System.out.println(a);
            return;
        }

        int c2 = k - a - b;
        System.out.println(a - c2);
    }
}

Measured memory_bytes: 35828
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    println!("{}", v[0] * v[1]);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 2084
n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

print(ans)


Measured memory_bytes: 43580
def bellman_ford(n, s, edges, init_val = float('inf')): 
    d = [init_val] * n
    d[s] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    while updated: #閉路の存在
        updated = False
        for vf, vt, w in edges:
            if d[vt] > d[vf] + w:
                d[vt] = -float('inf')
                updated = True
    return d

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1,b-1,-w))
d = bellman_ford(n, 0, edges)
print(-d[-1] if d[-1] != -float('inf') else 'inf')


Measured memory_bytes: 74620
#00:12
import math

def sum_of_num(target,num):
    return (((2*target)/num)-num+1)/2


while True:
    target_num = int(input())
    if target_num ==0:
        break
    
    count = 0
    for i in range(2,int(target_num)):
        n = sum_of_num(target_num,i)
        if n.is_integer() and n >0:
            count = count + 1
    
    print(count)



Measured memory_bytes: 5660
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int K, T;
    cin >> K >> T;
    int a[T];
    for(int i=0;i<T;i++)
        cin >> a[i];

    int r = T, y = -1;
    if(r == 1){
        cout << K - 1 << endl;
        return 0;            
    }
    for(int i=0;i<K;i++){       // 全K日
        int max = 0, index;
        for(int j=0;j<T;j++){   // 全T種類
            if(a[j] > max && j != y){
                index = j;
                max = a[j];
            }
        }
        a[index]--;
        if(a[index] == 0)
            r--;
        if(r == 1){
            cout << K - i - 2 << endl;
            return 0;            
        }
        y = index;
    }
    
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<vector>
#include<algorithm>


#ifdef L_JUDGE
#pragma warning(disable:4996)
#endif

using namespace std;
const int MAXN=1005;


int main(){
	#ifdef L_JUDGE
		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
	#endif
    int W,A,B;
    cin>>W>>A>>B;
    int ans=0;
    if(B+W<A){
         ans=A-(B+W);
    }else if(A+W<B){
        ans=B-A-W;
    }
    printf("%d\n",ans);

	#ifdef L_JUDGE
		fclose(stdin);
		fclose(stdout);
//		system("out.txt");
	#endif

	return 0;
}


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

int main() {
    int N; cin >> N;
    int maxP = 0;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        int p; cin >> p;
        maxP = max(maxP, p);
        sum += p;
    }
    cout << (sum - (maxP/2)) << endl;
    
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
int main(){
    string s;
    int p=0;
    cin >> s;
    if(s.size()==1){
        cout << 0 << endl;
    }
    else{
        for(int i=0; i<(s.size()/2); i++){
            if(s.at(i)!=s.at(s.size()-1-i)) p++;
        }
        cout <<  p << endl;
    }
}

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


int main(){


    long long n, a, b, i;

    long long t = 0;

    vector< pair<long long, long long> > p;


    cin >> n;


    for( i = 0 ; i < n ; i = i + 1 ){

         cin >> a >> b;

         p.push_back( make_pair(b, a) );

         }


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


    for( i = 0 ; i < n ; i = i + 1 ){

         t += p[i].second;

         if( p[i].first < t ){

             cout << "No" << endl;

             return 0;

             }

         }


    cout << "Yes" << endl;

    
    return 0;


    }


Measured memory_bytes: 6544
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	int temp = a * b;
	if(temp % 2 == 0){
		cout << "No" << endl;
	}else{
		cout << "Yes" << endl;
	}
}

Measured memory_bytes: 256
//gauravsinghh
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 1000000000
#define lim 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define deb(x) cout << #x << " " << x << endl;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(ll i = a; i <= b; i++)
#define ffo(i, a, b) for(ll i = a; i >= b; i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
 
int main(){
    IOS
    //io_set();

    ll n, m  = 1e18;
    cin >> n;
    for(ll i = 1; i * i <= n; i++){
    	if(n%i == 0){
    		ll x = n/i;
    		ll ans = abs(x-1)+abs(i-1);
    		if(ans < m){
    			m = ans;
    		}
    	}
    }
    cout << m << endl;
    return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;
typedef pair<int,P> P2;
typedef pair<int,P2> P3;
const int MAX=1000000007;

int dy[4]={-1,0,1,0},dx[4]={0,-1,0,1};
bool check(int n,int m,int x,int y) {
  if(x<0 || x>=n) return false;
  if(y<0 || y>=m) return false;
  return true;
}
int d[1001][1001][4];
priority_queue<P3,vector<P3>,greater<P3> > que;

int main() {
  int n,m,k;
  while(cin >> n >> m >> k && (n||m||k)) {
    while(!que.empty()) que.pop();

    string c;
    string s[n];
    cin >> c;
    for(int i=0; i<n; i++) cin >> s[i];
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
	for(int l=0; l<4; l++) d[i][j][l]=MAX;
      }
    }

    int sx,sy,tx,ty;
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
	if(s[i][j]=='S') {
	  sx=i;sy=j;
	}
	if(s[i][j]=='G') {
	  tx=i;ty=j;
	}
      }
    }

    que.push(P3(0,P2(1,P(sx,sy))));
    d[sx][sy][1]=0;
    bool ck=false;
    while(!que.empty()) {
      P3 p=que.top();que.pop();
      int j=p.F,z=p.S.F,nx=p.S.S.F,ny=p.S.S.S;
      if(nx==tx && ny==ty) {
	ck=true;
	break;
      }


      int x=nx+dx[z],y=ny+dy[z];
      if(check(n,m,x,y) && s[x][y]!='#' && d[x][y][z]>j) {
	d[x][y][z]=j;
	que.push(P3(j,P2(z,P(x,y))));
      }
      
      x=nx;y=ny;
      int z2=z;
      bool b[4];
      memset(b,false,sizeof(b));
      b[z]=true;
      for(int i=j; i<k; i++) {
	if(c[i]=='L') z2--;
	else z2++;
	if(z2<0) z2+=4;
	else if(z2>=4) z2-=4;
	if(b[z2]) continue;
	b[z2]=true;
	if(d[x][y][z2]>i+1) {
	  d[x][y][z2]=i+1;
	  que.push(P3(i+1,P2(z2,P(x,y))));
	}
      }
    }
    if(ck) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}

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

#define ms(a,b) memset(a, b, sizeof(a))
#define rep(a,b,c) for(int a = (int)(b); a < (int)(c); a++)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define m_p(a,b) make_pair(a, b)
#define lson l,mid,o << 1
#define rson mid + 1,r,o << 1 | 1
#define ls o << 1
#define rs o << 1 | 1
#define inf 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

inline bool isdigit(char& ch) {
	return ch >= '0' && ch <= '9';
}
template<class T>
void read(T &x) {
	x = 0;
	ll f = 1;char ch = getchar();
	for (;!isdigit(ch);ch = getchar()) 
		if (ch == '-') f = -1;
	for (; isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + ch - '0';
	x *= f;
}
template<class T>
inline void write(T x) {
	if (x == 0) {putchar('0');return ;}
	if (x < 0) {putchar('-');x = -x;}
	int _stk[65],_top = 0;
	for (;x;x /= 10) _stk[++_top] = x % 10 + 48;
	for (;_top;_top--)putchar(_stk[_top]);
}

ll x[10];
ll ans;
int main () {
	rep(i, 1, 6) {
		cin >> x[i];
		if (x[i] == 0)
			ans = i;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3596
import sys
input = sys.stdin.readline
from itertools import product


def read():
    R, G, B, N = map(int, input().strip().split())
    return R, G, B, N


def solve(R, G, B, N):
    ans = 0
    for r, g in product(range(3001), range(3001)):
        v = N - R * r - G * g
        b = v // B
        if v >= 0 and B * b == v:
            ans += 1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 9228
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#include <ctime>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 1LL << 62
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

struct bit {
    vector<ll> v; // 部分和をbitで管理 仮想配列はa[1...n]
    bit(int n){ // bit(int n) : v(n + 1) {}
        v.resize(n + 1);
    }
    
    ll sum(int i){ // 仮想配列a[1]~a[i]の和を求める
        ll ret = 0;
        for(; i > 0; i -= i & -i){ // i & -i: iの1が立っている最高位bitをの2^を返す
            ret += v[i];
        }
        return ret;
    }
    
    void add(int i, ll w) { // index:iにwを加える
        for (; i < v.size(); i += i & -i) {
            v[i] += w;
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> S(N + 1);
    rep(i, N) {
        cin >> S[i + 1];
        S[i + 1] -= K;
        S[i + 1] += S[i];
    }
    
    vector<ll> T = S;
    sort(all(T));
    map<ll, int> M;
    rep(i, N + 1) {
        if (i && T[i] == T[i - 1]) continue;
        M[T[i]] = i + 1;
    }
    
    bit B(N + 1);
    B.add(M[0], 1);
    ll ans = 0;
    rep(i, 1, N + 1) {
//        cout << M[S[i]] << ":" <<  B.sum(M[S[i]]) << endl;
        ans += B.sum(M[S[i]]);
        B.add(M[S[i]], 1);
    }

    output(ans);
    
    
    return 0;
}


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

int main(void){

    double N,D;
    double X,Y;
    double total;
    double count = 0;

    scanf("%lf %lf",&N,&D);

    for(int i = 0;i < N;i++){

        scanf("%lf %lf",&X,&Y);

        total = sqrt((X * X) + (Y * Y));

        if(total <= D){
            count++;
        }
    }

    printf("%.0lf\n",count);

    return 0;
}

Measured memory_bytes: 2216
#include<bits/stdc++.h>
using namespace std;
int n,a[4][4],b[111];
bool v[4][4];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            a[i][j]=read();
    n=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=n;k++)
                if(a[i][j]==b[k]) v[i][j]=1;
    for(int i=1;i<=3;i++){
        bool flag=1;
        for(int j=1;j<=3;j++)
            if(!v[i][j]) flag=0;
        if(flag) return puts("Yes"),0;
    }
    for(int i=1;i<=3;i++){
        bool flag=1;
        for(int j=1;j<=3;j++)
            if(!v[j][i]) flag=0;
        if(flag) return puts("Yes"),0;
    }
    if(v[1][1]&&v[2][2]&&v[3][3]) return puts("Yes"),0;
    if(v[1][3]&&v[2][2]&&v[3][1]) return puts("Yes"),0;
    puts("No");
    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>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

combination comb(2005);
mint f(int n, int k) {
    return comb(n-1,k-1);
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        //mint red = f(n-k,i+1) + f(n-k,i)*2 + f(n-k,i-1);
        mint red = comb(n-k+1, i);
        mint blue = f(k,i);
        mint ans = red * blue;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <iterator>  // std::back_inserter()
#include <set>
#include <algorithm>  // std::copy()
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
using namespace std;

#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for (int i=0; i < (int)(n); i++)  // 0 ~ n-1
#define REPN(i, n) for (int i=1; i <= (int)(n); i++)  // 1 ~ n
#define MIN(vec) min_element(ALL((vec)))  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(ALL((vec)))
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(ALL((vec)), 0)  // 0 は初期値
#define COPY(vec1, vec2) copy(ALL(vec1), back_inserter(vec2))  // vec1をvec2にコピーする vec2は空にしておく必要あり
typedef long long ll;

const int MOD = 1000000007;  // 1 000 000 007

template <class T>
void print2DVec(vector< vector<T>> &vec) {
    size_t len = vec.size(), front = vec.front().size();
    REP(i, len) {
        REP(j, front) {
            cout << vec[i][j];
        }
        cout << "\n";
    }
    cout << "\n";
}


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

    // input
    int W, H, N;
    cin >> W >> H >> N;
    W;
    H;
    vector< vector<int> > plane(W, vector<int>(H, 0));  // (N, M) array 0で初期化
    vector< vector<int> > vec(N, vector<int>(3));  // (N, M) array 0で初期化
    REP(i, N) cin >> vec[i][0] >> vec[i][1] >> vec[i][2];
    
    // calc
    vector<int> point;
    int x_min = 0, x_max = W, y_min = 0, y_max = H;
    int x , y, a;
    REP(i, N) {
        point = vec[i];
        x = point[0];
        y = point[1];
        a = point[2];
        
        if (a == 1) {
            x_min = max(x_min, x);
        } else if (a == 2) {
            x_max = min(x_max, x);
        } else if (a == 3) {
            y_min = max(y_min, y);
        } else if (a == 4) {
            y_max = min(y_max, y);
        }
    }
    int width = x_max - x_min;
    int height = y_max - y_min;
    int w = (width >= 0)? width: 0;
    int h = (height >= 0)? height: 0;
    cout << w * h << "\n";
    
    return 0;
}


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

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

  bool ok = false;
  for (int i = 0; i <= N; i += 4) {
    for (int j = 0; j <= N; j += 7) {
      if (i + j == N) {
        ok = true;
        goto LOOPEND;
      }
    }
  }

LOOPEND:
  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
// コーナーケース（全部A,全部B）のときの中央値
// 何か一つの値が1増えることで左から右にうつると、
// 中央値はNが奇数のとき1,偶数のとき1/2増える
#include <bits/stdc++.h>
using namespace std;

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

using ll = long long;
using ull = unsigned long long;
using veci = vector<int>;
using vecll = vector<ll>;
using vecull = vector<ull>;

ll N;
vecll A, B;

int main(void) {
    cin >> N;

    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        A.emplace_back(a);
        B.emplace_back(b);
    }

    sort(ALLOF(A));
    sort(ALLOF(B));

    long double amed = A[N / 2];
    long double bmed = B[N / 2];
    if (N % 2 == 0) {
        amed = (A[N / 2] + A[N / 2 - 1]);
        bmed = (B[N / 2] + B[N / 2 - 1]);
    }

    ll ans = bmed - amed + 1;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6572
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int w[401000], P[401000];
long long K, Nxt[201000][41];
int U[401000], C[401000];
int main() {
	int i, j;
	scanf("%d%lld", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		w[n + i] = w[i];
	}
	for (i = n + n; i >= 1; i--) {
		if (i <= n) {
			Nxt[i - 1][0] = P[w[i]] - (i - 1);
		}
		P[w[i]] = i;
	}
	for (i = 0; i < 40; i++) {
		for (j = 0; j < n; j++) {
			Nxt[j][i+1] = Nxt[j][i] + Nxt[(j+Nxt[j][i])%n][i];
		}
	}
	long long s = 0;
	int cur = 0;
	for (i = 40; i >= 0; i--) {
		while (s + Nxt[cur][i] <= n*K) {
			s += Nxt[cur][i];
			cur = s % n;
		}
	}
	if (s == n * K) {
		return 0;
	}
	int cnt = 0;
	for (long long ii = s; ii < n * K; ii++) {
		int t = w[ii % n + 1];
		if (C[t]) {
			while (C[t]) {
				cnt--;
				C[U[cnt]]--;
			}
		}
		else {
			U[cnt++] = t;
			C[t]++;
		}
	}
	for (i = 0; i < cnt; i++)printf("%d ", U[i]);
}

Measured memory_bytes: 71296
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		// 0を取り除いた文字列の長さを調べる
		s = s.replaceAll("0", "");
		System.out.println(s.length());
	}
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q;
    cin>>q;
    ll con=0;
    ll cnt=0;
    ll now;
    ll sl=0,sr=0;
    multiset<ll> l,r;
    rep(i,q){
      int c;
      cin>>c;
      if(c==1){
        ll a,b;
        cin>>a>>b;
        con+=b;
        if(cnt==0){
          l.insert(a);
          r.insert(a);
          sl+=a;
          sr+=a;
          now=a;
          cnt++;
          continue;
        }
        if(cnt%2==0){
          if(now<a){
            sr-=*begin(r);
            r.erase(begin(r));
            r.insert(a);
            sr+=a;
            now=*begin(r);
            l.insert(now);
            sl+=now;
          }else{
            l.insert(a);
            sl+=a;
          }
        }else{
          if(now<=a){
            r.insert(a);
            sr+=a;
          }else{
            auto itr=end(l);
            itr--;
            l.erase(itr);
            sl-=*itr;
            l.insert(a);
            sl+=a;
            itr=end(l);
            itr--;
            now=*itr;
            r.insert(now);
            sr+=now;
          }
        }
        cnt++;
      }else{
        ll ans=con;
        ans+=sr-now*len(r);
        ans+=now*len(l)-sl;
        cout<<now<<' '<<ans<<endl;
      }
    }
}

Measured memory_bytes: 9600
def LI():return list(map(int,input().split()))

n=int(input())

def main(n):
    ans=0
    from math import floor
    
    def f(n):
        return n*(n+1)*(2*n+1)//6
        
    for m in range(1,floor(n**0.5)+1):
        tmp=m*(m+floor(n/m))*(floor(n/m)+1-m)
        ans+=tmp
        
    return (ans-f(floor(n**0.5)))

print(main(n))


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

int main() {
    int n, x;
    cin >> n >> x;
    int l[n];
    for (int i = 0; i < n; i++)
        cin >> l[i];
    
    int ans = 1, d = 0;
    for (int i = 0; i < n; i++) {
        d += l[i];
        if (d > x) {
            cout << ans << endl;
            return 0;
        }
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
int n;
ll ans;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    ans+=n/500 *1000;
    ans+=(n%500)/5 * 5; 
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9+7;
//const ll MOD = 998244353;
//const ll MOD = 924844033;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
const double EPS = 1e-5;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

#ifdef DEBUG
#define OUTPUT(x) (output(x), outendl())
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}


int main(){
	int n,u,v;
	cin >> n >> u >> v;
	--u;
	--v;
	vvector<int> edges(n);
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		--a;
		--b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	vector<int> tf(n,INF);
	vector<int> af(n,INF);
	tf[u] = 0;
	af[v] = 0;
	stack<int> st;
	st.push(v);
	while(st.size()){
		int d = st.top();
		st.pop();
		foreach(i,edges[d]){
			if(af[i] <= af[d] + 1)continue;
			af[i] = af[d] + 1;
			st.push(i);
		}
	}
	int ans = 0;
	st.push(u);
	while(st.size()){
		int d = st.top();
		st.pop();
		chmax(ans,af[d] - 1);
		foreach(i,edges[d]){
			if(tf[i] <= tf[d] + 1)continue;
			tf[i] = tf[d] + 1;
			if(tf[i] >= af[i])continue;
			st.push(i);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define mod (int)1e9+7
#define inf (int)1e16
#define rep(i,n) for (int i = 0; i < n; i++)
#define Rep(i,n) for (int i = n; i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define cend cout<<endl;
#define P pair<int, int>
#define F first
#define S second
#define prique priority_queue<P, vector<P>, greater<P>>
using namespace std;

string s;
int k;
vector<int> ta;

signed main() {
	cin>>s>>k;
	rep(i,(int)s.size()){
		if(s[i]=='a')ta.push_back(0);
		else ta.push_back(26-(s[i]-'a'));
	}
	rep(i,(int)ta.size()){
		if(ta[i]<=k){
			k-=ta[i];
			s[i]='a';
		}
	}
	k%=26;
	s[(int)s.size()-1]=s[(int)s.size()-1]+k;
	cout<<s<<endl;
}


Measured memory_bytes: 1528
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String b = sc.next();
        sc.close();

        Map<String, String> map = new HashMap<>();
        map.put("A", "T");
        map.put("T", "A");
        map.put("C", "G");
        map.put("G", "C");
        System.out.println(map.get(b));
    }

}


Measured memory_bytes: 21716
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll INF = 9223372036854775807/2;
const int MOD = 1000000007;
const int N_MAX = 3 * pow(10,3) + 10;

vector<vector<double>> dp(N_MAX, vector<double>(N_MAX, -1));
vector<double> coin(N_MAX, 0);

double dfs(int n, int f) {
  if (n==0) {
    if (f==0) return dp[n][f] = 1;
    else return dp[n][f] = 0;
  }
  if (dp[n][f]>=0) return dp[n][f];
  double result = 0;
  if (f!=0) result += dfs(n-1, f-1) * coin[n-1];
  result += dfs(n-1, f) * (1-coin[n-1]);
  return dp[n][f] = result;
}

int main() {
  int N; cin >> N;
  rep(i, N) cin >> coin[i];

  rep(i, N+1) dfs(N, i);
  // rep(i, N+1) { rep(j, N+1) {cout << dp[i][j] << " ";} cout << endl; }
  double result = 0; for (int i=N; i>N-i; i--) { result+=dp[N][i]; }
  cout << fixed << setprecision(10) << result << endl;
  return 0;
}

Measured memory_bytes: 73344
n = int(input())
num_list = list(map(int, input().split()))
m = {}
for i in range(-1, 10**5+2):
    m[i] = 0
for i in num_list:
    m[i-1] += 1
    m[i] += 1
    m[i+1] += 1
ans_list = m.values()
print(max(ans_list))

Measured memory_bytes: 20468
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n,k;
	scanf("%lld%lld",&n,&k);
	ll cnt=n/k;
	ll ans=cnt*cnt*cnt;
	if(k%2==0){
		ll x=(n-(k/2))/k+1;
		if(n<k/2){
			x=0;
		}
		ans+=x*x*x;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (ll i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  FOR(i, 1, n + 1) {
    if (i * (i + 1) / 2 >= n) {
      FOR(j, 1, i + 1) {
        if (j != i * (i + 1) / 2 - n) cout << j << endl;
      }
      return 0;
    }
  }


  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a,b,c,m,g;
int gcd(int a, int b, int c){
m = min({a,b,c})+1;
for(int i=1; i < m; i++){
  if (a % i == 0 && b % i == 0 && c % i == 0){
      g = i;
  }
}
return g;
}

int main(){
  int K,S;
  S=0;
  cin >> K;
  for (int i =1; i < K+1; i++){
    for (int j =1; j < K+1; j++){
      for (int k =1; k < K+1; k++){
        S += gcd(i,j,k);
      }
    }
  }
  cout << S << endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define rep(i,a,b) for (rg int i=(a);i<=(b);i++)
#define per(i,a,b) for (rg int i=(b);i>=(a);i--)
#define pb push_back
#define lowbit(x) (x&(-x))
#define mk make_pair
#define VI vector<int>
#define pii pair<int,int>
#define pLL pair<long long,long long>
#define fi first
#define se second
#define il inline
#define ll long long
#define db double
#define ld long double
#define inf 0x3f3f3f3f
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<15,stdin),p1==p2)?EOF:*p1++)
char buf[1<<15],*p1 = buf,*p2 = buf;
inline ll read(){
    #define num ch-'0'
    char ch;bool flag=0;ll res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10ll+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
inline void write(ll x){
	if (x < 0) x = ~x + 1ll, putchar('-');
	if (x > 9) write(x / 10ll);
	putchar(x % 10ll + '0');
}
#define mid ((l + r)>>1)
#define ls (x<<1)
#define rs ((x<<1)|1)
#undef mid
#undef ls
#undef rs
#define maxn 1010
ll dp[maxn][1<<12];
void solve()
{
	int n = read(),m = read();
	rep(i,0,m) rep(j,0,(1<<n)-1) dp[i][j] = inf;
	dp[0][0] = 0;
	rep(i,1,m)
	{
		ll cost = read();
		int K = read();
		int x = 0;
		rep(i,1,K)
		{
			int v = read();
			x|=(1<<(v-1));
		}
		rep(k,0,(1<<n)-1)
		{
			dp[i][k] = min(dp[i][k],dp[i-1][k]);
			dp[i][k|x] = min(dp[i][k|x],dp[i-1][k] + cost);
		}
	}
	cout<<(dp[m][(1<<n)-1] >=inf?-1:dp[m][(1<<n)-1]);
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("data.txt","r",stdin);
	#endif
//	int T = read();
//	while(T--)
	solve();
}

Measured memory_bytes: 35664