akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    //ABピザを2*x枚買うとき
    int aab = max(0,y-x)*b+2*x*c;
    int bab = max(0,x-y)*a+2*y*c;
    int n = min(aab,bab);
    cout << min(a*x+b*y,n) << endl;
    return 0;
}


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

signed main() {
  int N, M;
  cin >> N >> M;
  
  vector<string> A(N);
  for( int i = 0; i < N; i++ ) cin >> A.at(i);
  vector<string> B(M);
  for( int i = 0; i < M; i++ ) cin >> B.at(i);
  
  for( int i = 0; i < N; i++ ){
    for( int j = 0; j < N; j++ ){
      
      bool hantei = true;
      for( int k = 0; k < M; k++ ){
        for( int l = 0; l < M; l++ ){
          if ( i+k >= N || j+l >= N ){
            hantei = false;
            break;
          }
          if( A.at(i+k).at(j+l) != B.at(k).at(l) ) hantei = false;
        }
      }
      if( hantei == true ){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
      
            
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int N;
	cin>>N;
	int a[N];
	for(int i = 0;i<N;i++){
		cin>>a[i];
	}
	int dp[N] = {1000000};
	int ans = 0;
	dp[0] = 0;
	for(int i = 1;i<N;i++){
		if(i>1){
			dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]));
		}
		else{
			dp[i] = abs(a[i]-a[i-1]);
		}
	}
	cout << dp[N-1] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>

#define rep(i, n) for(int i = 0; i < n; i++)
using ll = long long;

using namespace std;

int main()
{
    int n;  cin >> n;
    vector<int> h(n);   rep(i, n) cin>> h[i];

    int view = h[0];
    int ans  = 1;
    for(int i = 1; i < n; i++){
        if(h[i] >= view){
            ans++;
            view = h[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll n,m,q;

ll cul(vector<vector<ll>> &A,ll x,ll y,ll x2,ll y2){
    if(x2<x || y2<y){return 0;}
    ll ret=A[x2][y2];
    if(y!=0){ret-=A[x2][y-1];}
    if(x!=0){ret-=A[x-1][y2];}
    if(y!=0 && x!=0){ret+=A[x-1][y-1];}
    return ret;
}



int main(){
    cin>>n>>m>>q;
    vector<string> a(n);
    for(auto &I:a){cin>>I;}
    vector<vector<ll>> A(n,vector<ll>(m,0));
    vector<vector<ll>> B(n,vector<ll>(m,0));
    vector<vector<ll>> C(n,vector<ll>(m,0));
    for(int i=0;i<n;i++){
        for(int t=0;t<m;t++){
            A[i][t]=a[i][t]-'0';
        }
    }
    for(int i=1;i<n;i++){
        for(int t=0;t<m;t++){
            A[i][t]+=A[i-1][t];
        }
    }
    for(int i=0;i<n;i++){
        for(int t=1;t<m;t++){
            A[i][t]+=A[i][t-1];
        }
    }
    for(int i=1;i<n;i++){
        for(int t=0;t<m;t++){
            B[i][t]=(a[i][t]=='1' && a[i-1][t]=='1');
        }
    }
    for(int i=1;i<n;i++){
        for(int t=0;t<m;t++){
            B[i][t]+=B[i-1][t];
        }
    }
    for(int i=0;i<n;i++){
        for(int t=1;t<m;t++){
            B[i][t]+=B[i][t-1];
        }
    }
    for(int i=0;i<n;i++){
        for(int t=1;t<m;t++){
            C[i][t]=(a[i][t]=='1' && a[i][t-1]=='1');
        }
    }
    for(int i=1;i<n;i++){
        for(int t=0;t<m;t++){
            C[i][t]+=C[i-1][t];
        }
    }
    for(int i=0;i<n;i++){
        for(int t=1;t<m;t++){
            C[i][t]+=C[i][t-1];
        }
    }
    while(q--){
        ll x,y,x2,y2;
        cin>>x>>y>>x2>>y2;
        x--; y--; x2--; y2--;
        ll blue=cul(A,x,y,x2,y2);
        blue-=cul(B,x+1,y,x2,y2);
        blue-=cul(C,x,y+1,x2,y2);
        cout<<blue<<endl;
    }
    
    
    
    return 0;
}


Measured memory_bytes: 100352
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define pi 3.14159265358979323846
#define Endl endl
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
int fl[110][110];
int dis[110][110];
signed main(){
	int h,w;
	cin>>h>>w;
	for(int i=0;i<h;i++){
		string st;
		cin>>st;
		for(int j=0;j<w;j++){
			if( st[j] == '#' ){
				fl[i+1][j+1] = 1;
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			dis[i][j] = inf;
		}
	}
	dis[1][1] = fl[1][1];
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if( i != 1 ){
				if( fl[i][j] == fl[i-1][j] || fl[i][j] == 0 ){
					dis[i][j] = min( dis[i][j], dis[i-1][j] );
				}
				else{
					dis[i][j] = min( dis[i][j], dis[i-1][j]+1 );
				}
			}
			if( j != 1 ){
				if( fl[i][j] == fl[i][j-1] || fl[i][j] == 0 ){
					dis[i][j] = min( dis[i][j], dis[i][j-1] );
				}
				else{
					dis[i][j] = min( dis[i][j], dis[i][j-1]+1 );
				}
			}
		}
	}
	cout<<dis[h][w]<<endl;
	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
ll n;

ll m(ll x){
  if(x == n+1) return 0;
  if(x == -1) return n;
  return x;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    cin >> n;
    ll a[n+1];
    a[0] = 0;
    FOR(i,1,n+1) cin >> a[i];
    ll sum = 0;
    FOR(i,1,n+2){
      sum += abs(a[m(i-1)] - a[m(i)]);
    }
    FOR(i,1,n+1){
      cout << sum - abs(a[m(i)] - a[m(i+1)]) - abs(a[m(i-1)] - a[m(i)]) + abs(a[m(i-1)] - a[m(i+1)])<<endl;
    }

    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 2048
N, K = gets.chomp.split.map(&:to_i)
 
counter = Hash.new(0)
 
K.times do
  _d = gets.chomp.to_i
  A = gets.chomp.split
  A.each do |a|
  	counter[a] += 1
  end
end
 
print N - counter.length

Measured memory_bytes: 14320
#include<stdio.h>
#include<string.h>
int main()
{
	char m,n;
	scanf("%c %c",&m,&n);
	if(m == 'H')
	{
		if(n == 'H')
		{
			printf("H\n");
		}
		else
		{
			printf("D\n");
		}
	}
	else
	{
		if(n == 'H')
		{
			printf("D\n");
		}
		else
		{
			printf("H\n");
		}
	}
	return 0;
}

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

int previnst[200005];

int main(){
    int n;
    scanf("%d", &n);
    int pmatch[n];
    long long waystofin[n+1];
    for(int i = 0; i < 200005; i++){
        previnst[i] = -1;
    }
    for(int i = 0; i < n; i++){
        waystofin[i] = 0;
        int col;
        scanf("%d", &col);
        pmatch[i] = previnst[col];
        previnst[col] = i;
    }
    waystofin[n] = 1;
    for(int i = n-1; i >= 0; i--){
        waystofin[i] += waystofin[i+1];
        waystofin[i] %= 1000000007;
        if(pmatch[i] != -1 && pmatch[i] != i-1){
            waystofin[pmatch[i]] += waystofin[i];
        }
    }
    printf("%lld", waystofin[0]);
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)


int main(){
	int a,b;
	cin >> a >> b;
	if (a <= 8 && b <= 8) cout << "Yay!"<< endl;
	else cout << ":(" << endl;
	
	
	return 0; 
}



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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

int checked[100000000] = {};

void func(pair<ll, list<int>>* node, int p)
{
	checked[p] = 1;
	for (int tmp : node[p].second) {
		if (checked[tmp])
			continue;
		node[tmp].first += node[p].first;
		func(node, tmp);
	}
	return ;
}


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

	int n, q;
	cin >> n >> q;

	pair<ll, list<int>> node[n];
	rep (i, 0, n - 1) {
		int a, b;
		cin >> a >> b;
		node[a - 1].second.push_back(b - 1);
		node[b - 1].second.push_back(a - 1);
	}

	rep (i, 0, q) {
		int p;
		ll x;
		cin >> p >> x;
		node[p - 1].first += x;
	}

	func(node, 0);

	rep (i, 0, n)
		cout << node[i].first << endl;

	return 0;
}


Measured memory_bytes: 29696
from collections import deque

def bfs(sy,sx):
    dist[sy][sx]=0
    q=deque([[sy,sx]])
    while q:
        cy,cx=q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx=cy+i,cx+j
            if ny<0 or h-1<ny or nx<0 or w-1<nx or path[ny][nx]=='#':continue
            if path[ny][nx]=='.' and dist[ny][nx]==-1:
                dist[ny][nx]=dist[cy][cx]+1
                q.append([ny,nx])
    max_dist=-1
    for i in range(h):
        for j in range(w):
            if path[i][j]=='#':continue
            max_dist=max(max_dist,dist[i][j])
    return max_dist

h,w=map(int,input().split())
path=[input() for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            continue
        dist=[[-1]*w for i in range(h)]
        t=bfs(i,j)
        ans=max(ans,t)
print(ans)

Measured memory_bytes: 3316
import java.util.Scanner;

public class Main{
    static long lcm (long a, long b) {
	     long temp;
	      long c = a;
	       c *= b;
	        while((temp = a%b)!=0) {
  		        a = b;
		            b = temp;
  	           }
	     return (long)(c/b);
     }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    long a=scanner.nextLong();
    long b=scanner.nextLong();
    long c=scanner.nextLong();
    long d=scanner.nextLong();
    //int a[]=new int[n];

    //System.out.println(a);
    long bc,bd,ac,ad;
    bc=b/c;
    bd=b/d;
    ac=(a-1)/c;
    ad=(a-1)/d;
    long num1,num2;
    num1=bc-ac;
    num2=bd-ad;
    long scd;
    long bscd,ascd;
    scd=lcm(c,d);
    bscd=b/scd;
    ascd=(a-1)/scd;
    long num3;
    num3=bscd-ascd;

    long cnt=b-a+1-num1-num2+num3;
    //System.out.println(b+"-"+a+"-"+num1+"-"+num2+"+"+num3);
    System.out.println(cnt);
  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>     // [PRIMES]               1777 ~2^10.80  
using namespace std;                     //                       10333 ~2^13.33
using ll=long long;                      // seq 1 128 | factor   100333 ~2^16.61
using vl=vector<ll>;                     //   | grep -v ' .* '  1300111 ~2^20.31
using vvl=vector<vl>;                    //                    10300777 ~2^23.30
using vb=vector<bool>;                   //                   100400999 ~2^26.58
using vs=vector<string>;                 //                  1300400999 ~2^30.28
using pll=pair<ll,ll>;                   //                 10200500333 ~2^33.25
const ll oo =0x3f3f3f3f3f3f3f3fLL;       //                100200400777 ~2^36.54
const double eps=1e-9;                   //               1200300700111 ~2^40.13
#define sz(c) ll((c).size())             //              10200300500777 ~2^43.21
#define all(c) begin(c),end(c)           //             100200300400777 ~2^46.51
#define mp make_pair                     //            1200300400600999 ~2^50.09
#define mt make_tuple                    //           10200300400600111 ~2^53.18
#define pb push_back                     //          100200300400600333 ~2^56.48
#define eb emplace_back                  //         1200300400500800999 ~2^60.06
#define xx first
#define yy second
#define FOR(i,a,b) for(ll i=(a); i<(ll)(b); i++)
#define FORD(i,a,b) for(ll i=ll(b)-1;i>=(a);i--)
#define TR(X) ({if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

vvl dat;

vvl dp;

ll f(ll i ,ll j){
    if(i < 0) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    ll maxi = -1;
    FOR(it,0,3){
        if(it == j) continue;
        ll res = dat[i][j] + f(i-1,it);
        maxi = max(maxi, res);
    }
    dp[i][j] = maxi;
    return maxi;
}

int main(){
    ll N;
    cin >> N;
    dp.resize(N, vl(3,-1));
    FOR(bnm,0,N){
        ll ia,ib,ic;
        cin >> ia >> ib >> ic;
        vl tmp = {ia, ib, ic};
        dat.pb(tmp);
    }
    cout << max(f(N-1,0), max(f(N-1,1), f(N-1,2)))<< endl;

    
} //cin.tie(0) bei schnellem Wechseln




Measured memory_bytes: 19376
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		String n = in.next();
		
		
		
		long sum = 0;
		
		for(int i = 0;i<n.length();i++) {
			int num = n.charAt(i) - '0';
			sum = sum + num;
		}
		
		
		
		if(sum % 9 == 0) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 31064
#include<bits/stdc++.h>
using namespace std;
#define intt long long int
#define intu unsigned long long int
#define vi vector<intt>
#define ii pair<int,int>
#define pb push_back
//#define mp make_pair
#define ff first
#define ss second
#define fast_io ios::sync_with_stdio(0);cin.tie(NULL);std::cout.tie(NULL);
# define PI           3.14159265358979323846 
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
int mod = 1000000007;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a * b / gcd(a, b); }
intt bpow(intt a,intt b) 
{
  intt res = 1;
  while (b > 0) {
    if (b & 1)res = res * a;
      a = a * a;
      b >>= 1;
  }
  return res;
}
intt fact(intt n) { 
   if ((n==0)||(n==1))
      return 1; 
   else
      return n*fact(n-1);
}

void go()
{
#ifndef ONLINE_JUDGE
  freopen("IN.txt","r",stdin);
  freopen("OUT.txt","w",stdout);
  #endif
}


int main(){
	go();
	fast_io

	string s,t;cin>>s>>t;
	int ans=INT_MAX;
	for(int i=0;i<s.size()-t.size()+1;i++){
		int temp=0;
		for(int j=0;j<t.size();j++){
			if(s[j+i]!=t[j]){
				temp++;
			}
		}
		ans=min(ans,temp);
	}
	cout << ans <<"\n";
}




















Measured memory_bytes: 3620
N = int(input())
L = [int(l) for l in input().split()]
cnt = 0
for i in range(N):
    Li = L[i]
    for j in range(i + 1, N):
        Lj = L[j]
        for k in range(j + 1, N):
            Lk = L[k]

            if Li != Lj and Lj != Lk and Lk != Li:
                _L = sorted([Li, Lj, Lk])
                if _L[0] + _L[1] > _L[2]:
                    cnt += 1

print(cnt)

Measured memory_bytes: 9216
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define PI 3.141592653589793
typedef long long ll;

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

    int a[3],n,ans = 0,max = 0,b;
    cin >> a[0] >> a[1] >> a[2] >> n;

    rep(i,3){
        if(max < a[i]) {
            max = a[i];
            b = i;
        }
    }

    rep(i,n){
        a[b] = a[b] * 2;
    }

    cout << a[0] + a[1] + a[2] << endl;

    return 0;
}

Measured memory_bytes: 256
fun main (args : Array<String>) {
    val (s, t) = readLine()!!.split(" ")
    val (a, b) = readLine()!!.split(" ")
    val u= readLine()!!

    var A : Int = a.toInt()
    var B : Int = b.toInt()

    if (u.toString() == s.toString()) {
        A--
    } else if (u.toString() == t.toString()) {
        B--
    }

    println("${A} ${B}")

}

Measured memory_bytes: 36220
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long Y = scanner.nextLong();
        boolean found = false;
        for(int x=0;x<=n;x++){
            if(found) break;
            for(int y=0;y<=n;y++){
                int z = n-x-y;
                if(z>=0 && 10*x+5*y+z==Y/1000){
                    System.out.println(x+" " +y+" "+z);
                    found = true;
                    break;
                }
            }
        }
        if(!found) System.out.println("-1 -1 -1");
    }
}

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

using ll=long long;
ll n,a,b,c,d;

int main()
{
	cin>>n>>a>>b>>c>>d;
	for (int i=0;i<n;i++)
	if ((n*c-c-b+a)<=i*(c+d) && i*(c+d)<=(n*d-d-b+a)) return 0*puts("YES");
	return 0*puts("NO");
}

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

pair<long, int> a[2222];
long d[2222][2222];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        a[i] = {x, i};
    }
    sort(a, a + n);
    for(int l = 1; l <= n; l++) {
        for(int i = 0; i + l <= n; i++) {
            auto [x, j] = a[l - 1];
            d[l][i] = max(d[l - 1][i] + abs(i + l - 1 - j) * x,
                          d[l - 1][i + 1] + abs(i - j) * x);
        }
    }
    cout << d[n][0] << endl;
    return 0;
}


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

class LCA {
    using Adj = std::vector<std::vector<int>>;  // 隣接リスト

private:
    int n;                              // 要素数
    int logn;                           // floor(log2(n)) + 1
    int root;                           // 根
    std::vector<std::vector<int>> par;  // par[k][i]: i番目のノードの2^k番目の親
    std::vector<int> dep;               // 深さ

    void init(const Adj& g, int root) {
        n = static_cast<int>(g.size());
        root = root;

        logn = 1;
        while (n >> logn) ++logn;

        par.assign(logn, std::vector<int>(n, -1));
        dep.assign(n, -1);
        dfs(g, root, -1, 0);

        // parを初期化する
        for (int k = 0; k + 1 < logn; k++) {
            for (int i = 0; i < n; i++) {
                if (par[k][i] != -1)
                    par[k + 1][i] = par[k][par[k][i]];
            }
        }
    }
    // 初期化時にpar[0]やdepを求めるためのDFS
    void dfs(const Adj& g, int v, int p, int d) {
        par[0][v] = p;
        dep[v] = d;
        for (const auto& to : g[v]) {
            if (to != p) dfs(g, to, v, d + 1);
        }
    }

public:
    /**
     * コンストラクタ
     */
    LCA(const Adj& g, int root) {
        init(g, root);
    }
    // u と v のLCAを返す
    int lca(int u, int v) const {
        if (dep[u] > dep[v]) std::swap(u, v);

        // u と v の深さが同じになるまで親をたどる
        for (int k = 0; k < logn; k++) {
            if ((dep[v] - dep[u]) >> k & 1) {
                v = par[k][v];
            }
        }

        if (u == v) return u;

        // 二分探索する
        for (int k = logn - 1; k >= 0; k--) {
            if (par[k][u] != par[k][v]) {
                u = par[k][u];
                v = par[k][v];
            }
        }

        return par[0][u];
    }
    int parent(int idx, int d) const { return par[d][idx]; }
};

void solve() {
    ll N;
    cin >> N;
    using Graph = vector<Vi>;
    Graph g(N);
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        for (ll j = 0; j < a; j++) {
            ll v;
            cin >> v;
            g[i].emplace_back(v);
        }
    }

    LCA lca(g, 0);

    int Q;
    cin >> Q;
    while (Q--) {
        ll u, v;
        cin >> u >> v;
        cout << lca.lca(u, v) << "\n";
    }
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}


Measured memory_bytes: 18140
#include <bits/stdc++.h>
using namespace std;
 
int main(){ 
    int d;
    cin>>d;
    if(d==25)cout<<"Christmas";
    if(d==24)cout<<"Christmas Eve";
    if(d==23)cout<<"Christmas Eve Eve";
    if(d==22)cout<<"Christmas Eve Eve Eve";
 
    return 0;
}

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


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");

		int N = Integer.parseInt(tmp[0]);
		int K = Integer.parseInt(tmp[1]);

		String S = br.readLine();

		for(int i = 0;i<N;i++){
			if(i+1 == K){
				int a = (int)S.charAt(i) + 32;
				byte[] ascii = {Byte.parseByte(String.valueOf(a))};
				String resultString = new String(ascii, "US-ASCII");
				System.out.print(resultString);
			}else{
				System.out.print(S.charAt(i));
			}
		}



	}

}

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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

double kaijyo(int n){
    int k(1);
    for(int i=n;i>0;i--){
        k *= i;
    }

    return k;
}

double distance(int x[],int y[],int i,int j){
    int dx = (x[i] - x[j]) * (x[i] - x[j]);
    int dy = (y[i] - y[j]) * (y[i] - y[j]);
    return sqrt(dx+dy);
}

int main(){
    int n;  cin >> n;
    int x[n],y[n];
    rep(i,n)    cin >> x[i] >> y[i];

    double d[n][n];
    rep(i,n){
        rep(j,n){
            d[i][j] = distance(x,y,i,j);
        }
    }

    vector<int> next(n);
    rep(i, n) next[i] = i;

    double sum(0.0);

    do{
        rep(i,n-1){
            sum += d[next[i]][next[i+1]];
        }
    } while (next_permutation(next.begin(), next.end()));

    sum /= kaijyo(n);

    cout << setprecision(10) << sum << endl;

    return 0;
}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int x;
  cin >> x;
  if (x < 1200)
    cout << "ABC" << endl;
  else
    cout << "ARC" << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define N 100010
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n)  for(int i = n - 1; i >= 0; --i)
#define forr1(i, n) for(int i = n; i >= 1; --i)
#define form(l, r, i)   for(int i = l; i <= r; ++i)
#define forv(r, l, i)   for(int i = r; i >= l; --i)
#define r0 return 0
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lld long double
#define elif else if
  
const int inf = 1e9 + 7;
const lld EPS = 0.00000001;
const ll modw = 1e9 + 9;
  
using namespace std;

int main()
{
    barnarnar
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << ' ' << x << ' ' << y;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
/*n 人の学生を含むクラスでプログラミングの試験を行った。それぞれの得点をs1, s2 ... snとしたときの、標準偏差を求めるプログラムを作成せよ。
 */
using namespace std;

int main(){
	int n;
	double sum = 0;
	double subedSum = 0;
	cout << setprecision(30);
	while(true){
		vector<double> v;
		sum = 0;
		subedSum = 0;
		cin >> n;
		if(n == 0) return 0;
		for(int i = 0; i < n; i++){
			double tmp;
			cin >> tmp;
			v.push_back(tmp);
			sum += tmp;
		}
		double average = sum / n;
		for(int i = 0; i < n; i++){
			subedSum += (v[i] - average) * (v[i] - average);
		}
		cout << sqrt(subedSum / n) << '\n';
	}
}



Measured memory_bytes: 3240
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, j) for (long long i = 0; i < j; i++)
#define int long long

using namespace std;

signed main()
{
    int N, M, x;
    cin >> N >> M;
    vector<int> A_arr;
    vector<int> A_subarr;
    rep(i, N)
    {
        cin >> x;
        A_arr.push_back(x);
    }
    sort(A_arr.begin(), A_arr.end(), std::greater<int>());
    int pre_M = M + 1;
    while (M > 0 && pre_M != M) {
        pre_M = M;
        int A_0 = A_arr[0] / 2;
        rep(i, N)
        {
            int A_i = A_arr[i];
            if (M > 0 && A_i > A_0) {
                M--;
                A_arr[i] = A_i / 2;
            } else {
                sort(A_arr.begin(), A_arr.end(), std::greater<int>());
                break;
            }
        }
    }
    int answer = 0;
    rep(i, N)
    {
        answer += A_arr[i];
    }
    cout << answer << endl;
}


Measured memory_bytes: 1528
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())
s = list(input())
q = int(input())

char_idx = [[] for _ in range(26)]
for i in range(n):
    char_idx[ord(s[i])-ord('a')].append(i)
# print(char_idx)

query = [input().split() for _ in range(q)]
# print(query)

for t, a, b in query:
    if t=='1':
        i = int(a) - 1
        if s[i] == b:
            continue
        else:
            idx = bisect.bisect_left(char_idx[ord(s[i])-ord('a')], i)
            if char_idx[ord(s[i])-ord('a')][idx] == i:
                del char_idx[ord(s[i])-ord('a')][idx]
            bisect.insort_left(char_idx[ord(b)-ord('a')], i)
            s[i] = b
    else:
        l = int(a) - 1
        r = int(b) - 1
        ans = 0
        for i in range(26):
            if len(char_idx[i]) == 0:
                continue
            it = bisect.bisect_left(char_idx[i], l)
            if it < len(char_idx[i]) and char_idx[i][it] <= r:
                ans += 1
        print(ans)


Measured memory_bytes: 33720
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		int c = b - a;
		int ans = 0;
		for (int i = 1; i < c; i++) {
			ans += i;
		}
		System.out.println(ans - a);
		
	}
	
}


Measured memory_bytes: 20948
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
    fastio;
    int n;
    cin >> n;
    int h[n],dp[(int)1e5];
    for(int i=0;i<n;i++){cin >> h[i];}
    dp[0]=0;
    dp[1] = abs(h[1]-h[0]);
    for(int i=2;i<n;i++){
        dp[i] = min(abs(h[i]-h[i-2])+dp[i-2],abs(h[i]-h[i-1])+dp[i-1]);
    }
    cout << dp[n-1] << "\n";
    return 0;
}


Measured memory_bytes: 4384
fn main() {
    let mut line = String::new();
    let stdin = std::io::stdin();
    let _ = stdin.read_line(&mut line);
    let n = line.split_whitespace().nth(0).unwrap().parse::<usize>().unwrap();
    line.clear();
    let mut sunuke = vec![false; n];
    while let Ok(l) = stdin.read_line(&mut line) {
        if l <= 0 { break; }
        line.clear();
        let _ = stdin.read_line(&mut line);
        for i in line.split_whitespace().map(|x| x.parse::<usize>().unwrap()) {
            sunuke[i-1] = true;
        }
        line.clear();
    }
    println!("{}", sunuke.iter().filter(|&x| !*x).count());
}


Measured memory_bytes: 2072
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
typedef priority_queue<string> priquest;
typedef priority_queue<string,vector<string>,greater<string>> rpriquest;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}

const ll big=1000000007;
ll exp(ll x,ll y){
    if(y==0)return 1;
    if(x==1||x==0)return x;
    if(y%2==1)return (exp(x,y-1)*x);
    ll t=exp(x,y/2);
    return (t*t);
}
void chmin(ll a,ll b){
    if(a>b)a=b;
    return;
}
  
int main(){
  int n,m,x;cin >> n >> m >> x;
  vector<int> money(n);
  vector<vector<int>> book(n,vector<int>(m));
  vector<int> MAX(m);
  ll ans=0;
  rep(i,n){
    cin >> money[i];
    ans+=money[i];
    rep(j,m){
      cin >> book[i][j];
      MAX[j]+=book[i][j];
    }
  }
  
  rep(i,m)if(MAX[i]<x){cout << -1 << endl;return 0;}
  ll t=(1<<n);
  
  rep(ii,t){
    bitset<12> buy(ii);
    vector<ll> skill(m);
    int mon=0;
    rep(i,n){
      if(buy.test(i)){
        mon+=money[i];
        rep(j,m)skill[j]+=book[i][j];
      }
    }
    bool can=true;
    rep(i,m)if(skill[i]<x)can=false;
    if(!can)continue;
    ans=min(ans,mon);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include<iostream>

using namespace std;

const int max_n = 1000000;

int par[max_n];
int rnk[max_n];

void init(int n){

	for(int i=0; i<n; i++){
		par[i] = i;
		rnk[i] = 0;
	}
}

int find_root(int x){
	if(par[x] == x) return x;
	else 			return par[x] = find_root(par[x]);
}

void unite(int x, int y){
	x = find_root(x);
	y = find_root(y);
	if(x == y) return;

	if(rnk[x] < rnk[y]){
		par[x] = y;
	}
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
}

bool same(int x, int y){
	return find_root(x) == find_root(y);
}

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

	int p[n+1];
	for(int i=1;i<n+1;i++) cin >> p[i];

	init(n);

	int x,y;
	for(int i=0;i<m;i++){
		cin >> x >> y;
		unite(x,y);
	}

	int ans=0;
	for(int i=1;i<n+1;i++){
		if(same(i,p[i])) ans++;
	}

	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 5120
S = list(input())
N = len(S)

a = int((N - 1)/ 2)
b = int((N + 3)/ 2)

count = 0
S_bak = list(reversed(S))
# print(S)
# print(S_bak)
if S == S_bak:
    count += 1
    # print("1")

one = S[0:a]
# print(a)
# print(one)
one_bak = list(reversed(one))
if one == one_bak:
    count += 1
    # print("2")

two = S[b-1:N]
# print(b)
# print(two)
two_bak = list(reversed(two))
# print(two_bak)
if two == two_bak:
    count += 1
    # print("3")

if count == 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
//
//AtCoder Beginner Contest 047
//B
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    ll n, m;
    cin >> n >> m;
    ll ans = m*1900 + (n-m)*100;
    ans *= pow(2,m);
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

long long INF=LLONG_MAX;

ll a[200222];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	ll n,k; cin >> n >> k;
	ll sum = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	sort(a,a+n);
	for(int i = 0; i < n-k; i++){
		sum += a[i];
	}
	cout << sum << endl;
}	


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

namespace ConsoleApplication2
{
    public class Program
    {
        static void Main(string[] args)
        {
            String input = Console.ReadLine();
            String temp = input;
            String ans = "YES";
            var mdl = new modl();
            while (ans == "YES")
            {
                if (temp.Length == 0)
                {
                    break;
                }

                if (mdl.isDreamer(temp))
                {
                    temp = temp.Substring(0,temp.Length-7);
                    continue;
                }

                if (mdl.isEraser(temp))
                {
                    temp = temp.Substring(0, temp.Length - 6);
                    continue;

                }

                if (mdl.isDream(temp))
                {
                    temp = temp.Substring(0, temp.Length - 5);
                    continue;

                }
                if (mdl.isErase(temp))
                {
                    temp = temp.Substring(0, temp.Length - 5);
                    continue;
                }

                ans = "NO";
            }
            Console.WriteLine(ans);

        }



    }

    public class modl
    {
        public bool isDream(string str)
        {
            if (str.Length < 5)
            {
                return false;
            }
            String sub = str.Substring(str.Length-5);
            if (sub == "dream")
            {
                return true;
            }
            return false;
        }

        public bool isDreamer(string str)
        {
            if (str.Length < 7)
            {
                return false;
            }
            String sub = str.Substring(str.Length-7);
            if (sub == "dreamer")
            {
                return true;
            }
            return false;
        }

        public bool isErase(string str)
        {
            if (str.Length < 5)
            {
                return false;
            }
            String sub = str.Substring(str.Length-5);
            if (sub == "erase")
            {
                return true;
            }
            return false;
        }

        public bool isEraser(string str)
        {
            if (str.Length < 6)
            {
                return false;
            }
            String sub = str.Substring(str.Length-6);
            if (sub == "eraser")
            {
                return true;
            }
            return false;
        }
    }
}


Measured memory_bytes: 29752
#include<bits/stdc++.h>
using namespace std;
 
#define __ ios::sync_with_stdio(0),  cin.tie(0);
#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'
 
typedef long long ll;
 
const int N = 5e5+5, SZ = 720;
int n, q, a[N], cnt[N], dsnct=0;
 
struct Qry
{
  int idx, l, r;
  bool operator<(Qry oth) const { return make_pair(l/SZ, r)<make_pair(oth.l/SZ, oth.r); }
}qry[N];
 
void add(int idx) {
  cnt[a[idx]]++;
  if(cnt[a[idx]]==1)  dsnct++;
}
 
void remove(int idx) {
  cnt[a[idx]]--;
  if(cnt[a[idx]]==0)  dsnct--;
}
 
int get_ans(){
  return dsnct;
}
 
vector<int> mos(){
  sort(qry, qry+q);
  int curl = 0, curr = -1;
  vector<int> ans(q);
  for (int i = 0; i < q; ++i){
    while (curl>qry[i].l){
      curl--;
      add(curl);
    }
    while (curr<qry[i].r){
      curr++;
      add(curr);
    }
    while (curl<qry[i].l){
      remove(curl);
      curl++;
    }
    while (curr>qry[i].r){
      remove(curr);
      curr--;
    }
    ans[qry[i].idx] = get_ans();
  }
  return ans;
}
 
int main(){__
  cin >> n;
  cin >> q;
  for (int i = 0; i < n; ++i){
    cin >> a[i];
  }
  for (int i = 0; i < q; ++i){
    qry[i].idx = i;
    cin >> qry[i].l >> qry[i].r;  qry[i].l--, qry[i].r--;
  }
  vector<int> ans = mos();
  for(int u: ans) {
    printf("%d\n", u);
  }
  return 0;
} 

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

using namespace std;

const int N = 200000 + 77;
int Mod;
int n , dpDown[N] , dpUp[N];
vector < int > a[N];
void dfsDown(int v , int prev = - 1){
   dpDown[v] = 1;
   for(int u : a[v]){
      if(u == prev)
         continue ;
      dfsDown(u , v);
      dpDown[v] = 1ll * dpDown[v] * (dpDown[u] + 1) % Mod;
   }
}
void dfsUp(int v , int prev = - 1){
   for(int t = 0;t < 2;++ t){
      int sum = 1;
      for(int u : a[v]){
         if(u == prev)
            continue ;
         dpUp[u] = 1ll * dpUp[u] * sum % Mod;
         if(t == 1)
            dpUp[u] = (1ll * dpUp[u] * dpUp[v] + 1) % Mod ;
         sum = 1ll * sum * (dpDown[u] + 1) % Mod;
      }
      reverse(a[v].begin() , a[v].end());
   }
   for(int u : a[v]){
      if(u == prev)
         continue ;
      dfsUp(u , v);
   }
}
int main(){
   ios::sync_with_stdio(0);cin.tie(0);
   cin >> n >> Mod;
   for(int v , u , i = 1;i < n;++ i){
      cin >> v >> u;
      a[v].push_back(u);
      a[u].push_back(v);
   }
   dfsDown(1);
   for(int i = 1;i <= n;++ i)
      dpUp[i] = 1;
   dfsUp(1);
   for(int i = 1;i <= n;++ i){
      cout << dpUp[i] * 1ll * dpDown[i] % Mod << '\n';
   }
   return 0;
}


Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
int main()
{
	char c;
	cin >> c;
	if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cout << "vowel" << endl;
	else cout << "consonant" << endl;

	return 0;
}

Measured memory_bytes: 256
// G++ MACRO.CPP -STD=C++17
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#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;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
template <class T = ll>
T IN(){T x;cin>>x;return (x);}
 
template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
  VECCIN(head);
  VT2(move(tail)...);
}
 
template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
  seco[head]=IN();
  VT3(head,move(tail)...);
}
 
#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc
 
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision; // cpp_int
 
#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>
 
#define pb(a) push_back(a)
#define mp make_pair
 
 
int main(){
  CIN(n);VC1(n,a);
  sort(ALL(a));
  SCOUT(a.back());
  
  //ncr = n!/n!(n-r)!

  pair<double,int> ans = mp(INF,0);
  REP(i,n){
    double diff = abs(a[i]*1.0 - 1.0*a.back()/2.0);
    if(ans.first > diff){ans.first = diff;ans.second = a[i];}
  }
  COUT(ans.second);

  return 0;
}

Measured memory_bytes: 1024
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author NikuKyabe
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n)  FOR(i,0,(n))
typedef vector<int> vec;
typedef vector< vector<int> > mat;


class Longest_Common_Subsequence {
public:
	void solve(std::istream& in, std::ostream& out) {
	  int q;
	  in >> q;
	  REP(i, q){
	    string x,y;
	    in >> x >> y;
	    mat dp = mat(x.length()+1, vec(y.length()+1, 0));
	    REP(j,x.length())REP(k,y.length()){
	      if(x[j] == y[k]){
	        dp[j + 1][k + 1] = dp[j][k] + 1;
	      }
	      else{
	        dp[j + 1][k + 1] = max(dp[j][k + 1], dp[j + 1][k]);
	      }
	    }
	    out << dp[x.length()][y.length()] << endl;
	  }
	}
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout << fixed;
	Longest_Common_Subsequence solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}



Measured memory_bytes: 10796
#include <stdio.h>
#include <string.h>

bool nope[105][105];

int main() {
  int n;
  scanf("%d", &n);
  memset(nope, false, sizeof(nope));
  int m = n * (n - 1) / 2;
  for (int i = 1, j = (n % 2 == 0 ? n : n - 1); i < j; i++, j--) {
    nope[i][j] = true;
    nope[j][i] = true;
    m--;
  }
  printf("%d\n", m);
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      if (i != j && !nope[i][j]) {
        printf("%d %d\n", i, j);
      }
    }
  }
  return 0;
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> c(H, vector<char>(W));
    rep(i, H)
    {
        rep(j, W)
        {
            cin >> c[i][j];
        }
    }

    int ans = 0;
    for (int rb = 0; rb < (1 << H); ++rb) {
        for (int cb = 0; cb < (1 << W); ++cb) {
            int cnt = 0;
            for (int row = 0; row < H; row++) {
                for (int col = 0; col < W; col++) {
                    if ((rb >> row) & 1) {
                        continue;
                    } else if ((cb >> col) & 1) {
                        continue;
                    } else {
                        if (c[row][col] == '#') {
                            cnt++;
                        }
                    }
                }
            }
            if (cnt == K) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
n,m,c = map(int, input().split())
b = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
vecprod = [0] * n
for i,ln in enumerate(a):
    s = 0
    for j in range(m):
        s += ln[j] * b[j]
    vecprod[i] = s
vecprod = [1 if x + c > 0 else 0 for x in vecprod]
print(sum(vecprod))

Measured memory_bytes: 9024
n = int(input())
h = list(map(int,input().split()))
dp = [-1 for i in range(n)]

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,n):
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n-1])

Measured memory_bytes: 13980
N = int(input())
A = list(input())
B = list(input())
C = list(input())

d1=0
d2=0
for i in range(N):
    if A[i]==B[i]==C[i]:
        continue
    elif A[i]!=B[i]!=C[i]!=A[i]:
        d2+=1
    else:
        d1+=1
    
print(d1+d2*2)

Measured memory_bytes: 3060
#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()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int n;
    ll  sum = 0;
    cin >> n;
    vector <int> fd(n);
    vector <int> pt(n);
    vector <int> ad(n - 1);
    rep(i, n) {
        cin >> fd.at(i);
    }
    rep(i, n) {
        cin >> pt.at(i);
    }
    rep(i, n - 1) {
        cin >> ad.at(i);
    }
    rep(i, n - 1) {
        sum += pt.at(fd.at(i) - 1);
        if (fd.at(i) + 1 == fd.at(i + 1)) {
            sum += ad.at(fd.at(i) - 1);
        }
        // cout << "sum=" << sum << endl;
    }
    cout << sum + pt.at(fd.at(n - 1) - 1) << endl;




    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int  long long
#define tc(t)  int t; cin>>t; while(t--)
#define f(n)    for(int i=0;i<n;i++)
#define endl   "\n"







int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   int n,k;
   cin>>n>>k;
   vector<int>v(n);
   for(int i=0;i<n;i++) cin>>v[i];
   vector<int> dp(n+1,0);
   dp[0]=0;
   dp[1]=0;
   for(int i=2;i<=n;i++)
   {
       dp[i]=INT_MAX;
       for(int j=i;j>=i-k&&j>0;j--)
       {
           dp[i]=min(abs(v[i-1]-v[j-1])+dp[j],dp[i]);
       }






   }
   
   cout<<dp[n]<<endl;





}

Measured memory_bytes: 4696
#include <stdio.h>

int yu(int x, int y, int *p)
{
	int i;
	
	
	if (x <= y){
		x += y;
		y = x - y;
		x -= y;
	}
	*p = 0;
	while(1){
		
		x = x % y;
		
		x += y;
		y = x - y;
		x -= y;
		
		*p += 1;
		if (y == 0){
			break;
		}
	}
	return (x);
}

int main(void)
{
	int x, y;
	int step;
	
	while(1){
		
		scanf("%d %d", &x, &y);
		
		if (x == 0 && y == 0){
			break;
		}
		
		x = yu(x, y, &step);
		
		printf("%d %d\n", x, step);
		
	}
	
	return (0);
}

Measured memory_bytes: 600
import math

n,d = map(int,input().split())
x=[]
for i in range(n):
    x.append(list(map(int,input().split())))
    
ans = 0
for i in range(n):
    for m in range(i+1,n):
        temp = 0
        for l in range(d):
            temp += (x[i][l]-x[m][l])**2
            
        temp **= 0.5

        if temp%1==0:
            ans += 1
        
print(ans)

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> to(n), cost(n);
    rep(i, n - 1) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        to[a].push_back(b);
        cost[a].push_back(w);
        to[b].push_back(a);
        cost[b].push_back(w);
    }

    vector<int> ans(n, -1);
    queue<int> que;

    ans[0] = 0;
    que.push(0);

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        rep(i, to[v].size()) {
            int u = to[v][i];
            int w = cost[v][i];

            if (ans[u] != -1)
                continue;
            ans[u] = (ans[v] + w) % 2;
            que.push(u);
        }
    }

    rep(i, n) cout << ans[i] << "\n";

    return 0;
}

Measured memory_bytes: 12416