akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    input! {
    a:isize,
    b:isize,
    }
    println!("{}",if a%500<=b {"Yes" }else{"No"})
}

Measured memory_bytes: 2080
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int main(){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if(c >= a && c<= b)
        printf("Yes\n");
    else
        printf("No\n");
    
    
    return 0;
	
}


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

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

//===

const ll mod = static_cast<int>(1e9 + 7);

int binary_search(Vi& vec, int key) {
	int left = -1, right = static_cast<int>(vec.size());
	while (right - left > 1) {
		int mid = (left + right) / 2;
		if (vec[mid] <= key) {
			left = mid;
		}
		else {
			right = mid;
		}
	}
	return left;
}


int main() {
	int H, W;
	cin >> H >> W;
	vector<Vi> obs_h(H);
	vector<Vi> obs_w(W);
	for (int i = 0; i < H; ++i) {
		string s_tmp;
		cin >> s_tmp;
		int len_s_tmp = static_cast<int>(s_tmp.size());
		for (int j = 0; j < len_s_tmp; ++j) {
			if (s_tmp[j] == '#') {
				obs_h[i].push_back(j);
				obs_w[j].push_back(i);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			int pos_h = binary_search(obs_h[i], j);
			int pos_w = binary_search(obs_w[j], i);

			if (pos_h != -1 && pos_w != -1) {
				if (obs_h[i][pos_h] == j && obs_w[j][pos_w] == i) {
					continue;
				}
			}


			int obs_h_l, obs_h_g, obs_w_l, obs_w_g;

			if (pos_h == -1) {
				obs_h_l = -1;
			}
			else {
				obs_h_l = obs_h[i][pos_h];
			}

			if (pos_h == obs_h[i].size() - 1) {
				obs_h_g = W;
			}
			else {
				obs_h_g = obs_h[i][pos_h + 1];
			}

			if (pos_w == -1) {
				obs_w_l = -1;
			}
			else {
				obs_w_l = obs_w[j][pos_w];
			}

			if (pos_w == obs_w[j].size() - 1) {
				obs_w_g = H;
			}
			else {
				obs_w_g = obs_w[j][pos_w + 1];
			}

			int num = (obs_h_g - obs_h_l) + (obs_w_g - obs_w_l) - 3;
			ans = max(ans, num);
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 34304
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main( String[] args ){
		Scanner sc = new Scanner( System.in );
		while( true ){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if( n == 0 && m == 0){ break;}
			int[] tl = new int[ n + m ];
			for( int i = 0; i < n; i++ ){
				tl[ i ] = sc.nextInt();
			}
			for( int i = n; i < n + m; i++ ){
				tl[ i ] = sc.nextInt();
			}
			Arrays.sort( tl );

			int max = 0;
			for( int i = 0; i < tl.length; i++ ){
				int temp = ( i == 0 ) ?  tl[ i ] - 0 : tl[ i ] - tl[ i - 1 ];
				if( max < temp ){ max = temp; }
			}
			System.out.println( max );
		}
	}
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int X[100][100];
int main() {
	int N,D;
	cin>>N>>D;
	rep(i,N)rep(j,D){
		cin>>X[i][j];
	}
	int ans = 0;
	rep(i,N){
		rep(j,N){
			if(i == j)continue;
			int res = 0;
			rep(k,D){
				res += (X[i][k] - X[j][k])*(X[i][k] - X[j][k]);
			}
			double aaa = sqrt(res);
			if(aaa == int(aaa)){
				ans++;
				//cerr<<i<<" "<<j<<endl;
			}
		}
	}
	cout<<ans/2<<endl;
}

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s; cin>>s;
  int l=s.size();
  int ans=0;
  rep(i,l){
    if(i==l/2) break;
    if(s.at(i)!=s.at(l-1-i)) ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
use std::io;

fn main() {
    let n = input();

    let mut i = 1;

    loop {
        let mut x = i;
        if x % 3 == 0 {
            print!(" {}", i);
        } else {
            loop {
                if x % 10 == 3 {
                    print!(" {}", i);
                    break;
                }

                x /= 10;
                if x == 0 {
                    break;
                }
            }
        }

        i += 1;
        if i > n {
            break;
        }
    }

    println!("");
}

fn input() -> i32 {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    s.trim().parse().unwrap()
}



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

void solve()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a * c, a * d, b * c, b * d}) << endl;
}

int main()
{
    // srand((unsigned)time(NULL));
    // int t = clock();
    solve();
    // double et = 1.0 * (clock() - t) / CLOCKS_PER_SEC;
    // printf("Execution Time: %.4lf sec\n", et);
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
//#include <stdio.h>
#include <algorithm>
//#include <tuple>
#include <cmath>
#include <string>
#include <vector>


#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
using namespace std;

int n, a,b, c;
int l[8];


int dfs(int tmp,int x, int y, int z) {
	if (tmp == n) {
		if(min(x,min(y,z))>0)	return abs(a - x) + abs(b - y) + abs(c - z)-30;
		else return 30000000;
	}
	int suj1 = dfs(tmp + 1, x, y, z);
	int suj2 = dfs(tmp + 1, x + l[tmp], y, z)+10;
	int suj3 = dfs(tmp + 1, x, y + l[tmp], z)+10;
	int suj4 = dfs(tmp + 1, x, y, z + l[tmp])+10;
	return min(suj1, min(suj2, min(suj3, suj4)));

}


int main (){
	cin >> n >> a >> b >> c;
	rep(i, n) {
		cin >> l[i];
	}
	
	cout <<dfs(0, 0, 0, 0) <<"\n";

	return 0;
}


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

using namespace std;

int main() {
    long long N;
    cin >> N;

    int factor = 0;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            factor = max(factor, (int) i);
        }
    }

    int res = (int) log10(N / factor) + 1;
    cout << res << endl;
}


Measured memory_bytes: 768
/* Dynamic Programming implementation of LCS problem */
#include<iostream> 
#include<cstring> 
#include<cstdlib> 
using namespace std; 

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
void lcs( string X,string Y, int m, int n ) 
{ 
int L[m+1][n+1]; 

/* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++) 
{ 
	for (int j=0; j<=n; j++) 
	{ 
	if (i == 0 || j == 0) 
		L[i][j] = 0; 
	else if (X[i-1] == Y[j-1]) 
		L[i][j] = L[i-1][j-1] + 1; 
	else
		L[i][j] = max(L[i-1][j], L[i][j-1]); 
	} 
} 

// Following code is used to print LCS 
int index = L[m][n]; 

// Create a character array to store the lcs string 
char lcs[index+1]; 
lcs[index] = '\0'; // Set the terminating character 

// Start from the right-most-bottom-most corner and 
// one by one store characters in lcs[] 
int i = m, j = n; 
while (i > 0 && j > 0) 
{ 
	// If current character in X[] and Y are same, then 
	// current character is part of LCS 
	if (X[i-1] == Y[j-1]) 
	{ 
		lcs[index-1] = X[i-1]; // Put current character in result 
		i--; j--; index--;	 // reduce values of i, j and index 
	} 

	// If not same, then find the larger of two and 
	// go in the direction of larger value 
	else if (L[i-1][j] > L[i][j-1]) 
		i--; 
	else
		j--; 
} 

// Print the lcs 
cout << lcs; 
} 

/* Driver program to test above function */
int main() 
{ 
string X,Y;
cin>>X>>Y;
int m = X.length(); 
int n = Y.length(); 
lcs(X, Y, m, n); 
return 0; 
} 


Measured memory_bytes: 35456
#include <stdio.h>

int main(void){
  int a,b;//左右の柱の埋もれていない部分
  int dif;//
  int height=0;
  int dep;//積雪量
  scanf("%d %d",&a,&b);
  dif=a-b;
  if(dif<0){
    dif=-dif;
  }
  /*低い方の柱の高さを求める*/
  for(int i=0;i<dif;i++){
    height+=i;
  }
  dep=height-a;

  printf("%d",dep);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define mem(a) memset(a,0,sizeof(a))
#define pd(a) printf("%.10f\n",a)
#define pb(a) push_back(a)
#define in(a) insert(a)
#define pi M_PI
#define R cin>>
#define F first
#define S second
#define C class
#define ll long long
#define ln cout<<'\n'
template<C T>void pr(T a){cout<<a;ln;}
template<C T,C T2>void pr(T a,T2 b){cout<<a<<' '<<b;ln;}
template<C T,C T2,C T3>void pr(T a,T2 b,T3 c){cout<<a<<' '<<b<<' '<<c;ln;}
template<C T>void PR(T a,int n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n,m;
  cin >> n >> m;
  bool u[10];
  mem(u);
  rep(i,m) {
    int x;
    R x;
    u[x]=1;
  }
  REP(x,n,100000) {
    string s;
    stringstream ss;
    ss << x;
    ss >> s;
    bool f=1;
    rep(i,s.size()) {
      if(u[s[i]-'0']) f=0;
    }
    if(f) {
      pr(x);
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  Main();return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <cstdlib>
#include <cmath>
#include <functional>

#define INF 1000000000000000000
using namespace std;
typedef long long ll;

int main() {
	ll v[55];
	int n,a,b;
	cin >> n >> a >> b;
	v[n] = 0LL;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v, v + n, greater<ll>());
	ll temp = v[a - 1];
	int min_ = -1, max_ = -1;
	ll sum = 0;
	for (int i = 0; i <= n; i++) {
		if (i < a)sum += v[i];
		if (min_ == -1 && v[i] == temp)min_ = i;
		if (max_ == -1 && v[i] < temp)max_ = i;
	}
	ll ans = 1LL;
	for (int i = 0; i < a - min_; i++) {
		ans *= max_ - min_ - (ll)i;
		ans /= (ll)(i+1);
	}
	if (v[0] == v[a - 1]) {
		for (int j = a + 1; j <= min(b,max_); j++) {
			ll ad = 1LL;
			for (int i = 0; i < j - min_; i++) {
				ad *= max_ - min_ - (ll)i;
				ad /= (ll)(i + 1);
			}
			ans += ad;
		}
	}

	printf("%.10lf\n", (double)sum / (double)(a));
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rfor(i,a,b) for(ll (i) = (a); (i) > (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(a) cout << (a) << endl;
#define all(x) (x).begin(),(x).end()

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

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

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    for (ll d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

vector<bool> used(8,false);
vector<double> x(8),y(8);
int n;
double cnt;

void cntf(int now,int a){
    rep0(i, n){
        if(!used[i]){
            used[i] = true;
            cnt += sqrt((x[now] - x[i]) * (x[now] - x[i]) + (y[now] - y[i]) * (y[now] - y[i])) * factorial(n - a);
            cntf((int)i,a + 1);
            used[i] = false;
        }
    }
    return;
}

int main()
{
    cin >> n;
    rep0(i, n)cin >> x[i] >> y[i];
    cnt = 0;
    rep0(i, n){
        used[i] = true;
        cntf((int)i,2);
        used[i] = false;
    }
    double ans = cnt / factorial(n);
    printf("%.12f\n",ans);
    return 0;
}


Measured memory_bytes: 256
import numpy as np
import sys
sys.setrecursionlimit(100000)
i8 = np.int64
i4 = np.int32


def solve(i, prev, prevc, t, d, ans):
    num = len(t[i])
    x = 1
    if prevc == 1:
        x = 2
    for c in t[i]:
        if c == prev:
            continue
        ans[d[(i, c)]] = x
        num = max(num, solve(c, i, x, t, d, ans))
        x += 1
        if x == prevc:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = {}
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
        d[(a - 1, b - 1)] = count
        d[(b - 1, a - 1)] = count
        count += 1
    num = solve(0, -1, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)

main()

Measured memory_bytes: 100784
#include <iostream>

int main(){
  int r, d, x;
  std::cin >> r >> d >> x;

  int tmp = x;
  for(int i = 0; i < 10; i++){
    int ret = r*tmp - d;
    std::cout << ret << std::endl;
    tmp = ret;
  }

  return 0;
}


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

using namespace std;

int main()
{
	string s;
	cin >> s;

	int n = s.length();

	int ones = 0;
	int zeros = 0;

	for (int i = 0; i < n; i++)
	{
		if (s[i] == '0')
		{
			zeros++;
		}
		else
		{
			ones++;
		}
	}

	cout << min(ones, zeros) * 2 << endl;

}

Measured memory_bytes: 512
//設定言語check
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;

int main(){
  int D, check = 0, count = 0, scoreA = 0, scoreB = 0 ;
  int C[27] ;
  cin >> D ;
  int S[27][D+1], choiceA[D+1] = {}, choiceB[D+1] = {}, history[27] = {} ;
  for(int i=1;i<27;i++){
    cin >> C[i] ;
    history[i] = D ;
  }  
  for(int i=1;i<(D+1);i++){
    for(int j=1;j<27;j++){
      cin >> S[j][i] ;
    }
  }
  for(int date=D;date>0;date--){
    int search = 0, maxi = -1 ;
    for(int i=1;i<27;i++){
      if(maxi <= ( S[i][date] + (history[i] - date) * C[i] ) ){
        search = i ;
        maxi = S[i][date] + (history[i] - date) * C[i] ;
      }
    }
    choiceB[date] = search ;
    history[search] = date ;
  }
  for(int i=1;i<27;i++){
    history[i] = 0 ;
  }
  for(int date=1;date<(D+1);date++){
    int search = 0, maxi = -1 ;
    for(int i=1;i<27;i++){
      if(maxi <= ( S[i][date] + (date - history[i] ) * C[i] ) ){
        search = i ;
        maxi = S[i][date] + (date - history[i] ) * C[i] ;
      }
    }
    choiceA[date] = search ;
    history[search] = date ; 
  }
  for(int i=1;i<27;i++){
    history[i] = 0 ;
  }
  for(int date=1;date<(D+1);date++){
    history[choiceA[date]] = date ;
    scoreA += S[choiceA[date]][date] ;
    for(int i=1;i<27;i++){
      scoreA -= C[i] * ( date - history[i]) ;
    }
  }
  for(int i=1;i<27;i++){
    history[i] = 0 ;
  }
  for(int date=1;date<(D+1);date++){
    history[choiceB[date]] = date ;
    scoreB += S[choiceB[date]][date] ;
    for(int i=1;i<27;i++){
      scoreB -= C[i] * ( date - history[i]) ;
    }
  }
  if(scoreA > scoreB){
    for(int date=1;date<(D+1);date++){
      cout << choiceA[date] << endl ;
    }
  }
  else{
    for(int date=1;date<(D+1);date++){
      cout << choiceB[date] << endl ;
    }
  }
  
  return 0 ;
}  

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

int main(){
	int W,H,x,y,r;
		cin>>W>>H>>x>>y>>r;
	if(x-r<0 || x+r>W) cout<<"No"<<endl;
	else if(y-r<0 || y+r>H) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}

Measured memory_bytes: 1160
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9000000000000000000;
const double PI = acos(-1);

int N, W;
LL v[101], w[101];
LL dp[1010][10101];
int main() {
	cin >> N >> W;
	LL sumv = 0;
	for (int i = 0; i < N; i++) {
		cin >> v[i] >> w[i];
		sumv += v[i];
	}
	for (int i = 0; i < 1010; i++)for (int j = 0; j < 10101; j++)dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= sumv; j++) {
			if (v[i] > j)dp[i + 1][j] = dp[i][j];
			else dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
		}
	}
	
	for (int i = sumv;i>=0; i--) {
		if (dp[N][i] <= W) {
			cout << i << endl;
			break;
		}
	}
}

Measured memory_bytes: 82820
fun main(args: Array<String>) {
    var k = readLine()!!.toInt()
    var c = mutableMapOf<Int, Int>()
    var v:Int
    var num: Int
    for (i in 1..k) {
        for (j in 1..k) {
            v = gcd(i, j)
            num = c.getOrPut(v, {0})
            c[v] = num + 1 
        }
    }
    var ans = 0L
    for ((x, y) in c){
        for (i in 1..k) {
            ans += gcd(i, x)*y
        }
    }
    println(ans)
}

tailrec fun gcd(a:Int, b:Int):Int {
    if (b==0) {
        return a
    }
    return gcd(b, a%b)
}


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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  rep(i, N) {
    int l, r;
    cin >> l >> r;
    sum += r - l + 1;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#UnionFind木とそれを利用したクラスカル法
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

    def nums(self,x):
        return abs(self.parents[self.find(x)])

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
edge = []
A.sort()
for i in range(N-1):
    w = A[i+1][0]-A[i][0]
    edge.append((w,A[i][2],A[i+1][2]))
A.sort(key=lambda x:x[1])
for i in range(N-1):
    w = A[i+1][1]-A[i][1]
    edge.append((w,A[i][2],A[i+1][2]))

edge.sort()

uf = UnionFind(N)
ans = 0
for i in range(len(edge)):
    u,x,y = edge[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Measured memory_bytes: 48148
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<double> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  sort(v.begin(),v.end());
  double ans=(v[0]+v[1])/2;
  for(int i=2;i<n;i++){
    ans+=v[i];
    ans/=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

for _ in range(K):
    flg = True
    imos = [0]*(N+1)
    for i in range(N):
        imos[max(0, i-A[i])] += 1
        imos[min(N, i+A[i]+1)] -= 1
    A = [0]*N
    c = 0
    for i in range(N):
        c += imos[i]
        A[i] = c
        if c != N:
            flg = False
    if flg is True:
        print(*([N]*N), sep=' ')
        exit()


print(*A)


Measured memory_bytes: 221252
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x <= 1) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
ll h,n,x,sum;
int main(){
 	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> n;
	for(int i = 0;i < n;i++){
		cin >> x;
		sum += x;
	}
	if(sum >= h) cout << "Yes" << endl;
	else cout << "No" << endl;
 	return 0;
}
//do smt instead of nothing! never give up!
//take care of long long!
//take care of upper or lower case e.g "yes" or "YES"?
//boundary condition! e.g. n = 0?
//brute force is always the first choice!
// print the ans to look for patterns in the data!

Measured memory_bytes: 256
import fractions


def main():
    A, B = map(int, input().split())
    n = fractions.gcd(A, B)
    print(num_prime_factor(n))

def num_prime_factor(n):
    
    if n == 1:
        return 1
    
    ret = 1
    cursor = 2
    if n % cursor == 0:
        ret += 1
        n = n // cursor
        while n % cursor == 0:
            n = n // cursor
    
    cursor = 3
    while cursor**2 <= n:
        if n == 1:
            break
        if n % cursor == 0:
            ret += 1
            while n % cursor == 0:
                n = n // cursor
        cursor += 2

    if n != 1:
        ret += 1
        
    return ret

if __name__ == "__main__":
    main()

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

typedef long long lint;
typedef long double louble;

#define lf ('\n')

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}

	template<typename T> inline int ts(T *s)
	{
		int a=0,c=fetch();
		while(c<=32 && c!=EOF)c=fetch();
		while(c>32 && c!=EOF)s[a++]=c,c=fetch();
		s[a]=0;
		return a;
	}
}
using ae86::ty;
using ae86::ts;

const int _ = 100007 , mo = 1000000007;

int n,val[_],las[3]={0,-1,-1};
lint f[_]={0};

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);
	
	n=ts(val+1);
	for(int i=1;i<=n;i++)val[i]-='a'-1;
	
	int able=0;
	for(int i=1;i<n;i++)if(val[i]==val[i+1])able=1;
	if(!able){cout<<1<<lf;return 0;}

	f[0]=1;
	for(int i=1,now=0;i<=n;i++)
	{
		now=(now+val[i])%3;
		if(now==0 && i<n)f[i]=1;
		now=(now+1)%3;if(las[now]>=0)f[i]=(f[i]+f[las[now]])%mo;
		now=(now+1)%3;if(las[now]>=0)f[i]=(f[i]+f[las[now]])%mo;
		now=(now+1)%3,las[now]=i;
	}
	cout<<f[n]<<lf;

	return 0;
}


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

int main(){
int n;
cin>>n;
double ans=0;
for(int i=0;i<n;i++){
double amount=0;
string s;
cin>>amount>>s;
if(s=="JPY"){
ans=ans+amount;}
else{
ans=ans+(amount*380000.000);}}
cout<<ans;
return 0;}

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

namespace AtCoders {
	class Program {
		static void Main(string[] args) {

		var inputArray = retreiveLongArray();
			var inputCount = 3;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			var x = inputArray[0];
			var y = inputArray[1];
			var z = inputArray[2];


			//答えの出力
			Console.WriteLine($"{z} {x} {y}");

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray =  Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 13396
#include<iostream>
#include<string>
#include<algorithm>
using namespace std; 
int main(void){ 
	string S;
	cin >> S;
	string front,back,C;
	int Q,T,F,top;
	top = 1;
	cin >> Q;
	for(int i=0;i<Q;i++){
		cin >> T;
		if(T == 1){
			top *=-1;
		}else{
			cin >> F;
			cin >> C;
			if(F == 1){
				if(top == 1){
					front = C + front;
				}else{
					back = back + C;
				}
			}else{
				if(top == 1){
					back = back + C;
				}else{
					front = C + front;
				}
			}
		}
	}
	if(top == 1){
		cout << front << S << back;
	}else{
		reverse(front.begin(),front.end());
		reverse(back.begin(),back.end());
		reverse(S.begin(),S.end());
		cout << back << S << front;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
typedef pair<int,int>   ii;
typedef vector<int>     vi;
typedef set<int>        si;

template<typename T> T sgn (T x)      {return x<0? -1:x!=0; }
template<typename T> T gcd (T a, T b) {return a ? gcd (b % a, a) : b; }
//pi=acos(-1)
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define clr(x,v) memset(x,v,sizeof x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define popcount __builtin_popcount
#define eb emplace_back
#define emp emplace
#define ss second
#define ff first
#define MOD ((int)1e9+7)
#define N ((int)2e5+123)
void reads(string& x){ char kk[N]; scanf("%s",kk); x = kk;}

int ans;
int n, m;
int v[N];

void solve(){
    scanf("%d %d", &n, &m);
    
    printf("%d\n",n*m);
}

int main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;//canf("%d",&t);
    while(t--)solve();
}

Measured memory_bytes: 3836
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<int> in(3, 0); cin >> in[0] >> in[1] >> in[2];
    sort(in.begin(), in.end());
    printf("%d\n", (in[1] - in[0]) + (in[2] - in[1]));
}

Measured memory_bytes: 3708
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
A = LIST()

n = max(A+[K]).bit_length()
cnt = [[0, 0] for _ in range(n)]

for a in A:
	b = "{:b}".format(a).zfill(n)[::-1]
	for i in range(n):
		cnt[i][int(b[i])] += 1

max_X = []
for cnt_0, cnt_1 in cnt:
	if cnt_0 <= cnt_1:
		max_X.append(0)
	else:
		max_X.append(1)
max_X = max_X[::-1]     #Aのリストのみから算出た最大Xの2進数表記

k = "{:b}".format(K).zfill(n)

if len(k) == n:
	for i in range(n):
		if int(k[i]) > max_X[i]:
			break
		elif int(k[i]) < max_X[i]:
			max_X[i] = 0

X = 0
for i, p in enumerate(max_X[::-1]):
	X += 2**i*p

#print(X)
ans = 0
for a in A:
	ans += a^X

print(ans)


Measured memory_bytes: 93412
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<math.h>
#include<string>
#include<utility>
#include<queue>
#include<stdlib.h>
#define FOR(i,a,b,c) for(int i=a;i<b;i+=c)
using namespace std;
typedef pair<int, int> P;
int main() {
	int n, s[10001], t[501], q, ans = 0, fi = 0;
	cin >> n;
	FOR(i, 0, n, 1)cin >> s[i];
	sort(s, s + n);
	cin >> q;
	FOR(i, 0, q, 1)cin >> t[i];
	FOR(i, 0, q, 1) {
		if (*lower_bound(s, s + n, t[i]) == t[i]) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


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

int N, L;

int main() {
  cin >> N >> L;
  int last = -1;
  int prev_a;
  for(int i = 0; i < N; ++i) {
    int a; cin >> a;
    if(i > 0 && a + prev_a >= L) last = i - 1;
    prev_a = a;
  }
  if(last < 0) cout << "Impossible" << endl;
  else {
    cout << "Possible" << endl;
    for(int i = 0; i < last; ++i) cout << i + 1 << endl;
    for(int i = N - 2; i > last; --i) cout << i + 1 << endl;
    cout << last + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 768
n=int(input())
word=[]
for i in range(n):
    word.append(str(input()))

count=0

for i in range(n-1):
    if word[i][-1] != word[i+1][0]:
        count += 1

if len(set(word)) != len(word):
    count += 1

if count==0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int dp[1000009],arr[109];
int main()
{ memset(dp,0,sizeof(dp));

    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    sort(arr,arr+n);
     for(int i=1;i<=n;i++)
        dp[arr[i]]=1;
        dp[0]=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i>=arr[j])
                {if(!dp[i-arr[j]])
                  dp[i]=1;}


        }
    }
    if(dp[k]==1)
        cout<<"First\n";
    else
        cout<<"Second"<<endl;
}


Measured memory_bytes: 4096
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[200005],mid;
long long sum;
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		a[i]-=i;
	}
	sort(a,a+n);
	mid=a[n/2];
	for(int i=0;i<n;i++)sum+=abs(a[i]-mid);
	printf("%lld",sum);
}

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

int main() {
    int a,b,h,m;
    cin >> a >> b >> h >> m;
    
    double radH,radM,rad;
    radM =  2 * pi * (double)m / 60;
    radH =  2 * pi / 12 * (radM / pi / 2 + (double)h );
    
    rad = abs(radH-radM);
    double ans;
    //cout << "h=" << radH/pi << "m=" << radM/pi << "rad=" << rad/pi << " cos" << cos(rad)<< endl;
 
    //cout << "h" << radH  << endl << "m" << radM << endl <<  "rad" << rad << endl;
    ans = (double)a*(double)a + (double)b*(double)b - 2*(double)a*(double)b*cos(rad);
    //cout << cos(rad);
    //cout <<(double)a*(double)a + (double)b*(double)b << endl << 2*(double)a*(double)b*cos(rad) << endl;
    ans = pow(ans,0.5);
    printf("%.12f\n",ans);
    return 0;
}


Measured memory_bytes: 4212
def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	m = sum(a)
	ans = float('inf')
	r = 0
	for i in range(n-1, 0, -1):
		r += a[i]
		ans = min(ans, abs(m - 2*r))
	print(ans)
resolve()

Measured memory_bytes: 76752
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


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

    if(a == 'H'){
        if(b == 'H'){
            cout << 'H' << endl;
        }else{
            cout << 'D' << endl;
        }
    }else{
        if(b == 'D'){
            cout << 'H' << endl;
        }else{
            cout << 'D' << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(int i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define wi(t) int t;cin>>t;while(t--)
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int mpow(int base, int exp); 
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

void solve()
    {
     ll int n,k;
     cin>>n>>k;
      if(n>=1&&n<=9&&k>=1&&k<=9)
      cout<<n*k<<endl;
      else
      {
          cout<<"-1"<<endl;
      }
      

  
  
  
  
    }

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

 //   wi(t)
    {
      solve();
    }

    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
    u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}







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

typedef long long int ll;
int main() {
    int n;
    cin>>n;
    vector<pair<ll,ll>> v;
    for(int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        v.push_back(make_pair(a,b));
    }
    int min=INT_MAX;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int p=v[j].first-v[i].first;
            int q=v[j].second-v[i].second;
            int count=0;
            // int arr[n];
            // for(int k=0;k<n;k++){
            //     arr[k]=0
            // }
            for(int k=0;k<n;k++){
                int l=0;
                for(l=0;l<n;l++){
                    if(v[k].first-v[l].first==p && v[k].second-v[l].second==q && l!=k){
                        break;
                    }
                }
                if(l==n) count++;
            }
            if(count<min) min=count;
            // cout<<count<<"c";
        }
    }
    cout<<min;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    int n,m;
    cin>>n>>m;
    ll ans = 0;
    if (n >= 2 && m >= 2)
    	cout << 1ll * (n - 2) * (m - 2) << '\n';
    else
    if (n == 1 && m >= 2)
    	cout << (m - 2) << '\n';
    else
   	if (m == 1 && n >= 2)
   		cout << (n - 2) << '\n';
   	else
   		cout << "1\n";
    return 0;
}

Measured memory_bytes: 256
args = []
while line = gets do
  a, b, c, d, e, f = line.split.map(&:to_f)
  y = (a * f - d * c) / (a * e - d * b)
  x = (c - b * y) / a
  puts "#{sprintf("%.3f", x)} #{sprintf("%.3f", y)}"
end

Measured memory_bytes: 6128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <ctype.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
const int inf{ int(1e9) };

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


	int ans = {inf};
	rep(i, n) {
		int c, t; cin >> c >> t;
		if (t <= T && c < ans) {
			 ans = c;
		}
	}
	if (ans != inf) {
		cout << ans << endl;
	}
	else {
		cout << "TLE" << endl;
	}
}


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

#define RV reverse
#define NP next_permutation
#define SZ(v) static_cast<LL>(v.size())
#define UQ(v) v.erase(unique(ALL(v)), v.end())
template<typename T> class RPQ : public PQ<T, vector<T>, greater<T>> { };
template<typename T> T mod(T x, T y) { return (x % y + y) % y; }
template<typename T> T setmod(T & x, T y) { return ((x %= y) += y) %= y; }
template<typename T> T fl(T x, T y) { return x / y; }
template<typename T> T ce(T x, T y) { return (x + y - 1) / y; }

LL n;

int main() {
	cin >> n;
	if(n % 2 == 0) {
		cout << n / 2 << " " << n << " " << n << endl;
		return 0;
	}
	
	inc1(i, 3500) {
	inc1(j, 3500) {
		LL d = (4 * i * j - n * (i + j));
		if(d != 0) {
			LL m = n * i * j % d;
			LL k = n * i * j / d;
			if(m == 0 && k > 0) {
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}
	}
	assert(false);
}


Measured memory_bytes: 256
n = int(input())
t = 1; a = 1;
for _ in range(n):
    ti,ai = map(int,input().split())
    if t%ti != 0 : t = (t//ti+1)*ti
    if a%ai != 0 : a = (a//ai+1)*ai
    r = max(t//ti,a//ai)
    t = ti*r
    a = ai*r

print(a+t)


Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
using namespace std;
int n,Ans,a[100005];
int get ()
{
	bool f=0; int x; char ch;
	while (!isdigit (ch=getchar ())) if (ch=='-') f=1; x=ch-48;
	while (isdigit (ch=getchar ())) x=(x<<1)+(x<<3)+ch-48;
	return f?-x:x;
}
int main ()
{
	n=get ();
	for (int i=1;i<=n;++i) a[i]=get ();
	for (int i=1;i<=n;++i)
	{
		if (a[i]==i)
		{
			++Ans;
			if (a[i+1]==i+1) ++i;
		}
	}
	cout<<Ans<<endl;
	return 0;
}


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

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

    long long int value[n],weight[n];

    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
    }
    
    long long int dp[n+1][wt+1];
    memset(dp,0,sizeof(dp));

    for(int i=0;i<=n;i++){
        for(int w=0;w<=wt;w++){
            if(w==0 || i==0){
                dp[i][w]=0;
            }
            else if(weight[i-1]<=w){
                dp[i][w]=max(value[i-1]+dp[i-1][w-weight[i-1]],dp[i-1][w]);
            }
            else{
                dp[i][w]=dp[i-1][w];
            }
        }
    }
    cout<<dp[n][wt]<<endl;

}

Measured memory_bytes: 79104
h,w = map(int,input().split())
if w == 1 or h == 1:
    ans = 1
    
else:
    if h % 2 ==0:
        tate = h // 2
        ans = tate * w
    else:
        tate = h // 2 + 1
        if w % 2 == 0:
            ans = (2 * tate - 1) * (w // 2)
        else:
            ans = (2 * tate - 1) * (w // 2) + tate
print(ans)

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


int main() {
  ll n, k, q, tmp;
  cin >> n >> k >> q;
  vector<int>a(n);
  rep(i,n) a[i] = (k-q);
  rep(i,q) {
    cin >> tmp;
    tmp--;
    a[tmp]++;
  }
  
  rep(i,n) {
    if(a[i]<=0) {
      cout << "No" << endl;
    }else {
      cout << "Yes" << endl;
    }
  }
  return 0;
}
  
  
  
  

Measured memory_bytes: 1024
# ダイクストラ法の練習に．
from heapq import heapify, heappop, heappush


def main():
    vertex, edge, root = map(int, input().split())
    max_val = 10 ** 10
    graph = [[] for _ in range(vertex)]
    for _ in range(edge):
        s, t, d = map(int, input().split())
        graph[s].append((t, d))
    dist = [max_val for _ in range(vertex)]
    dist[root] = 0
    q = []
    heapify(q)
    heappush(q, (0, root))
    while q:
        now_d, now_v = heappop(q)
        for next_v, length in graph[now_v]:
            now_dist = dist[now_v] + length
            if dist[next_v] > now_dist:
                dist[next_v] = now_dist
                heappush(q, (dist[next_v], next_v))

    for d in dist:
        print("INF" if d == max_val else d)


if __name__ == '__main__':
    main()




Measured memory_bytes: 89280
A, B, C = map(int, input().split())
M = max([A, B, C])


if (3*M) % 2 == (A+B+C) % 2:
    print((3 * M - A - B - C) // 2)
else:
    print((3 * (M+1) - A - B - C) // 2)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans,n,i;
    cin>>n;
    int a[n-1];
    for(i=0;i<n-1;i++) cin>>a[i];
    ans=a[0]+a[n-2];
    for(i=0;i<n-2;i++)
        ans += min(a[i],a[i+1]);

    cout<<ans;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N)]

AB.sort(key=lambda x: x[0])
ans = 0
for i in range(N):
    if M >= AB[i][1]:
        ans += AB[i][0] * AB[i][1]
        M -= AB[i][1]
    else:
        ans += AB[i][0] * M
        M = 0
    if M == 0:
        break
print(ans)


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

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> p(n);
  for(int i=0;i<n;i++){
    cin >> p.at(i);
  }
  sort(p.begin(),p.end());
  int sum=0;
  for(int i=0;i<k;i++){
    sum+=p.at(i);
  }
  cout << sum << endl;
}


Measured memory_bytes: 3692
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            args = reader.readLine().split(" ");
            int A = Integer.parseInt(args[0]);
            int B = Integer.parseInt(args[1]);

            int ans = Math.max(A - B * 2, 0);

            System.out.println(ans);
        }
    }

}


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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pll = P<LL,LL>;
using Pdd = P<double,double>;
using Psi = P<string,double>;

template<typename T>
T SUM(V<T> v, T init_val=0){return accumulate(ALL(v),T(init_val));}

template<typename T>
T MAX(V<T> v){return *max_element(ALL(v));}

struct unionFind{
    private:
        Vi data;
        int set_num;
    public:
        unionFind(int size) : data(size,-1){ set_num = size;}
        bool unionSet(int x,int y){
            x=root(x);y=root(y);
            if(x!=y){
                if(data[y]<data[x]){swap(x,y);}
                data[x]+=data[y]; data[y]=x;
                set_num--;
            }
            return x!=y;
        }
        bool findSet(int x,int y){ return root(x)==root(y);}
        int root(int x){return ((data[x]<0)?x:(data[x]=root(data[x])));}
        int size(int x){return -data[root(x)];}
        int set_size(){return set_num;}
};

int main(){
    int n,m;
    cin>>n>>m;
    Vi x(m);
    REP(i,m) cin>>x[i];

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

    sort(ALL(x));

    V<P<int,Pii>> diffs;
    REP(i,m-1){
        diffs.pb(mp(x[i+1]-x[i],mp(i,i+1)));
    }
    sort(ALL(diffs));

    unionFind U(m);
    REP(i,diffs.size()){
        U.unionSet(diffs[i].se.fi,diffs[i].se.se);
        if(U.set_size() == n){
            LL total = 0;
            REP(j,m-1){
                if(U.findSet(j,j+1)){
                    total += x[j+1]-x[j];
                }
            }
            cout<<total<<endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 2296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  string o, e;
  cin >> o >> e;
  ll n = o.size() + e.size();
  for (ll i = 0; i < n; i++) {
    if (i % 2 == 0) cout << o[i / 2];
    else cout << e[i / 2];
  }
  cout << endl;
}


Measured memory_bytes: 256
import bisect
from array import array


def slow_solve(N, As):
    colors = []
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.append(a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i-1] = a
        colors.sort()
        print(colors)
    return len(colors)


def solve(N, As):
    colors = array('I', [])
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.insert(0, a)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i - 1] = a
                j = i - 1
                while j + 1 < len(colors) and colors[j] > colors[j + 1]:
                    colors[j], colors[j + 1] = colors[j + 1], colors[j]
                    j += 1
        # print(colors)
    return len(colors)

#
# for _ in range(100):
#     import random
#     N = 10
#     As = [random.randint(1, 10) for _ in range(5)]
#     if slow_solve(N, As) != solve(N, As):
#         print("OUT")
#         print(N)
#         print(As)
#         input()
# print("OK")

if __name__ == "__main__":
    N = int(input())
    As = []
    [As.append(int(input())) for i in range(N)]
    print(solve(N, As))


Measured memory_bytes: 7840