akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef priority_queue<long long> prque;
#define ain(i,n,a) for(long long i=0;i<(long long)(n);i++){cin>>a[i];}
#define aout(i,n,a) for(long long i=0;i<(long long)(n);i++){if(i){cout<<" ";}cout<<a[i];if(i==n-1){cout<<endl;}}
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define vsort(v) sort((v).begin(),(v).end())
#define vrsort(v) sort((v).rbegin(),(v).rend())
#define vreverse(v) reverse((v).begin(),(v).end())
#define pf(a) push_front(a)
#define pb(a) push_back(a)
#define INF 1998021900
#define MOD 1000000007
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //input
  ll s;cin>>s;
  if(s<1000000001){cout<<0<<" "<<0<<" "<<1<<" "<<0<<" "<<0<<" "<<s<<endl;return 0;}
  cout<<0<<" "<<0<<" ";
  ll a,b,c,d;//|a*d-c*d|=s
  ll sq=sqrt(s)+1;
  if((sq<1000000001)&&((sq*sq-s)<1000000001)){
  a=sq;d=sq;c=a*d-s;b=1;
  cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
  return 0;
  }
  ll h=1000000000000000000-s;
  if(h<1000000001){
  cout<<1000000000<<" "<<1<<" "<<h<<" "<<1000000000<<endl;
  return 0;
  }
  if(s%2==0){cout<<1000000000<<" "<<2<<" "<<500000000000000000-(s/2)<<" "<<1000000000<<endl;
  return 0;}
  if(s%3==0){cout<<1000000000<<" "<<3<<" "<<(1000000000000000000-s)/3<<" "<<1000000000<<endl;
  return 0;}
  if(s%5==0){cout<<1000000000<<" "<<5<<" "<<(1000000000000000000-s)/5<<" "<<1000000000<<endl;
  return 0;}
}

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

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}} End

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

    size_t N; cin >> N;
    string s, t; cin >> s >> t;

    size_t res = 2 * N;
    for (size_t i = 0; i < N; ++i) {
        string value1(s, i, N - i);
        string value2(t, 0, N - i);
        if (value1 == value2) {
            return cout << res - (N - i) << "\n", 0;
        }
    }

    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <array>
#include <deque>
#include <bitset>
typedef long long ll;
using namespace std;
#define trace(x) cerr << #x << " is " << x << endl;

int main() {
    string s, t;
    cin >> s >> t;
    int n, m;
    cin >> n >> m;
    string u;
    cin >> u;
    if (u == s) {
        n -= 1;
    } else if (u == t) {
        m -= 1;
    }
    cout << n << " " << m <<endl;
    return 0;
}

Measured memory_bytes: 256
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use proconio::*;
use text_io::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    input! {
        x:isize,
        k:usize,
        d:usize,
    }

    let x = x.abs() as usize;

    let a = x / d;
    let b = x % d;

    if a > k {
        println!("{}", x - k * d);
        return;
    }

    if (k - a) % 2 == 0 {
        println!("{}", b);
    } else {
        println!("{}", d - b);
    }
}


Measured memory_bytes: 2128
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 自分のグループの頂点数を取得
    def size(self,x):
        return -self.parents[self.find(x)]

    def connect(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return False
        
        # 大きい方(A)に小さい方(b)をくっつけたい
        # 大小が逆ならひっくり返す
        if self.parents[a] > self.parents[b]:
            a,b = b,a

        self.parents[a] += self.parents[b]
        self.parents[b] = a
        return True

n, m = map(int,input().split())

A = [0] * m
B = [0] * m
ans = [0]*m
ans[m-1] = n * (n-1) / 2


for i in range(m):
    A[i],B[i] = map(int,input().split())
    A[i] -= 1
    B[i] -= 1


Uni = UnionFind(n)

#for i in reversed( range(1, m-1 ) ):
for i in range(m-1, 0, -1):
    ans[i-1] = ans[i]
    if Uni.find(A[i]) != Uni.find(B[i]):
        ans[i - 1] -= Uni.size(A[i]) * Uni.size(B[i])
        Uni.connect(A[i], B[i])

for i in range(m):
    print(int(ans[i]))


Measured memory_bytes: 16252
import sys,random
try: sys.stdin = open('in.in','r')
except: pass

ans = 0
allboth = 1
l = r = 0

n = int(input())
for i in range(n):
	s = input().strip()
	ans += s.count('AB')
	if s[0] == 'B' or s[-1] == 'A':
		l += s[0] == 'B'
		r += s[-1] == 'A'
		if s[0] != 'B' or s[-1] != 'A':
			allboth = 0

ans += min(l,r)
if allboth and l:
	ans -= 1
print(ans)


Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<ii> vii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fr(be, en) for(int i = be; i <= en; i++) 
ll mod = LLONG_MAX;
ll power(ll a, ll b)
{
	if(b == 0) return 1;
	ll ans = power(a, b/2);
	ans = (ans*ans)%mod;
	if(b%2) ans*=a;
	return ans%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	int n, val; cin >> n;
	vi v(n + 1, 0);
	// v[1] = 1;
	fr(2, n)
	{
		cin >> val;
		v[val]++;
	}
	fr(1, n) cout << v[i] << "\n";
}

Measured memory_bytes: 3988
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
int n,k;
int x;
p_queue q;
ll res;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>k,k=min(k,n);
	for(int i=0;i<n;i++)cin>>x,q.push(x);
	while(k--)q.pop();
	while(q.size())res+=q.top(),q.pop();
	cout<<res;
	return 0;
}


Measured memory_bytes: 1400
n=gets.to_i
ab=[]
n.times do|i|
	ab[i]=gets.chomp.split(" ").map(&:to_i)
end
def Quick_sort(list,l,r)
	i=l+1
	k=r
	while(i<k)
		while(list[i][1]<list[l][1] and i<r)
			i+=1
		end
		while(list[k][1]>=list[l][1] and k>l)
			k-=1
		end
		if(i<k)
			w=list[i]
			list[i]=list[k]
			list[k]=w
		end
	end
	if(list[l][1]>list[k][1])
		w=list[l]
		list[l]=list[k]
		list[k]=w
	end
	Quick_sort(list,l,k-1) if(l<k-1)
	Quick_sort(list,k+1,r) if(k+1<r)
	return list
end
ab=Quick_sort(ab,0,n-1)
taskT=0
flag=false
n.times do|i|
	taskT+=ab[i][0]
	if(taskT>ab[i][1])
		flag=true
		break
	end
end
print(flag ? "No" : "Yes")

Measured memory_bytes: 16252
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	if (s == "Sunny")
		cout << "Cloudy\n";
	else if (s == "Cloudy")
		cout << "Rainy\n";
	else
		cout << "Sunny\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51},K;
    cin>>K;
    cout<<a[K-1];
}


Measured memory_bytes: 256
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

using i8 = ::std::int_least8_t;
using i32 = ::std::int_least32_t;
using i64 = ::std::int_least64_t;
using u8 = ::std::uint_least8_t;
using u32 = ::std::uint_least32_t;
using u64 = ::std::uint_least64_t;
using isize = ::std::ptrdiff_t;
using usize = ::std::size_t;

template <class T = usize> class rep {
	const T f, l;

public:
	class itr {
		friend rep;
		T i;
		constexpr itr(T x) noexcept : i(x) {}

	public:
		void operator++() noexcept { ++i; }
		constexpr T operator*() const noexcept { return i; }
		constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	constexpr rep(const T first, const T last) noexcept : f(first), l(last) {}
	constexpr itr begin() const noexcept { return itr(f); }
	constexpr itr end() const noexcept { return itr(l); }
};
template <class T = usize> class revrep {
	const T f, l;

public:
	class itr {
		friend revrep;
		T i;
		constexpr itr(T x) noexcept : i(x) {}

	public:
		void operator++() noexcept { --i; }
		constexpr T operator*() const noexcept { return i; }
		constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	constexpr revrep(const T first, const T last) noexcept : f(first), l(last) {}
	constexpr itr begin() const noexcept { return itr(l - 1); }
	constexpr itr end() const noexcept { return itr(f - 1); }
};
template <class T> bool amax(T &a, const T &b) {
	return a <= b ? (a = b, 1) : 0;
}
template <class T> bool amin(T &a, const T &b) {
	return b <= a ? (a = b, 1) : 0;
}
template <class T> bool samax(T &a, const T &b) {
	return b <= a ? 0 : (a = b, 1);
}
template <class T> bool samin(T &a, const T &b) {
	return a <= b ? 0 : (a = b, 1);
}
template <class T> using vec_alias = ::std::vector<T>;
template <class T> auto md_vec(usize n, const T &value) {
	return ::std::vector<T>(n, value);
}
template <class... Args> auto md_vec(usize n, Args... args) {
	return ::std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> const T &as_const(const T &v) noexcept { return v; }
template <class T> constexpr T difference(const T &a, const T &b) {
	return a <= b ? b - a : a - b;
}

#include <cstddef>

template <class T> T power(T x, u64 exp) {
	T ret = 1;
	while (exp) {
		if (exp & 1)
			ret *= x;
		exp >>= 1;
		x *= x;
	}
	return ret;
}


#include <algorithm>
#include <iostream>
#include <utility>
#include <cmath>
#include <limits>
#include <stack>

int main() {
	usize n;
	::std::cin >> n;
	while (n--) {
		u32 a;
		::std::cin >> a;
		if (a & 1) {
			::std::cout << "first" << ::std::endl;
			return 0;
		}
	}

	::std::cout << "second" << ::std::endl;
	return 0;
}


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

int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if ((b - a) % 2 == 1) {
		ll x = min(a - 1, n - b) + 1 + (b-a-1)/2;
		cout << x << endl;
	}
	else {
		ll y = (b - a) / 2;
		cout << y << endl;
	}
}

Measured memory_bytes: 256
open Printf
open Scanf

let rec loop x fn =
  match fn x with
  | `Break x -> x
  | `Continue x -> loop x fn

let ( |- ) x f = f x; x
let flip f a b = f b a

module Int = struct
  include Int64
  module Infix = struct 
    let ( + ) = add and ( - ) = sub
    and ( * ) = mul and ( / ) = div
  end
end

let () =
  let read_ints () =
    let str = loop (Buffer.create 10) begin fun buf ->
        try 
          `Continue (buf |- (flip Buffer.add_bytes)
                       (read_line () ^ " "))
        with _ ->
          `Break (buf |> Buffer.contents) end in
    str |> Str.(split (regexp " ")) |> List.map int_of_string in

  let num:: avg:: xs = read_ints () in
  let xs = xs |> Array.of_list in

  let cache, cached, get = let open Hashtbl in
    let memo = create 10 in
    let cache = replace memo in
    let cached = mem memo in
    let get = find memo in
    cache, cached, get in

  let rec solve ~sum ~cnt ~idx : Int64.t =
    if cached (sum, cnt, idx)
    then get (sum, cnt, idx)
    else if idx >= num
    then if cnt != 0 && cnt * avg = sum then 1L else 0L
    else
      let idx' = idx + 1 in
      let sum' = sum + xs.(idx) and cnt' = cnt + 1 in
      let open Int.Infix in
      let ans = solve ~sum ~cnt ~idx: idx'
                + solve ~sum: sum' ~cnt: cnt' ~idx: idx' in
      ans |- cache (sum, cnt, idx) in

  let sum = 0 and cnt = 0 and idx = 0 in
  let ans = solve ~sum ~cnt ~idx in
  printf "%Ld\n" ans


Measured memory_bytes: 44028
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = [0]*(N+1)
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

from collections import deque

todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    ans[x] += ans[parent]
    for next in tree[x]:
        if next == parent:
            continue
        else:
            todo.append((next,x))
            
answer = ' '.join(map(str,ans[1:]))
print(answer)

Measured memory_bytes: 65636
def check_a(numbers):
    if numbers.count(5) == 2 and numbers.count(7) == 1:
        return 'YES'
    else:
        return 'NO'


def main():
    numbers = list(map(int, input().split()))
    print(check_a(numbers=numbers))


if __name__ == '__main__':
    main()


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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define endl "\n"
typedef long long LL;
const int mod = 1e9 + 7;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 1e5 + 5;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    //freopen("input.txt", "r", stdin);
  #endif // LOCAL
  int n;
  cin >> n;
  set <int> S;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    S.insert(x);
  }
  if ((int)S.size() == n) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}



Measured memory_bytes: 9600
#include <stdio.h>

int main(void)
{

    int h, r, a;

    scanf("%d %d", &h, &r);

    if(h + r > 0)
        a = 1;
    else if(h + r == 0)
        a = 0;
    else
        a = -1;

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

    return 0;
}
    

Measured memory_bytes: 596
#include<iostream>

using namespace std;

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

	int ans = 0;

	for(int i = 0; i <= 999; ++i){
		string v = "000";
		v[0] = i%10+'0'; v[1] = i/10%10+'0'; v[2] = i/100+'0';
		int k = 2;
		for(int j = 0; j < N; ++j){
			if(S[j] == v[k]) { k--; } // cout << v[k+1] << endl; }
			if(k < 0) break;
		}
		if(k < 0){ ans++; }
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
const unsigned long long int M= 1000000007;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()	
#define fr(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define int long long 
#define endl "\n"
using namespace std;
int power(int x,int y){int res=1;while(y>0){if(y&1)res=x*res; y=y>>1;x=x*x;}return res;}
int power(int x,int y,int mod){int res=1;while(y>0){if(y&1)res=x*res%mod; y=y>>1;x=x*x%mod;}return res;}

void nik()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
}

 	#define F first 
	#define S second 


signed main()
{	nik();


int test=1;
//cin>>test;
while(test--)
{
int n;
cin>>n;

int a[n];
fr(i,n)cin>>a[i];

int money=1000,prev=a[0];
bool st=1;

int ans=money;
int pm=money;
int stock=money/a[0];
money-=a[0]*stock;
int ps=stock;

for(int i=1;i<n;i++)
{
	if(st)
	{
		if(a[i]<prev)
			{
				
				stock=pm/a[i];
				money=pm-a[i]*stock;
			}
		else if(a[i]>prev)
			{
				pm=money;
				money+=a[i]*stock;
				ans=max(ans,money);
				ps=stock;
				stock=0;
				st=0;
			}
	}
	else
	{
		if(a[i]>prev)
		{
			money=pm+a[i]*ps;
			ans=max(ans,money);
		}
		else if(a[i]<prev)
		{
			ps=stock;
			stock=money/a[i];
			pm=money;
			money-=a[i]*stock;
			st=1;
			
		}
	}


	prev=a[i];
}

cout<<ans<<endl;






	}
return 0;
}




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

long long mod(long long a, long long m) {
	a %= m;
	return a >= 0 ? a : a+m;
}

int main() {
	int n;
	string s;
	cin >> n >> s;
	vector<int> ans(n);
	for (int bits = 0; bits < 4; bits++) {
		bool ok = true;
		if ((bits>>1) & 1) ans[n-1] = 0;
		else ans[n-1] = 1;
		if (bits & 1) ans[0] = 0;
		else ans[0] = 1;
		for (int i = 0; i < n; i++) {
			int a = s[i]=='o' ? 0 : 1;
			int next = a ^ ans[mod(i-1, n)] ^ ans[i];
			if (i == n-2 || i == n-1) {
				if (next != ans[mod(i+1, n)]) ok = false;
			}
			else ans[i+1] = next;
		}
		if (ok) {
			for (int i = 0; i < n; i++) {
				if (ans[i] == 0) cout << 'S';
				else cout << 'W';
			}
			cout << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 3356
// 2016/05/28 Tazoe

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int main()
{
	stack<int> S;

	string expr;
	getline(cin, expr);	// 1???????????????

	istringstream is(expr);	// ????????????????????????

	while(!is.eof()){
		string op;
		is >> op;

		int tmp1, tmp2;

		switch(op[0]){
		case '+':
			tmp1 = S.top();  S.pop();
			tmp2 = S.top();  S.pop();
			S.push(tmp2+tmp1);
			break;
		case '-':
			tmp1 = S.top();  S.pop();
			tmp2 = S.top();  S.pop();
			S.push(tmp2-tmp1);
			break;
		case '*':
			tmp1 = S.top();  S.pop();
			tmp2 = S.top();  S.pop();
			S.push(tmp2*tmp1);
			break;
		default:
			istringstream is2(op);
			is2 >> tmp1;
			S.push(tmp1);
			break;
		}
	}

	cout << S.top() << endl;

	return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
typedef long long ll;
#define repran(i, a,b) for (int i = a; i<b;i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using LP = pair<ll,ll>;
using P = pair<int,int>;
const int inf = 500;


int main()
{
    int h, w;
    cin >> h >> w;
    int n = h*w;
    vector<char> g(n);
    rep(i,n) cin >> g[i];
    vector<vector<int>> dist(n, vector<int>(n, inf));
    //隣接する場所の距離は1
    rep(i, n){
        if (g[i] == '#') continue;
        rep(j, n){
            if (g[j] == '#') continue;
            if (i == j) dist[i][j] = 0;
            else if (abs(i-j) == w) dist[i][j] = 1;
            else if (i/w == j/w and abs(i-j) == 1) dist[i][j] = 1;
        }
    }
    rep(k, n) {
        if (g[k] == '#') continue;
        rep(i, n){
            if (g[i] == '#') continue;
            rep(j, n){
                if (g[j] == '#') continue;
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    int ans = 0;
    rep(i, n)rep(j, n) {
        if (dist[i][j] == inf) continue;
        ans = max(ans, dist[i][j]);
    }
    
    cout << ans << endl;

}

Measured memory_bytes: 4276
from scipy.sparse.csgraph import floyd_warshall

H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
grid = [list(map(int, input().split())) for _ in range(H)]

C = floyd_warshall(C)

ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] != -1:
            ans += C[grid[i][j], 1]

print(int(ans))


Measured memory_bytes: 14092
using System;

class Program
{
    static void Main()
    {
        for (int i = 1; i > 0; i ++)
        {
            int x = int.Parse(Console.ReadLine());
            
            if (x == 0)
            {
                break;
            }
            else
            {
                Console.WriteLine("Case {0}: {1}", i, x);
            }
        }
    }
}


Measured memory_bytes: 15880
from collections import deque


def main():
    n = int(input())  # n
    friendliness = [int(x) for x in input().split()]
    friendliness.sort()
    friendliness = deque(friendliness)
    edges = deque()
    popped = friendliness.pop()
    edges.append(popped)
    ans = 0
    counter = 0
    while friendliness:
        ans += edges.popleft()
        counter += 1
        popped = friendliness.pop()
        edges.append(popped)
        edges.append(popped)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 97092
n = int(input())
s = []
for i in range(n):
    s.append(int(input()))
s.sort()
score = sum(s)
if score % 10 == 0:
    for i in range(n):
        if s[i]%10>0:
            score -= s[i]
            break
    if score % 10 == 0:
        print(0)
    else:
        print(score)
else:
    print(score)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

int main()
{
  int n; cin >> n;
  vector<ll> a(n);
  vector<ll> dp(n,LLINF);
  REP(i,n) cin >> a[i];
  REP(i,n) *lower_bound(dp.begin(),dp.end(),a[i]) = a[i];
  cout << lower_bound(dp.begin(),dp.end(),LLINF)-dp.begin() << endl;
  return 0;
}

Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define SZ(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define rep2(i, j, n) for(int i=j;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;
const ll INF = 1000000LL;
int N,W;
int main(){
    int n;
    cin >> n;
    ll dp[n+1];
    rep(i, n+1) dp[i]=INF;
    dp[0]=0;
    int a=6, b=9;
    rep(i, n){
        dp[i+1] = min(dp[i+1], dp[i]+1);
        a=6;
        rep(j, 7){
            if(i+a<=n){
                dp[i+a] = min(dp[i+a], dp[i]+1);
                a*=6;
            } else {
                break;
            }
        }
        b=9;
        rep(j, 7){
            if(i+b<=n){
                dp[i+b] = min(dp[i+b], dp[i]+1);
                b*=9;
            } else {
                break;
            }
        }
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 4192
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,s,f) for(int i=s;i<f;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define endl "\n"
#define fcout cout<<fixed<<setprecision(15)
typedef pair<int, int> P;
struct edge { int to, cost; };

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 (b < a) { a = b; return 1; } return 0; }

bool prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return n != 1;
}
int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int modinv2(int a, int mod) {
    return mod_pow(a, mod - 2, mod);
}
int digit(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}
int read() {
    int tmp;
    cin >> tmp;
    return tmp;
}
int xor128() {
    static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    int t = (x xor (x << 11));
    x = y; y = z; z = w;
    return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
map<int, int> factaring(int x) {
    map<int, int>ans;
    int now = 2;
    while (now * now <= x) {
        if (x % now == 0) {
            x /= now;
            ans[now]++;
        }
        else now++;
    }
    if (x != 1) ans[x]++;
    return ans;
}
int comb(int n, int k, int mod) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    k = min(k, n - k);
    int x = 1, y = 1;
    rep(i, k) {
        y *= i + 1;
        y %= mod;
    }
    for (int i = n - k + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }
    return x * modinv(y, mod) % mod;
}

signed main() {
    //srand((unsigned)time(NULL));

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    set<string>se;

    cin >> n;
    rep(i, n) {
        string s;
        cin >> s;
        se.insert(s);
    }
    cout << se.size() << endl;

    return 0;
}


Measured memory_bytes: 19260
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()


def main():
    H,W,m=map(int, input().split())
    Hline=[]
    wline=[]
    blist=dict()
    for k in range(m):
        h,w=map(int, input().split())
        Hline.append(h)
        wline.append(w)
        blist[h*(W+2)+w]=0
    hc=Counter(Hline).most_common()
    wc=Counter(wline).most_common()
    ans=hc[0][1]+wc[0][1]
    hl=[]
    wl=[]
    for hcc in hc:
        if hcc[1]!= hc[0][1]:
            break
        hl.append(hcc[0])
    for wcc in wc:
        if wcc[1]!= wc[0][1]:
            break
        wl.append(wcc[0])
    for hll in hl:
        for wll in wl:
            if hll*(W+2)+wll not in blist:
                print(ans)
                exit()
    print(ans-1)

    
        



if __name__ == '__main__':
    main()

Measured memory_bytes: 266096
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define mp make_pair

using namespace std;

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10);
	#ifdef PIYUSH_HOME
		I_O;
	#else
	#define print(...) 0
	#endif
	int A[3];
	for (int o = 0; o < 3; ++o) { cin >> A[o]; }
	sort(A, A + 3);
	cout << A[2] - A[0];
}

Measured memory_bytes: 256
import numpy as np

k = int(input())


# ルンルン数で無くても二分探索を怖れない
def check(n):
    digits = []
    while n:
        n, m = divmod(n, 10)
        digits.append(m)
    digits.reverse()

    dp = np.zeros(10, dtype=np.int64)
    dp[1:digits[0]] = 1
    edge = digits[0]
    for d in digits[1:]:
        odp = dp.copy()
        dp[:-1] += odp[1:]
        dp[1:] += odp[:-1]
        dp[1:] += 1
        if edge != -1:
            if edge - 1 > d:
                edge = -1
            elif edge + 1 >= d:
                dp[max(0, edge - 1):d] += 1
                edge = d
            else:
                dp[max(0, edge - 1):edge + 2] += 1
                edge = -1
    result = dp.sum()
    if edge != -1:
        result += 1
    return result >= k


l = 0
r = 3234566667
while l + 1 < r:
    m = (l + r) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)


Measured memory_bytes: 14432
#include <iostream>

using namespace std;

int main() {
  int a;
  cin >> a;
  bool contains = false;
  while (a > 0) {
    int tmp = a % 10;
    if (tmp == 7) {contains = true; break;}
    a = a/ 10;
  }
  if (contains) cout << "Yes";
  else cout << "No";
}


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

using namespace std;
#define int long long
const int MOD=1e9+7;

vector< int > g[200000];
int dist[200000], ans[200000],son[200000],anc[200000],pre[200000];
int F[200000];

void dfs1(int idx, int par)
{
  for(int &to : g[idx]) {
    if(to == par) continue;
    dfs1(to, idx);
    son[idx]++;
  }
}
void dfs3(int idx,int par){
  for(int &to:g[idx]){
    if(to==par)continue;
    dfs3(to,idx);
    anc[idx]+=1+anc[to];
  }
}
int pw(int n,int k){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}
void dfs4(int idx,int par){
  for(int &to:g[idx]){
    if(to==par)continue;
    dfs4(to,idx);
    (pre[idx]*=pre[to]*(anc[to]+1)%MOD)%=MOD;
  }
}


void dfs2(int idx,int par)
{
  ans[idx]=dist[idx];
  for(int &to : g[idx]) {
    if(to == par) continue;
    int tmp=pre[idx];
    (tmp*=pw(pre[to]*(anc[to]+1)%MOD,MOD-2))%=MOD;
    int tmpa=anc[idx];
    tmpa-=anc[to]+1;tmp+=MOD;
    (pre[to]*=(tmp*(tmpa+1))%MOD)%=MOD;
    anc[to]+=1+tmpa;
    dist[to]=F[anc[to]]*pw(pre[to],MOD-2)%MOD;
    dfs2(to,idx);
  }
}

signed main()
{
  int N;
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  F[0]=1;
  for(int i=1;i<200000;i++)F[i]=(F[i-1]*i)%MOD;
  for(int i=0;i<N;i++)pre[i]=1;

  dfs1(0, -1);
  dfs3(0,-1);
  dfs4(0,-1);
  for(int i=0;i<N;i++)dist[i]=F[anc[i]]*pw(pre[i],MOD-2)%MOD;
  dfs2(0, -1);
  for(int i = 0; i < N; i++) {
    cout<<ans[i]<<endl;
  }
}


Measured memory_bytes: 25472
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoders {
	class Program {
		static void Main(string[] args) {

			var inputArray = retreiveLongArray();
			var inputCount = 2;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}

			var N = inputArray[0];
			var K = inputArray[1];

			//答えはN/Kの剰余か剰余からKを引いた絶対値になる
			var remainder = N % K;
			var otherCandicate = Math.Abs(remainder - K);

			//答えの出力
			var ans = Math.Min(remainder, otherCandicate);
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray =  Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


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

int main(){
    int k, n;
    int ans = 0;
    cin >> k >> n;
    vector<int>A(n);
    vector<int>B(n);
    for (int i = 0; i < n; i++){
        cin >> A[i];
    }
    for (int j = 0; j < n-1; j++){
        B[j]=A[j+1]-A[j];
    }
    B[n-1]=k-A[n-1]+A[0];
    sort(B.begin(), B.end());
    for(int i = 0; i < n-1; i++){
        ans = ans + B[i];
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000007;
long long modpow(long long a, long long b){
	a %= MOD;
	long long res = 1;
	while (b > 0){
		if (b % 2 == 1) res = res * a % MOD;
		a = a * a % MOD;
		b = b / 2;
	}
	return res;
}
long long modinv(long long a){
	return modpow(a, MOD - 2);
}
vector<long long> mf;
long long modfact(long long n){
	if (n < mf.size()){
		return mf[n];
	} else {
		if (mf.empty()) mf.push_back(1);
		long long res = mf.back();
		for (int i = mf.size(); i <= n; i++){
			res = res * i % MOD;
			mf.push_back(res);
		}
		return res;
	}
}
long long modbinom(long long n, long long r){
	long long res;
	res = modfact(n);
	res = res * modinv(modfact(r)) % MOD;
	res = res * modinv(modfact(n - r)) % MOD ;
	return res;
}
int main(){
  int K;
  cin >> K;
  string S;
  cin >> S;
  int N = S.size();
  long long ans = 0;
  for (int i = 0; i <= K; i++){
    long long tmp = 1;
    tmp *= modpow(25, K - i);
    tmp %= MOD;
    tmp *= modbinom(K - i + N - 1, N - 1);
    tmp %= MOD;
    tmp *= modpow(26, i);
    tmp %= MOD;
    ans += tmp;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 21568
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <functional>
#include <queue>
#include <tuple>
#include <cstring>

using namespace std;

#define rep(i,n) for(int i = 0;i < n;i++)
#define each(i,n) for(auto i : n)
#define all(n) n.begin(),n.end()
#define clr(n) memset(n,0,sizeof(n))
#define mclr(n) memset(n,-1,sizeof(n))

int main() {
	int n;
	while (cin >> n && n) {
		vector<string> s(n);
		rep(i, n) {
			cin >> s[i];
		}
		for (int i = 0;; i++) {
			bool end = true;
			rep(j, n) {
				if (i < s[j].size() && s[j][i] != '.') {
					end = false;
					for (int k = j + 1;; k++) {
						if (k >= n || (i < s[k].size() && s[k][i] != '.')) {
							int r = -1;
							for (int l = j + 1; l < k; l++) {
								if (i + 1 < s[l].size()) {
									if (s[l][i + 1] != '.') {
										s[l][i] = '+';
										r = l;
									}
								}
							}
							for (int l = j + 1; l < r; l++) {
								if (i + 1 < s[l].size()) {
									if (s[l][i] == '.') {
										s[l][i] = '|';
									}
								}
							}

							break;
						}
					}
				}
			}
			if (end)break;
		}
		rep(i, n) {
			rep(j, s[i].size()) {
				if (s[i][j] == '.')s[i][j] = ' ';
			}
			cout << s[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3696
#include <cstdio>
#include <iostream>
#include <vector>
#include <cassert>
#include <string>
using namespace std;

struct QuickFind {
    int N;
    vector<int> i2g;
    vector< vector<int> > g2i;
    vector<long long int> weight;

    QuickFind(int N_) {
        N = N_;
        i2g.resize(N);
        g2i.resize(N);
        weight.resize(N);

        for(int i=0; i<N; i++) {
            i2g[i] = i;
            g2i[i] = vector<int>{i};
        }
    }

    bool same(int u, int v) {
        return i2g[u] == i2g[v];
    }

    // v の方が w だけ大きい
    void unite(int u, int v, int w) {
        int ru = i2g[u], rv = i2g[v];
        if(ru == rv) return;

        if(g2i[rv].size() > g2i[ru].size()) {
            swap(ru, rv);
            swap(u, v);
            w = -w;
        }

        long long int prev = weight[v];
        weight[v] = weight[u] + w;

        for(auto e : g2i[rv]) {
            i2g[e] = ru;
            long long int diff = weight[e] - prev;
            if(e != v) weight[e] = weight[v] + diff;
        }

        for(auto e : g2i[rv]) {
            g2i[ru].push_back(e);
        }
        g2i[rv].clear();
    }

    long long int query(int u, int v) {
        assert(same(u, v));
        return weight[v] - weight[u];
    }
};

int N, Q;

int main() {
    while(cin >> N >> Q, N || Q) {
        QuickFind qf(N);
        for(int i=0; i<Q; i++) {
            char query; cin >> query;
            if(query == '!') {
                int u, v, w; cin >> u >> v >> w;
                u--; v--;
                qf.unite(u, v, w);
            }
            else {
                int u, v; cin >> u >> v;
                u--; v--;
                if(qf.same(u, v)) {
                    cout << qf.query(u, v) << endl;
                }
                else {
                    cout << "UNKNOWN" << endl;
                }
            }
        }
    }
    return 0;
}


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

using namespace std;

int main()
{
    long long int a,b,n,ans,x;
    cin>>a>>b>>n;
    if((b-1)<=n)
    {
        x=b-1;
    }
    else
    {
        x=n;
    }
    ans = floor(a * x / b) - a * floor(x/b);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define P pair<int,int>
#define All(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
typedef long long ll;
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;
const ll LINF = 1e18;
int main() {
	int n;
	cin >> n;
	int a[n], b[n];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum = 0;
		for (int j = 0; j <= i; j++) {
			sum += a[j];
		}
		for (int j = i; j < n; j++) {
			sum += b[j];
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main(){    
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string buf;
        char c;
        scanf("%c", &c);

        getline(cin,buf);
       // cout << "buf is " << buf << endl;
        int pos=0;
        int cn;
        cin>>cn;
        for(int k=0;k<cn;k++){
            string command;
            cin >> command;
            if(command=="forward"){
                cin >> command;
                if(command=="char"){
                    if(!buf.empty())
                    pos = min(pos+1,(int)buf.size());
                }else{
                    // word
                    while(pos < buf.size()&& buf[pos]==' ')pos++;
                    while(pos < buf.size()&& buf[pos]!=' ')pos++;
                }
            }else if(command=="backward"){
                cin >> command;
                if(command=="char"){
                    pos = max(pos-1,0);
                }else{
                    // word
                    while(pos > 0 && buf[pos-1]==' ' )pos--;
                    while(pos > 0 && buf[pos-1]!=' ')pos--;
                }
            }else if(command=="insert"){
                getline(cin,command);
                ungetc('\n',stdin);
                string text;
                bool f= false;
                for(int i=0;i<command.size();i++){
                    if(f&&command[i]=='\"')break;
                    if(f)text.push_back(command[i]);
                    if(command[i]=='\"')f=true;
                }
                buf.insert(pos,text);
                pos+= text.size();
            }else {//delete
                cin >> command;
                if(command== "char"){
                    if(!buf.empty()&&pos!=buf.size()){
                        buf.erase(pos,1);
                    }

                }else{
                    if(!buf.empty()){
                        int t=pos;
                        while(t<buf.size() && buf[t]==' ')t++;
                        if(t<buf.size()){
                        while(t<buf.size() && buf[t]!=' ')t++;
                       // while(t<buf.size() && buf[t]==' ')t++;

                        buf.erase(pos,t-pos);}
                    }
                }
            }
        }
       cout << buf.substr(0,pos) << "^" << buf.substr(pos) << endl; 
    }
    return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int input = Integer.parseInt(scan.next());
        //int second = Integer.parseInt(scan.next());
        //long in = Long.parseLong(scan.next());
        //String s = scan.next();
        //String second = scan.next();
        //for (int i = 1; i <=input; i++) {
        //}
        int yen500cnt = input/500;
        int div = input%500;
        int yen5cnt = div/5;
        System.out.println((yen500cnt*1000) + (yen5cnt*5));
    }

    public static void res(boolean flg) {
        if(flg) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21844
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [float(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
p = LI()
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(0,i+1):
        dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1-p[i-1])

print(sum(dp[-1][N//2+1:]))


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

int main() {
  using vi = vector<int>;
  using vs = vector<string>;
  using vvi = vector<vi>;
  using vvs = vector<vs>;
  using pii = pair<int, int>;
  using vpii = vector<pii>;
  
  long long N, Y;
  cin >> N >> Y;
  long long yuk = -1, hig = -1, nog = -1;

  if (Y % 1000 != 0) {
    printf("%lld %lld %lld\n", yuk, hig, nog);
    return 0;
  }
  else {
    for (int i = 0; i <= N; i++) {
      long long tmpY = Y;
      yuk = i;
      tmpY -= yuk * 10000;
      for (int j = 0; j <= N - i; j++) {
        long long tmptmpY = tmpY;
        hig = j;
        tmptmpY -= hig * 5000;
        nog = tmptmpY / 1000;
        if (yuk + hig + nog > N) continue;
        else if (yuk + hig + nog == N) {
          printf("%lld %lld %lld\n", yuk, hig, nog);
          return 0;
        }
        else if (yuk + hig + nog < N) break;
      }
      if (i == N) {
        yuk = -1;
        hig = -1;
        nog = -1;
        printf("%lld %lld %lld\n", yuk, hig, nog);
        return 0;
      }
    }
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rpd(i,a,b) for(register int i=a;i>=b;--i)
#define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
typedef long long ll;
const int N=2000+5;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,tot,K,ans=1e9;int head[N],nxt[N<<1],to[N<<1],dep[N];
void add(int u,int v){nxt[++tot]=head[u];head[u]=tot;to[tot]=v;}
void dfs(int x,int fa,int now){dep[x]=now;rep1(i,x){int p=to[i];if(p==fa)continue;dfs(p,x,now+1);}}
int main(){
	n=read();K=read();
	rep(i,1,n-1){int u=read(),v=read();add(u,v);add(v,u);}
	if(K&1){
		rep(i,1,n){
			rep1(j,i){
				int p=to[j];if(p>i)continue;
				int sum=0;dfs(p,i,0);dfs(i,p,0);
				rep(t,1,n)if(dep[t]>K/2)sum+=1;
				ans=min(ans,sum);
			}
		}
	}
	else{
		rep(i,1,n){
			int sum=0;dfs(i,0,0);
			rep(j,1,n)if(dep[j]>K/2)sum+=1;
			ans=min(ans,sum);
		}
	}
	return printf("%d\n",ans),0;
}

Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

	int N = in.nextInt();
	int A[] = new int[N];
	int sum = 0;
	Arrays.fill(A, -1);

	for(int cnt = 0; cnt < N; cnt++){
		A[cnt] = in.nextInt();
	}
	Arrays.sort(A);
	for(int cnt = 0; cnt < N - 1 ; cnt++){
		if(A[cnt] == A[cnt + 1]){
			A[cnt] = 0;
			A[cnt + 1] = 0;
		}
	}
	for(int cnt = 0; cnt < N; cnt++){
		if(A[cnt] == 0){
			sum++;
		}
	}
	in.close();
	System.out.println(N - sum);
	}
}

Measured memory_bytes: 50448
# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)

Measured memory_bytes: 19132
N = int(input())
MOD = int(1e9+7)
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
# T = 0 A = 1 G = 2 C = 3
dp[0][0][0][0] = 1
for n in range(N):
    for i in range(4):
        for j in range(4):
            if dp[n][i][j] == 0:
                continue
            for k in range(4):
                for a in range(4):
                    if j == 1 and i == 2 and a == 3: # AGC
                        continue
                    if j == 2 and i == 1 and a == 3: # GAC
                        continue
                    if j == 1 and i == 3 and a == 2: # ACG
                        continue
                    if k == 1 and i == 2 and a == 3: # A*GC
                        continue
                    if k == 1 and j == 2 and a == 3: # AG*C
                        continue
                    dp[n+1][a][i][j] += dp[n][i][j][k]
                    dp[n + 1][a][i][j] %= MOD
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= MOD
print(ans)

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

int main(){
        string a, b;
        cin >> a >> b;
        int n = a.size(), m = b.size();
        int dp[n + 1][m + 1];
        for(int j = 0; j <= m; j++){
                for(int i = 0; i <= n; i++){
                        if(i == 0) dp[i][j] = j;
                        else if(j == 0) dp[i][j] = i;
                        else if(a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
                        else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
                }
        }
        cout << dp[n][m] << endl;
        return 0;
}



Measured memory_bytes: 7076
#include<stdio.h>
main()
{
	int a,b,c,n,t;
	while(~scanf("%d",&n))
	{
		while(n--)
		{
			scanf("%d%d%d",&a,&b,&c);
		if(a<=b){t=a;a=b;b=t;}
		if(a<=c){t=a;a=c;c=t;}
		if(a*a==b*b+c*c)printf("YES\n");
		else printf("NO\n");
		}
	}
	return 0;
}

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

const ll mod = 1000000007;
struct mint {
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    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;
    }

    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;
    }
};

struct combination {
    vector<mint> fact, ifact;
    // init struct with "n" of "nCk" (maximum number in other words)
    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;
    }
    // c(n,k) returns mint that contains nCk (mod p (= 1e9+7)) in x
    // i.e.) mint num = c(n,k), then num.x == nCk (mod p (= 1e9+7))
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }

    // nPk - permutation
    mint p(int n, int k) {
        return fact[n] * ifact[n - k];
    }
};

int main() {
    ll n, k;
    cin >> n >> k;
    combination nck(n);

    k = min(k, n - 1);
    mint ans;
    for (ll i = 0; i <= k; i++) {
        ans += nck(n, i) * nck((n - i - 1) + i, i);
    }
    cout << ans.x << endl;
}

Measured memory_bytes: 6432