akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

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

		int a[] = new int[N];

		int min = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			a[i] = L + i;
			int tmp = Math.abs(a[i]);
			if (min >= tmp) {
				min = tmp;
			}
		}
		long sum =0;

		for (int i = 0; i < N; i++) {
			if (Math.abs(a[i]) == min) {
				continue;
			}
			sum += a[i];
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 23764
use std::io;
fn main() {
    let n: i32 = get_line().parse().expect("can't parse it");
    println!("{}", n / 3);
}

fn get_line() -> String {
    let mut inp = String::new();
    io::stdin().read_line(&mut inp).expect("input err");
    inp.trim().to_string()
}


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

#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)

using namespace std;

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

const int MX = 3005, mod = 1e9+7;

int n, q, a[MX], x[MX], y[MX], cn[MX][MX], ult[MX][MX], pw[MX];
ll res = 0;

void upd (int i, int act) {
	for (int k = 0; k < n; k++) {
		cn[i][k] = ll(cn[i][k]) * pw[max(act-ult[i][k]-1,0)] % mod;
		ult[i][k] = act;

		cn[k][i] = ll(cn[k][i]) * pw[max(act-ult[k][i]-1,0)] % mod;
		ult[k][i] = act;
	}
}

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

	pw[0] = 1;
	for (int i = 1; i < MX; i++)
		pw[i] = 2 * pw[i-1] % mod;

	cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < q; i++)
		cin >> x[i] >> y[i];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cn[i][j] = a[i] < a[j], ult[i][j] = -1;

	for (int i = 0; i < q; i++) {
		upd(--x[i], i);
		upd(--y[i], i);

		for (int k = 0; k < n; k++) {
			if (k == x[i] || k == y[i]) continue;

			int d = cn[x[i]][k], e = cn[y[i]][k];
			cn[x[i]][k] = (cn[x[i]][k] + e) % mod;
			cn[y[i]][k] = (cn[y[i]][k] + d) % mod;
		}

		for (int k = 0; k < n; k++) {
			if (k == x[i] || k == y[i]) continue;
			
			int d = cn[k][x[i]], e = cn[k][y[i]];
			cn[k][x[i]] = (cn[k][x[i]] + e) % mod;
			cn[k][y[i]] = (cn[k][y[i]] + d) % mod;
		}

		int d = cn[x[i]][y[i]], e = cn[y[i]][x[i]];
		cn[x[i]][y[i]] = (cn[x[i]][y[i]] + e) % mod;
		cn[y[i]][x[i]] = (cn[y[i]][x[i]] + d) % mod;
	}

	for (int i = 0; i < n; i++)
		upd(i, q);

	for (int i = 1; i < n; i++)
		for (int j = 0; j < i; j++)
			res = (res + cn[i][j]) % mod;

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 70784
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

#define DEBUG 0
#define OUT

#if DEBUG
    #define LOG(...) {printf(__VA_ARGS__); printf("\n");}
    #define print_int_array(arr, n) {\
                for (int k = 0; k < n; ++k) {\
                    std::cout << std::setw(2) << arr[k] << " ";\
                }\
                    std::cout << "\n";\
                }
#else
    #define LOG(...) {}
    #define print_int_array(arr, n) {}
#endif

const size_t n_max = (size_t)1e5;

int main(int argc, char** argv)
{
    int n;
    std::cin >> n;
    int h[n_max];
    
    for (int i = 0; i < n; ++i) {
        std::cin >> h[i];
    }

    // init
    std::vector<int> dp(n_max);
    
    // base case
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]) + dp[0];

    for (int i = 2; i < n; ++i) {
        dp[i] = std::min(abs(h[i] - h[i-1]) + dp[i-1],
                         abs(h[i] - h[i-2]) + dp[i-2]);
        
        LOG("%d : %d ", i, dp[i]);
    }
    std::cout << dp[n-1];

    return 0;
}

/*
4
10 30 40 20

*/

Measured memory_bytes: 1024
from collections import deque


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

matrix = [[0]*n for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    matrix[a][b] = 1
    matrix[b][a] = 1

graph = [[] for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if matrix[i][j] == 0:
            graph[i].append(j)
            graph[j].append(i)


def coloring(graph):
    n = len(graph)
    visited = [-1] * n
    ans = []
    for i in range(n):
        if visited[i] >= 0:
            continue
        visited[i] = 0
        q = deque([i]) 
        num = [1, 0]
        while q:
            _from = q.pop()
            for to in graph[_from]:
                if visited[to] == visited[_from]:
                    return [[-1, -1]]
                if visited[to] >= 0:
                    continue
                visited[to] = visited[_from] ^ 1
                num[visited[to]] += 1
                q.append(to)
        ans.append(num)
    return ans

num = coloring(graph)
if num[0][0] == -1:
    print(-1)
    exit()

dp = [[False]*(n+1) for _ in range(len(num) + 1)]
dp[0][0] = True

for i in range(len(num)):
    a, b = num[i]
    for j in range(n+1):
        if j-a >= 0:
            dp[i+1][j] = dp[i][j-a] or dp[i+1][j]
        if j-b >= 0:
            dp[i+1][j] = dp[i][j-b] or dp[i+1][j]

ans = 10**20
for i, boolian in enumerate(dp[len(num)]):
    if boolian:
        tmp_ans = i * (i-1) // 2 + (n-i) * (n-i-1) // 2 
        ans = min(tmp_ans, ans)
print(ans)

Measured memory_bytes: 96088
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 10000007;
const int inf = 1001001001;



int main(void) {
  string s;
  cin >> s;
  int n = s.size();
  if(n%2==1) {
    cout << "No" << endl;
    return 0;
  }
  
  rep(i,n/2){
    if(s[2*i] != 'h' || s[2*i+1] != 'i'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  
}


Measured memory_bytes: 256
# coding: utf-8

from collections import Counter

s = input().strip()
l = len(s)
c = Counter(s)
cs = [0, 0]
for i, (_, cnt) in enumerate(c.most_common(2)):
    cs[i] = cnt
if (cs[0] - 1 <= l - cs[0]) and (l - cs[0] - cs[1] >=  cs[0] - 1):
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3444
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxm = 12;
const int maxn = 10024;

int a[maxm][maxn];

int main() {
    int m, n;
    while(~scanf("%d%d", &m, &n) && (m || n)) {
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j) {
                scanf("%d", &a[i][j]);
            }
        int up = 1 << m;
        int ans = 0;
        for(int i = 0; i < up; ++i) {
            int temp = 0;
            //行变换
            for(int j = 0; j < m; ++j) {
                if(i & (1 << j)) {
                    for(int k = 0; k < n; ++k)
                        a[j][k] ^= 1;
                }
            }
            //列计数
            for(int j = 0; j < n; ++j) {
                int cnt = 0;
                for(int k = 0; k < m; ++k) {
                    if(a[k][j]) ++cnt;
                }
                temp += max(cnt, m - cnt);
            }
            //变回原数组
            for(int j = 0; j < m; ++j) {
                if(i & (1 << j)) {
                    for(int k = 0; k < n; ++k)
                        a[j][k] ^= 1;
                }
            }
            ans = max(ans, temp);
        }
        printf("%d\n", ans);
    }
    return 0;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define LOCAL 1
int main(){
	#if LOCAL
//	freopen("E:\\in.txt","r", stdin);
	#endif
	int n;
	cin >> n;
	int t1 = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j < i; j++){
			if(i * j >= n){
				break;
			}
			t1++;
		}
	}
	int t2 = 0;
	for(int i = 1; i <= n; i++){
		if(i * i >= n) break;
		t2++;
	}
	cout << 2 * t1 + t2 << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N; cin>>N;
  double ans;
  if(N%2==0) ans = 0.5;
  else {
    ans = (N+1)/2;
    ans/= N;
  }
  Out(ans);
}

Measured memory_bytes: 256
x = [int(i) for i in input().split()]

def fun(x):
  for i in range(x[0] + 1):
    for l in range(x[0] - i + 1):
      n = x[0] - (i + l)
      tmp = (10000*i) + (5000*l) + (1000*n)
      if tmp == x[1]:
        return i,l,n
  else:
    return -1,-1,-1
    
a,b,c = fun(x)
print(a,b,c)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int m = max({a, b, c});
  int sum = a + b + c;
  int ans;
  if(m%2==sum%2){
    ans = (3 * m - sum) / 2;
  } else {
    ans = (3 * (m + 1) - sum) / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
#include<cmath>
#include<string>
#include<iomanip>
#include <numeric>
#include <limits>
using namespace std;

int main()
{
 long long n,n0=2,n1=1,number;
 cin>>n;
 if(n==1) cout<<1;
 else{
 for(int i=0;i<=n-2;i++)
 {
     number=n0+n1;
     n0=n1;
     n1=number;
 }
 cout<<number;
 }
 return 0;
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func main() {
	var n,d,x int
	fmt.Scan(&n,&d,&x)
	
	mem := make([]int,n)
	
	for i := 0; i < n; i++ {
		fmt.Scan(&mem[i])
	}

	cnt := n;
	for i := 0; i < n; i++ {
		j := 1;
		for (j * mem[i]) + 1 <= d {
				cnt++
				j++
		}
	}
	fmt.Println(cnt + x)
}

Measured memory_bytes: 512
# coding: utf-8
# Your code here!
n,x=[int(x) for x in input().split()]
burgurnum=["" for _ in [0]*51]
burgurnumP=["" for _ in [0]*51]
def burgurNumFunc(level):
    if burgurnum[level]=="":
        if level==0:
            burgurnum[level]=1
        else:
            burgurnum[level]=burgurNumFunc(level-1)*2+3
    return burgurnum[level]
def burgurnumPFunc(level):
    if burgurnumP[level]=="":
        if level==0:
            burgurnumP[level]=1
        else:
            burgurnumP[level]=burgurnumPFunc(level-1)*2+1
    return burgurnumP[level]
    
    
def burger(num,level):
    if level==0:
        return 1
    elif num==1:
        return 0
    elif 1<num<=1+burgurNumFunc(level-1):
        return burger(num-1,level-1)
    elif num==burgurNumFunc(level-1)+2:
        return burgurnumPFunc(level-1)+1
    elif burgurNumFunc(level-1)+2<num<=burgurNumFunc(level-1)*2+2-1:
        return burgurnumPFunc(level-1)+1+burger(num - burgurNumFunc(level-1)-2,level-1)
    else:
        return burgurnumPFunc(level-1)*2+1
    

print(burger(x,n))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()




using namespace std;

vector <int> H(100010,0);
vector <int> higher(100010,1);





int main(){
  ll N,M; cin>>N>>M;
  REP(i,N) cin>>H[i+1];
  vector < vector <int> > Hs(N+1);

  REP(i,M){
    int a,b; cin>>a>>b;
    if(H[a] <= H[b]) higher[a] = 0;
    if(H[b] <= H[a]) higher[b] = 0;
  }

  int ans = 0;
  for(int i=1;i<=N;i++){
    if(higher[i] == 1) ans++;
  }

  cout<<ans<<endl;


  



  return 0;
}

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> P(N);
    vector<int> C(N);
    for(int i = 0; i < N; i++){
        cin >> P.at(i);
    }
    for(int i = 0; i < N; i++){
        cin >> C.at(i);
    }
    for(int i = 0; i < N; i++){
        P.at(i)--; //1startだとめんどいのでデクリメント
    }
    long long ans = -1e18;
    for(int si = 0; si < N; si++){
        int x = si;
        vector<int> score;
        long long sum = 0;
        while(true){
            x = P.at(x);
            score.push_back(C.at(x));
            sum += C.at(x);
            if(x == si){
                break;
            }
        }
        int l = score.size();
        long long t = 0;
        for(int i = 0; i < l; i++){
            t += score.at(i);
            if(i + 1 > K){
                break;
            }
            long long now = t;
            if(sum > 0){
                long long e = (K - (i + 1)) / l;
                now += sum * e;
            }
            ans = max(ans, now);
        }
    }
    /*for(int i = 0; i < N; i++){
        int score = 0;
        int blank = i;
        for(int j = 0; j < K; j++){
            score += C.at(P.at(blank) - 1);
            blank = P.at(blank) - 1;
        }
        cout << score << endl;
        if(score_max < score){
            score_max = score;
        }
    }*/
    cout << ans << endl;
}

Measured memory_bytes: 3724
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  int n, m;
  cin >> n;

  map<string, pair<int,int>> mp;
  string s;
  rep(i, n) {
    cin >> s;
    mp[s].first += 1;
  }

  cin >> m;
  rep(i, m) {
    cin >> s;
    mp[s].second += 1;
  }

  int mmax = 0;
  for (auto&& itr : mp) {
    pair<int,int> p = itr.second;
    mmax = max(p.first - p.second, mmax);
  }
  cout << mmax << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl



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


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

int main() {
  string S;
  cin >> S;
  char c1, c2, c3, c4;
  c1 = S[0];
  c2 = S[1];
  c3 = S[2];
  c4 = S[3];
  
  if (c1 == c2 && c3 == c4 && c1 != c3) cout << "Yes" << endl;
  else if (c1 == c3 && c2 == c4 && c1 != c4) cout << "Yes" << endl;
  else if (c1 == c4 && c3 == c2 && c1 != c3) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())

Li_2 = 2
Li_1 = 1
Li = Li_2 + Li_1
for i in range(N-1):
    Li = Li_2 + Li_1
    Li_2 = Li_1
    Li_1 = Li

if N == 1:
  print(1)
else:
  print(Li)

Measured memory_bytes: 38392
#include <stdio.h>


int main(){
    int a,b,i,max;
    scanf("%d %d",&a,&b);
    int ans[3] = {a+b,a-b,a*b};
    
    max = -1000000;
    for(i=0;i<3;i++){
        if(max<ans[i]){
            max = ans[i];
        }
    }
    printf("%d",max);
}


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

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N;
    cin >> N;
    cout << fixed << setprecision(15);
    cout <<((N % 2 == 0) ? 0.5 : (double) (N + 1) / 2 / N)  << endl;
    
    return 0;
}

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

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

  int X = 0;
  if (N < 10) {
      X = 100 * (10 - N) + R;
  }
  else X = R;
  
  cout << X << endl;
}


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

int main(){
  int n;
  cin >>n;
  cout << pow(n,3) << endl;

  return 0;
}


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

int main()
{
	int n;
	int a[100];
	int A = 0, B = 0;

	cin >> n;
	for (int i = 0; i < n; i++)  cin >> a[i];
	
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; j > i; j--) {
			if (a[j] > a[j - 1]) {
				swap(a[j], a[j - 1]);
			}
		}
	}

	if (n % 2 == 0) {
		for (int i = 0; i < n; i = i + 2) {
			A += a[i];
			B += a[i + 1];
		}
	}
	else {
		for (int i = 0; i < n; i = i + 2) {
			A += a[i];
			if (i == n - 1)  break;
			B += a[i + 1];
		}
	}
	cout << A - B << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

const int MAXN = 100004;

int N;
int uf[MAXN];
long long xx[MAXN];

int findp(int);

int main() {
  int N, q;
  scanf("%d%d", &N, &q);
  std::fill(uf, uf + N, -1);
  for (int i = 0; i < q; ++i) {
    int l, r, d;
    scanf("%d%d%d", &l, &r, &d);

    int ll = findp(l), rr = findp(r);
    if (ll == rr) {
      if (xx[r] - xx[l] != d) goto fail;
      continue;
    }

    uf[rr] = ll;
    xx[rr] = (d + (long long)xx[l]) - xx[r];
  }
  puts("Yes");
  return 0;

fail:
  puts("No");
  return 0;
}

int Q[MAXN];
int qr;

int findp(int t) {
  Q[0] = t;
  qr = 1;
  int pt = uf[t];
  while (pt != -1) {
    t = Q[qr++] = pt;
    pt = uf[t];
  }
  int sum = 0;
  for (int i = qr - 2; i >= 0; --i) {
    sum += xx[Q[i]];
    xx[Q[i]] = sum;
    uf[Q[i]] = t;
  }
  return t;
}


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

int main(){
int a,b,c=0;
cin >>a>>b;
for (int i = 0; i < 2; i++) {
if(a>=b){
  c+=a;
  a--;
}
else{
  c+=b;
  b--;
}
}
  cout<<c<<endl;
}



Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    s = S()
    t = 0
    for i in range(len(s)//2):
        if s[i] != s[-i-1]:
            t += 1

    return t


print(main())




Measured memory_bytes: 6352
#include <cstdio>
using namespace std;

int max(int a, int b){
	if(a > b) return a;
	else return b;
}

int main(){
	const int MAX_N = 100000;
	int n, a[MAX_N], k, S, S1, S2;
	int p;
	
	while(true){
		scanf("%d%d", &n, &k);
		if(n == 0 && k == 0) break;
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		
		S = 0;
		for(p = 0; p < k; p++){
			S += a[p];
		}
		S1 = S;
		
		while(p < n){
			S2 = S1 + a[p] - a[p - k];
			
			S = max(S, S2);
			
			S1 = S2;
			
			p++;
		}
		
		printf("%d\n", S);
	}
	
	return 0;
}

Measured memory_bytes: 1416
u=["","Man","Oku","Cho","Kei","Gai","Jo","Jou","Ko","Kan","Sei","Sai","Gok","Ggs","Asg","Nyt","Fks","Mts"];
[*$<][0..-2].map{|s|n,m=s.split.map &:to_i;a=n**m;
ans="";
u.size.times{|i|if a%10000>0;ans=(a%10000).to_s+u[i]+ans;end;a/=10000}
puts ans
}


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

template<class T> void chmin(T &a, T b) {
    if (a > b) a = b;
}

const long long INF = 1LL<<60;

int main() {
    int N; cin >> N;
    vector<int> h(N);
    for (int i = 0; i < N; ++i) cin >> h[i];
    
    vector<long long> dp(N, INF);
    dp[0] = 0;
    
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
        if (i > 1) {
            chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
        }   
    }
    
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 4192
import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

struct Edge {
    int to, cost;
}

const INF = 1<<28;

int N, M, C;
Edge[][] G;
bool input() {
    scanf("%d %d %d\n", &N, &M, &C);
    if (N == 0 && M == 0 && C == 0) return false;
    G = new Edge[][N];
    foreach (i; 0 .. M) {
        int f, t, c;
        scanf("%d %d %d\n", &f, &t, &c);
        f--; t--;
        G[f] ~= Edge(t, c);
    }
    return true;
}

struct P {
    int k, v;
}

struct S {
    int k, v, cost;
}

void solve() {
    //writeln([N, M, C]);
    int[P] D;
    BinaryHeap!(Array!S, "a.k == b.k ? a.cost > b.cost : a.k > b.k") PQ;
    PQ.insert(S(0, 0, 0));
    while (!PQ.empty) {
        S cur = PQ.front; PQ.removeFront;
        //writeln(cur);
        if (cur.v == N - 1 && cur.cost <= C) {
            writeln(cur.k);
            return;
        }
        foreach (e; G[cur.v]) {
            auto next = S(cur.k, e.to, cur.cost + e.cost);
            if (D.get(P(next.k, next.v), INF) > next.cost) {
                D[P(next.k, next.v)] = next.cost;
                PQ.insert(next);
            }
            next = S(cur.k + 1, e.to, cur.cost);
            if (D.get(P(next.k, next.v), INF) > next.cost) {
                D[P(next.k, next.v)] = next.cost;
                PQ.insert(next);
            }
        }
    }
}

void main() {
    while (input) solve;
}

Measured memory_bytes: 2340
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include "bits/stdc++.h"
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int N;
vpll adj[100000];
ll d[100000],color[100000];
void dijkstra(){
	priority_queue<pll> PQ;
	rep(i,N){
		d[i]=INFl;
		color[i]=0;
	}
	d[0]=0;
	color[0]=1;
	PQ.push(mp(0,0));
	while(!PQ.empty()){
		pll f=PQ.top();
		PQ.pop();
		ll u=f.second;
		color[u]=2;
		if(d[u]< -f.first) continue;
		rep(j,adj[u].size()){
			ll v=adj[u][j].first;
			if(color[v]==2) continue;
			if(d[v]>d[u]+adj[u][j].second){
				d[v]=d[u]+adj[u][j].second;
				PQ.push(mp(-d[v],v));
				color[v]=1;
			}
		}
	}
}
int main(){
	scan(N);
	rep(i,N-1){
		ll u,v,w;
		scan(u>>v>>w);
		u--; v--;
		adj[u].push_back(mp(v,w));
		adj[v].push_back(mp(u,w));
	}
	dijkstra();
	rep(i,N){
		prin(d[i]%2);
	}
	return 0;
}


Measured memory_bytes: 9472
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
/////////////////////////////////
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    vector<double> b(n);
    rep(i, n) b[i] = (double)1 / a[i];
    double k=0;
    rep(i, n) k += b[i];
    cout << 1 / k << endl;
}

Measured memory_bytes: 3828
A = list(map(int, input().split()))

ans = A[1]
B = [A[0], A[3], A[4]]
C = []
for b in B:
    if b == 0:
        C.append(0)
        continue
    a = (b-1)//2
    ans += a*2
    C.append(b-a*2)

if C.count(2) >= 2:
    for c in C:
        ans += c//2*2
elif min(C) == 1:
    ans += 3
else:
    for c in C:
        ans += c//2*2

print(ans)

Measured memory_bytes: 3064
fn main() {
    let mut input = String::new();
    let stdin = std::io::stdin();
    let _ = stdin.read_line(&mut input).expect("read line");
    let nab: Vec<u64> = input
        .trim()
        .split_whitespace()
        .map(|n| n.parse().expect("parse"))
        .collect();
    println!("{}", solve(nab[0], nab[1], nab[2]));
}

fn solve(n: u64, a: u64, b: u64) -> u64 {
    if n == 1 {
        return if a == b { 1 } else { 0 };
    }
    if a > b {
        return 0;
    }
    (b - a) * (n - 2) + 1
}


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

vector<int> bfs(vector<vector<int>> &G, int s) {
  vector<bool> used(n);
  vector<int> d(n);
  queue<pair<int, int>> que;

  d[s] = 0;
  used[s] = true;
  que.push(make_pair(s, 0));

  while (!que.empty()) {
    pair<int, int> q = que.front(); que.pop();
    int cx = q.first;
    int ct = q.second;
    used[cx] = true;
    d[cx] = ct;

    rep (i, G[cx].size()) {
      int nx = G[cx][i];
      if (!used[nx]) {
        que.push(make_pair(nx, ct+1));
      }
    }
  }
  return d;
}

int main() {
  cin >> n;
  vector<vector<int>> G(n);

  rep (i, n-1) {
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  int s = 0;
  int g = n-1;

  vector<int> d1 = bfs(G, s);
  vector<int> d2 = bfs(G, g);

  int l = 0;
  int r = 0;

  rep (i, n) {
    if (d1[i] <= d2[i]) l++;
    else r++;
  }

  if (l > r) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
  return 0;
}


Measured memory_bytes: 6584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    int x = 0;
    for (int i = 0; i < n; i++)
        x ^= a[i];
    
    for (int i = 0; i < n; i++)
        cout << (x^a[i]) << " ";
    cout << endl;
    
    return 0;
}


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

int f(int n, int k){
	int ans = 0;
	while(0 < n){
		n /= k;
		ans++;
	}
	return ans;
}

int main(){
	int n, k;
	cin >> n >> k;

	int ans = f(n, k);
	cout << ans << endl;

	return 0;
}

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

int main(){
	ll A, B, K;
	cin >> A >> B >> K;
	ll a, b;
	a = max(0LL, A - K);
	K -= (A - a);
	b = max(0LL, B - K);
	cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  int sum = accumulate(all(A), 0);
  ll ans = longinf;
  int cand[] = {sum/N-1, sum/N, sum/N+1};
  for(int c: cand) {
    ll tmp = 0;
    rep(i, N) tmp += (A[i] - c) * (A[i] - c);
    ans = min(tmp, ans);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 5100000;
const int MOD = 1e9 + 7;

const double PI=3.14159265358979323846;


long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

std::vector<int> Eratosthenes(int n ){
    std::vector<bool> is_prime( n + 1 );
    for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;
    std::vector<int> P;
    for( int i = 2; i <= n; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= n; j += i ){
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

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

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



int main(){
    map<map<char, int>, int> dict;
    cin >> N;
    string str;
    while(N){
        cin >> str;
        map<char, int> mp;
        for(int i = 0; i < 10; ++i){
            mp[str[i]]++;
        }
        dict[mp]++;
        --N;
    }
    
    ll ans = 0;
    for(auto i = dict.begin(); i != dict.end(); ++i){
        ll n = i->second;
        ans += n*(n-1)/2;
    }
    cout << ans ;
    return 0;
}

Measured memory_bytes: 49152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
#define INF (1e9)

const string YES = "YES";
const string NO = "NO";

int main() {
  ll A;
  cin >> A;
  ll V;
  cin >> V;
  ll B;
  cin >> B;
  ll W;
  cin >> W;
  ll T;
  cin >> T;

  bool ans = false;
  if (A < B) {
    ans = A + T * V >= B + T * W;
  } else {
    ans = A - T * V <= B - T * W;
  }

  cout << (ans ? YES : NO) << endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i, n) for (int i = 0; i < n; i++)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
int dxx[8] = { 1, 1, 1, 0, 0, -1, -1, -1 }, dyy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

int main() {
    string s, t;
    cin >> s >> t;
    if (s == t.substr (0, s.size())) cout << "Yes"
                                          << "\n";
    else
        cout << "No"
             << "\n";
}

Measured memory_bytes: 3632
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()

    ret = 0
    while N != 0:
        N //= K
        ret += 1
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10224
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 5100000;
const int MOD = 1e9 + 7;

const double PI=3.14159265358979323846;


long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

std::vector<int> Eratosthenes(int n ){
    std::vector<bool> is_prime( n + 1 );
    for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;
    std::vector<int> P;
    for( int i = 2; i <= n; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= n; j += i ){
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

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



int main(){
    cin >> K;
    priority_queue<ll> que;
    for(int i = 1; i < 10; ++i) que.push(-i);
    ll num ;
    for(int i = 0; i < K; ++i){
        num = -que.top(); que.pop();
        que.push(-10*num - num%10);
        if(num % 10 != 0) que.push(-10*num - (num%10) + 1);
        if(num % 10 != 9) que.push(-10*num - (num%10) - 1);
    }
    std::cout << num << "\n";
    return 0;
}

Measured memory_bytes: 2420
#include <stdio.h>
#define N 20
int  main(void)
{
  char s1[N]={0},s2[N]={0},s3[N]={0},ans[N]={0};
  int i;
  scanf("%s%s%s",s1,s2,s3);
  ans[0]=s1[0];
  ans[1]=s2[0];
  ans[2]=s3[0];
  for(i=0;i<3;i++)
  {
    if(ans[i]>='a' && ans[i]<='z')
    {
      ans[i]=ans[i]-('a'-'A');
    }
  }
  printf("%s\n",ans);
  return 0;
}


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

int fanc(string s){
    int res = 0;
    int tmp = 0;
    tmp += (int)(s[7] - '0');
    tmp += 10*(int)(s[6] - '0');
    res += tmp;
    tmp = 0;
    tmp += (int)(s[4] - '0');
    tmp += 10*(int)(s[3] - '0');
    res += tmp * 60;
    tmp = 0;
    tmp += (int)(s[1] - '0');
    tmp += 10*(int)(s[0] - '0');
    res += tmp * 3600;
    return res;
}

int main(){

    while(1){
    
        int n; cin >> n;
        if(!n) break;

        int imos[100000] = {};        
        for(int i = 0; i < n; i++){
            string s, t; cin >> s >> t;
            int S = fanc(s);
            int T = fanc(t);        
            imos[T]--;
            imos[S]++;
        }

        for(int i = 1; i < 100000; i++){
            imos[i] += imos[i - 1];
        }

        int ans = 0;
        for(int i = 0; i < 100000; i++){
            ans = max(ans, imos[i]);
        }

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


Measured memory_bytes: 3472
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n) 
{ v = vector<T>(n); for (lli i=0; i<n; ++i) cin >> v[i]; }
template<class T, class U> void read_n(vector<pair<T, U>>& v, size_t n)
{ v = vector<pair<T, U>>(n); 
  for (lli i=0; i<n; ++i) cin >> v[i].first >> v[i].second; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli a, b;
int main() {
  cin >> a >> b;
  lli ans = (a + b + 1) / 2;
  cout << ans << endl;
  return 0;
}


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

int main() {
	
	int a[18];
	string c;
	
	int x,hito,kane;
	hito=0;
	kane=0;
	
	for(int i=0;i<18;i=i+2){
		cin >> c ;
		cin >> a[i] >> a[i+1] ;
		hito=a[i]+a[i+1];
		kane=a[i]*200+a[i+1]*300;
		
		
		cout << c << " " << hito << " " << kane << endl;
		x=x+1;
	}
	
	return 0;
}

Measured memory_bytes: 3124
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);
    int h = cin.nextInt();
    int w = cin.nextInt();
    char[][] matrix = new char[h][w];
    int count = 0;
    Queue<int[]> waiting = new LinkedList<>();
    for (int i = 0; i < h; i++) {
      char[] item = cin.next().toCharArray();
      matrix[i] = item;
      for (int j = 0; j < w; j++) {
        if (item[j] == '#')
          waiting.add(new int[]{i, j});
      }
    }

    int res = 0;
    while (!waiting.isEmpty()) {
      int size = waiting.size();
      for (int k = 0; k < size; k++) {
        int[] pos = waiting.poll();
        int i = pos[0];
        int j = pos[1];
        if (matrix[Math.max(0, i - 1)][j] == '.') {
          matrix[Math.max(0, i - 1)][j] = '#';
          waiting.add(new int[]{Math.max(0, i - 1), j});
        }
        if (matrix[Math.min(h - 1, i + 1)][j] == '.') {
          matrix[Math.min(h - 1, i + 1)][j] = '#';
          waiting.add(new int[]{Math.min(h - 1, i + 1), j});
        }
        if (matrix[i][Math.max(0, j - 1)] == '.') {
          matrix[i][Math.max(0, j - 1)] = '#';
          waiting.add(new int[]{i, Math.max(0, j - 1)});
        }
        if (matrix[i][Math.min(w - 1, j + 1)] == '.') {
          matrix[i][Math.min(w - 1, j + 1)] = '#';
          waiting.add(new int[]{i, Math.min(w - 1, j + 1)});
        }
      }
      res++;
//      for (char[] item : matrix)
//        System.out.println(Arrays.toString(item));
//      System.out.println(" ");

    }

    System.out.println(res-1);
  }

}

Measured memory_bytes: 75060
import sys

sys.setrecursionlimit(2000000)


def update(M, S, i, j, H, W, cluster):
    for i_n in [i - 1, i, i + 1]:
        for j_n in [j - 1, j, j + 1]:
            if i_n >= H or i_n < 0:
                continue
            if j_n >= W or j_n < 0:
                continue

            if i_n == i and j_n == j:
                continue
            if abs(i - i_n) + abs(j - j_n) == 2:
                continue

            if S[i][j] != S[i_n][j_n] and M[i_n][j_n] == 0:
                # print(M)
                M[i_n][j_n] = cluster
                update(M, S, i_n, j_n, H, W, cluster)


H, W = list(map(int, input().split()))
S = []
for i in range(H):
    S.append(input().strip())

cluster = 1
counts_B = {}
counts_W = {}
M = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            M[i][j] = cluster
            update(M, S, i, j, H, W, cluster)
            cluster = cluster + 1
        counts_B[M[i][j]] = 0
        counts_W[M[i][j]] = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            counts_B[M[i][j]] += 1
        else:
            counts_W[M[i][j]] += 1

    #     print(M[i][j], end=" ")
    # print("")

total = 0
for k in counts_B.keys():
    if k in counts_W:
        total += counts_B[k] * counts_W[k]
    # print(counts[k])

print(total)


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

int main() {
	int N;
	cin >> N ;
	vector<int> card(N);
	for (int i = 0 ; i < N ; i++){
		cin >> card[i];
	}

	sort(card.begin(),card.end());
	reverse(card.begin(),card.end());
	int Bob = 0 ,Alice = 0;
	for (int i = 0 ; i < N ; i ++ ){
		if ( i % 2 == 0 ){
			Bob += card[i];
		}
		else {
			Alice += card[i];
		}
	}
	cout << Bob - Alice <<endl;
	
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
/*既に塗った色の配列　tuple(親、子、その間の辺の色)の配列
  を用意
*/


int main(){
    string S;
    cin >> S;
    int N = S.size();
    int ans = 0;

    for(int i = 0;i<N;i++){
      for(int j = 1;j<=N-i;j++){
        string s = S.substr(i,j);
        //cout << s << " " << s.size() << endl;
        bool flag = true;//ACGT文字列かどうか判定
        int c = s.size();
        for(int k = 0;k<c;k++){
          if(s[k] != 'A' && s[k] != 'C' && s[k] != 'G'
           && s[k] != 'T'){
             flag = false;
             break;
           }
        }
        
        if(flag){
         // cout << "true" << endl;
          ans = max(ans,(int)s.size());
        }
      }
    }
    cout << ans << endl;
  }

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

using namespace std;
const int MAX=1e5;
typedef long long ll;
ll a[MAX],dp[MAX];

int main(){
  int n;
  ll sum=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(i%2==0){
      sum+=a[i];
    }
    else{
      sum-=a[i];
    }
  }
  dp[0]=sum/2;
  for(int i=1;i<n;i++){
    dp[i]=a[i-1]-dp[i-1];
  }
  for(int i=0;i<n;i++){
    cout<<2*dp[i]<<" ";
  }
}


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

const int mod = 100000;

int main(){
  int w,h;
  while(cin >> w >> h, w){
    int dp[110][110][4] = {};
    dp[1][0][0] = dp[0][1][1] = 1;

    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(i>0){
          (dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][2]) %= mod;
          (dp[i][j][2] += dp[i-1][j][1]) %= mod;
        }
        if(j>0){
          (dp[i][j][1] += dp[i][j-1][1] + dp[i][j-1][3]) %= mod;
          (dp[i][j][3] += dp[i][j-1][0]) %= mod;
        }
      }
    }

    int ans = 0;
    for(int k=0;k<4;k++) (ans += dp[h-1][w-1][k]) %= mod;
    cout << ans << endl;
  }
}

Measured memory_bytes: 1352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d) cout<<"Left"<<endl;
  else if(a+b<c+d) cout<<"Right"<<endl;
  else cout<<"Balanced"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
    return os << "(" << P.first << "," << P.second << ")";}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
typedef long long ll;
typedef double ld;
#define pll pair<ll,ll>
#define pii pair<int, int>
#define pb push_back
#define mp(x, y) make_pair((x), (y))
#define F first
#define S second
#define I insert
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define all(x) (x).begin(), (x).end()
#define sz(x) (ll)(x).size()

const ll INF = 1e16 + 7;
const int N  = 1e5 + 7;

ll H[N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n , a , b ;
	cin >> n >> a >> b ;
	for(int i = 1;i <= n ;i++)
		cin >> H[i];

	sort(H+1 , H+n+1);
	
	ll l = 1 , r = INF , ans = INF , mid;

	while(l <= r){


		mid = (l+r)>>1;

		bool ok = true;

		ll left = mid;
		for(int i = n ;i >= 1; i--){

			// overflow
			if(b >= (H[i] + mid-1)/mid)
				continue;

			ll req = (H[i] - mid*b + (a-b-1))/(a-b);


			if(req > left){
				ok = false;
				break;
			}

			left -= req;
		}
		if(left < 0)
			ok = false;

		if(ok){
			ans = mid;
			r = mid-1;
		}
		else{
			l = mid+1;
		}
	}
	cout << ans << '\n';



	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#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 srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

bool is_ok(int a, int b, int c, int k) {
  // a < b < c
  while (b <= a) {
    --k;
    b *= 2;
  }
  while (c <= b) {
    --k;
    c *= 2;
  }
  return (k>=0);
}
int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int a, b, c;
  cin >> a >> b >> c;
  int k;
  cin >> k;
  if (is_ok(a, b, c, k)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


Measured memory_bytes: 3644