akhauriyash/Code-Regression huggingface dataset:
// Contest: AtCoder Beginner Contest 175 (https://atcoder.jp/contests/abc175)
// Problem: C: Walking Takahashi (https://atcoder.jp/contests/abc175/tasks/abc175_c)


// region boilerplate
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <chrono>
#include <cstdint>
#include <deque>
#include <exception>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#if __cplusplus >= 201703L
#   include <optional>
#   include <string_view>
#   include <variant>
#endif

using namespace std;

#if __cplusplus >= 201703L
#   define all(a)      begin(a),end(a)
#   define sz(x)       ((int)size(x))
#else
#   define all(a)      (a).begin(),(a).end()
#   define sz(x)       ((int)(x).size())
#endif

#define rep(a, b)      for(int a = 0; a < (b); ++a)
#define reps(a, b, c)  for(int a = (b); a < (c); ++a)
#define trav(a, b)     for(auto& a : b)

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;

#if __cplusplus >= 201703L
#   define MAYBE_UNUSED [[maybe_unused]]
#else
#   define MAYBE_UNUSED
#endif

MAYBE_UNUSED static constexpr int INF = (int)1e9 + 5;
MAYBE_UNUSED static constexpr ll INFL = (ll)1e18 + 5;
MAYBE_UNUSED static mt19937 rng((u32)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion

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

    ll x, k, d; cin >> x >> k >> d;

    if (x < 0) x = -x;
    ll tozero = (x + d - 1) / d;
    if (tozero > k)
        cout << (x - k * d) << '\n';
    else if (tozero % 2 == k % 2)
        cout << (tozero * d - x) << '\n';
    else
        cout << (x - (tozero - 1) * d) << '\n';

    return 0;
}


Measured memory_bytes: 3632
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 9000000000000000000 //9e18:極めて大きい値
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
#define LOGMAXR 18 // floor(log2(10^5)) + 1: 配列の最大のrangeのlog
//略記
//#define PB push_back //vectorヘの挿入
//#define MP make_pair //pairのコンストラクタ
//#define F first //pairの一つ目の要素
//#define S second //pairの二つ目の要素

ll gcd(ll a, ll b){
  a = abs(a);
  b = abs(b);
  if(b < a) swap(a, b);
  if(a == 0) return b;
  return gcd(b % a, a);
}

// n ^ p
ll modpow(ll n, ll p, ll mod){
  ll ret = 1;
  while(p){
    if(p & 1){
      ret *= n;
      ret %= mod;
    }
    p >>= 1;
    n = n * n;
    n %= mod;
  }
  return ret;
}

int main(){
  ll N, K;
  cin >> N >> K;
  ll ret[K];
  REPD(i, K){
    ll x = i + 1;
    ret[i] = modpow(K / x, N, MOD);
    FOR(j, 2, K){
      if(j * x > K) break;
      ret[i] -= ret[j * x - 1];
      while(ret[i] < 0) ret[i] += MOD;
      ret[i] %= MOD;
    }
  }
  ll ans = 0;
  REP(i, K){
    ans += ret[i] * (i + 1);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

int main_back(){
  ll N, K;
  cin >> N >> K;
  ll G[N][20];
  REP(i, N) G[i][0] = 1;
  REP(r, 19){
    REP(i, N) G[i][r + 1] = 0;
    REP(i, N) REP(j, N){
      ll newg = G[i][r] * G[j][r];
      newg %= MOD;
      G[gcd(i + 1, j + 1) - 1][r + 1] += newg;
      G[gcd(i + 1, j + 1) - 1][r + 1] %= MOD;
    }
  }

  cout << G[0][19] << endl;
  return 0;
}


Measured memory_bytes: 3904
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 200 + 10, inf = 1e5;

vector<int> g[N];
int color[N], dist[N];

bool odd_cycle(int u);
int bfs(int s, int n);

int main() {
	fast_cin();
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			char c; cin >> c;
			if (c == '1') {
				g[i].pb(j);
			}
		}
	}
	color[1] = 1;
	if (odd_cycle(1)) {
		cout << -1 << endl;
	} else {
		int ans = 0;
		for (int s = 1; s <= n; ++s) {
			ans = max(ans, bfs(s, n));
		}
		cout << ans << endl;
	}
}

bool odd_cycle(int u) {
	for (auto &v : g[u]) {
		if (color[v] == 0) {
			color[v] = 1 ^ 2 ^ color[u];
			if (odd_cycle(v)) {
				return true;
			}
		} else if (color[v] == color[u]) {
			return true;
		}
	}
	return false;
}

int bfs(int s, int n) {
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
	}
	dist[s] = 0;
	int ans = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		auto u = q.front();
		q.pop();
		for (auto &v : g[u]) {
			if (dist[v] == inf) {
				dist[v] = 1 + dist[u];
				q.push(v);
				ans = dist[v];
			}
		}
	}
	return ans + 1;
}

Measured memory_bytes: 512
import java.util.*

private var unit = listOf(0)

fun mul(A: List<Int>, B: List<Int>): List<Int> = A.map { B[it] }

fun pow(A: List<Int>, k: Long): List<Int> {
    var R = unit
    var B = A
    var l = k

    while (l > 0) {
        if (l and 1 != 0L) {
            R = mul(R, B)
        }
        B = mul(B, B)
        l /= 2
    }

    return R
}

fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map{it.toLong()}
    val A = readLine()!!.split(" ").map{it.toInt()}
    val ts = Array(200010) { TreeSet<Int>() }
    val mp = Array(A.size + 1) { it }

    A.forEachIndexed { index, v -> ts[v].add(index) }
    unit = Array(mp.size) {it}.asList()

    mp[A.size] = 0
    for (i in A.indices.reversed()) {
        if (i == A.size - 1) {
            mp[i] = ts[A[i]].first() + 1

            continue
        }

        val a = ts[A[i]].higher(i)
        if (a != null) {
            if (a >= mp.size - 1) {
                mp[i] = 0
            } else {
                mp[i] = mp[a + 1]
            }
        } else {
            mp[i] = ts[A[i]].first() + 1
        }
    }

    var B = pow(mp.asList(), K - 1)
    if (B[0] == B.size - 1) {
        B = pow(mp.asList(), K - 2)
    }

    val S = ArrayDeque<Int>()
    val st = TreeSet<Int>()

    for (i in B.first() % A.size until A.size) {
        if (st.contains(A[i])) {
            while (S.isNotEmpty()) {
                st.remove(S.last)
                if (S.pollLast() == A[i]) {
                    break
                }
            } } else {
            S.addLast(A[i])
            st.add(S.last)
        }
    }

    println(S.joinToString(" "))
}


Measured memory_bytes: 166720
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    int X;
    cin >> X;
    if (X >= 30) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <stdio.h>
#define MAX 100

int A[MAX];
int change_num = 0;

void bubbleSort(int n) {
    int flag = 1;
    int index = 0;
    while (flag) {
        flag = 0;
        for ( int j = n-1; j > index; j-- ) {
            if ( A[j] < A[j-1] ) {
                std::swap(A[j], A[j-1]);
                flag = 1;
                change_num ++;
            }
        }
        index ++;
    }
}

int main() {
    int n;
    scanf( "%d\n", &n );
    
    for ( int i = 0; i < n; i++ ) {
        int tmp;
        std::cin >> tmp;
        A[i] = tmp;
    }
    
    bubbleSort(n);
    
    for (int i= 0; i < n; i++) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    
    printf("\n");
    printf("%d\n", change_num);
    
    return 0;
}

Measured memory_bytes: 3216
def main():
    from itertools import accumulate
    from collections import Counter
    _ = int(input())
    A = [int(i) for i in input().split()]
    S = list(accumulate([0] + A))
    c = Counter(S)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()


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

int n, a[21], b[21], c[21], fp;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i], fp += b[i];
    for(int i = 1; i < n; ++i) cin >> c[i];
    for(int i = 1; i < n; ++i) {
    	if(a[i + 1] - 1 == a[i]) {
    		fp += c[a[i]];
		}
	}
	cout << fp << endl;
	return 0;
}


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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

void solve() {
  string s, t;
  cin >> s >> t;
  cout << t << s;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    set<int> ws;
    REP(i, 31) REP(j, 15) {
        if (i * a * 100 + j * b * 100 > f) continue;
        ws.insert(i * a * 100 + j * b * 100);
    }
    double mp = 0.0;
    int w = 0;
    int s = 0;
    double p;
    for (auto x : ws) {
        REP(i, x / 100 * e + 1) REP(j, x / 100 * e + 1) {
            if (i * c + j * d > x / 100 * e) continue;
            if (x + i * c + j * d > f) continue;
            p = (100.0 * (i * c + j * d)) / (x + (i * c + j * d));
            if (mp < p) {
                mp = p;
                w = x;
                s = i * c + j * d;
            }
        }
    }
    if (s == 0) {
        cout << 100 * a << " 0" << endl;
    } else {
        cout << (w + s) << " " << s << endl;
    }
}


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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define mp make_pair
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

int N, A;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

signed main() {
    cin >> N;
    int ans = 0;
    REP(i, N) {
        cin >> A;
        ans = gcd(A, ans);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int change(int x, int y){
    if(x > y) {
        return x-1;
    }
    return x;
}
 
int kaijo(int x) {
    int ans=1;
    for(int i=1;i<=x;i++){
        ans*=i;
    }
    return ans;
}
 
int main() {
    int N;
    scanf("%d", &N);
    int *P = (int*)malloc(N * sizeof(int));
    int *Q = (int*)malloc(N * sizeof(int));
    for(int i=0; i<N; i++) {
        scanf("%d", &P[i]);
    }
    for(int i=0; i<N; i++) {
        scanf("%d", &Q[i]);
    }
    int a = 0, b = 0;
    for(int i=0; i<N-1; i++) {
        a += (P[i] - 1) * kaijo(N-i-1);
        b += (Q[i] - 1) * kaijo(N-i-1);
        for(int j=i+1; j<N; j++) {
            P[j] = change(P[j], P[i]);
			Q[j] = change(Q[j], Q[i]);
        }
    }
    printf("%d\n", abs(a-b));
 
    free(P);
    free(Q);
    return 0;
}

Measured memory_bytes: 128
#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;
const int MAX_N = 2005;
vector<int> L;

int main()
{
	int N;
	cin >> N;
	rep(i,N)
	{
		int l;
		cin >> l;
		L.push_back(l);
	}

	sort(L.begin(),L.end());
	int ans = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = i+1; j < N; ++j)
		{
			int now = L[i] + L[j];
			ans += (lower_bound(L.begin()+j+1,L.end(),now) - L.begin()) - j - 1;
			//cout << i << " " << j << " " << now << " " << lower_bound(L.begin()+j+1,L.end(),now) - L.begin() << " " << ans << endl;
		}
	}

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

Measured memory_bytes: 256
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[][] l = new int[100001][2];
		int[][] r = new int[100001][2];
		for (int i = 0; i < N; i++) {
			int d = in.nextInt();
			if (i % 2 == 0) {
				l[d][0] = d;
				l[d][1]++;
			} else {
				r[d][0] = d;
				r[d][1]++;
			}
		}
		Arrays.sort(l, (x, y) -> Integer.compare(x[1], y[1]));
		Arrays.sort(r, (x, y) -> Integer.compare(x[1], y[1]));
		if (l[l.length - 1][0] != r[r.length - 1][0]) {
			System.out.println(N - l[l.length - 1][1] - r[r.length - 1][1]);
		} else {
			System.out.println(
					Math.min(N - l[l.length - 2][1] - r[r.length - 1][1], N - l[l.length - 1][1] - r[r.length - 2][1]));
		}
		in.close();
	}
}

Measured memory_bytes: 68820
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define dump(o) { cerr << #o << " " << o << endl; }
#define dumpc(o) { cerr << #o; for (auto &e : (o)) cerr << " " << e; cerr << endl; }
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

int main() {
	int N, M; cin >> N >> M;
	vector<int> t(N,1), r(N, 0);
	r[0] = 1;
	//dumpc(t); dumpc(r);
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		r[y] += r[x];
		t[x]--; t[y]++;
		if (t[x] == 0)r[x] = 0;
		//dumpc(t); dumpc(r);
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (r[i] > 0)cnt++;
	}
	cout << cnt << endl;
	return 0;
}

//int main() {
//	int N, M; cin >> N >> M;
//	vector<double> r(N), w(N, 1);
//	r[0] = 1; w[0] = 0;
//	dumpc(r); dumpc(w);
//	for (int i = 0; i < M; i++) {
//		int x, y; cin >> x >> y;
//		x--; y--;
//		if (r[x] + w[x] == 1) {
//			r[y] += r[x];
//			w[y] += w[x];
//			r[x] = w[x] = 0;
//		}
//		else {
//			double W = w[x] * w[x] / (w[x] + r[x]), R = r[x] * r[x] / (w[x] + r[x]);
//			r[y] += R;
//			w[y] += W;
//			r[x] -= R;
//			w[x] -= W;
//		}
//		dumpc(r); dumpc(w);
//	}
//	int cnt = 0;
//	for (int i = 0; i < N; i++) {
//		if (r[i] > 0)cnt++;
//	}
//	cout << cnt << endl;
//	return 0;
//}

Measured memory_bytes: 1024
//ITP1_3_C

using System;
using System.Collections.Generic;
/*using System.Linq;
using System.Text;
using System.Threading.Tasks;*/

class Program { 
    static void Main(string[] args)
    {
        int i = 0;
        while (i++ < 3000) {

            //?????????????????????????????????int??????iaaray????????????????????\

            int[] iarray = Array.ConvertAll<string, int>((Console.ReadLine().Split(' ')), delegate (string value)
            {
                return int.Parse(value);
            });

            if (iarray[0] == 0 && iarray[1] == 0)       //??\??????????????¨???0????????????
                break;

            Array.Sort(iarray);             //???????????§???????????????
            Console.WriteLine(iarray[0] +" "+ iarray[1]);
        }
    }

}

Measured memory_bytes: 9492
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

#import math,heapq
from math import sqrt
from heapq import heappush,heappop

def pdist(x1,y1,x2,y2):
    return sqrt((x2-x1)**2+(y2-y1)**2)

xs,ys,xt,yt = inm()
n = inn()
cir = []
for i in range(n):
    x,y,r = inm()
    cir.append((x,y,r))
dst = [[0]*(n+2) for i in range(n+2)]
dst[n][n+1] = dst[n+1][n] = pdist(xs,ys,xt,yt)
for i in range(n):
    x,y,r = cir[i]
    dst[n][i] = dst[i][n] = max(0.0,pdist(xs,ys,x,y)-r)
    dst[n+1][i] = dst[i][n+1] = max(0.0,pdist(xt,yt,x,y)-r)
    for j in range(i+1,n):
        xx,yy,rr = cir[j]
        dst[j][i] = dst[i][j] = \
          max(0.0,pdist(xx,yy,x,y)-rr-r)

if False and DBG:
    for i in range(n+2):
        ddprint(dst[i])

cost = [float(BIG)]*(n+2)
q = [(0.0,n)]
while len(q)>0:
    d,p = heappop(q)
    #ddprint(f"{d=} {p=}")
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in range(n+2):
        newdist = d+dst[p][v]
        if v!=p and newdist<cost[v]:
            heappush(q,(newdist, v))

print(cost[n+1])


Measured memory_bytes: 146820
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include<bits/stdc++.h>
#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 ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  string s;
  cin >>s;
  if(s[5]=='0'&&(s[6]=='4'||s[6]=='3'||s[6]=='2'||s[6]=='1'))cout <<"Heisei"<<endl;
  else cout <<"TBD"<<endl;
}
  


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    bridge = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        bridge.append((a, b))

    # unionfindは辺の追加しかできないので、後ろからやっていく
    tree = UnionFind(N)
    inconv = [N * (N - 1) // 2]
    for _ in range(M - 1):
        a, b = bridge.pop()
        if tree.same(a, b):
            inconv.append(inconv[-1])
        else:
            num_a = tree.size(a)
            num_b = tree.size(b)
            inconv.append(inconv[-1] - num_a * num_b)
        tree.union(a, b)

    for _ in range(M):
        x = inconv.pop()
        print(x)




if __name__ == "__main__":
    main()


Measured memory_bytes: 87072
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <queue>
#include <list>
#include <map>
#include <numeric>
#include <stack>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <strstream>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
typedef long long ll;

int x=10,y=10;

int measure(char c,int m,bool jewel[][21],int flag){
	if(c == 'N'){
		rep(i,m){
			y++;
			if( jewel[x][y] ){
				flag++;
				jewel[x][y] = false;
			}
		}
	}
	else if(c == 'E'){
		rep(i,m){
			x++;
			if( jewel[x][y] ){
				flag++;
				jewel[x][y] = false;
			}
		}
	}
	else if(c == 'S'){
		rep(i,m){
			y--;
			if( jewel[x][y] ){
				flag++;
				jewel[x][y] = false;
			}
		}
	}
	else if(c == 'W'){
		rep(i,m){
			x--;
			if( jewel[x][y] ){
				flag++;
				jewel[x][y] = false;
			}
		}
	}
	return flag;
}

int main(){
	int n,m;

	while( cin >> n ,n){
		x=10,y=10;
		bool jewel[21][21] = {0};
		int flag = 0;
		
		rep(i,n){
			int x,y;
			cin >> x >> y;
			jewel[x][y] = true;
		}
		
		cin >> m;
		
		rep(i,m){
			char compass;
			int di;
			cin >> compass >> di;
			flag += measure(compass,di,jewel,0);
		}
		if( n == flag ) puts("Yes");
		else puts("No");
	}
	return 0;
}

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

int main(){
    string a, b;
    cin >> a >> b;

    int x = stoi(a+b);

    for(int i = 1; i <= sqrt(x); i++){
        if(i*i == x){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

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

char next(char X){
  if (X=='a') return 'a';
  else if (X=='b') return 'b';
  else return 'c';
}

int main(){
  string Sa, Sb, Sc;
  cin >> Sa >> Sb >> Sc;
  
  char now='a';
  bool x=true;
  while(x){
    if (now=='a'){
      if (Sa.empty()){
        cout << 'A' <<endl;
        return 0;
      }
      now=next(Sa[0]);
      Sa.erase(Sa.begin());
    }else if (now=='b'){
      if (Sb.empty()){
        cout << 'B' <<endl;
        return 0;
      }
      now=next(Sb[0]);
      Sb.erase(Sb.begin());
    }
    else if (now=='c'){
      if (Sc.empty()){
        cout << 'C' <<endl;
        return 0;
      }
      now=next(Sc[0]);
      Sc.erase(Sc.begin());
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-11)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	vd x(3),y(3),e(3);
	cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2];
	e[0]=hypot(x[0]-x[1],y[0]-y[1]);
	e[1]=hypot(x[2]-x[1],y[2]-y[1]);
	e[2]=hypot(x[0]-x[2],y[0]-y[2]);
	double m=*max_element(all(e));
	double s=(e[0]+e[1]+e[2])/2;
	double S=sqrt(s*(s-e[0]))*sqrt((s-e[1])*(s-e[2]));
	double R=S/s;
	double l=0,r=1000;
	while(abs(r-l)>EPS){
	    double d=(r+l)/2;
	    double x=(R-d)*m/R;
	    if(x>=d*2){
	        l=d;
	    }else{
	        r=d;
	    }
	}
	fcout(12)<<l<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <unistd.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#define PI 3.14159265358979323846

using namespace std;

int main()
{
	int A, B, C;

	cin >> A >> B >> C;

	if((C>A and C<B) or (C>B and C<A))
		cout << "Yes\n";
	else
		cout << "No\n";

	return 0;
}

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

using namespace std;

int main(){
    int p[3];
    int max_p = 0;
    int sum = 0;
    for(int i = 0; i < 3; i++){
        scanf("%d", &p[i]);
        max_p = max(max_p, p[i]);
        sum += p[i];
    }

    printf("%d\n", sum - max_p);

    return 0;
}

Measured memory_bytes: 128
fun main(args: Array<String>) {
    val n = readInt()
    val v = readIntList().sorted()

    var ans = 0.0
    ans += (v[0] + v[1]) / 2.0
    for (i in 2 until n) {
        ans = (ans + v[i]) / 2.0
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

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

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
const int INF = 1e9;
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
using namespace std;

void solve()
{
    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int ki = 0, gu = 0;
    for (auto i : a)
    {
        if (i % 2 == 0)
            gu++;
        else
            ki++;
    }
    if (ki == 0)
    {
        if (p == 0)
            cout << ((ll)1 << n) << endl;
        else
            cout << 0 << endl;
    }
    else
        cout << ((ll)1 << (n - 1)) << endl;
}
int main(void)
{
    solve();
}

Measured memory_bytes: 3596
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'
const int inf = 1e9+7;
const int N = 1e6+9;
int f[N+9];

void solve() {
	int a, b, n;
	cin>>n;
	set<int> st;
	for(int i=1;i<=n;++i) {
		cin>>a;
		f[a]++;
		st.insert(a);
	}

	int cnt=0;
	for(auto p: st) {
		if(f[p]>1) {
			cnt+=f[p];
			f[p]=0;
		}
		for(int i=p+p;i<N;i+=p) {
			cnt+=f[i];
			f[i]=0;
		}
	}
	cout<<n-cnt<<endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    int T=1 ,cas=0;
    while(T--) {
    	solve();
    }
    return 0;
}

// ll, reset, 1, bottom

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

int main()
{
  int A, B, H, M;
  cin >> A >> B >> H >> M;
  M += H * 60;
  double theta_A = M * M_PI / 360.0, theta_B = M * M_PI / 30.0;
  double x_A = A * cos(theta_A), y_A = A * sin(theta_A), x_B = B * cos(theta_B), y_B = B * sin(theta_B);
  double d = sqrt((x_A - x_B) * (x_A - x_B) + (y_A - y_B) * (y_A - y_B));
  printf("%.21f\n", d);
}

Measured memory_bytes: 4068
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, char> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};

int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }




int main()
{
	int n, q;
	cin >> n >> q;
	vi a(n);
	int par = sqrt(n);
	vi v(n / par + 1);
	int cnt = 0, sum = 0;
	REP(i, q)
	{
		int c, x, y;
		cin >> c >> x >> y;
		if (c == 0)
		{
			x--;
			v[x / par] += y;
			a[x] += y;
		}
		else
		{
			x--;
			int ans = 0;
			int i = x;
			for (; i < y && i%par != 0;i++)
			{
				ans += a[i];
			}
			for (; i + par <= y; i += par)
			{
				ans += v[i / par];
			}
			for (i; i < y; i++)
			{
				ans += a[i];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1524
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! { a:usize, b:usize, c:usize }
    let w = c / (7 * a + b);
    let r = c - (7 * a + b) * w;
    println!("{}", 7 * w + std::cmp::min((r + a - 1) / a, 7));
}



Measured memory_bytes: 5032
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cinttypes>

#define fi first
#define se second

using namespace std;

typedef int64_t ll;
typedef uint64_t ull;

const ll INF = 1e18 + 10;
const double EPS = 1e-9;

typedef pair<int, int> P;
inline P operator+(const P& p1, const P& p2) {
  return P(p1.first + p2.first, p1.second + p2.second);
}

int main() {
  string S;
  cin >> S;
  string T = S;
  reverse(T.begin(), T.end());

  int n = T.find("LAVITSEF");

  for (int i = 0; i < S.size() - n - 8; i++) {
    cout << S[i];
  }

  cout << endl;

  return 0;
}


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

int main() {
    int N, H, W;
    cin >> N >> H >> W;
    int answer = 0;
    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        if (A >= H && B >= W) ++answer;
    }
    cout << answer << endl;
}

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

set<P> st; // first=y second=x
int H, W, M;
void input() {
  cin >> H >> W >> M;
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    st.emplace(a, b);
  }
}

void solve() {
  map<int, int> mapY, mapX;
  int maxY = 0, maxX = 0;
  for (auto p : st) {
    maxY = max(maxY, ++mapY[p.first]);
    maxX = max(maxX, ++mapX[p.second]);
  }

  vector<int> vY;
  for (auto e : mapY) {
    if (maxY == e.second)
      vY.emplace_back(e.first);
  }
  vector<int> vX;
  for (auto e : mapX) {
    if (maxX == e.second)
      vX.emplace_back(e.first);
  }

  int ans = maxY + maxX;
  for (auto y : vY) {
    for (auto x : vX) {
      if (st.find({y, x}) == st.end()) {
        cout << ans << endl;
        return;
      }
    }
  }
  cout << ans - 1 << endl;
}

int main() {
  input();
  solve();
  getchar();
  return 0;
}

// 写経
// 回答例(C++, kort0n氏より引用)
// https://atcoder.jp/contests/abc176/submissions/16180005
// https://atcoder.jp/contests/abc176/editorial/66

Measured memory_bytes: 49660
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string T;
  cin >> T;
  int sizeT = T.size();
  vector<char> S(sizeT);
  for (int i = 0; i < sizeT; i++) {
    if (T.at(i) == 'P' || T.at(i) == 'D') {
      S.at(i) = T.at(i);
    } else {
      S.at(i) = 'D';
    }
  }
  for (int i = 0; i < sizeT; i++) {
    cout << S.at(i);
  }
  cout << endl;
}

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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string s, t;
  cin >> s >> t;

  int ans = 0;
  for ( int i = 0; i < 3; i++ ) {
    if ( s[i] == t[i] ) ans++;
  }

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


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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

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

template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  ll n;
  cin >> n;

  if (n <= 2) {
    cout << 0 << endl;
    return 0;
  }

  ll ans = 0;
  for (ll i = 1; i * i < n - i; i++) {
    ll m = (n - i) / i;
    if ((n - i) % i == 0 and n - i == i * m) {
      // mod, fav number
      // cout << i << " " << m << endl;
      ans += m;
    }
  }

  cout << ans << endl;

  return 0;
}


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

#define lop(i,s,e)                                for(int i=s;i<(int)e;i++)
const int N = 1e6 + 7, M = 1000000007, inf = INT_MAX;

int freq[N], f2[N];


void solve()
{
	int n;
	cin >> n;

	int arr[n], brr[n], res[n];
	lop(i, 0, n) cin >> arr[i], f2[ arr[i] ]++;
	lop(i, 0, n) cin >> brr[i], freq[ brr[i] ]++;

	lop(i, 0, n + 1) if ( f2[i] + freq[i] > n )
	{
		cout << "No" << endl;
		return;
	}

	reverse(brr, brr + n);
	vector<int> pos1, pos2;
	lop(i, 0, n)	if ( arr[i] == brr[i] )  pos1.push_back(i);
	int x = -1;
	if ( pos1.size() ) x = arr[ pos1[0] ];
	lop(i, 0, n)
	{
		if ( arr[i] == brr[i] or arr[i] == x or brr[i] == x )continue;
		pos2.push_back(i);
	}

	for (auto &i : pos1)
	{
		swap( brr[i], brr[ pos2.back() ]);
		pos2.pop_back();
	}
	cout << "Yes" << endl;
	lop(i, 0, n) cout << brr[i] << " "; cout << endl;
}

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

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


}






















Measured memory_bytes: 7576
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>

using namespace std;

const int Maxn=60;

const long double g=9.8;
const long double eps= 1e-8;

int N; long double V,X,Y;

long double L[Maxn],B[Maxn],R[Maxn],T[Maxn];

long double Calcy(long double vy,long double t){return vy*t-0.5*g*t*t;}
long double Calcx(long double vx,long double t){return vx*t;}

int cmp(long double lb,long double ub,long double a)
{
  return a<lb ? -1 : a>ub-eps ? 1 : 0;
}

bool Check(long double x,long double y) // ????????????(x,y) 
{
  long double a=0.25*g*g; long double b=g*y-V*V; long double c=x*x+y*y;
  long double delta= b*b-4*a*c;
  if(delta < 0 && delta > -eps) delta=0.0;
  else if(delta < 0) return 0;
  for(int op=-1;op<=1;op+=2)
  {
    long double t=sqrt((-b+sqrt(delta)*op)/(2.0*a));
    if(t<=0) continue;
    long double vx=x/t; long double vy=(y+0.5*g*t*t)/t; //?????????
    long double yt=Calcy(vy,X/vx); //???????¨?????????????
   	if(yt < Y-eps) continue;
   	bool ok=1;
   	for(int i=1;i<=N;i++)
   	{
   	  if(L[i] >= X) continue;
   	  if(R[i] == X && yt >= T[i] && B[i] >= Y){ok=0; break;}
   	  int yL=cmp(B[i],T[i],Calcy(vy,L[i]/vx));
   	  int yR=cmp(B[i],T[i],Calcy(vy,R[i]/vx));
   	  int xH=cmp(L[i],R[i],Calcx(vx,vy/g));
   	  int yH=cmp(B[i],T[i],Calcy(vy,vy/g));
   	  if( xH == 0 && yH >= 0 && yL<=0){ok=0; break;}
   	  if(yL * yR <=0){ok=0; break;}
   	}
   	if(ok) return 1;
  } 
  return 0;
}

int main()
{

  cin >> N >> V >> X >> Y;
  for(int i=1;i<=N;i++) cin >> L[i] >> B[i] >> R[i] >> T[i];

  for(int i=1;i<=N;i++) R[i]=min(R[i],X);

  bool ok=0;
  ok=Check(X,Y);

  for(int i=1;i<=N;i++) ok|=Check(L[i],T[i]);

  puts(ok ? "Yes" : "No");

  return 0;
}

Measured memory_bytes: 3232
def ed(x, y):
    if len(x) > len(y):
        x, y = y, x
    nx, ny = len(x), len(y)
    dp = [[0] * (nx+1) for _ in range(ny+1)]

    for i in range(1, ny+1):
        dp[i][0] = i
        if i < nx+1: dp[0][i] = i
    
    for i in range(1, ny+1):
        for t in range(1, nx+1):
            dp[i][t] = min(dp[i-1][t-1]+(x[t-1]!=y[i-1]), dp[i-1][t]+1, dp[i][t-1]+1)

    return dp[-1][-1]

x, y = input().rstrip(), input().rstrip()
print(ed(x, y))


Measured memory_bytes: 43048
#include<bits/stdc++.h>
using namespace std;
 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////
typedef struct _a{
	int x;
	int y;
	ll h;
}a;

int main(){
	int n;
	cin >> n;
	vector<a> v(n);
	rep(i,0,n)
		cin >> v[i].x >> v[i].y >> v[i].h;

	a ans = {0,0,0};
	rep(i,0,101){
		rep(j,0,101){
			ll H;
			rep(k,0,n){
				if( v[k].h > 0 )
					H = v[k].h + abs( v[k].x - j ) + abs( v[k].y - i );
			}
			H = max( H , 0LL );
			bool f = true;
			rep(k,0,n){
				ll h = H - abs( v[k].x-j ) - abs(	v[k].y-i );
				h = max( h , 0LL );
				if( h != v[k].h ){
					f = false;
					break;
				}
			}
			if(f && H > 0 ){
				if( H > ans.h ){
					ans.x = j;
					ans.y = i;
					ans.h = H;
				}
			}
		}
	}
		
	cout << ans.x << " " << ans.y << " " << ans.h << endl;

	ret 0;
}

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


using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(n) n.begin(),n.end()
#define eb emplace_back
#define endl "\n"

const ll maxn=3e5+50;

const ll maxx=1e13;
const ll mod1=1000000007;
const ll mod=998244353;


ll p,q, r;
ll a[maxn];
ll b[maxn];
ll c[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.txt","r",stdin);
    //freopen("FRAC.INP", "r", stdin);
    // freopen("WALKING.OUT", "w", stdout);
    ll len, n;
    cin>>len>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    ll mn=1e15;
    for (int i=2;i<=n;i++)
    {
        ll t= a[i]-a[i-1];
        mn=min(mn,len-t);
    }
    mn=min(mn, a[n]-a[1]);
    cout <<mn;
}


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

int main()
{
    double z[21];
    z[0]=1;
    for(int i=1; i<=20; i++)
        z[i]=z[i-1]*2;
    double n; int k;
    cin>>n>>k;
    double ans=0.0;
    for(int i=1; i<=n; i++)
    {
        double x=k/i; int y;
        if(k%i!=0) x++;
        for(int j=0; j<=20; j++)
            if(z[j]>=x)
            {
                y=j;
                break;
            }
        ans = ans + ((1/n)*(1/z[y]));
    }
    cout<<fixed;
    cout<<setprecision(15)<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
def calc(mae,ushiro):
    reverse_mae = ''.join(list(reversed(mae)))
    if ushiro == reverse_mae:
        cnt = 0
    else:
        cnt=0
        for i in range(len(ushiro)):
            if ushiro[i] == reverse_mae[i]:
                pass
            else:
                cnt+=1
    return cnt


s = input()
if len(s) == 1:
    print(0)

elif len(s)%2==0:
    mae = s[:len(s)//2]
    ushiro = s[len(s)//2:]
    cnt = calc(mae,ushiro)
    print(cnt)

else:
    mae = s[:len(s)//2]
    ushiro = s[len(s)//2+1:]
    cnt = calc(mae,ushiro)
    print(cnt)



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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> b[i];
  rep(i,n) cin >> c[i];
  ll res = 0;
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  for (int i = 0; i < n; i++) {
    auto itr1 = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
    auto itr2 = upper_bound(c.begin(), c.end(), b[i]) - c.begin();
    itr2 = n - itr2;
    res += (ll)itr1 * itr2;
  }
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

void failed(){
    cout<<"No"<<endl;
    exit(0);
}

void solve(vector<string> &s){
    vec pn(0), p(0), mn(0), m(0);
    rep(i,N){
        ll need = 0, plus = 0;
        for(char c : s[i]){
            plus += (c == '(' ? 1 : -1);
            need = max(need, -plus);
        }
        if(plus >= 0){
            pn.push_back(need);
            p.push_back(plus);
        }else{
            mn.push_back(need);
            m.push_back(plus);
        }
    }
    vec op(p.size()), om(m.size());
    int nump = p.size(), numm = m.size();
    rep(i,nump) op[i] = i;
    rep(i,numm) om[i] = i;
    sort(ALL(op), [&](int x, int y){return pn[x] < pn[y];});
    sort(ALL(om), [&](int x, int y){
        return mn[x] + m[x] > mn[y] + m[y];
    });
    ll adv = 0, id = 0;
    while(id != nump && pn[op[id]] <= adv){
        adv += p[op[id]];
        ++id;
    }
    if(id != nump) failed();
    id = 0;
    while(id != numm && mn[om[id]] <= adv){
        adv += m[om[id]];
        ++id;
    }
    if(id!=numm) failed();
    return;
}
int main() {
    cin>>N;
    vector<string> s(N);
    rep(i,N) cin>>s[i];
    ll num = 0;
    rep(i,N){
        for(char c : s[i]) num += (c == '(' ? 1 : -1);
    }
    if(num != 0)failed();
    solve(s);
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 58040
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#include<bitset>
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
int euclid( int a, int b )
{
    int temp;
    
    if( a < b ) { temp = a; a = b; b = temp; }
    if( b < 1 ) return -1;
    
    if( a % b == 0 ) return b;
    return euclid( b, a % b );
}
signed  main(){
    int n,x;cin>>n>>x;
    vector<int>v;
    rep(i,0,n){
        int a;cin>>a;
        v.push_back(a);
    }v.push_back(x);
    sort(v.begin(),v.end());
    int ans=v[1]-v[0];
    rep(i,2,n+1){
        if(v[i]==v[i-1])continue;
        ans=euclid(ans,v[i]-v[i-1]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1012345678;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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



int l[1000000];
int r[1000000];
int num[1000000];
int main(){
  int N, Q;
  int ans = 0;
  cin >> N >> Q;
  string s;
  cin >> s;
  rep(i,Q){
    cin >> l[i] >> r[i];
  }
  rep(i,N-1){
    if(s.substr(i,2) == "AC"){
      ans++;
    }
    num[i] = ans;
  }
  cout << endl;
  rep(i,Q){
    cout << num[r[i] - 2] - num[l[i] - 2] << endl;
  }
}


Measured memory_bytes: 9600
#include <iostream>
using namespace std;
int main()
{
	string s;
	cin>>s;
	if(tolower(s[2])==tolower(s[3])&&tolower(s[4])==tolower(s[5])&&s.size()==6){
		cout<<"Yes";
	}
	else{
		cout<<"No";
		}
}

Measured memory_bytes: 256