akhauriyash/Code-Regression huggingface dataset:
// D - Cake 123

// 解説pdfの解法 #4

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

ll X, Y, Z, K;
ll A[1000], B[1000], C[1000];

// 美味しさの合計がP以上である個数がK個以上あるかどうかを判定
bool is_ok(ll P) {
	int cnt = 0;
	for (int i=0; i<X; i++) {
		for (int j=0; j<Y; j++) {
			for (int k=0; k<Z; k++) {
				if (A[i] + B[j] + C[k] < P) break;
				cnt++;
				if (cnt >= K) return true;
			}
		}
	}

	return false;
}

ll find_max_ok(ll lower, ll upper) {
	if (!is_ok(lower)) return -1; // 存在しない

	ll ok = lower;
	ll ng = upper;

	while(ng - ok > 1) {
		ll trying = (ng + ok) / 2;

		if (is_ok(trying)) {
			ok = trying;
		} else {
			ng = trying;
		}
	}

	return ok;
}

int main() {
	cin >> X >> Y >> Z >> K;

	for (int i=0; i<X; i++) {
		cin >> A[i];
	}
	sort(A, A+X, greater<ll>());

	for (int i=0; i<Y; i++) {
		cin >> B[i];
	}
	sort(B, B+Y, greater<ll>());

	for (int i=0; i<Z; i++) {
		cin >> C[i];
	}
	sort(C, C+Z, greater<ll>());

	ll P = find_max_ok(0, INF); // 美味しさがP以上のものがK個までに含まれる

	vector<ll> ans;
	int cnt = 0;
	for (int i=0; i<X; i++) {
		for (int j=0; j<Y; j++) {
			for (int k=0; k<Z; k++) {
				if (A[i] + B[j] + C[k] < P + 1) break;
				ans.push_back(A[i] + B[j] + C[k]);
				cnt++;
			}
		}
	}

	sort(ans.begin(), ans.end(), greater<ll>());

	for (int i=0; i<K; i++) {
		if (i < cnt) cout << ans[i] << endl;
		else cout << P << endl;
	}

	return 0;
}

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

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

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N;
    cin >> N;
    vector<ll> a(N);
    for (int i=0; i<N; ++i) cin >> a[i];

    ll res = 1000;
    for (int i=0; i<N-1; ++i) {
        if (a[i] < a[i+1]) {
            res = a[i+1] * (res / a[i]) + res % a[i];
        }
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int H,W;

i64 c[10][10];

int main() {
  cin >> H >> W;
  rep(i,0,9) rep(j,0,9) cin >> c[i][j];
  rep(k,0,9) rep(i,0,9) rep(j,0,9) c[i][j] = min(c[i][j] , c[i][k] + c[k][j]);
  i64 ans = 0;
  rep(i,0,H * W - 1) {
    int a;
    cin >> a;
    if(a == -1) continue;
    ans += c[a][1];
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cctype>
#include<string>
#include<cmath>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(a==b) cout<<c<<endl;
	if(a==c) cout<<b<<endl;
	if(b==c) cout<<a<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
const int INF = 1 << 20;

typedef long long ll;




int main(){
  int n;
  cin >> n;
  int d,x;
  int sum = 0;
  cin >> d >> x;
  REP(i,n){
    //sum += 1;
    int a;
    cin >> a;
    for(int j = 1;j <= d;j = j+a){
      sum++;
    }
  }
  cout << sum+x << endl;
  return 0;
}


Measured memory_bytes: 256
import Data.List

main = do
    _ <- getLine
    as <- map read . words <$> getLine
    print $ solve as

solve :: [Int] -> Int
solve xs = let (x':xs') = sort xs
               (y:ys) = x':(map (`mod` x') xs')
               in if all (==0) ys then y
                                  else solve . filter (/= 0) $ (y:ys)

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

int main() {
	set<string> gacha;
	int count = 1;
	int N;
	cin >> N;
	while (count <= N) {
		string s;
		cin >> s;
		gacha.insert(s);
		count++;
	}
	cout << gacha.size();

	return 0;
}

Measured memory_bytes: 15620
#include<bits/stdc++.h>
//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<cstdlib>
//#include<cmath>
//#include<algorithm>
//#include<vector>
//#include<queue>
//#include<stack>
//#include<map>
//#include<set>
using namespace std;
#define SC scanf
#define PR printf
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define db double
#define ldb long double
#define uint unsigned
#define ll long long
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef pair<pii,pii> ppp;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef map<int,int> mii;
const int INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
int inline in(){
	int x=0,c;
	for(;(uint)((c=getchar())-'0')>=10;){
		if(c=='-')return -in();
		if(!~c)throw ~0;
	}
	do{
		x=(x<<3)+(x<<1)+(c-'0');
	}while((uint)((c=getchar())-'0')<10);
	return x;
}
ll a[100005],b[100005];
int main(){
    cin.sync_with_stdio(false);cin.tie(0);
    int n;
	cin>>n;
	rep(i,n+1)cin>>a[i];
	rep(i,n)cin>>b[i];
	ll ans=0;
	ll tmp;
	rep(i,n){
		tmp=min(a[i],b[i]);
		ans+=tmp;
		a[i]-=tmp;
		b[i]-=tmp;
		tmp=min(a[i+1],b[i]);
		ans+=tmp;
		a[i+1]-=tmp;
		b[i]-=tmp;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A+B > C+D)
    cout << "Left" << endl;
  else if (A+B == C+D)
    cout << "Balanced" << endl;
  else
    cout << "Right" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll N;
ll A[200010];

int main(){
	cin >> N;
	bool judge = true;
	for(int i=0;i<N;i++){
		cin >> A[i];
		if(A[i]>i) judge = false;
		if(i>=1){
			if(A[i]-A[i-1]>=2) judge = false;
		}
	}
	if(!judge){
		cout << -1 << endl;
		return 0;
	}
	ll ans = 0;
	for(int i=1;i<N;i++){
		if(A[i]-A[i-1]==1) ans++;
		else ans += A[i];
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
n,m = map(int,input().split())
h = list(map(int,input().split()))
ans = [1]*n
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if h[a] <= h[b]:
        ans[a] = 0
    if h[b] <= h[a]:
        ans[b] = 0
print(sum(ans))

Measured memory_bytes: 20120
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e9+7;


int main() {
    ll n;
    cin >> n;
    vector<ll> a(10001);
    for(ll i=1;i<=100;i++){
        for(ll j=1;j<=100;j++){
            for(ll k=1;k<=100;k++){
                ll v=i*i+j*j+k*k+i*j+j*k+k*i;
                if(v<=10000) a[v]++;
            }
        }
    }
    for(ll i=1;i<=n;i++){
        cout << a[i] << endl;
    }
    return 0;
}

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

vector<pair<long long, long long>> prime_factorize(long long n) {
    vector<pair< long long, long long >> res;
     for (long long p = 2; p*p <= n; ++p) {
        if (n%p != 0) continue;
        int num = 0 ;
        while (n%p == 0 ) {++num; n /= p;}
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair (n, 1));
     return res;
}

int main () {
    long long N;
    cin >> N;
    auto pf = prime_factorize (N);
    long  long res = 0 ;
    for (auto p : pf) {
        long long e = p.second;
        long long tmp = 0, cur = 1;
        while (e >= cur) e -= cur++, ++tmp;
        res += tmp;
    }
    cout << res << "\n";
}

Measured memory_bytes: 3592
use proconio::input;

fn main() {
    input! {
        string: String,
        model: String
    }

    let string_len = string.chars().count();
    let model_len = model.chars().count();

    let mut result = model_len;

    let limit = string_len - model_len;
    let mut current_index = 0;

    loop {
        let current = match string.get(current_index..current_index + model_len) {
            Some(c) => c,
            None => break
        };

        // println!("{}", current);

        let diff = model
            .chars()
            .zip(current.chars())
            .filter(|(a, b)| a != b)
            .count();

        // println!("current: {}, diff: {}, re: {} ", current, diff, result);

        result = result.min(diff);
        if result == 0 {
            break;
        }

        current_index += 1;
        if current_index == limit {
            break;
        }
    }

    println!("{}", result);
}


Measured memory_bytes: 2196
N = gets.to_i
A = gets.split.map(&:to_i)
B = A.map.with_index(1) { |a, i| a - i }.sort

b = B[N / 2]

ans = 0

A.each.with_index(1) do |a, i|
  ans += (a - i - b).abs
end

puts ans



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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void()
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  vector<int> cnt_w(n), cnt_e(n);
  for (int i = 0; i < n; i++) {
    if (i != 0) {
      cnt_w[i] = cnt_w[i - 1];
      cnt_e[i] = cnt_e[i - 1];
    }
    if (s[i] == 'W') {
      cnt_w[i]++;
    } else {
      cnt_e[i]++;
    }
  }
  int ans = (int)1e9;
  debug(cnt_w, cnt_e);
  for (int i = 0; i < n; i++) {
    if (i == 0) {
      ans = min(ans, cnt_e[n - 1] - cnt_e[i]);
    } else {
      ans = min(ans, cnt_w[i - 1] + cnt_e[n - 1] - cnt_e[i]);
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 6120
n, m = map(int, input().split())
route = {i + 1 : [] for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
if set(route[1]) & set(route[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 104416
#include<bits/stdc++.h>
#include<queue>
using namespace std;
vector<queue<int>>gra;
vector<int>dp;
vector<int>si;
int path(int x) {
  int &ret = dp[x];
  if (ret != -1) return ret;
  ret = 0;
  for (int i = 0; i < si[x]; i ++) {
    int y = gra[x].front();
    gra[x].pop();
    if (ret < path(y) + 1) ret = path(y) + 1;
    gra[x].push(y);
  }
  return ret;
}
int main () {
  int N;
  cin >> N;
  gra.resize(N + 1);
  dp.assign(N + 1, -1);
  si.assign(N + 1, 0);
  int M;
  cin >> M;
  for (int i = 0; i < M; i ++) {
    int x, y;
    cin >> x >> y;
    gra[x].push(y);
    si[x] ++;
  }
  int ans = 0;
  for (int i = 1; i <= N; i ++) {
    if (ans < path(i)) ans = path(i);
  }
  cout << ans << endl;
}


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

using namespace std;

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

    vector<long long> participant(3 * n);

    for (long long &strength : participant)
        cin >> strength;

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

    long long answer = 0;
    for (int i = 0; i < n; i++)
        answer += participant[2 * i + 1];

    cout << answer << endl;
    
    return 0;
}

Measured memory_bytes: 5556
#include<iostream>
#include <climits>
#include<cstdio>
using namespace std;

const int MAX = 2 * 100000;
long long count=0;
int a[MAX];


void Merge(int a[],int l,int mid,int r){
  int n1 = mid - l+1,n2 = r-mid;
  int L[n1+1],R[n2+1];
  for(int i=0;i<n1;i++){
    L[i]=a[l+i];
  }
  for(int i=0;i<n2;i++){
    R[i]=a[mid+i+1];
  }
  L[n1]=R[n2]=INT_MAX;
  int pr =0,pl = 0;
  for(int i=l;i<r+1;i++){
    if ( L[pl] <= R[pr]){
      a[i]=L[pl++];
    }
    else if (L[pl]>R[pr]){
      ::count+=n1-pl;
      //cout << R[pr] << endl;
      a[i]=R[pr++];
    }
  }
  
}

void MergeSort(int a[],int l,int r){
  if (l < r){
    int q = (r+l)/2;
    MergeSort(a,l,q);
    MergeSort(a,q+1,r);
    Merge(a,l,q,r);
  }

}

int main(){
  string in;
  cin >> in;
  int n = in.size();
  long long ans=  0;
  int bcnt = 0;
  for(int i = 0;i < n;i++){
    if (in[i] == 'W'){
      ans += bcnt;
    } else if (in[i] == 'B'){
      bcnt++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 644
#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>;

ll dp[105][2][105];

int main(){
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();

    dp[0][0][0] = 1;
    rep(i,n) rep(j,n){
        dp[i+1][1][j+1] += dp[i][1][j] * 9;
        dp[i+1][1][j] += dp[i][1][j];

        int ni = (s[i] - '0');

        if(ni > 0){
            dp[i+1][1][j+1] += dp[i][0][j] * (ni - 1);
            dp[i+1][1][j] += dp[i][0][j];
        }
        
        if(ni > 0){
            dp[i+1][0][j+1] = dp[i][0][j];
        }
        else{
            dp[i+1][0][j] = dp[i][0][j];
        }
    }

    ll ans = dp[n][0][k] + dp[n][1][k];
    cout << ans << endl;
}

Measured memory_bytes: 3696
Module _20191029

    Sub Main()
        'https://atcoder.jp/contests/abc144/tasks/abc144_b

        Dim sRead As Integer = CInt(Console.ReadLine())

        Dim isYes As Boolean = False

        For i As Integer = 1 To 9

            If sRead Mod i = 0 AndAlso sRead \ i > 0 AndAlso sRead \ i < 10 Then

                isYes = True

            End If

        Next

        If isYes = True Then

            Console.WriteLine("Yes")

        Else

            Console.WriteLine("No")

        End If

    End Sub

End Module

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

const int inf=1000000007;
const int MOD=1000000007;
const long long INF=1000000000000000007;


int main() {
  int n;
  cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    string is = to_string(i);
    if (is.length() % 2 == 1) {
      ans++;
    }
  }

  cout << ans << endl;
}


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

int main(){
    string s;
    cin >> s;
    int c = 0;
    for(int i = 0; i < s.size(); i++){
        c += s[i] - '0';
    }
    if(c%9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
const int N=1e5+3;
ll a[N];
int main()
{
    ft
    ll t,i,j,n,m,l,r,k,q;
    cin>>n>>k>>q;
    for(i=1;i<=n;i++)
    {
        a[i]=k;
    }
    l=0;
    while(q--)
    {
        cin>>r;
        a[r]++;
        l++;
    }
    for(i=1;i<=n;i++)
    {
        a[i]-=l;
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]<=0)
        {
            cout<<"No\n";
        }
        else
        {
            cout<<"Yes\n";
        }
    }
    return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int main() {
	ll n;
	cin >> n;
	ll a, b;
	cin >> a >> b;
	ll stagesub = b - a;
	if (stagesub % 2 == 0) {
		cout << stagesub / 2 << endl;
	}
	else {
		ll index = min(a - 1, n - b);
		if (index == a - 1) {
			b -= index;
			cout << index +1 + (b-1) / 2 << endl;
			
		}
		else if (index == n - b) {
			a += n - b;
			cout << index +1+ (n-a) / 2 << endl;
		}

	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
W = list(map(int,input().split()))
add_1 = 0
add_2 = 0
add_diffence = []
for i in range(len(W)):
    add_1 = sum(W[:i+1])
    add_2 = sum(W[i+1:])
    add_diffence.append(abs(add_1-add_2))

print(min(add_diffence))

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();

        for (int i = 0; i < s.length(); i++) {
            int codep = (s.codePointAt(i) - 65 + n) % 26;
            String tmp = String.valueOf((char) (codep + 'A'));
            System.out.print(tmp);
        }
    }
}


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

#define ll long long int
ll dp[105][100005] = {0};
ll knapsack(int n, int W, int* wt, int* val) {

	for (int i = 1; i <= n; i++) {
		for (int w = 1; w <= W; w++) {
			if (w >= wt[i - 1]) {
				dp[i][w] = val[i - 1] + dp[i - 1][w - wt[i - 1]];
			}

			dp[i][w] = max(dp[i][w], dp[i - 1][w]);
		}
	}
	return dp[n][W];
}

int main() {
	int n, W;
	cin >> n >> W;
	int* wt = new int[n];
	int* val = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> wt[i] >> val[i];
	}

	cout << knapsack(n, W, wt, val) << endl;

	return 0;
}

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

int main() {
  string a;
  cin >> a;
  int ans = 0;
  for (int i = 0; i < 3; i++) {
    if (a.at(i) == '1') {
      ans++;
    }
  }
  cout << ans << endl;
}
      

Measured memory_bytes: 256
require 'prime'
include Math
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times {|i|yield(i)}                    end
def repl(st,en,n=1);       n*= -1 if st>en;st.step(en,n){|i|yield(i)} end

def func n,x
	n >= 0 ? n/x + 1 : 0
end

a,b,x = gi
ans = 0
puts func(b,x) - func(a-1,x)


Measured memory_bytes: 2044
import io,sys
sys.setrecursionlimit(10**6)

def main():
    n,k = map(int,input().split())
    D = list(map(int,input().split()))

    while True:
        temp = n
        num = []
        while temp > 0:
            num.append(temp%10)
            temp//=10
        
        flag = True
        for i in num:
            if i in D:
                flag = False
                break
        if flag:
            print(n)
            sys.exit()
        else:
            n+=1
main()

Measured memory_bytes: 9180
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		int C = Integer.parseInt(sc.next());
		int K = Integer.parseInt(sc.next());
		sc.close();
		
		int grCount = 0;
		int blCount = 0;
		while(A >= B) {
			B *= 2;
			grCount++;
		}
		while(B >= C) {
			C *= 2;
			blCount++;
		}
		if(grCount + blCount <= K) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}

Measured memory_bytes: 35668
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

struct UnionFind{
  vector<int> par;
  UnionFind(int N):par(N){
    REP(i,N)par[i]=i;
  }
  int root(int x){
    if(par[x]==x)return x;
    return par[x]=root(par[x]);
  }
  void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)return;
    par[rx]=ry;
  }
};

struct node{
  int a,b;
  int l;
  node(int a,int b,int l):a(a),b(b),l(l){}
  
  bool operator<(const node& r) const{
    return (l<r.l);
  }
};

int main(){
  int N;
  cin>>N;
  vector<pair<int,int> > vx,vy;
  REP(i,N){
    int x,y;
    cin>>x>>y;
    vx.push_back(make_pair(x,i));
    vy.push_back(make_pair(y,i));
  }
  sort(ALL(vx));
  sort(ALL(vy));
  vector<node> nodes;
  FOR(i,1,N){
    node xn(vx[i].second,vx[i-1].second,vx[i].first-vx[i-1].first);
    node yn(vy[i].second,vy[i-1].second,vy[i].first-vy[i-1].first);
    nodes.push_back(xn);
    nodes.push_back(yn);
  }
  sort(ALL(nodes));
  UnionFind tree(N);
  int conected=0;
  int ans=0;
  for(int i=0;conected<N-1;i++){
    if(tree.root(nodes[i].a)!=tree.root(nodes[i].b)){
      tree.unite(nodes[i].a,nodes[i].b);
      conected++;
      ans+=nodes[i].l;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 7144
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdint.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
int main()
{
    string s;cin >> s;int chars[26];
    rep(i, 26) chars[i] = 0;
    rep(i, s.length()) chars[s[i] - 'a']++;
    bool NO = false;
    rep(i, 26){
        if (chars[i] & 1){
            NO = true;
            break;
        }
    }
    cout << (NO ? "No" : "Yes") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define INF INT_MAX/2

struct Maxflow {
	struct edge { int to, cap, rev; edge(int t, int c, int r) { to = t; cap = c; rev = r; } };
	int V;
	vector<vector<edge>> G;
	vector<int> itr, level;

	Maxflow(int V) : V(V) { G.assign(V, vector<edge>()); }

	void add_edge(int from, int to, int cap) {
		G[from].push_back(edge( to, cap, (int)G[to].size() ));
		G[to].push_back(edge( from, 0, (int)G[from].size() - 1 ));
	}

	void bfs(int s) {
		level.assign(V, -1);
		queue<int> q;
		level[s] = 0; q.push(s);
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (auto &e : G[v]) {
				if (e.cap > 0 and level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}

	int dfs(int v, int t, int f) {
		if (v == t) return f;
		for (int& i = itr[v]; i < (int)G[v].size(); ++i) {
			edge& e = G[v][i];
			if (e.cap > 0 and level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	int run(int s, int t) {
		int ret = 0, f;
		while (bfs(s), level[t] >= 0) {
			itr.assign(V, 0);
			while ((f = dfs(s, t, INF)) > 0) ret += f;
		}
		return ret;
	}
};

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

	Maxflow mf(1+X+Y+1);
	rep(i, 0, X) mf.add_edge(0, i+1, 1);
	rep(i, 0, E)
	{
		int x, y;
		cin >> x >> y;
		mf.add_edge(1 + x, 1 + X + y, 1);
	}
	rep(i, 0, Y) mf.add_edge(1 + X + i, 1 + X + Y, 1);

	cout << mf.run(0, 1 + X + Y) << endl;
}

Measured memory_bytes: 3220
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    public static int[] num;
    public static Edge[] e;
    public static int n, k;

    static void solve(InputReader in, PrintWriter out){
        n = in.ni();
        k = in.ni();
        e = new Edge[n];
        num = new int[n];
        Arrays.fill(num, -1);
        for (int i = 0; i < n; i++) e[i] = new Edge();
        for (int i = 0; i < n-1; i++) {
            int from = in.ni()-1, to = in.ni()-1;
            e[from].add(to);
            e[to].add(from);
        }
        num[0] = k;
        long ans = 1;
        if(dfs(-1,0)){
            for (int i = 0; i < n; i++) {
                ans *= num[i];
                ans %= mod;
            }
            out.println(ans);
        }else out.println(0);
    }
    public static boolean dfs(int par, int child){
        boolean flag = true;
        int c = k-2;
        if(par==-1) c++;
        for(int i: e[child]){
            if(i!=par){
                if(c>0){
                    num[i] = c--;
                    flag = flag&&dfs(child, i);
                }
                else flag = false;
            }
        }
        return flag;
    }
    public static class Edge extends ArrayList<Integer>{}

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 72940
A=[list(map(int,input().split())) for i in range(3)]
n=int(input())
B=[int(input()) for i in range(n)]
for i in range(3):
    for j in range(3):
        if A[i][j] in B:
            A[i][j]=0
ans='No'
for i in range(3):
    if A[i].count(0)==3:
        ans='Yes'
for i in range(3):
    temp=[A[0][i],A[1][i],A[2][i]]
    if temp.count(0)==3:
        ans='Yes'
if A[0][0]==0 and A[1][1]==0 and A[2][2]==0:
    ans='Yes'
elif A[0][2]==0 and A[1][1]==0 and A[2][0]==0:
    ans='Yes'
print(ans)

Measured memory_bytes: 3064
N = int(input())
Alist = list(map(int, input().split()))
Alist = sorted([Alist[i] - i - 1 for i in range(N)])
if N%2 == 0:
    mid = (Alist[N//2-1]+Alist[N//2])//2
else:
    mid = Alist[N//2]
ans = sum([abs(a-mid) for a in Alist])
print(ans)

Measured memory_bytes: 101332
/*
* @author:  codancer
* @createTime:  2020-03-31, 19:08:04
*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 200;
ll dp[N][N];
char maze[N][N];
int main(){
	int n,m;
	cin>>n>>m;
	rep(i,1,n){
		rep(j,1,m){
			cin>>maze[i][j];
		}
	}
	rep(i,1,n){
		rep(j,1,m){
			dp[i][j]=1e9;
		}
	}
	if(maze[1][1]=='#'){
		dp[1][1]=1;
	}else{
		dp[1][1]=0;
	}
	rep(i,1,n){
		rep(j,1,m){
			if(i+1<=n) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(int)(maze[i][j]!=maze[i+1][j]));
			if(j+1<=m) dp[i][j+1]=min(dp[i][j+1],dp[i][j]+(int)(maze[i][j]!=maze[i][j+1]));
		}
	}
	// cout<<dp[n][m]<<endl;
	cout<<(dp[n][m]+1)/2<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define maxn 55
#define eps 1e-8
#define endl printf("\n")
#define ll long long
using namespace std;
ll m,n,a[maxn],s;
bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    scanf("%lld%lld",&m,&n);
    for(int i=0;i<m;i++) scanf("%lld",&a[i]);
    sort(a,a+m,cmp);
    for(int i=0;i<n;i++) s+=a[i];
    printf("%lld\n",s);
    return 0;
}


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




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

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

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

bool is_prime(int x) {
	if (x <= 1) return false;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) return false;
	}
	return true;
}

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<int, int>;

/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

ll nCr(ll n, ll r) {
	ll a = 1;
	for (ll i = n; i > n - r; --i) {
		a = a * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		a = a / i;
	}
	return a;
}

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}

const int INF = 1001001001;

int main() {
	string n;
	cin >> n;
	if (n[n.size() - 1] == '2' || n[n.size() - 1] == '4' || n[n.size() - 1] == '5' || n[n.size() - 1] == '7' || n[n.size() - 1] == '9') {
		cout << "hon";

	}
	else if (n[n.size() - 1] == '0' || n[n.size() - 1] == '1' || n[n.size() - 1] == '6' || n[n.size() - 1] == '8') {
		cout << "pon";
	}
	else {
		cout << "bon";
	}
	return 0;
}













Measured memory_bytes: 3628
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	int a[50000];
	int cnum[8]={};
	int targetnum=0;
	scan(N);
	rep(i,N){
		scan(a[i]);
		if(a[i]<3200){
			cnum[a[i]/400]=1;
		}
		else{
			targetnum++;
		}
	}
	int mini=0;
	rep(i,8) mini+=cnum[i];
	printf("%d %d\n",max(1,mini),mini+targetnum);

	return 0;
}


Measured memory_bytes: 256
s = input()
t = input()
u = list(s)
v = list(t)
com1 = []
com1.append(u[0])

p = 0

for i in range(len(u)):
    for j in range(len(u)):
        if j == len(u) - 1:
            u[0] = com1[j]
        else:
            com1.append(u[j + 1])
            u[j + 1] = com1[j]

    if u == v:
        print("Yes")
        p = 1
        break
    com1 = []
    com1.append(u[0])

if p == 0:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int q;
int main() {
    cin >> q;
    for(int i = 0; i < q; ++i) {
        string x, y;
        cin >> x >> y;
        int xlen = x.length(); int ylen = y.length();

        vector< vector<int> > dp(1010, vector<int>(1010, 0));
        for(int i = 0; i < xlen; ++i) {
            for(int j = 0; j < ylen; ++j) {
                if(x.at(i) == y.at(j)) {
                    dp[i+1][j+1] = dp[i][j]+1;
                }else {
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        cout << dp[xlen][ylen] << endl;
    }
}


Measured memory_bytes: 6840
def main():
    N, K = map(int, input().split())
    dots = [tuple(map(int, input().split())) for _ in range(N)]
    
    xs = set()
    ys = set()
    for x, y in dots:
        xs.add(x)
        ys.add(y)
    
    xs = sorted(xs)
    ys = sorted(ys)

    def isOK(l, r, d, u):
        num = sum([l <= x and x <= r and d <= y and y <= u for x, y in dots])
        return num >= K

    ans = 4 * 10 ** 18
    for i, x1 in enumerate(xs):
        for x2 in xs[i+1:]:
            for j, y1 in enumerate(ys):
                for y2 in ys[j+1:]:
                    area = (x2-x1)*(y2-y1)
                    if isOK(x1, x2, y1, y2):
                        ans = min(ans, area)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 70884
package main

import (
	"fmt"
)

func extgcd(a, b int, x, y *int) int {
	if b == 0 {
		*x = 1
		*y = 0
		return a
	}
	d := extgcd(b, a%b, y, x)
	*y -= (a / b) * *x
	return d
}

func main() {
	var a, b, x, y int
	fmt.Scan(&a, &b)
	extgcd(a, b, &x, &y)
	fmt.Printf("%d %d\n", x, y)
}



Measured memory_bytes: 1136
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

#define ll long long
#define ld long double
#define mod 1000000007
#define pb push_back
#define inf 1000000000000000000
#define ff first
#define ss second
#define deb(x) cout<<#x<<" "<<x<<"\n"
#define Clear(x) memset(x,0,sizeof(x))
#define all(x) (x).begin(),(x).end()

void checkpoint1()
{
	/******think more code less******/
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		freopen("Error.txt", "w", stderr);
	#endif
}

bool comp(pair< ll,ll > &a,pair< ll,ll > &b)
{
	if(a.ff!=b.ff)
		return a.ff<b.ff;
	else
	{
		if(a.ss>b.ss)
			return b.ss<a.ss;
		else if(a.ss<b.ss)
			return a.ss<b.ss;
	}
	return a.ff>b.ff;
}

ll powe(ll a,ll b)
{
	ll res=1;
	while(b>0)
	{
		if(b&1)
		{
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		b>>=1;
	}
	return res;
}

void solve()
{
	ll n;
	cin>>n;
	ll op=0;
	while(n--)
	{
		ll x,y;
		cin>>x>>y;
		if(x==y){
			op++;
			if(op>=3)
			{
				cout<<"Yes";
				exit(0);
			}
		}
		else
		{
			op=0;
		}
	}
	cout<<"No";
}

int main()
{	
	checkpoint1();
/********************************************************/	
	auto startrrr = high_resolution_clock::now();
	cout << setprecision(20);
/*******************************************************/	
	
	solve();


/*******************************************************/	
	auto stoprrr = high_resolution_clock::now();
	auto duration = duration_cast<microseconds>(stoprrr - startrrr);
	#ifndef ONLINE_JUDGE
		cerr << "Time: " << duration.count()/1000.0<<"\n";
	#endif
/*******************************************************/		
	return 0;
}

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


int main() {
    string s,front,back;
    ll q;
    cin>>s>>q;

    int jdg=0;

    rep(i,q){
        int n;
        cin>>n;

        if(n==1){
            if(jdg==0)jdg=1;
            else jdg=0;
        }
        else {
            int f;
            char c;
            cin>>f>>c;

            if(jdg==0){
                if(f==1)front.push_back(c);
                else back.push_back(c);
            }
            else {
                if(f==1)back.push_back(c);
                else front.push_back(c);
            }
        }
    }

    if(jdg==0){
        repr(i,front.size()-1,0)cout<<front[i];
        cout<<s;
        rep(i,back.size())cout<<back[i];
        cout<<endl;
    }
    else{
        repr(i,back.size()-1,0)cout<<back[i];
        repr(i,s.size()-1,0)cout<<s[i];
        rep(i,front.size())cout<<front[i];
        cout<<endl;
    }
}


Measured memory_bytes: 1088
x, n = map(int, input().split())
if n > 0:
	p = list(map(int, input().split()))
else:
	p = []

distance = 1000
foundminimum = None
for i in range(102):
	if i in p:
		continue
	if distance > abs(x - i):
		distance = abs(x - i)
		foundminimum = i

print(foundminimum)


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

#define ll long long
#define pb push_back
#define INF 1e9+7
#define cases int t;cin>>t;while(t--)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ff first
#define ss second

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	ll n1,k;
	cin>>n1>>k;
	string s;
	cin>>s;
	// ll cnt=0,mx;
	vector<ll>l1,r1,l2,r2;
	ll flag=0,a,b;
	if(s[0]=='0'){
		a=0;
		flag=0;
	}
	else{
		b=0;
		flag=1;
	}
	rep(i,1,n1){
		if(s[i]=='1'&&flag==0){
			flag=1;
			b=i;
			l2.pb(a+1);
			r2.pb(i);
		}
		else if(s[i]=='0'&&flag){
			flag=0;
			a=i;
			l1.pb(b+1);
			r1.pb(i);
		}
	}
	if(flag){
		l1.pb(b+1);
		r1.pb(n1);
	}
	else{
		l2.pb(a+1);
		r2.pb(n1);
	}
	
	if(l2.size()<k)
		k=l2.size();
	ll cnt;
	ll p=0,mx=-INF;
	if(s[0]=='1'){
		if(l2.size()==0){
			cout<<n1;
			return 0;
		}
		rep(i,k-1,l2.size()){
			if(l1.size()>=(i+2)){
				cnt=r1[i+1];
			}
			else{
				cnt=r2[i];
			}
			cnt-=p;
			if(mx<cnt)
				mx=cnt;
			p=r2[i-k+1];
		}
	}
	else{
		if(l2.size()==0){
			cout<<n1;
			return 0;
		}
		rep(i,k-1,l2.size()){
			if(l1.size()>=(i+1)){
				cnt=r1[i];
			}
			else{
				cnt=r2[i];
			}
			// test1(cnt)
			cnt-=p;
			if(mx<cnt)
				mx=cnt;
			p=r2[i-k+1];
		}
	}
	cout<<mx;
	return 0;
}

Measured memory_bytes: 5192
n=int(input())
#a,b=map(int,input().split())
xl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]


mn=min(xl)
mx=max(xl)
dis=[]
for p in range(mn,mx+1):
    total=0
    for i in range(n):
        total+=(xl[i]-p)**2
    dis.append(total)
print(min(dis))



Measured memory_bytes: 3060
s = list(input())
index=0
cout=0
maxC=0
flag=0
while index < len(s):
    if flag:
        if s[index] in ["A", "T", "G", "C"]:
            cout+=1
        else:
            if maxC < cout:
                maxC=cout
                cout=0
                flag=0
    else:
        if s[index] in ["A", "T", "G", "C"]:
            cout += 1
            flag=1
    index+=1
if maxC < cout:
    maxC = cout
print(maxC)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int merge(vector<int>&a, int l, int r) {
	int mid = (l + r) / 2;
	int n1 = mid - l, n2 = r - mid;
	vector<int>L(n1 + 1), R(n2 + 1);
	rep(i, 0, n1)L[i] = a[l + i];
	L[n1] = INF;
	rep(i, 0, n2)R[i] = a[mid + i];
	R[n2] = INF;
	int ret(0);
	int i(0), j(0);
	rep(k, l, r) {
		ret++;
		if (L[i] <= R[j])a[k] = L[i++];
		else a[k] = R[j++];
	}
	return ret;
}
int mergesort(vector<int>&a, int l, int r) {
	if (r - l > 1) {
		return mergesort(a, l, (l + r) / 2)
			+ mergesort(a, (l + r) / 2, r)
			+ merge(a, l, r);
	}
	return 0;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	int ans = mergesort(a, 0, N);
	rep(i, 0, N)cout << a[i] << (i == N - 1 ? '\n' : ' ');
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6704
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
int main()
{
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i =1;i<=n;i++)
    {
        ll terms = n/i;
        ll last = terms*i;
        ll sum = (terms*(i+last))/2;
        ans += sum;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<"Bad"<<endl;return 0;}
//template
int M=2e5+4;
vector<int> r(M,1),p(M,0),sx(M,0),sy(M,0);

int find(int x){
  return (x==p[x]?x:p[x]=find(p[x]));
}
bool same(int x,int y){
  return find(x)==find(y);
}
void unite(int a,int b){
  a=find(a);b=find(b);
  if(a==b) return;
  if(r[a]<r[b]) swap(a,b);
  r[a]+=r[b];
  p[b]=a;
  sx[a]+=sx[b];
  sy[a]+=sy[b];
}
//main
signed main(){
  for(int i=0;i<M;i++)p[i]=i;
  for(int i=0;i<=1e5;i++)sx[i]++;
  for(int i=1e5+1;i<M;i++)sy[i]++;

  int N;cin>>N;
  set<int> s;
  for(int i=0;i<N;i++){
    int x,y;cin>>x>>y;y+=1e5;
    unite(x,y);
    s.insert(x);s.insert(y);
  }
  int ans=-N;

  set<int> t;
  for(int q:s)t.insert(find(q));
  for(int q:t)ans+=sx[q]*sy[q];
  cout<<ans<<endl;
}


Measured memory_bytes: 11136
#include<iostream>
using namespace std;
int main()
{
    int a,b,c,d,e;
    cin>>a;
    cin>>b;
    cin>>c;
    d = b-a;
    e= c-b;

   if(d==e)
   {
       cout<<"YES";
   }
   else
   {
       cout<<"NO";
   }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
typedef long long ll;
int main()
{
   int n, a[200007];
   map<int,ll> m;
   cin >> n;
   for(int i=1;i<=n;i++)
   {

      cin >> a[i];
      m[a[i]]++;
   }
   long long res = 0;
   for(auto it = m.begin(); it != m.end(); it++)
   {
      res = res + (it->second * (it->second - 1) /2);
   }
  // cout << "Res = " << res << endl;
   for(int i = 1; i <= n; i++)
   {


         cout << res - m[a[i]]*(m[a[i]] -1)/2 + (m[a[i]]-1)*(m[a[i]] -2)/2 << endl;


   }
   return 0;

}


Measured memory_bytes: 10240
#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define mod 1000000009
using namespace std;

int a[200005];
int pos[200005];
int nyak[200005];

int main(){
	int n; cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pos[a[i]] = i;
	}

	for(int i = 1; i <= n; i++){
		if(a[i] != 1 && pos[a[i] - 1] < i){
			nyak[a[i]] = nyak[a[i] - 1] + 1;
		}else{
			nyak[a[i]] = 1;
		}
	}

	int maks = 0;
	for(int i = 1; i <= n; i++){
		maks = max(maks, nyak[i]);
	}

	cout << n - maks << "\n";

}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int n = N;
  N = pow(2,N);
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  sort(vec.rbegin(),vec.rend());
  
  bool flag = true;
  
  vector<int> done(0);
  done.push_back(vec[0]);
  
  multiset<int> MS;
  for(int i=1; i<N; i++){
    MS.insert(vec[i]);
  }
  
  for(int i=0; i<n; i++){
    int D = done.size();
    for(int j=0; j<D; j++){
      auto B = MS.begin();
      auto itr = MS.lower_bound(done[j]);
      if(itr == B){
        flag = false;
        continue;
      }
      itr--;
      int x = *itr;
      done.push_back(x);
      MS.erase(itr);
    }
  }
  
  if(flag){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 17156
def readinput():
    s=input()
    t=input()
    return s,t

def main(s,t):
    ans=len(t)
    for i in range(len(s)-len(t)+1):
        count=0
        for j in range(len(t)):
            if s[i+j]!=t[j]:
                count+=1
        ans=min(ans,count)
    return ans

if __name__=='__main__':
    s,t=readinput()
    ans=main(s,t)
    print(ans)


Measured memory_bytes: 9124
N,M,X,Y = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
max_x = max(x)
min_y = min(y)
if max_x >= min_y or max_x >= Y or min_y <= X:
	print("War")
else:
	print("No War")

Measured memory_bytes: 3060
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        if(N==1){
            System.out.println("Hello World");
        }else{
            System.out.println(sc.nextInt()+sc.nextInt());
        }
    }
}


Measured memory_bytes: 21844