akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

struct RSQ {
	using type = int;
	static const type id() { return 0; }
	static type op(const type& l, const type & r) { return l + r; }
};

const int PMAX = 3000000;

template <typename M>
class PersistentSegmentTree {
	using T = typename M::type;
	struct node {
		T val;
		node *l, *r;
		node() {}
		node(T val) : val(val), l(nullptr), r(nullptr) {}
		void init(T v, node *left, node *right) {
			val = v;
			l = left;
			r = right;
		}
	};
	const int n;
	vector<node> pool;
	int it;
	vector<node*> root;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	node *new_node(int val = 0, node *l = nullptr, node *r = nullptr) {
		pool[it].init(val, l, r);
		return &pool[it++];
	}
	node *fix(node *x, int p, T val, int lb, int ub) {
		if (p < lb || ub <= p) return x;
		if (lb + 1 == ub) return new_node(M::op(x == nullptr ? M::id() : x->val, val));
		if (x == nullptr) x = new_node(M::id());
		else x = new_node(x->val, x->l, x->r);
		int c = (lb + ub) / 2;
		x->l = fix(x->l, p, val, lb, c);
		x->r = fix(x->r, p, val, c, ub);
		x->val = M::op(x->l == nullptr ? M::id() : x->l->val, x->r == nullptr ? M::id() : x->r->val);
		return x;
	}
	T sub(node *x, int l, int r, int lb, int ub) {
		if (x == nullptr || ub <= l || r <= lb) return M::id();
		if (l <= lb && ub <= r) return x->val;
		int c = (lb + ub) / 2;
		return M::op(sub(x->l, l, r, lb, c), sub(x->r, l, r, c, ub));
	}
public:
	PersistentSegmentTree(int n_) : n(size(n_)), pool(PMAX), it(0) {
		root.push_back(nullptr);
	}
	void add(int p, T val, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		root.push_back(fix(root[rt], p, val, 0, n));
	}
	T find(int l, int r, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		return sub(root[rt], l, r + 1, 0, n);
	}
	int getversion() {
		return root.size() - 1;
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q, com, x, y;
	cin >> n >> q;
	PersistentSegmentTree<RSQ> st(n);
	while (q--) {
		cin >> com >> x >> y;
		if (com) {
			printf("%d\n", st.find(x - 1, y - 1));
		}
		else {
			st.add(x - 1, y);
		}
	}
	return 0;
}

Measured memory_bytes: 33368
import std.stdio;
import std.conv;
import std.string;
import std.math;

int f(int x, int y) {
  return x - y + 1;
} 

void main() {
  int n = readln.strip.to!int;
  int h = readln.strip.to!int;
  int w = readln.strip.to!int;

  writeln(f(n, h) * f(n, w));

}


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

#define    ll    long long int

int isPalindrome(string s)
{
    string t = s;
    reverse(t.begin(), t.end());
    if (t == s) return 1;
    return 0;
}

int main( )
{
    string s;
    int i, j, k, l;
    cin >> s;
    l = (int) s.size();
    i = l / 2;
    string first = s.substr(0, i);
    string second = s.substr(i + 1, i);

    if (isPalindrome(first) && isPalindrome(second) && isPalindrome(s)) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 256
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def next_digit(i):
    if i == 0:
        return [0,1]
    elif i == 9:
        return [8,9]
    else:
        return [i-1,i,i+1]

K = I()

q = [1,2,3,4,5,6,7,8,9]
n = len(q)
num = 0
while q:
    q1 = []
    for v in q:
        num += 1
        if num == K:
            print(v)
            exit()
        for u in next_digit(int(str(v)[-1])):
            q1.append(10*v+u)
    q = q1

Measured memory_bytes: 48604
import java.util.Scanner;

public class Main {

	public Main() {
		// TODO 自動生成されたコンストラクター・スタブ
	}

	public static void main(String[] args){
			Scanner sc = new Scanner(System.in);
			// 整数の入力
			int a,b,p;
			int result;
			a = sc.nextInt();
			p = sc.nextInt();
			sc.close();
			result=(a*3+p)/2;
			

			// 出力

			System.out.println(result);
	}
}

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

using namespace std;

int H, W, C, ans, cnt;
const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};
bool used[8][8];
typedef pair<int,int> P;

bool inField(int y, int x){
  return 0 <= y && y < H && 0 <= x && x < W;
}

void color_count(vector<vector<int> > &vec, int y, int x){
  if(used[y][x]) return;
  used[y][x] = true;
  if(vec[y][x] == C){
    cnt++;
  }
  for(int i = 0 ; i < 4 ; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(!inField(ny, nx)) continue;
    if(vec[ny][nx] != C) continue;
    color_count(vec, ny, nx);
  }
}

vector<P> pos;
void color_change(int y, int x, int c1, int c2, 
                  bool flg, vector<vector<int> > &vec){
  if(used[y][x]) return;
  used[y][x] = true;
  pos.push_back(P(y,x));
  for(int i = 0 ; i < 4 ; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(!inField(ny, nx)) continue;
    if(vec[ny][nx] != c1 && vec[ny][nx] != c2) continue;
    if(vec[y][x] != vec[ny][nx] && !flg){
      flg = true;
      color_change(ny, nx, c1, c2, flg, vec);
    }else{
      if(flg){
        if(vec[y][x] != vec[ny][nx]) continue;
        color_change(ny, nx, c1, c2, flg, vec);
      }else{
        color_change(ny, nx, c1, c2, flg, vec);
      }
    }
  }
}

void solve(vector<vector<int> > &vec, int rem){
  if(rem == 0){
    memset(used, false, sizeof(used));
    cnt = 0;
    color_count(vec, 0, 0);
    ans = max(ans, cnt);
    return;
  }
  
  for(int i = 0 ; i < 6 ; i++){
    vector<vector<int> > next = vec;
    pos.clear();
    memset(used, false, sizeof(used));
    color_change(0, 0, i+1, vec[0][0], false, vec);
    for(int j = 0 ; j < pos.size() ; j++){
      P p = pos[j];
      next[p.first][p.second] = i+1;
    }
    solve(next, rem-1);
  }
}

int main(){
  while(cin >> H >> W >> C , (H | W | C)){
    vector<vector<int> > vec(H, vector<int>(W));
    for(int i = 0 ; i < H ; i++){
      for(int j = 0 ; j < W ; j++){
        cin >> vec[i][j];
      }
    }
    ans = 0;
    solve(vec, 5);   
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1232
import math
n, m = map(int, input().split())
if abs(n - m) == 0:
    print(2 * math.factorial(n) * math.factorial(m) % (10 ** 9 + 7))
elif abs(n - m) == 1:
    print(math.factorial(n) * math.factorial(m) % (10 ** 9 + 7))
else:
    print(0)

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

struct thread{
  int to;
  int val;
  string s;
};

void print(struct thread t[],int index,int n){
  for(int i=0;i<t[index].val;i++) cout<<".";
  cout<<t[index].s<<endl;
  for(int i=index+1;i<=n;i++){
    if(t[i].to==index) print(t,i,n);
  }
}

int main(){
  struct thread t[1001];
  t[0].val=-1;
  int n;

  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>t[i].to>>t[i].s;
    t[i].val=t[t[i].to].val+1;
  }
  print(t,1,n);
}


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

int main() {
  int A, B, count = 0;
  cin >> A >> B;
  for (int i = A; i <= B; i++) {
    if (i / 10000 == i % 10) {
      if ((i - i / 10000 * 10000) / 1000 == (i - i % 10) % 100 / 10)
        count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
import math
from functools import reduce
N = int(input())
 
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
 
sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)
 
print(sum_N)

Measured memory_bytes: 69632
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {//
        n:usize,a:usize,b:usize,

    }
    println!("{}", min(a * n, b));
}


Measured memory_bytes: 2160
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> a[100010];
pair<int, int> ans[100010];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int p, y;
    cin >> p >> y;
    a[p].push_back(make_pair(y, i));
  }
  for (int i = 1; i <= n; i++) {
    sort(a[i].begin(), a[i].end());
    for (int j = 0; j < a[i].size(); j++) {
      ans[a[i][j].second].first = i;
      ans[a[i][j].second].second = j + 1;
    }
  }
  for (int i = 0; i < m; i++) {
    cout << setw(6) << setfill('0') << ans[i].first;
    cout << setw(6) << setfill('0') << ans[i].second;
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,i,j,k,ans=0;
  cin>>n>>k;
  int a[26]={};
  string s;
  for(i=0;i<n;i++) cin>>s,a[s[0]-'A']++;
  priority_queue<int> q;
  for(i=0;i<26;i++) if(a[i]>0) q.push(a[i]);
  while(k<=q.size()){
    ans++;
    vector<int> v;
    for(i=0;i<k;i++){
      j=q.top();q.pop();
      v.push_back(j-1);
    }
    for(i=0;i<k;i++) if(v[i]>0) q.push(v[i]);
  }
  cout << ans << endl;
  return 0;
}


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

int main(int argc, char const *argv[])
{
	int a,b;
	cin>>a>>b;
	if (a%2==0||b%2==0)
	{
		cout<<"No\n";
	}
	else
	{
		cout<<"Yes\n";
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sstream>
#include <fstream>

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

using namespace std;

int main() {
  int N;
  cin >> N;
  vector< vector<int> > A(2, vector<int>(N));
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < N; ++j) {
      cin >> A[i][j];
      if (i == 0 && j != 0) {
	A[i][j] = A[i][j] + A[i][j - 1];
      }
    }
  }

  for (int i = N - 2; i >= 0; --i) {
    A[1][i] = A[1][i] + A[1][i + 1];
  }

  int ans = 0;
  for (int i = 0; i < N; ++i) {
    ans = max(A[0][i] + A[1][i], ans);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

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

	int x, i;
	int n;

	scanf("%d", &x);

	for(i=1; i<=x; i++) {
		if(i%3 == 0) printf(" %d", i);

		else{
			n = i;

		while(n % 10 != 3 && n) {
			n /= 10;
		}

		if(n){
			printf(" %d", i);
		}
		}
	}
	printf("\n");

	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	string s,t,t1;
	long long k;
	cin >> s;
	cin >> k;
	int l = s.length();
	t = s;
	t1 = s;
	long long ans1 = 0,ans2 = 0,ans3 = 0;
	for(int i = 1; i < l; i++){
		if(t[i] == t[i - 1]){
			ans1++;
			t[i] = '0';
		}
	}
	if(s[0] != s[l - 1])
		ans2 = ans1;
	else{
		if(s[0] == t[l - 1]){
			s[0] = '0';
			ans2++;
		}
		for(int i = 1; i < l; i++){
			if(s[i] == s[i - 1]){
				ans2++;
				s[i] = '0';
			}
		}
	}
	if(t1[0] == s[l - 1]){
		t1[0] = '0';
		ans3++;
	}
	for(int i = 1; i < l; i++){
		if(t1[i] == t1[i - 1]){
			ans3++;
			t1[i] = '0';
		}
	}
	long long sum = ans1 + (ans3 + ans2) * ((k - 1) / 2);
	if((k - 1) % 2 == 1)
		sum += ans2;
	cout << sum << endl;
	return 0;
}

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

using namespace std;

int even_string(string s, int l){
	for (int i = 0; i < l; i++){
		if (s[i] != s[i+l])
			return 0;
	}

	return 1;
}

int main(void){
	string s;

	cin >> s;

	int ok = 0;
	for (int i = s.size()/2 - 1; i >= 0; i--){
		if (even_string(s, i)){
			cout << 2*i << endl;
			break;			
		}
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 1005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;

set<int> st[maxn];

int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
    //cin >> T;
    T = 1;
    for (int cs = 1; cs <= T; cs++) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            int k;
            cin >> k;
            for (int j = 1; j <= k; j++) {
                int x;
                cin >> x;
                st[x].insert(i);
            }
        }
        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            // cerr <<st[i].size() << endl;
            if ((int)st[i].size() >= n) cnt++;
        }
        cout << cnt << endl;
    }

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

Measured memory_bytes: 384
#include <iostream>

int main(){
    int n;
    int a[210];

    std::cin >> n;
    for(int i=0; i < n; i++){
        std::cin >> a[i];
    }

    int counter =0;
    bool check = true;
    while(true){

    for(int i=0; i < n; i++){
        int tmp = a[i] % 2;
        if(tmp == 0){
            a[i] = a[i] / 2;
        }
        else{
            check = false;
            break;
        }
    }
    
    if(!check){
        break;
    }
    counter++;
    }

    std::cout << counter;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll MAX = 1e+18;

int main()
{
    ll X, Y;
    cin >> X >> Y;

    if (X % Y == 0) {
        cout << -1 << endl;
    } else {
        cout << X << endl;
    }

    return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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 ans;
ll N;

bool check(string s){
    VI n(10,0);
    REP(i,s.size()) n[s[i]-'0']++;
    return n[3] && n[5] && n[7];
}

void rec(string s){
    if(s.size() && N < (ll)toInt(s)) return;
    if(check(s)) ans++;
    rec(s+'3');
    rec(s+'5');
    rec(s+'7');
    return;
}

int main(void){
    cin >> N;
    rec("");
    cout << ans << endl;
    return 0;
}

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

S = []

for _ in range(N):
    s = int(input())
    S.append(s)

max = sum(S)

if max%10!=0:
    print(max)
else:
    min = float('inf')
    for i in range(N):
        if S[i]<min and S[i]%10!=0:
            min = S[i]
    if min==float('inf'):
        print(0)
    else:
        print(max-min)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ve vector
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

int main(){
    ll n,k;
    cin >> n >> k;
    ve<ll> c(n), p(n);
    rep(i,n){
        cin >> p[i];
        p[i]--;
    }
    rep(i,n) cin >> c[i];
    ve<bool> check(n,false);
    
    ll ans=-1e13;
    
    rep(i,n){
        if(check[i]) continue;
        ve<ll> c1;
        check[i] = true;
        c1.push_back(c[i]);
        ll x = i;
        while(!check[p[x]]){
            check[p[x]] = true;
            c1.push_back(c[p[x]]);
            x = p[x];
        }
        ll nc = c1.size();
        c1.insert(c1.end(), c1.begin(), c1.end());
        
        ve<ll> ruiseki(2*nc+1);
        ruiseki[0] = 0;
        rep(j,2*nc)ruiseki[j+1] = ruiseki[j] + c1[j];
        if(nc>k){
            rep(p,nc){
                rep(q,k){
                    chmax(ans,ruiseki[p+q+1]-ruiseki[p]);
                }
            }
        }else{
            if(ruiseki[nc]<=0){
                rep(p,nc){
                    rep(q,nc){
                        chmax(ans,ruiseki[p+q+1]-ruiseki[p]);
                    }
                }
            }else{
                ll memo = k/nc;
                memo *= ruiseki[nc];
                ll amari = k%nc;
                if (amari==0) {
                    amari = nc;
                    memo -= ruiseki[nc];
                }
                rep(p,nc){
                    rep(q,amari){
                        chmax(ans, ruiseki[p+q+1]-ruiseki[p]+memo);
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3784
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

int main() {
    long long n,h;
    cin >> n >> h;
    vector<long long> a(n), b(n);
    for (long long i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    long long am = *max_element(a.begin(), a.end());
    vector<long long> th;
    sort(b.begin(), b.end(), greater<long long>());
    for (long long j = 0; j < n; ++j) {
        if(b[j] > am) {
            th.push_back(b[j]);
        }
    }

    long long res = 0;
    while(h>0) {
        if(res < th.size()) {
            h-= th[res];
        }
        else {
            h-= am;
        }
        res++;
    }
    cout << res;


    return 0;
}


Measured memory_bytes: 2936
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

if __name__ == '__main__':
    n, q = map(int, input().split())
    ds = DisjointSet(n)    
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            ds.unite(x, y)
        else:
            if ds.same(x, y):
                print(1)
            else:
                print(0)



Measured memory_bytes: 6040
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld,ll> P;
ll xz[1005]={0},yz[1005]={0};
ll rz[1005]={0};
ld dist[1005][1005]={0};
ld get_dist(ll i,ll j){
  ll da=(xz[i]-xz[j])*(xz[i]-xz[j]);
  da+=(yz[i]-yz[j])*(yz[i]-yz[j]);
  ll db=(rz[i]+rz[j])*(rz[i]+rz[j]);
  if(da<=db) return 0;
  else return sqrt((ld)da)-(rz[i]+rz[j]);
}
int main(){
  ll xs,ys,xg,yg;
  cin>>xs>>ys>>xg>>yg;
  ll n;
  cin>>n;
  xz[0]=xs;
  yz[0]=ys;
  xz[n+1]=xg;
  yz[n+1]=yg;
  for(int i=1;i<=n;i++) cin>>xz[i]>>yz[i]>>rz[i];
  for(int i=0;i<=n+1;i++){
    for(int j=0;j<=n+1;j++){
      if(i!=j) dist[i][j]=get_dist(i,j);
    }
  }
  ld min_cost[1005]={0};
  bool used[1005]={false};
  used[0]=false;
  for(int i=1;i<=n+1;i++) {
    min_cost[i]=174417441744.00;
    used[i]=false;
  }
  priority_queue<P,vector<P>,greater<P>> pque;
  pque.push(P(0,0));
  while(!pque.empty()){
    P p=pque.top();
    pque.pop();
    ld cos=p.first;
    ll pos=p.second;
    if(used[pos]) continue;
    used[pos]=true;
    for(int i=0;i<=n+1;i++){
      if(i!=pos&&!used[i]){
        ld ncos=cos+dist[pos][i];
        if(ncos<min_cost[i]){
          min_cost[i]=ncos;
          pque.push(P(ncos,i));
        }
      }
    }
  }
  cout<<fixed;
  cout<<setprecision(15)<<min_cost[n+1]<<endl;
}


Measured memory_bytes: 25708
#include<stdio.h>
#include<math.h>
#include<stdlib.h>  
int main(void)
{
	int a=0,b=0,mod=0,print1=0,print2=0,i=0,gcd=0,lcm=0;
	while(scanf("%d %d",&a,&b)!=EOF){
	print1 = (a>b) ? a : b;
	print2 = (a>b) ? b : a;
	for(i=0;i<=print1;i++)
	{
	print1=print1%print2;
	if(print1==0)
		{
		gcd=print2;
		printf("%d ",gcd);
		break;
		}
	print2=print2%print1;
	if(print2==0)
		{
		gcd=print1;
		printf("%d ",gcd);
		break;
		}
	}
	lcm=a/gcd;
	lcm*=b;
	printf("%d\n",lcm);
	}
	return 0;
} 


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
    // ifstream in("data1.txt");
    // cin.rdbuf(in.rdbuf());
    int N = 6;
    vector<int> v(N);
    rep(i, N) cin >> v[i];
    string s = "Yay!";
    if(v[5] < v[4] - v[0]){
        s = ":(";
    }
    cout << s << endl;
}

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

#define INF (i64)1e18
#define MOD (i64)(1e9+7)
#define REP(i, n) for(i64 i = 0; i < n; i++)
#define RANGE(i, a, b) for(i64 i = a; i < b; i++)

int main() {
  int n;
  cin >> n;
  vector<i64> a(n);
  for(auto& e : a) cin >> e;
  sort(a.begin(), a.end(), greater<i64>());

  i64 ans2 = 0;
  RANGE(k, 1, n) {
    ans2 += a[k/2];
  }
  std::cout << ans2 << endl;

  return 0;
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }
template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

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

    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (register ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (register ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef queue <pii> qii ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int maxn = 2e6 + 10 ;
const int inf = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 1e9 + 7 ;
const double eps = 1e-7 ;
template <class T> void read(T &a)
{
	int f = 1 ; a = 0;
	char ch = getchar() ;
	while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
	while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
	a *= f;
}

ll n, h, w, ans;

struct card
{
	ll a, r, c;
}
a[maxn];

ll fa[maxn];

bool circle[maxn];

void init(ll t)
{
	rep(i, 1, t) fa[i] = i;
	return ;
}

ll getfa(ll a)
{
	return a == fa[a] ? a : fa[a] = getfa(fa[a]);
}

signed main()
{
	scanf("%lld %lld %lld", &n, &h, &w);
	init(h + w);
	rep(i, 1, n) scanf("%lld %lld %lld", &a[i].r, &a[i].c, &a[i].a);
	sort(a + 1, a + n + 1, [](card a, card b)
		{
			return a.a > b.a;
		}
	);
	rep(i, 1, n)
	{
		ll u = a[i].r, v = a[i].c + h;
		// cout << u << ' ' << v << endl;
		// printf("I : %lld %lld %lld\n", a[i].r, a[i].c, a[i].a);
		u = getfa(u), v = getfa(v);
		// printf("%lld %lld\n", u, v);
		if(u != v)
		{
			if(!circle[u] || !circle[v] ) ans += a[i].a, fa[u] = v, circle[v] = circle[u] = circle[v] | circle[u];
		}
		else
		{
			if(!circle[u]) circle[u] = 1, ans += a[i].a;
			// else puts("No");
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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

typedef char String[1024];

int main(void)
{
  String moneyStr;
  scanf("%s",moneyStr);
  int money = atoi(moneyStr);
  int fivehundredyens = money / 500;
  int fiveyens = ( money % 500 ) / 5;
  int Happiness = ( fivehundredyens * 1000 ) + ( fiveyens * 5 );
  printf("%d",Happiness);
  return 0;
}




Measured memory_bytes: 128
fn main() {
    let _: u32 = read();
    let s: String = read();
    let k: u32 = read();


    let cs = s.chars().collect::<Vec<char>>();
    let kth = cs[k as usize - 1 ];

    let ans: String = cs.iter().map(|i| {
        if i == &kth {
            *i
        } else {
            '*'
        }
    }).collect();


    println!("{}", ans);

}

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

#[warn(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

#[warn(dead_code)]
fn read_mat<T: std::str::FromStr>(row: u32) -> Vec<Vec<T>> {
    let mut vec = Vec::new();

    for _i in 0..row {
        vec.push(read_vec::<T>());
    }

    vec
}

Measured memory_bytes: 4352
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;



int main(void){
	ll N,Z,W,a[2010],ans;
	scanf("%lld%lld%lld",&N,&Z,&W);
	rep(i,N)scanf("%lld",&a[i]);
	if(N==1 || abs(a[N-1]-W)>abs(a[N-2]-a[N-1])){//N=1の時，必ず最後のを取ることになる
		ans=abs(a[N-1]-W);
	}else{
		ans=abs(a[N-2]-a[N-1]);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 1e5+10,p = 1e2+10;
ll n,w;
ll weight[mx];
ll cost[mx];
ll dp[p][mx];
ll solve(ll i,ll we)
{
    ll profit,profit1;
    if(i==n)
        return 0;
    if(dp[i][we]!=-1)
        return dp[i][we];
    if(we+weight[i]<=w)
    {
        profit = cost[i]+solve(i+1,we+weight[i]);
    }
    else profit = 0;

    profit1 = solve(i+1,we);
    return dp[i][we] = max(profit,profit1);
}
int main()
{
    cin>>n>>w;
    for(int i=0;i<n;i++)
    {
        cin>>weight[i]>>cost[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<(ll)solve(0,0)<<endl;
}

Measured memory_bytes: 86272
#include<iostream>
#include<algorithm>
using namespace std;
int a[1<<17];
int md=1e9;
bool zero=false;
main()
{
	int n,k;cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n-1;i++)
	{
		if(a[i+1]-a[i]==0)continue;
		md=min(md,a[i+1]-a[i]);
	}
	bool flag=false;
	for(int i=0;i<n;i++)
	{
		if(a[i]<k)continue;
		flag|=a[i]==k;
		flag|=a[i]%md==k%md;
	}
	cout<<(flag?"POSSIBLE":"IMPOSSIBLE")<<endl;
}


Measured memory_bytes: 640
import java.util.Scanner;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        double[] p = IntStream.range(0, n).map(e -> sc.nextInt()).mapToDouble(e -> (e + 1d) / 2d).toArray();

        double[] kitai = new double[n];
        for (int i = 0; i < k; i++) {
            kitai[0] += p[i];
        }
        for (int i = 1; i < n - k + 1; i++) {
            kitai[i] = kitai[i - 1] + p[i + k - 1] - p[i - 1];
        }

        double max = DoubleStream.of(kitai).max().getAsDouble();

        System.out.println(max);
        sc.close();
    }
}

Measured memory_bytes: 85968
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    int N = 0;
    cin >> N;
    long long happy[N][3];
    for (int i = 0; i < N; ++i) {
        cin >> happy[i][0] >> happy[i][1] >> happy[i][2];
    }

    long long dp[N + 1][3];
    for (int i = 0; i < N + 1; ++i) {
        for (int j = 0; j < 3; ++j) {
            dp[i][j] = 0;
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j != k) {
                    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + happy[i][k]);
                }
            }
        }
    }
//    for (int i = 0; i < N + 1; ++i) {
//        for (int j = 0; j < 3; ++j) {
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }

    long long result = 0;
    for (int i = 0; i < 3; ++i) {
        result = max(result, dp[N][i]);
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 4992
#include "bits/stdc++.h"
using namespace std;
int main(){
    int H,W,i,j,count;
    count = 0;
    cin >> H >> W;
    int A[H][W];
    int B[H][W];
    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            cin >> A[i][j];
            B[i][j]=0;
        }
    }
    for(i=0;i<H-1;i++){
        for(j=0;j<W;j++){
            if(A[i][j] %2){
                B[i][j] = 1;
                A[i+1][j] += 1;
                count++;
            }
        }
    }
    for(j=0;j<W-1;j++){
        if(A[H-1][j]%2){
            B[H-1][j]=1;
            A[H-1][j+1] += 1;
            count++;
        }
    }
    cout << count << endl;
    for(i=0;i<H-1;i++){
        for(j=0;j<W;j++){
            if(B[i][j]) cout << i+1 << " " << j+1 << " " << i+2 << " " << j+1 << endl;
        }
    }
    for(j=0;j<W-1;j++){
        if(B[H-1][j]) cout << H << " " << j+1 << " " << H << " " << j+2 << endl;
    }
    return 0;
}

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

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,arr,n) for(int i=arr;i<=n;i++)
#define repd(i,arr,n) for(int i=arr;i>=n;i--)
#define trav(arr,x) for(auto& arr:x)
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(arr) arr.size()
#define pi 3.14159265358979323846
#define MAX (1000*1000*1000+7)
#define vi vector<int>
#define pii pair<int,int>
#define pqueue priority_queue<int>
#define pdqueue priority_queue<int,vi,greater<int> >

const int mod=998244353;
const long double inf=1e14;
int power(int a,int b,int p)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}

int32_t main()
{
    string str;
    cin>>str;
    int a=(str[0]-'0')*10+(str[1]-'0');
    int b=(str[2]-'0')*10+(str[3]-'0');

    if(a<=12 && a>0 &&b>0&&b<=12)
    {
        cout<<"AMBIGUOUS"<<endl;
    }
    else if((a>12 && b>12)||(a>12 && b==0)||(a==0 && b>12)||(a==0 && b==0))
        cout<<"NA"<<endl;
    else if(a>12||a==0)
        cout<<"YYMM"<<endl;
    else
        cout<<"MMYY"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
	size_t N;
	std::cin >> N;

	size_t ans = 0;
	for (size_t n = 0; n < N; ++n)
	{
		size_t a;
		std::cin >> a;
		while (a % 2 == 0 && a != 0) {
			a /= 2;
			++ans;
		}
	}
	std::cout << ans << std::endl;

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N;
  cin >> N;
  
  vector<int> button(N);
  int L1 = 0;
  int L2 = 0;
  int C = 0;
  
  for (int i = 0; i < N ; i++) {
     cin >> button.at(i);
  }
  
  while (L1 != 1) {
    
    if (button.at(L1) == -1) {
      cout << -1 << endl;
      break;
    }
    
    L1 = button.at(L1)-1;
    button.at(L2) = -1;
    L2 = L1;
    C++;
  }
  
  if (L1 == 1) {
    cout << C <<endl;
  }
}

Measured memory_bytes: 3792
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#define int long long
#define double long double
#define oku7 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用

using namespace std;
std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位


signed main() {
	int N;
	cin >> N;
	int ma = -1, su = 0;
	for (int i = 0; i < N; i++) {
		int inp = 0;
		cin >> inp;
		su += inp;
		if (ma < inp) ma = inp;
	}
	cout << su - ma / 2 << "\n";
	


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;

const int MAX_V = 100010;
struct edge {
    int to,cost;
};
int n;
vector<edge> G[MAX_V];  //重み付き有効グラフの隣接リスト表現
ll d[MAX_V];

void dijkstra(int s){
    //greater<P>を指定することでfirstが小さい順に取り出せるようにする
    priority_queue<P, vector<P>,greater<P> > que;
    fill(d,d+n,INF);
    d[s] = 0;
    que.push(P(0,s));

    while(!que.empty()){
        P p = que.top(); que.pop();     // firstは最短距離、secondは頂点の番号
        int v = p.second;
        if(d[v] < p.first) continue;  
        for(int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                // 現在のd[]の要素とくらべて小さいものだけ追加するため、高速に計算可能
               d[e.to] = d[v] + e.cost;
               que.push(P(d[e.to],e.to));    
            }
        }
    }
}

int main()
{
    cin >> n;

    for(int i = 0; i < n-1; i++){
        int u,v,w;
        cin >> u >> v >> w;
        u--; v--;
        edge e1,e2;
        e1.to = u; e1.cost = w;
        e2.to = v; e2.cost = w;
        G[v].push_back(e1);
        G[u].push_back(e2);
    }
    dijkstra(0);
    for(int i = 0; i < n; i++){
        if(d[i] % 2 == 0){
            cout << 0 << endl;
        }else{
            cout << 1 << endl;
        }
    }
}

Measured memory_bytes: 7168
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

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

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}

const int mod = INF+7;
int main(){
    int n;cin>>n;
    VEC(int,l,n);
    sort(ALL(l));
    l.push_back(INF);
    ll res = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int tri = l[i]+l[j];
            res += (lower_bound(ALL(l),tri)-l.begin())-j-1;
        }
    }
    cout<<res;
}



Measured memory_bytes: 256
n,k = map(int,input().split())
ans = [1]
gone = [0] * n
now = 0
cnt = 0
lis = list(map(int,input().split()))
while True:
    if cnt == k:
        print(ans[k])
        exit()
    gone[now] = 1
    if gone[lis[now]-1] == 0:
        gone[lis[now]-1] = 1
        now = lis[now]-1
        ans.append(now+1)
    else:
        num = len(ans)
        now = lis[now]
        first = ans.index(now)
        k -= first
        k %= (num-first)
  #         print(ans,now)
  #         print(first,k)
  #         print(ans,now)
        print(ans[first+k])
        exit()
    cnt += 1

Measured memory_bytes: 33944
//package april2020;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		FastReader scn = new FastReader();
		OutputStream out = new BufferedOutputStream ( System.out );
		String s1 = scn.next();
		String s2 = scn.next();
		
		int[][] dp = new int[s1.length()+1][s2.length()+1];
		for(int i = s1.length();i>=0;i--) {
			for(int j=s2.length();j>=0;j--) {
				if(i==s1.length()||j==s2.length()) {
					dp[i][j]=0;
				}else {
					if(s1.charAt(i)==s2.charAt(j)) {
						dp[i][j]=dp[i+1][j+1]+1;
					}else {
						int c1 = dp[i+1][j];
						int c2 = dp[i][j+1];
						
						dp[i][j] = Math.max(c1, c2);
					}
				}
			}
		}
		StringBuilder res = new StringBuilder();
		int s1l = s1.length(), s2l = s2.length();
		int i=0,j=0;
		while(i<s1l&&j<s2l) {
			if(s1.charAt(i)==s2.charAt(j)) {
				res.append(s1.charAt(i));
				i++;
				j++;
			}else if(dp[i+1][j]>dp[i][j+1]) {
				i++;
			}else {
				j++;
			}
		}
		out.write((res.toString()+"\n").getBytes());
		out.close();
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
}


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

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

    int N; cin >> N;
    vector<int> x(N), y(N), h(N);
    for (int i = 0; i < N; i++)
        cin >> x[i] >> y[i] >> h[i];
    
    for (int cx = 0; cx <= 100; cx++) {
        for (int cy = 0; cy <= 100; cy++) {
            int ans = -1;
            bool flag = true;
            for (int i = 0; i < N; i++) {
                if (h[i] == 0) continue;
                int res = abs(x[i]-cx) + abs(y[i]-cy) + h[i];
                if (ans < 0) ans = res;
                else {
                    if (ans != res) {
                        flag = false;
                        break;
                    }
                }
            }
            if (!flag) continue;

            for (int i = 0; i < N; i++) {
                if (h[i] > 0) continue;
                int res = abs(x[i]-cx) + abs(y[i]-cy);
                if (ans > res) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cout << cx << " " << cy << " " << ans << "\n";
                return 0;
            }
        }
    }
}

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

int main(){
    int N;
    ll H, W;
    cin >> N >> H >> W;
    int count = 0;
    for(int i = 0; i < N; i++){
        ll tmpa, tmpb;
        cin >> tmpa >> tmpb;
        if(tmpa >= H && tmpb >= W) count++;
    }
    cout << count << endl;
    return 0;
}

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

int main()
{
    int n;cin>>n;
    vector <int> vect(n);
    for(int i=0;i<n;i++)
        cin>>vect[i];
    float num=0.00;
    for(int i=0;i<n;i++)
    {
        num =num + (1/(float)(vect[i]));
    }
    cout<<(1/(float)num);
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m = map(int,input().split())
A = list(map(int,input().split()))
S = sum(A)
for ai in A:
  if ai * 4 * m >= S:
    count += 1
if count >= m:
  print("Yes")
else:
  print("No")

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

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

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

using namespace std;

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

  long long n;
  int m;
  cin >> n >> m;
  while (m--) {
    int x;
    cin >> x;
    n -= x;
  }
  cout << max(-1ll, n);

  return 0;
}

Measured memory_bytes: 3660
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    Scanner sc = new Scanner(System.in);
   
    public static void main(String[] args) {
        new Main(); 
    }
   
    public Main() {
        new aoj1210().doIt();
    }
    class aoj1210{
    	int dice[] = {1,5,4,3,2,6};
    	void turn(char c) {
			switch(c){
			case 'n': swap(0,4,5,1); break;
			case 's': swap(0,1,5,4); break;
			case 'w': swap(0,3,5,2); break;
			case 'e': swap(0,2,5,3); break;
			}
		}
		void swap(int i, int j, int k, int l) {
			int temp = dice[l];
			dice[l] = dice[k];
			dice[k] = dice[j];
			dice[j] = dice[i];
			dice[i] = temp;
		}
    	void doIt(){
    		while(true){
    			int n = sc.nextInt();
    			for(int i = 0;i < 6;i++){
    				if(i == 0 || i == 5)dice[i] = i+1;
    				else dice[i] = 6-i;
    			}
    			if(n == 0)break;
    			for(int i = 0;i < n;i++){
    				String str = sc.next();
    				turn(str.charAt(0));
    			}
    			System.out.println(dice[0]);
    		}
    	}
    }
}

Measured memory_bytes: 29588
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	String strArr[] = br.readLine().split(" ");
        	int[] a=new int[12];

        	for(int j=0; j<12; j++){
        		a[j]=Integer.parseInt(strArr[j]);
        	}

        	for(int i=0;i<12-1;i++){
        	      for(int j=12-1;j>i;j--){

        		if(a[j]<a[j-1]){
        		  int t=a[j];
        		  a[j]=a[j-1];
        		  a[j-1]=t;
        		}
        	  }
        	}

        	if(a[0] == a[1] && a[2] == a[1] && a[3] == a[2] && a[4]==a[5] && a[5]==a[6] && a[6] == a[7] && a[8] == a[9] && a[9] == a[10] && a[10] == a[11]){
        		System.out.println("yes");
        	}
        	else{
        		System.out.println("no");
        	}
    }
}

Measured memory_bytes: 24368
#include <bits/stdc++.h>
#define REP(i,n) for(LL i=0;i<(LL)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long
#define pii pair<LL,LL>
#define pll pair<LL,LL>

using namespace std;

vector<LL> edge[100001];
bool used[100001];
pii pairg={0,0};
bool isPair=true;
bool color[100001];

void dfs(LL v,bool col){
    used[v]=true;
    color[v]=col;
    if(col)pairg.first++;
    else pairg.second++;
    for(LL u:edge[v]){
        if(!used[u])dfs(u,!col);
        else if(color[u]==col)isPair=false;
    }
}


int main(){

    LL N,M;cin>>N>>M;
    REP(i,M){
        LL a,b;cin>>a>>b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
    }
    fill_n(used,N,false);
    dfs(0,true);

    LL ans=0;
    if(isPair){
        ans = pairg.first*pairg.second - M;
    }else{
        ans = N*(N-1)/2 -M;
    }
    cout<<ans<<endl;

    return 0;
}

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for(int i=0; i<m; i++) {
        cin >> a[i];
        n -= a[i];
    }

    if( n < 0) n = -1;

    cout << n << endl;
}

Measured memory_bytes: 3664