akhauriyash/Code-Regression huggingface dataset:
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map(String::toLong)
    val union = UnionFind(n.toInt())
    for (i in 1..m) {
        val (x, y, z) = readLine()!!.split(' ').map(String::toInt)
        union.union(x - 1, y - 1)
    }
    println(union.count())
}

class UnionFind(private var num: Int) {
    private val parent: IntArray = IntArray(num)
    private val rank: IntArray = IntArray(num)
    private val size: IntArray = IntArray(num)

    init {
        for (i in 0 until num) {
            parent[i] = i
            rank[i] = 1
            size[i] = 1
        }
    }

    fun union(u: Int, v: Int): Int {
        var u = u
        var v = v
        u = root(u)
        v = root(v)
        if (u == v)
            return u
        if (rank[v] < rank[u]) {
            val t = v
            v = u
            u = t
        }
        parent[u] = v
        rank[v] += rank[u]
        rank[u] = -1
        num--

        return v
    }

    fun root(u: Int): Int {
        var u = u
        while (parent[u] != u)
            u = parent[u]
        return u
    }

    fun count(): Int {
        return parent.filterIndexed { index, i -> index == i }.size
    }
}

Measured memory_bytes: 58176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,t;
ll dp[3009][3009],b[3009][3009];
void best(ll x,ll y)
{
    if(x==s.size()||y==t.size())
    return void(dp[x][y]=0);
    ll &r=dp[x][y];
    if(r!=-1) return;
    if(s[x]==t[y]){
    best(x+1,y+1);
    r=dp[x+1][y+1]+1;
    b[x][y]=2;
    return;
    }
    best(x+1,y);
    best(x,y+1);
    if(dp[x+1][y]>dp[x][y+1]){
        r=dp[x+1][y];
    }
    else{
        r=dp[x][y+1];
        b[x][y]=1;
    }
    return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s>>t;
memset(dp,-1,sizeof dp);
best(0,0);
ll x=0,y=0;
while(x<s.size()&&y<t.size()){
    if(s[x]==t[y])
    cout<<s[x];
    if(b[x][y]==2)
    x++,y++;
    else if(b[x][y])
    y++;
    else x++;
}
return 0;
}


Measured memory_bytes: 145340
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	string S;
	cin >> S;
	rep(i, S.size() - 8)cout << S[i];
}

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

using namespace std;

int main(){
	
	int n, loop, count;
	
	bool same;
	
	int a[20], b[20];
	
	cin >> n;
	
	while(n != 0){
		
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		
		for(loop = 0; loop < 20; loop++){
			if(loop % 2 == 0){
				for(int i = 0; i < n; i++){
					count = 0;
					for(int j = 0; j < n; j++){
						if(a[i] == a[j]){
							count++;
						}
					}
					b[i] = count;
				}
			}else{
				for(int i = 0; i < n; i++){
					count = 0;
					for(int j = 0; j < n; j++){
						if(b[i] == b[j]){
							count++;
						}
					}
					a[i] = count;
				}
			}
			
			same = true;
			
			for(int i = 0; i < n; i++){
				if(a[i] != b[i]){
					same = false;
					break;
				}
			}
			if(same){
				break;
			}
		}
		
		printf("%d\n", loop);
		printf("%d", a[0]);
		
		for(int i = 1; i < n; i++){
			printf(" %d", a[i]);
		}
		
		printf("\n");
		
		cin >> n;
	}
	
	return 0;
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int mod = 1000000007;
  int n;
  long long int a[200005];
  cin >> n;
  for (int x = 0; x < n; ++x) {
	cin >> a[x];
  }
  long long int sum = 0;
  for (int i = 1; i < n; ++i) {
   	   sum += a[i];
       sum = sum % mod;
  }
  long long int ans = 0;
  for (int j = 0; j < n-1; ++j) {
		ans += a[j] * sum;
        ans %= mod;
        sum -= a[j+1];
        if (sum < 0) {sum += mod;}
  }
  cout << ans << endl;
 return 0; 
}

Measured memory_bytes: 5112
#!/usr/bin/env python3

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

# for i in range():

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

ab.sort()
# print(ab)
ans = 0
div = -1, -1
for i in range(len(ab)):
    a, b = ab[i]
    # print(a, b)

    if a == div[0]:
        continue
    elif a >= div[1]:
        div = a, b
        ans += 1
    else:
        div = a, min(b, div[1])
    # print(div, ans)

print(ans)


Measured memory_bytes: 27660
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl;
#define INF 1ll<<60;
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; }

using namespace std;
using ll = long long;
typedef pair<int, int> P;

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    vector<int> c;

    int n = min(a, b);
    for(int i=n; 1<=i; i--){
        if(a%i==0&&b%i==0){
            c.push_back(i);
        }
    }

    out(c[k-1]);
}

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

int main()
{
	int n;
	cin >> n;
	if(n==1)
	{
		cout << "Hello World" << endl;
		return 0;
	}
	else 
	{
		int a,b;
		cin >> a >> b;
		cout << a+b << endl;
		return 0;
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  if (a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) cout << "Possible" << endl;
  else cout << "Impossible" << endl;

  return 0;
}


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

#define pb push_back
#define fi first
#define se second
typedef long long ll;

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

	string s;
	cin >> s;

	int ans = 0, n = s.length();
	for (int i = 0; i < (n + 1) / 2; ++i)
		if (s[i] != s[n - i - 1])
			ans++;
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef vector<ll> vec;
typedef pair<ll, ll> P;
 
int main(){
    ll n, m, sum=0;
        cin >> n >> m;
    string ans="No";
 
    vec v(n);
        for(int i=0; i<n; i++){
            cin >> v.at(i);
            sum += v.at(i);
        }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    //for(int i=0; i<n; i++) cout << v.at(i)<<endl;
    if(sum<=4*m*v.at(m-1)) ans = "Yes";
    cout << ans << endl;
    
}



Measured memory_bytes: 256
n, m, x = gets.split.map!(&:to_i)
c = []
a = Array.new(n) { gets.split.map!(&:to_i).tap { |t| c << t.shift } }

if a.transpose.map!(&:sum).any? { |xi| xi < x }
  puts(-1)
  exit 0
end

y = 99999999
z = 1 << n
(1...z).each do |d|
  bool = (d + z).digits(2)
  bool.pop

  xx = bool.zip(a).keep_if { |b, *| b != 0 }.map!(&:last).transpose.map!(&:sum)
  if xx.all? { |xi| xi >= x }
    yy = bool.zip(c).keep_if { |b, *| b != 0 }.map!(&:last).sum
    y = yy if yy < y
  end
end

puts y

load __FILE__ unless $stdin.eof?



Measured memory_bytes: 14388
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int d;
    ll g;
    cin >> d >> g;
    vector<ll> p(d), c(d);
    for(int i = 0; i < d; i++) {
        cin >> p[i] >> c[i];
    }
    int ans = numeric_limits<int>::max();
    for(int mask = 0; mask < 1 << d; mask++) {
        int to_solve = 0, score = 0;
        vector<int> inc;
        for(int i = 0; i < d; i++) {
            if(mask & (1 << i)) {
                to_solve += p[i];
                score += c[i] + p[i] * 100 * (i + 1);
            } else {
                inc.push_back(i);
            }
        }
        while(score < g and inc.size()) {
            int solved = 0;
            while(score < g and solved < p[inc.back()] - 1) {
                to_solve++;
                score += 100 * (inc.back() + 1);
                solved++;
            }
            inc.pop_back();
        }
        if(score >= g) {
            ans = min(ans, to_solve);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-

def solve():
    import sys

    N, K = list(map(int, sys.stdin.readline().split()))
    As = [-1] + list(map(int, sys.stdin.readline().split()))

    now = 1
    dic = {1:0}
    turns = [1]
    for i in range(1, N+1):
        nx = As[now]
        turns.append(nx)

        if not nx in dic:
            dic[nx] = i
            now = nx

            if i == K:
                print(now)
                return

            continue
        else:
            # サイクルが存在している
            cycle_num = i - dic[nx]  # 再度同じところに戻ってくるのにかかるテレポーテーションの回数
            k = (K-i)%cycle_num
            cycle_turns = turns[dic[nx]:i]
            print(cycle_turns[k])
            return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 31384
#include<iostream>
#include <algorithm>
using namespace std;
int N_MAX=20;
int main()
{
  int n,i,res=0;
  int v[N_MAX],c[N_MAX];
  cin >> n;
  for(i=0;i<n;i++)
    cin >> v[i];
  for(i=0;i<n;i++)
    cin >> c[i];
  for(i=0;i<n;i++)
    res+=max(v[i]-c[i],0);
  cout << res << endl;
  return 0;
}

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

//わからん

using namespace std;

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	a %= b;
	c %= b;
	for (int i = 1; i <= b; i++) {
		if ((a*i) % b == c) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<numeric>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}




int main(void) {
	int n;
	cin >> n;
	vector<int>h(n);
	LL sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		sum += h[i];
	}
	for (int i = 0; i < n - 1; i++) {
		sum -= min(h[i], h[i + 1]);
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(c,i) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main()
{
	bool first=true;
	for(int a,b;cin>>a>>b,a|b;){
		cout<<(first?"":"\n");
		first=false;
		
		ostringstream oss;
		repi(i,a,b+1)
			if(i%400==0 || i%4==0 && i%100)
				oss<<i<<endl;
		if(oss.str().size())
			cout<<oss.str();
		else
			cout<<"NA"<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
n,a=map(int,input().split())
x=list(map(int,input().split()))
for i in range(n):
    x[i]-=a
# dp[i][j] = i番目までで(j-2500)を何個作れるか
dp=[[0]*5001 for i in range(n)]
dp[0][x[0]+2500]=1
for i in range(1,n):
    dp[i][x[i]+2500]=1
    for j in range(5000):
        for k in range(2):
            if 0<=j-k*x[i]<=5000:
                dp[i][j]+=dp[i-1][j-k*x[i]]
print(dp[n-1][2500])


Measured memory_bytes: 5588
/*
    Stay motivated and keep working hard
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9+7;
int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll h, w;
    cin >> h >> w;
    char a[h+1][w+1];
    for(ll i=1;i<=h;i++){
        string s;
        cin >> s;
        for(ll j=0;j<w;j++){
            a[i][j+1] = s[j];
        }
    }
    ll dp[h+1][w+1];
    memset(dp, 0, sizeof(dp));
    for(ll i=1;i<=h;i++){
        for(ll j=1;j<=w;j++){
            if(i == 1 && j == 1){
                dp[i][j] = 1;
            }
            if(a[i][j] == a[i-1][j] && a[i][j] == '.'){
                dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
            }
            if(a[i][j] == a[i][j-1] && a[i][j] == '.'){
                dp[i][j] = (dp[i][j] + dp[i][j-1]) % mod;
            }
        }
    }
    cout << dp[h][w] << "\n";


    return 0;
}

Measured memory_bytes: 12484
import fractions
n=int(input())
a=[int(i) for i in input().split()]
g=1
dx=fractions.gcd
for i in a:
  g*=i//dx(g,i)
suml=0
mod=10**9+7
for i in a:
  suml+=g*pow(i,mod-2,mod)
  suml%=mod
print(suml)


Measured memory_bytes: 6072
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
    int n;
    string ans="Three";
    cin>>n;
    REP(i,n){
      string s;
      cin>>s;
      if(s=="Y")ans="Four";
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = []
    a = {i: k for i, k in enumerate(a, start=1)}
    a = sorted(a.items(), key=lambda a: a[1])
    for i in a:
        ans.append(i[0])

    print(*ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 24160
import math

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())

#3辺の長さ
a = math.sqrt(((x1-x2)**2)+((y1-y2)**2))
b = math.sqrt(((x3-x2)**2)+((y3-y2)**2))
c = math.sqrt(((x1-x3)**2)+((y1-y3)**2))
s = (a+b+c)/2

r = math.sqrt(s*(s-a)*(s-b)*(s-c))/s #ヘロンの公式
xa, ya = x1+(x2-x1)*c/(b+c), y1+(y2-y1)*c/(b+c) #二等分線とaの交点
xb, yb = x2+(x3-x2)*a/(a+c), y2+(y3-y2)*a/(a+c)

if (xa-x3) != 0 and (xb-x1) != 0:
    a1, b1 = (ya-y3)/(xa-x3), -((ya-y3)/(xa-x3))*x3+y3 #二等分線の方程式
    a2, b2 = (yb-y1)/(xb-x1), -((yb-y1)/(xb-x1))*x1+y1
    cx = (b2-b1)/(a1-a2)
    cy = a1 * cx + b1

if xa-x3 == 0:
    cx = x3
    a2, b2 = (yb-y1)/(xb-x1), -((yb-y1)/(xb-x1))*x1+y1
    cy = a2 * cx + b2

if xb-x1 == 0:
    cx = x1
    a1, b1 = (ya-y3)/(xa-x3), -((ya-y3)/(xa-x3))*x3+y3
    cy = a1 * cx + b1

print(cx, cy, r)


Measured memory_bytes: 5692
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var n = o.a();
  var a = o.l();
  a.sort((a,b)=>a-b);
  var ans = [-a[0]];
  for(var i = 1; i < n-1; i++){
    ans[0] += Math.abs(a[i]);
  }
  ans[0] += a[n-1];
  var s = a[0];
  for(var l = 1; l < n-1; l++){
    if(a[l] < 0)continue;
    ans.push(s+" "+a[l]);
    s -= a[l];
  }
  ans.push(a[n-1]+" "+s);
  s = a[n-1]-s;
  for(var l = 1; ans.length !== n; l++){
    var x = ans.length;
    ans.push(s+" "+a[l]);
    s -= a[l];
  }
  return ans.join("\n")
}

Measured memory_bytes: 65664
using System;
      class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            //int a = int.Parse(vals[0]);
            //string s = vals[1];

            if (a >= 3200)
            {
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("red");
            }
        }
    }

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int n,x;
  while(cin >> n >> x,n){
    int ans = 0;
    FOR(i,1,n+1)FOR(j,i+1,n+1)FOR(k,j+1,n+1)if(i+j+k==x)++ans;
    cout << ans << endl;
  }
}





Measured memory_bytes: 3080
s = int(input())

def f(n):
    if n % 2:
        return 3 * n + 1
    return n // 2

S = {s}
for i in range(10 ** 6):
    s = f(s)
    if s in S:
        print(i + 2)
        break
    else:
        S.add(s)



Measured memory_bytes: 2940
import qualified Data.Vector         as V
import qualified Data.Vector.Mutable as VM
import Control.Applicative
import Control.Monad
import Data.IORef
import Text.Printf

type Process = (String, Int)

roundRobin :: Int -> [Process] -> IO ()
roundRobin q xs = do
  queue <- V.thaw $ V.fromList (xs ++ [("dummy", 0)])
  loop 0 queue 0 n
  where
    n = length xs
    
    loop :: Int -> VM.IOVector (String, Int) -> Int -> Int -> IO ()
    loop t vec front rear = do
      when (front /= rear) $ do
        (name, time) <- VM.read vec front
        let front' = if front == n then 0 else front + 1
        if time <= q
          then do
          printf "%s %d\n" name (t + time)
          loop (t + time) vec front' rear
          else do
          VM.write vec rear (name, time - q)
          let rear' = if rear == n then 0 else rear + 1
          loop (t + q) vec front' rear'

main :: IO ()
main = do
  [n, q] <- map read . words <$> getLine
  xs <- map (toTuple . words) <$> replicateM n getLine
  roundRobin q xs
    where toTuple [n, t]  = (n, read t)



Measured memory_bytes: 38356
#include<iostream>
#include<bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

int main(){
  long long int x;
  cin>>x;
  long long int now=100;
  long int yr=0;
  while(now<x)
  {
    yr++;
    now+=now/100;
  }
  cout<<yr<<endl;
  return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int nodeNum(string &s)
{
    if (s == "")
    {
        return -1;
    }

    int cur = 1;
    assert(s[0] == ('('));
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == '(')
            cur++;
        if (s[i] == ')')
            cur--;
        if (cur == 0 && isdigit(s[i]))
        {
            string ret = "";
            while (isdigit(s[i]))
            {
                ret += s[i];
                i++;
            }
            return stoi(ret);
        }
    }
    return -1;
}

string right(string &s)
{
    string ret = "";
    int cur = -1;
    rep(i, 1, s.size())
    {
        if (s[s.size() - 1 - i] == '(')
            cur++;
        if (s[s.size() - 1 - i] == ')')
            cur--;

        if (cur == 0)
            break;
        ret = s[s.size() - 1 - i] + ret;
    }
    return ret;
}
string left(string &s)
{
    string ret = "";
    int cur = 1;
    rep(i, 1, s.size())
    {
        if (s[i] == '(')
            cur++;
        if (s[i] == ')')
            cur--;

        if (cur == 0)
            break;
        ret += s[i];
    }
    return ret;
}

string calc(string a, string b)
{
    int x = nodeNum(a);
    int y = nodeNum(b);
    if (x == -1 || y == -1)
    {
        return "";
    }
    return "(" + calc(left(a), left(b)) + ")[" + to_string(x + y) + "](" + calc(right(a), right(b)) + ")";
}

int main()
{

    string a, b;
    cin >> a >> b;
    cout << calc(a, b) << endl;
    return 0;
}


Measured memory_bytes: 3428
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


n = onem()

if n % 2 == 1:
    print(0)
    exit()
else:
    kkk = n // 10
    po = 10
    while True:
        po *= 5
        if po > n:
            break
        kkk += n//po

print(kkk)




Measured memory_bytes: 66028
package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var D, G int
	fmt.Scan(&D, &G)
	p := make([]int, D)
	c := make([]int, D)
	for i := 0; i < D; i++ {
		fmt.Scan(&p[i], &c[i])
	}

	ans := 10000000
	for bit := uint(0); bit < (1 << uint(D)); bit++ {
		sum := 0
		cnt := 0
		for i := 0; i < D; i++ {
			if bit&(1<<uint(i)) > 0 {
				sum += p[i]*(100*(i+1)) + c[i]
				cnt += p[i]
			}
		}

		// コンプだけで超えた場合
		if sum >= G {
			ans = min(ans, cnt)
			continue
		}

		// 足りない分をコンプしていない大きい問題から回答
		for i := D - 1; i >= 0; i-- {
			if bit&(1<<uint(i)) > 0 {
				continue
			}
			for j := 0; j < p[i]; j++ {
				sum += 100 * (i + 1)
				cnt++
				if sum >= G {
					ans = min(ans, cnt)
					break
				}
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define forn(i,n)for(ll i=0;i<(n);i++)
#define forn_rev(i,n)for(ll i=(n)-1;i>=0;i--)
#define for1n(i,n) for(ll i=1;i<=(n);i++)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(*a)
#define MOD 1000000007
#define MAXN 100000

using namespace std;


ll power(ll x, ll y){
    int res = 1;
    x %= MOD;
    while(y){
        if(y&1) res = (res * x) % MOD;
        x *= x; x %= MOD;
        y >>= 1;
    }
    return res;
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    ll T=1;
    //cin>>T;
    while(T--)
    {
        ll N,K;
        cin>>N>>K;

        ll ans=0;
        vector<ll> a(K+1,0);
        for(ll i=K;i>=1;i--){
            ll temp=power(K/i,N);
            temp%=MOD;
            ll val=0;
            for(ll j=2*i;j<=K;j+=i){
                val=(val+a[j])%MOD;
            }
            a[i]=(temp-val)%MOD;
        }

        for1n(i,K){
            ans=(ans+i%MOD*a[i]%MOD)%MOD;
        }
        cout<<ans;






    }





    return 0;
}

Measured memory_bytes: 3928
S = input()
n = len(S)
A = [0] * n
p = -1
for i in range(n-1):
    if S[i] == 'R' and S[i+1] == 'L':
        for j in range(p+1, i+1):
            if S[j] == 'R':
                if (i+1-j)%2==0:
                    A[i+1]+=1
                else:
                    A[i]+=1
        p = i
p = n
for i in range(n-1, 0, -1):
    if S[i-1] == 'R' and S[i] == 'L':
        for j in range(p-1, i-1, -1):
            if S[j] == 'L':
                if (i-1-j)%2==0:
                    A[i-1]+=1
                else:
                    A[i]+=1
        p = i
print(' '.join(str(a) for a in A))


Measured memory_bytes: 84300
#include <bits/stdc++.h>
#define N 101010

using namespace std;

int n, h[N], d[N];

int main(){

	cin >> n;

	for(int i=0; i<n; i++) cin >> h[i];

	for(int i=1; i<n; i++){
		d[i] = d[i-1]+abs(h[i]-h[i-1]);
		if(i>1) d[i] = min(d[i], d[i-2]+abs(h[i]-h[i-2]));
	}

	cout << d[n-1] << endl;

	return 0;

}


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

using i64 = int64_t;

int main(){
    string s;
    cin >> s;
    i64 ans = 0, cnt = 0;
    reverse(s.begin(), s.end());
    int n = s.size();
    for(int i=0;i<n;++i){
        if(i<n-1 && s[i] == 'C' && s[i+1] == 'B'){
            cnt++;
            i++;
        }else if(s[i] == 'A'){
            ans += cnt;
        }else{
            cnt = 0;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

const int INF = 1001001001;

using P = pair<int, int>;
struct Edge {
    Edge(int _to, int _cost): to(_to), cost(_cost) {}
    int to;
    int cost;
};

void dijkstra(int s, vector<vector<Edge>> &g, vector<int> &cost) {
    priority_queue<P> q;
    cost[s] = 0;
    q.emplace(0, s);

    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        int v = p.second;
        if (cost[v] < p.first) continue;
        for (auto e: g[v]) {
            if (cost[e.to] > cost[v] + e.cost) {
                cost[e.to] = cost[v] + e.cost;
                q.emplace(cost[e.to], e.to);
            }
        }
    }
};


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

    vector<vector<Edge>> G(n, vector<Edge>());
    vector<int> d(n, INF);

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].emplace_back(b, 1);
    }
    dijkstra(0, G, d);

    cout << ((d[n - 1] == 2) ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}

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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
	int N;  cin >> N;
	vector<vector<int>> G(N);
	vector<pair<int,int>> vp;
	for(int i = 1 ; i < N ; i++){
	 	int a, b;
		cin >> a >> b;
		a -= 1, b -= 1;
		G[a].emplace_back(b);
		G[b].emplace_back(a);
		vp.emplace_back(a, b);
	}

	int K = 0;
	map<pair<int,int>, int> I;  //pair間の辺の色
	vector<int> cs(N, 0);  //親の頂点との間の辺の色

	vector<int> used(N, 0);
	queue<int> que;
	used[0] = 1;
	que.emplace(0);
	while(!que.empty()){
	 int v = que.front();  que.pop();
	 if(K < (int)G[v].size()) K = G[v].size();
	 int cur = 1;
	 for(int u: G[v]){
	  if(used[u])  continue;
	  //uの親vとその親への辺と同じ色はvからは伸ばせない
	  if(cur == cs[v]) cur++;
	  cs[u] = I[make_pair(u, v)] = I[make_pair(v, u)] = cur++;
	  used[u] = 1;
	  que.emplace(u);
	 }
	}

	cout << K << endl;
	for(auto p: vp) cout << I[p] << endl;

	return 0;
}

Measured memory_bytes: 20088
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a=new long[n];
		long[] b=new long[n];
		long ans=0;
		for(int i=0; i<n; i++){
			a[i] = Long.parseLong(sc.next());
			b[i] = Long.parseLong(sc.next());
		}
 
		for(int i=n-1;i>=0;i--){
			a[i] += ans;
		        ans += (a[i]+b[i]-1)/b[i]*b[i]-a[i];
		}
 
		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 48684
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;

//ノルム
double norm(double x, double y){
    return x*x + y*y;
}
//内積
double dot(double x1, double y1, double x2, double y2){
    return x1*x2 + y1*y2;
}

int main(){
    double xp1,yp1,xp2,yp2;
    int q;

    //標準入力
    cin >> xp1;
    cin >> yp1;
    cin >> xp2;
    cin >> yp2;
    cin >> q;

    double xv = xp2 - xp1;
    double yv = yp2 - yp1;
    double vnorm = norm(xv, yv);

    for(int i=0; i<q; i++){
        double xp,yp;
        cin >> xp;
        cin >> yp;

        double xu = xp - xp1;
        double yu = yp - yp1;

        double uvdot = dot(xv,yv,xu,yu);
        double x = double(xp1) + uvdot/vnorm*double(xv);
        double y = double(yp1) + uvdot/vnorm*double(yv);

        std::cout << setprecision(14) << x << " " << y << "\n";
    }

    return 0;
}



Measured memory_bytes: 3288
#include <iostream>

#include <algorithm>
using namespace std;
int a[100001];
int b[100001];
int judge(int x,int y,int z,int xx,int yy)
{
    if(z==1)
    {
        if(x<y)
            return 1;
        else if(x==y&&xx<yy)
        {
                return 1;
        }
    }else
    {
        if(x>y)
            return 1;
        else if(x==y&&xx>yy)
        {
                return 1;
        }
    }
    return 0;
}
void sorts(int l,int r)
{
    int hold,mid=a[(l+r)/2],bmid=b[(r+l)/2];
    int i=l,j=r;
    while(i<=j)
    {
        while(judge(a[i],mid,1,b[i],bmid)) i++;
        while(judge(a[j],mid,0,b[j],bmid)) j--;
        if(i<=j)
        {
            hold=a[i];
            a[i]=a[j];
            a[j]=hold;
            hold=b[i];
            b[i]=b[j];
            b[j]=hold;
            i++;
            j--;
        }
    }
    if(i<r) sorts(i,r);
    if(j>l) sorts(l,j);

}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];cin>>b[i];
    }
    sorts(0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" "<<b[i]<<endl;
    }
    return 0;
}



Measured memory_bytes: 3880
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
#define INF 1e15
#define MOD 1000000007
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
typedef long long ll;
#define END system("PAUSE");return 0
int n, m;
int cnt[33];
signed main() {
	cin >> n >> m;
	rep(i, n) {
		int k;
		cin >> k;
		rep(j, k) {
			int x;
			cin >> x;
			cnt[x]++;
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++)if (cnt[i] == n)ans++;
	cout << ans << endl;
	END;
}


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

string S,T;
vector<char> KS(26),KT(26);
int count_s=0,count_t=0,s,t;
int ks[26],kt[26];

bool explore_s(int x){
    for(int i=0;i<count_s;i++){
        if(S.at(x-1)==KS.at(i)){
            ks[i]++;
            s=i;
            return false;
        }
    }
    return true;
}

bool explore_t(int x){
    for(int i=0;i<count_t;i++){
        if(T.at(x-1)==KT.at(i)){
            kt[i]++;
            t=i;
            return false;
        }
    }
    return true;
}

bool dfs(int x){
    if(x==0) return true;
    if(dfs(x-1)){
        if(explore_s(x)) {
            count_s++;
            KS.at(count_s-1)=S.at(x-1);
            ks[count_s-1]=1;
        }
        if(explore_t(x)){
            count_t++;
            KT.at(count_t-1)=T.at(x-1);
            kt[count_t-1]=1;
        }
        if(count_s==count_t && ks[s]==kt[t]) return true;
    }
    return false;
}

int main(){
    cin>>S>>T;
    if(dfs(S.size())) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 10120
#include<iostream>
using namespace std;
long long gcd(long a, long b){
  if(a%b==0) return b;
  else return gcd(b,a%b);
}
long long lcm(long a,long b){
  return (a*b)/gcd(a,b);
}
  
int main(){
  long long A,B,C,D;
  cin>>A>>B>>C>>D;
  long long H=A-1;
  long long E=lcm(C,D);
  long long F=B-(B/C+B/D-B/E);
  long long G=H-(H/C+H/D-H/E);
  cout<<F-G<<endl;
}
 

  
  

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
// 標準入力からデータを読み込む準備
        int i,j;
        Scanner sc = new Scanner(System.in);
// 最初の文字の固まりを整数値と想定して読み込む
        while (true) {
            int H = sc.nextInt();
            int W= sc.nextInt();
            if (H == 0 && W == 0) {
                break;
            }
// 二重ループ(forの中にfor)を書いて、H x W個の # を表示しよう！

            for(i=0;i<H;i++){
                for(j=0;j<W;j++) System.out.printf("#");
                System.out.printf("\n");
            }
            System.out.printf("\n");
        }
    }
}


Measured memory_bytes: 60468
using System;
using System.Collections.Generic;
using System.Text;

namespace Kyoupro
{
    class Plactice
    {
        static void Main()
        {
            string S = Console.ReadLine();
            if(S == "SUN")
            {
                Console.WriteLine("7");
            }else if (S == "MON")
            {
                Console.WriteLine("6");
            }
            else if (S == "TUE")
            {
                Console.WriteLine("5");
            }
            else if (S == "WED")
            {
                Console.WriteLine("4");
            }
            else if (S == "THU")
            {
                Console.WriteLine("3");
            }
            else if (S == "FRI")
            {
                Console.WriteLine("2");
            }
            else if (S == "SAT")
            {
                Console.WriteLine("1");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> g[100005];
vector<int> vis[100005], cur[100005];
int dp[100005];
bool check[100005];
int main(){
    int n, m, u, v, c;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &u, &v, &c);
        g[u].push_back(pii(v, c));
        g[v].push_back(pii(u, c));
        vis[u].push_back(c);
        vis[v].push_back(c);
    }
    for(int i=1;i<=n;i++){
        sort(vis[i].begin(), vis[i].end());
        vis[i].erase(unique(vis[i].begin(), vis[i].end()), vis[i].end());
    }
    for(int i=1;i<=1000000;i++) cur[1].push_back(i);
    priority_queue<pii> q;
    memset(dp, -1, sizeof(dp));
    q.push(pii(-1, 1));
    dp[1] = 1;
    while(!q.empty()){
        int u = q.top().second;
        int val = -q.top().first;
        q.pop();

        if(val != dp[u]) continue;

        sort(cur[u].begin(), cur[u].end());
        cur[u].erase(unique(cur[u].begin(), cur[u].end()), cur[u].end());
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i].first, c = g[u][i].second;
            if(binary_search(cur[u].begin(), cur[u].end(), c)){

                if(dp[v] == -1 || dp[v] > dp[u]){
                    cur[v].clear();
                    cur[v].push_back(c);
                    dp[v] = dp[u];
                    q.push(pii(-dp[v], v));
                }
                else if(dp[v] == dp[u]){
                    cur[v].push_back(c);
                }
            }
            else{
                if(dp[v] == -1 || dp[v] > dp[u] + 1){
                    cur[v].clear();
                    cur[v].push_back(c);
                    dp[v] = dp[u] + 1;
                    q.push(pii(-dp[v], v));
                }
                else if(dp[v] == dp[u] + 1){
                    cur[v].push_back(c);
                }
            }
        }
    }
    printf("%d\n", dp[n]);
}

Measured memory_bytes: 28460
#include <bits/stdc++.h>
#define int long long

#define mp make_pair
#define pb push_back
#define mod (int)1e9+7
using namespace std;

signed main(){
    int n;
    cin >> n;
    int x,y;
    cin >> x >> y;
    int cnt[n+1];
    memset(cnt,0,sizeof cnt);
    x--;
    y--;
    for(int i = 0;i<n;i++){
        for(int z = i+1;z<n;z++){
            int res = z-i;
            res = min(res,abs(i-x)+1+abs(z-y));
            res = min(res,abs(i-y)+1+abs(z-x));
            cnt[res]++;
        }
    }
    for(int i = 1;i<n;i++){
        cout << cnt[i] << endl;
    }
}


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

int main()
{	
	int n;

	cin >> n;

	while (n > 0) {
		vector<int> t(n), h;

		for (int i = 0; i < n; i++)
			cin >> t[i];

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

		int i = 0, j = 1;
		while (i < n) {
			while (t[i] > j) {
				h.push_back(j);
				j++;
			}
			j++;
			i++;
		}

		while (j <= n * 2) {
			h.push_back(j);
			j++;
		}

		int tp = 0, hp = 0;
		bool f = 1;

		while (!t.empty() && !h.empty()) {
			if (f) {
				int s = 0;

				while (s < t.size() && t[s] < hp)
					s++;

				if (s < t.size()) {
					tp = t[s];
					t.erase(t.begin() + s);

					if (t.empty())
						break;
				}
				else {
					tp = 0;
					hp = 0;
				}
				f = 0;
			}

			if (!f) {
				int u = 0;

				while (u < h.size() && h[u] < tp)
					u++;

				if (u < h.size()) {
					hp = h[u];
					h.erase(h.begin() + u);
				}
				else {
					tp = 0;
					hp = 0;
				}
				f = 1;
			}
		}

		cout << h.size() << endl << t.size() << endl;

		cin >> n;
	}

	return 0;
}


Measured memory_bytes: 3048
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		while (true) {
			int N = sc.nextInt();
			if (N == 0) break;
			int K = sc.nextInt();
			int lo = 0;
			int hi = N;
			while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				long c = count(mid);
				if (c < N) {
					lo = mid;
				} else {
					hi = mid;
				}
			}
			String ret = "";
			int start = (int) (N - count(lo) - 1);
			for (int i = 0; i < K + start; ++i) {
				ret += lo + 1 + i;
			}
			System.out.println(ret.substring(start, start + K));
		}
	}

	static long count(int n) {
		long base = 10;
		long ret = 0;
		int d = 1;
		for (; base <= n; ++d, base *= 10) {
			ret += d * (base - base / 10);
		}
		ret += d * (n - base / 10 + 1);
		return ret;
	}

}

Measured memory_bytes: 25416
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
ans =""

for i in range(1, len(s)+1):
    for j in range(1, len(t)+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = max(dp[i-1][j-1]+1, dp[i][j])
        else:
            dp[i][j]= max(dp[i-1][j], dp[i][j-1])

i, j = len(s), len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i][j-1]:
        j-=1
        continue
    elif dp[i][j]==dp[i-1][j]:
        i-=1
        continue
    #elif dp[i][j]==dp[i-1][j-1]:
    else:
        ans = s[i-1] + ans
        i-=1
        j-=1
        continue
print(ans)
        


Measured memory_bytes: 112348
# 2020/02/29
# Tenka1 Programmer Beginner Contest - B

from operator import itemgetter

# Input
n = int(input())
l = list()

for i in range(n):
    ab = list(map(int,input().split()))
    l.append(ab)

l.sort(key=itemgetter(1))

# Calc
ans = l[0][0] + l[0][1]

# Output
print(ans)


Measured memory_bytes: 29096
#include"bits/stdc++.h"
using namespace std;

long int n;

void Main() {
  cin >> n;
  vector<long int> fct;

  for (long int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      fct.push_back(i);
    }
  }

  long int min = n - 1;
  for (long int i = 0; i < fct.size(); i++) {
    long int t = (fct[i] - 1) + (n / fct[i] - 1);
    if (t < min) {
      min = t;
    }
  }

  cout << min << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

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

int main() {
	string s;
	cin >> s;
	int n = s.size();
	char c = '0';
	int count = 0;
	for (auto &x : s) {
		if (x == c) count++;
		if (c == '0') c = '1';
		else c = '0';
	}
	cout << min(count, n - count) << endl;
	return 0;
}

Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
flag = False
i = 0
while True:
    for b in a:
        if b % 2 == 1:
            flag = True
            break
    if flag:
        break
    a = [int(x/2) for x in a]
    i += 1
print(i)


Measured memory_bytes: 3060
#include <stdio.h>
int n,A[20],M[200];
 
int res(int i,int m)
{
  if(A[i]==m) return 1;
  if(i==n) return 0;
  else
    {
      if(res(i+1,m)||res(i+1,m-A[i]))
    return 1;
    }
  return 0;
}
 
int main(){
  int i,k;
   
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
    }
  scanf("%d",&k);
  for(i=0;i<k;i++)
    {
      scanf("%d",&M[i]);
    }
 
  for(i=0;i<k;i++)
    {
      if(res(0,M[i]))
    printf("yes\n");
       
      else
    printf("no\n");
    }
return 0;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#ifdef LOCAL
#include<debug.h>
#else
#define db(...) 21
#endif
#define sz(a) (int)a.size()
#define found(m,x) ((m).find(x)!=(m).end())
#define uset unordered_set
#define umap unordered_map
#define a(x) x.begin(),x.end()
#define fo(i,n) for(int i=0;i<(int)n;i++)
#define Fo(i,k,n) for(int i=k;k<n?i<=(int)n:i>=(int)n;k<n?i++:i--)
#define input(v,n) fo(i,n)cin>>v[i]
using vi = vector<int>;
using vpi = vector<pair<int,int>>;
using pi = pair<int,int>;

const int nax = 1e5+7;
const int mod = 1e9+7; //1e9+2667 :: 0xcf : inf, 0xc0 -inf
const int inf = numeric_limits<int> :: max() - (int)9e6;
// ===================== MANASH =================== //

bool pali(string s) {
    int n = sz(s);
    for( int i = n/2-1; i>= 0; i--) {
        if(s[i] != s[n-i-1]) return false;
    }
    return true;
}
// n == 5
// n/2 -1 = 1 
// n/2 = 2
// n/2 + 1 = 3
// n == 7
// n/2 - 1 = 2
// n/2 = 3
// n/2 + 1 = 4
// aaabaaa

// aabaa


void test() {

    string s = "";
    cin >> s;
    int n = sz(s);
    bool d1 = pali(s);
    bool d2 = pali(s.substr(0,n/2));
    bool d3 = pali(s.substr(n/2+1));
    if ( d1 and d2 and d3 ) cout << "Yes";
    else cout << "No";
}

signed main() {

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif

    int T = 1;
    //cin >> T;
    while(T--) {
        test();
        cout << "\n";
    }
    return 0;

}

Measured memory_bytes: 3536
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int p = scan.nextInt();
		int ans=0;
		int mem=0;
		for(int i=0;i<p;i++){
			int q = scan.nextInt();
			if(mem<=q){
				ans++;
				mem=q;
			}
		}
		System.out.println(ans);
	}
}

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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define ALLTRUE(xs) all_of(ALL(xs),[](bool x){return x;})
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define ANYTRUE(xs) any_of(ALL(xs),[](bool x){return x;})
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define DUMPP(xs) for (auto x:xs) cout<<'('<<x.first<<','<<x.second<<')';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

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

struct edge { int to,cost; };

int main() {
  string s;cin>>s;
  string res = "";
  REP(i,s.size()) {
    if (s[i]=='0') {
      res.push_back('0');
    } else if (s[i]=='1') {
      res.push_back('1');
    } else {
      if (res.size()==0) continue;
      res.pop_back();
    }
  }
  OUT(res);

  return 0;
}

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


int main(){
  pair<int, int>x[100000], p[100000];
  map<pair<int, int>, pair<int, int>> ans;
  int n, m;

  cin >> n >> m;
  
  for(int i=0; i<m; ++i){
    cin >> x[i].first >> x[i].second;
    ans[x[i]] = pair<int, int>();
    p[i].first = x[i].first;
    p[i].second = x[i].second;
  }

  sort(x, x + m);

  int ci = x[0].first;
  for(int i=0, cnt = 1; i<m; ++i, ++cnt){
    if(ci != x[i].first){
      ci = x[i].first;
      cnt = 1;
    }
    pair<int, int> a;
    a.first = x[i].first; a.second = cnt;
    ans[x[i]] = a;
    
  }

  for(int i=0; i<m; ++i){
    printf("%06d%06d\n", ans[p[i]].first, ans[p[i]].second);
  }
}


Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> a;
    rep(i, n){ int tmp; cin >> tmp; a.push_back(tmp);}

    sort(a.begin(), a.end(), greater<int>());

    int sum = 0;
    rep(i, k){
        sum += a[i];
    }
    cout << sum << endl;
}



Measured memory_bytes: 256
N,K = map(int, input().split())
A = []
for i in range(K) :
    d = int(input())
    A.append(input().split(" "))
    
snukeList = []
for i in range(len(A)) :
    for j in range(len(A[i])) :
        snukeList.append(int(A[i][j]))
count = 0
for i in range(1, N+1) :
    if i in snukeList :
        continue
    count += 1
print(count)


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

typedef long long ll;
using namespace std;

int main(void) {
  int n, m; 
  cin >> n >> m;
  int maxL, minR;
  int lt, rt; cin >> lt >> rt;
  maxL = lt; minR = rt;
  for (int i = 1; i < m; i++) {
    cin >> lt >> rt;
    maxL = max(lt ,maxL); minR = min(minR, rt);
  }

  //cout << maxL; cout << minR;

  minR = min(n, minR);
  int res = minR - maxL + 1;
  res = res <= 0 ? 0 : res;

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 256