akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

#define fo(i,CApiTaL_N) for(int i=0; i<CApiTaL_N; i++)
#define Fo(i,k,CApiTaL_N) for(int i=k; i<CApiTaL_N; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int t;
const int mxN=400;
vl a(mxN+1);
vvl dp(mxN+1,vl(mxN+1,1e15)),ans(mxN+1,vl(mxN+1));
int n;
ll cost=0;

void test_case(){
    cin>>n;
    Fo(i,1,n+1){
        cin>>a[i];
    }
    Fo(len,1,n+1){
        Fo(srt,1,n+2-len){
            int end=srt+len-1;
            if(srt==end){
                dp[srt][end]=a[srt];
            }else{
                // cout<<srt<<" "<<end<<endl;
                int mid;
                for(int k=srt; k<end; k++){
                    if(dp[srt][k]+dp[k+1][end] < dp[srt][end]){
                        mid=k;
                        dp[srt][end]=dp[srt][k]+dp[k+1][end];
                    }
                    // dp[srt][end]=min(dp[srt][end],dp[srt][k]+dp[k+1][end]);
                }
                ll cost=1e15;
                for(int k=srt; k<end; k++){
                    // cout<<dp[srt][end]<<" K "<<dp[srt][k]<<" "<<dp[k+1][end]<<" "<<ans[srt][k]<<" "<<ans[k+1][end]<<endl;
                    if(dp[srt][end]==dp[srt][k]+dp[k+1][end]){
                        if((ans[srt][k]+ans[k+1][end]) < cost){
                            cost=ans[srt][k]+ans[k+1][end];
                            mid=k;
                        }
                    }
                }
                ans[srt][end]=(dp[srt][end]);
                if(srt+1<end){
                    // cout<<ans[srt][mid]<<" "<<ans[mid+1][end]<<endl;
                    ans[srt][end]+=(ans[srt][mid]+ans[mid+1][end]);
                }
                // cout<<ans[srt][end]<<" ans "<<dp[srt][end]<<" "<<mid<<endl;
            }
        }
    }
    cout<<ans[1][n]<<endl;
}

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

    t=1;
    while(t--){
        test_case();
    }
    
    return 0;
}

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

int main() {
  ll MOD = 1000000007;
  ll N,K;
  ll Ans=0;
  cin>>N>>K;
  rep2(i,K,N+2){
Ans+=i*(N-i+1)+1;
Ans=Ans%MOD;
  }
  cout<<Ans<<endl;
}


Measured memory_bytes: 3640
def solve():
    X = int(input())
    
    if X < 100:
        return 0
    
    upper1 = X // 100
    for p1 in range(0, 100 * upper1 + 1, 100):
        rest1 = X - p1
        if rest1 == 0:
            return 1
        upper2 = rest1 // 101
        for p2 in range(0, 101 * upper2 + 1, 101):
            rest2 = rest1 - p2
            if rest2 == 0:
                return 1
            upper3 = rest2 // 102
            for p3 in range(0, 102 * upper3 + 1, 102):
                rest3 = rest2 - p3
                if rest3 == 0:
                    return 1
                upper4 = rest3 // 103
                for p4 in range(0, 103 * upper4 + 1, 103):
                    rest4 = rest3 - p4
                    if rest4 == 0:
                        return 1
                    upper5 = rest4 // 104
                    for p5 in range(0, 104 * upper5 + 1, 104):
                        rest5 = rest4 - p5
                        if rest5 == 0:
                            return 1
                        upper6 = rest5 // 105
                        for p6 in range(0, 105 * upper6 + 1, 105):
                            rest6 = rest5 - p6
                            if rest6 == 0:
                                return 1
    else:
        return 0

print(solve())

Measured memory_bytes: 3064
#include <vector>
#include <numeric>
#include <utility>
#include <cassert>

struct UnionFind {
public:
	using size_type = std::size_t;
	
	UnionFind(size_type n) : n(n), size_(n, 1) {
		par.resize(n);
		std::iota(par.begin(), par.end(), 0);
	}
	
	size_type size(size_type x) { return size_[find(x)]; }
	
	size_type find(size_type x) {
		assert(x < n);
		while (par[x] != x) {
			par[x] = par[par[x]];
			x = par[x];
		}
		return x;
	}
	
	void merge(size_type x, size_type y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (size(x) > size(y)) std::swap(x, y);
		par[x] = y;
		size_[y] += size_[x];
	}
	
	bool issame(size_type x, size_type y) { return find(x) == find(y); }
	
private:
	size_type n;
	std::vector<size_type> size_, par;
};


#include <cstdio>
#include <vector>
#include <set>

int main() {
	int N, M, K;
	scanf("%d %d %d", &N, &M, &K);
	std::vector<std::vector<int>> g(N), g2(N);
	UnionFind uf(N);
	for (int i = 0; i < M; ++i) {
		int A, B;
		scanf("%d %d", &A, &B);
		--A; --B;
		g[A].emplace_back(B);
		g[B].emplace_back(A);
		uf.merge(A, B);
	}
	for (int i = 0; i < K; ++i) {
		int A, B;
		scanf("%d %d", &A, &B);
		--A; --B;
		g2[A].emplace_back(B);
		g2[B].emplace_back(A);
	}
	
	for (int i = 0; i < N; ++i) {
		int ans = uf.size(i) - 1;
		std::set<int> ss;
		for (int v : g[i]) ss.insert(v);
		for (int v : g2[i]) ss.insert(v);
		for (int v : ss) if (uf.issame(i, v)) --ans;
		printf("%d%c", ans, i + 1 == N ? '\n' : ' ');
	}
	
	return 0;
}

Measured memory_bytes: 18040
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	HashMap<String, Integer> map = new HashMap<String, Integer>();
	for(int i = 0; i<N; i++) {
	    String str = sc.next();
	    Integer base = (map.get(str)==null)?0: map.get(str);
	    map.put(str, base+1);
	}
	int M = sc.nextInt();
	for(int i = 0; i<M; i++) {
            String str = sc.next();
	    Integer base = (map.get(str)==null)?0: map.get(str);
            map.put(str, base-1);
	}
	int max = 0;
	for(String str: map.keySet()) {
	    max = Math.max(max,map.get(str));
	}
	System.out.println(max);
    }

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define INF 2147483647
#define lli long long int
#define MOD 1000000007
#define pb push_back

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;

int main() {
	int x; cin >> x;
	
	int ans = 0;
	int now = 0;
	for (int i = 1; now < x;i++){
		now += i;
		ans = i;
	}
	cout << ans << endl;

	return 0;
}





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

int main(){
    int S[13],H[13],C[13],D[13];
    int sum;
    cin >> sum;
    char moji;
    int num;


    for(int i=0;i<13;i++){
        S[i]=0;
    }
    for(int i=0;i<13;i++){
        H[i]=0;
    }
    for(int i=0;i<13;i++){
        C[i]=0;
    }
    for(int i=0;i<13;i++){
        D[i]=0;
    }

    for(int i=0;i<sum;i++){
        cin >> moji >> num;

        if(moji=='S'){
            S[num-1]=1;
        }

        else if(moji=='H'){
            H[num-1]=1;
        }

        else if(moji=='C'){
            C[num-1]=1;
        }

        else if(moji=='D'){
            D[num-1]=1;
        }
    }

    for(int i=0;i<13;i++){
        if(S[i]==0){
            cout << 'S' << ' ' << i+1 << endl;
        }
    }

    for(int i=0;i<13;i++){
        if(H[i]==0){
            cout << 'H' << ' ' << i+1 << endl;
        }
    }

    for(int i=0;i<13;i++){
        if(C[i]==0){
            cout << 'C' << ' ' << i+1 << endl;
        }
    }

    for(int i=0;i<13;i++){
        if(D[i]==0){
            cout << 'D' << ' ' << i+1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3092
fn main(){
    let _: usize = read();
    let mut v: Vec<u32> = read_vec();
    let q: i32 = read();

    let mut sv: Vec<u32> = v.clone();
    sv.sort();

    let mut dc: usize = v.iter().zip(sv.iter()).filter(|&(&x, &y)| x != y).count();
    let mut ix: i32 = 0;

    loop {
        if dc == 0 { break }

        ix += 1;
        if ix > q { ix = -1; break }

        let xy: Vec<usize> = read_vec();
        let x = xy[0] - 1;
        let y = xy[1] - 1;

        if v[x] != sv[x] && v[x] == sv[y] { dc -= 1 }
        if v[x] == sv[x] && v[x] != sv[y] { dc += 1 }
        if v[y] != sv[y] && v[y] == sv[x] { dc -= 1 }
        if v[y] == sv[y] && v[y] != sv[x] { dc += 1 }

        v.swap(x, y);
    }
    println!("{}", ix);
}

#[allow(dead_code)]
fn read<T>() -> T
where T: std::str::FromStr,
      T::Err: std::fmt::Debug
{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    buf.trim().parse().unwrap()
}

#[allow(dead_code)]
fn read_vec<T>() -> Vec<T>
where T: std::str::FromStr,
      T::Err: std::fmt::Debug
{
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).expect("failed to read");
    buf.split_whitespace().map(|e| e.parse().unwrap()).collect()
}



Measured memory_bytes: 11064
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int main(){
  int A, B;
  cin >> A >> B;
  ll ans = 0;
  if(A >= 13){
    ans = B;
  }else if(A >= 6){
    ans = B / 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();

        long left = (long)0, right = (long)0;
        String[] ans = new String[q];
        for(int i=0; i<q; i++){
            long p = sc.nextLong();
            String c = sc.next();
            long n = sc.nextLong();
            if(c.equals("(")) left += n;
            else right += n;
            if(left==right) System.out.println("Yes");
            else System.out.println("No");
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 46548
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) > (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define R cin>>
#define i64 unsigned long long
#define repr(i, n) REPR(i, n, 0)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define in(a) insert(a)
#define P(p) cout<<(p)<<endl;
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SORT(a) sort((a).begin(), (a).end())
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long int> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll mod = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;
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;}
template<typename T> void co(T e){cout << e << "\n";}
template<typename T> void co(const vector<T>& v){for(const auto& e : v)
    { cout << e << " "; } cout << "\n";}
ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0) return a;
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}
ll lcm(ll a, ll b) {
    ll g = gcd(a, b);
    return a * b / g;
}
bool prime(ll n) {
    for (ll i = 2; i <= sqrt(n); i++) {
        if (n%i == 0)return false;
    }
    return n != 1;
}


int pow(ll x, ll y, ll mod){
    ll ret=1;
    for(;y;y>>=1,x=1ll*x*x%mod){
        if(y&1) ret=1ll*ret*x%mod;
    }
    return ret;
}
void kill()
{
    cout << -1 << endl;
    exit(0);
}

int main() {
    sonic();
    int next, prev, total, i, t, n;
    ll ans=0;
    R n;
    priority_queue<pii> q;
    vi A(n), B(n);
    rep(i, n)R A[i];
    rep(i, n){
        R B[i];
        q.push(make_pair(B[i], i));
    }
    while(0<q.size()) {
        i = q.top().second;
        q.pop();
        if(B[i]==A[i])continue;
        if(B[i]<A[i])kill();
        next = (i + 1 + n) % n;
        prev = (n + i - 1) % n;
        total = B[next] + B[prev];
        t = (B[i] - A[i]) / total;
        if(t==0)kill();
        ans += t;
        B[i] -= t * total;
        q.push(make_pair(B[i], i));
    }
    cout << ans << endl;
}


Measured memory_bytes: 6892
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);

		boolean[] spade = new boolean[13];
		boolean[] diamond = new boolean[13];
		boolean[] club = new boolean[13];
		boolean[] heart = new boolean[13];

		int n = stdin.nextInt();

		for (int i = 0; i < n; ++i) {
			String markChar = stdin.next();
			int number = stdin.nextInt();
			boolean[] mark = null;
			if ("S".equals(markChar)) {
				mark = spade;
			} else if ("H".equals(markChar)) {
				mark = heart;
			} else if ("C".equals(markChar)) {
				mark = club;
			} else if ("D".equals(markChar)) {
				mark = diamond;
			}
			mark[number - 1] = true;
		}

		for (int i = 0; i < spade.length; ++i) {
			if (!spade[i]) {
				System.out.println("S " + (i + 1));
			}
		}
		for (int i = 0; i < heart.length; ++i) {
			if (!heart[i]) {
				System.out.println("H " + (i + 1));
			}
		}
		for (int i = 0; i < club.length; ++i) {
			if (!club[i]) {
				System.out.println("C " + (i + 1));
			}
		}
		for (int i = 0; i < diamond.length; ++i) {
			if (!diamond[i]) {
				System.out.println("D " + (i + 1));
			}
		}
	}
}

Measured memory_bytes: 26172
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	char m;
	int num;
	int index;
}card;

int partition(card A[], int p, int r);
void quicksort(card A[], int p, int r);
int isStable(card A[], int n);

int main() {
	int r, n, i;
	card *Card;
	Card = (card *)malloc(sizeof(card) * 100000);
	scanf("%d", &n);
	r = n-1;
	for (i = 0; i < n; i++) { scanf("%1s %d", &Card[i].m, &Card[i].num); Card[i].index = i; }
	quicksort(Card, 0, r);
	if (isStable(Card,n))puts("Stable"); else puts("Not stable");
	for (i=0; i < n; i++) printf("%c %d\n", Card[i].m,Card[i].num);
	free(Card);
	return 0;
}

int partition(card A[], int p, int r){
	int i,x,j;
	card tmp;
	x = A[r].num;
	i = p-1;
	for (j = p; j <= r; j++) {
		if (A[j].num <= x) {
			i++;
			tmp = A[i]; A[i] = A[j]; A[j] = tmp;
		}
	}
	return i;
}

void quicksort(card A[], int p, int r){
	int q;
	if (p < r) {
		q = partition(A, p, r);
		quicksort(A, p, q - 1);
		quicksort(A, q + 1, r);

	}
}

int isStable(card A[], int n)
{
	int i;
	for (i = 0; i < n - 1; i++) {
		if (A[i].num == A[i + 1].num&&A[i].index > A[i + 1].index) return 0;
	}
	return 1;
}

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

int main() {
	int n;
	cin >> n;
	int k;
	cin >> k;
	int answer;
	int amari;
	int in[100000];
	answer += (n-1)/(k-1);
	if((n-1)%(k-1)!=0){
		answer+=1;
	}
	
	cout << answer <<endl;
}


Measured memory_bytes: 256
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N = iin()
A = iln()

c = [0 for _ in range(N+1)]

for i in range(N):
    c[i+1] = c[i] + A[i]

cnt = collections.Counter(c)

ans = 0
for v in cnt.values():
    ans += v*(v-1) // 2
print(ans)


Measured memory_bytes: 43480
from sys import stdin
import math


def main(inp):
    h = int(inp)

    hp = h
    num_enemy = 1
    num_attack = 0
    while hp >= 1:
        hp, num_enemy, this_attack = attack(hp, num_enemy)
        num_attack += this_attack
    return num_attack


def attack(enemy_hp, num_enemy):
    num_attack = num_enemy
    enemy_hp = math.floor(enemy_hp / 2)
    num_enemy *= 2
    return enemy_hp, num_enemy, num_attack


if __name__ == '__main__':
    input_line = stdin.readline().rstrip()
    ret = main(input_line)
    print(ret)

Measured memory_bytes: 3064
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int a = sc.nextInt();
      
        if (a >= 3200) {
          System.out.println(sc.next());
        } else {
          System.out.println("red");
        }
	}
}

Measured memory_bytes: 22612
import fractions
mod = 10**9+7

n = int(input())
a = [int(x) for x in input().split()]


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


ans = 0
for i in range(n):
    ans += inv(a[i], mod)
    ans %= mod


lcm = a[0]

for i in range(1, n):
    lcm = lcm*a[i] // fractions.gcd(lcm,a[i])

lcm %= mod

ans *= lcm
ans %= mod

print(ans)


Measured memory_bytes: 68200
import sys
X = int(input())

if X < 4:
  print(X)
  sys.exit()

if X%2 ==0:
  A = X-1
else:
  A = X-2

ans = 0
while ans == 0:
  A += 2
  for n in range(2,int(A/2)+1):
    ans = A
    if A%n == 0:
      ans = 0
      break

ans = A
print(ans)

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

using namespace std;

int n;
long long c;

pair <long long, int> a[100005];

long long cw[100005], ccw[100005], dp1[100005], dp2[100005];

int main(){
	scanf("%d%lld", &n, &c);
	
	for(int i = 0; i < n; i++)
	scanf("%lld%d", &a[i].first, &a[i].second);
	
	long long res = 0;
	
	for(int i = 0; i < n; i++){
		if(i == 0)
		cw[i] = a[i].second - a[i].first;
		else
		cw[i] = cw[i - 1] + a[i].second - (a[i].first - a[i - 1].first);
		
		if(i == 0)
		dp1[i] = cw[i];
		else
		dp1[i] = max(dp1[i - 1], cw[i]);
		
		res = max(res, cw[i]);
	}
	
	for(int i = n - 1; i >= 0; i--){
		if(i == n - 1)
		ccw[i] = a[i].second - (c - a[i].first);
		else
		ccw[i] = ccw[i + 1] + a[i].second - (a[i + 1].first - a[i].first);
		
		if(i == n - 1)
		dp2[i] = ccw[i];
		else
		dp2[i] = max(dp2[i + 1], ccw[i]);
		
		res = max(res, ccw[i]);
	}
	
	//for each i
	//find ccw[j] i < j < n such that cw[i] + ccw[j] - a[i].first is maximize
	//max ccw[j]
	
	for(int i = 0; i < n - 1; i++)
	res = max(res, cw[i] + dp2[i + 1] - a[i].first);
	for(int i = n - 1; i >= 1; i--)
	res = max(res, ccw[i] + dp1[i - 1] - (c - a[i].first));
	
	printf("%lld\n", res);
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
#define int long long

signed main(){
  int N;
  cin >> N;
  int a[200000];
  int b[200000];//sorted
  LOOP(i,N){
    cin >> a[i];
    b[i]=a[i];
  }
  sort(b,b+N);
  int mid = N/2;
  LOOP(i,N){
    if(a[i]>=b[mid]){
      cout << b[mid-1] << endl;
    }else{
      cout << b[mid] << endl;
    }
  }
}


Measured memory_bytes: 5376
#include<stdio.h>

int main(void){
  char c[10];
  scanf("%s",c);
  if(strcmp(c,"SUN")==0){
    printf("7\n");
  }else if(strcmp(c,"MON")==0){
    printf("6\n");
  }else if(strcmp(c,"TUE")==0){
    printf("5\n");
  }else if(strcmp(c,"WED")==0){
    printf("4\n");
  }else if(strcmp(c,"THU")==0){
    printf("3\n");
  }else if(strcmp(c,"FRI")==0){
    printf("2\n");
  }else if(strcmp(c,"SAT")==0){
    printf("1\n");
  }
     
   return 0;
}


Measured memory_bytes: 1640
N = int(input())
d = list(map(int,input().split()))
sd = sorted(d)
#Kとしてあり得る値は sd[N // 2 - 1] + 1 から d[N // 2] までの合計 d[N // 2] - d[N // 2 - 1] 個
print(sd[N//2]-sd[N//2-1])

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

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

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

  int N, Q;
  cin >> N >> Q;
  vector<vector<int>> G(N);
  int tmp_a, tmp_b;
  for(int i = 0; i < N-1; i++){
    cin >> tmp_a >> tmp_b;
    tmp_a--;
    tmp_b--;
    G[tmp_a].push_back(tmp_b);
    G[tmp_b].push_back(tmp_a);
  }

  vector<ll> w(N);
  for(int i = 0; i < N; i++){
    w[i] = 0;
  }

  int tmp_p, tmp_x;
  for(int i = 0; i < Q; i++){
    cin >> tmp_p >> tmp_x;
    tmp_p--;
    w[tmp_p] += tmp_x;
  }

  vector<bool> visited(N);
  for(int i = 0; i < N; i++){
    visited[i] = false;
  }

  queue<int> q;
  q.push(0);

  while(!q.empty()){
    int now = q.front();
    q.pop();
    visited[now] = true;
    for(int i = 0; i < G[now].size(); i++){
      if(!visited[G[now][i]]){
        w[G[now][i]] += w[now];
        q.push(G[now][i]);
      }
    }
  }

  for(int i = 0; i < N; i++){
    cout << w[i] << " ";
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 16372
#import<bits/stdc++.h>
long i,j,n,x,m=1e9+7,s[222],d[1<<17];
main(){for(std::cin>>x>>x;std::cin>>s[n];n++);for(std::sort(s,s+n);j++<x;)d[j]=j;for(;j?:(j=x,++i<n);)d[j]=(d[j]*i+d[j--%s[i]])%m;std::cout<<d[x];}

Measured memory_bytes: 1024
S = input()
N = len(S)

if S[0] == '0' or S[-1] == '1':
    print(-1)
    exit()

mem = []
for i in range(N//2):
    if S[i] != S[-2-i]:
        print(-1)
        exit()
    if S[i] == '1':
        mem.append(i)

if len(mem)==0:
    print(-1)
    exit()

ans = []
for i in range(1,len(mem)+1):
    ans.append((i,i+1))

last_v = len(mem)+1

for i in range(mem[0]):
    last_v += 1
    ans.append((1,last_v))

for i,(a,b) in enumerate(zip(mem, mem[1:])):
    n = i+2
    k = b-a-1
    for _ in range(k):
        last_v += 1
        ans.append((n,last_v))

n = len(mem)+1
for _ in range(N):
    last_v += 1
    if last_v > N: break
    ans.append((n,last_v))

for row in ans:
    print(*row)

Measured memory_bytes: 18512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)
#define Graph vector<vecctor<ll>>
#define pairs vector<pair<ll,ll>>
#define pb push_back



using namespace std;
using ll = long long;
const ll INF = 1e18;
const double PI = acos(-1);

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



int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll>a(n);
    rep(i,n){
        cin >> a[i];
    }
    ll ma = 0,ans = 0;
    rep(i,n){
        if(a[i] < ma){
            ans += ma-a[i];
        }else{
            ma = max(ma,a[i]);
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4744
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

string S;
vector<int> prepi, sufpi;

inline void calcPrefix ( const string S, vector<int>& pi ) {
	int n = S.length ();
	pi.clear (), pi.push_back ( 0 );
	for ( int i = 1; i ^ n; ++ i ) {
		int j = pi[i - 1];
		for ( ; j && S[i] ^ S[j]; j = pi[j - 1] );
		pi.push_back ( j + ( S[i] == S[j] ) );
	}
}

int main () {
	ios :: sync_with_stdio ( false ), cin.tie ( 0 );
	cin >> S;
	int n = S.length ();
	bool allsame = true;
	for ( int i = 1; i ^ S.size () && allsame; ++ i ) allsame &= S[i] == S[0];
	if ( allsame ) return cout << n << "\n1\n", 0;
	calcPrefix ( S, prepi );
	reverse ( S.begin (), S.end () );
	calcPrefix ( S, sufpi );
	if ( ! prepi[n - 1] || n % ( n - prepi[n - 1] ) ) return cout << "1\n1\n", 0;
	int ans = 0;
	for ( int i = 0; i + 1 < n; ++ i ) {
		if ( ( ! prepi[i] || ( i + 1 ) % ( i + 1 - prepi[i] ) )
			&& ( ! sufpi[n - 2 - i] || ( n - i - 1 ) % ( n - i - 1 - sufpi[n - 2 - i] ) ) ) {
			++ ans;
		}
	}
	cout << "2\n" << ans << endl;
	return 0;
}

Measured memory_bytes: 6316
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int n;
	cin >> n;

	for(int i=0; i<26; i++){
		for(int j=0; j<16; j++){
			if(n==4*i+7*j){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
import heapq

n=int(input())
A=list(map(int,input().split()))
for i in range(n):
  A[i]*=-1
A.sort()
ans=0
Q=[A[0]]
heapq.heapify(Q)
for i in range(1,n):
  v=heapq.heappop(Q)
  v*=-1
  ans+=v
  heapq.heappush(Q,A[i])
  heapq.heappush(Q,A[i])

print(ans)

Measured memory_bytes: 105232
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();

    double p = 0;

    for (int i = 1; i <= n; ++i)
      p += (1 / (double) n) * Math.pow(0.5, Math.max(0, Math.ceil(log((double) k / i))));
    
    System.out.println(p);
  }

  public static double log(double x) {
    return Math.log(x) / Math.log(2);
  }
}

Measured memory_bytes: 21832
fn main() {
    let v = read_vec::<i32>();
    let a = v[0];
    let b = v[1];
    let n = format!("{}{}", a.to_string(), b.to_string()).parse::<i32>().unwrap();
    for i in 1..400 {
        if i * i == n {
            yn(true);
            return;
        }
    }
    yn(false);
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int N = in.Int();
            int[] A = in.Int(N);

            long cnt = 0;
            int sum = 0;
            int r = 0;
            for (int l = 0; l < N; l++) {
                while (r < N && (sum ^ A[r]) == sum + A[r]) {
                    sum += A[r++];
                }
                cnt += r - l;
                if (l == r) r++;
                else sum -= A[l];
            }
            out.println(cnt);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    return null;
                }
            }
            return st.nextToken();
        }

        public int Int() {
            return Integer.parseInt(next());
        }

        public int[] Int(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Int();
            }
            return a;
        }

    }
}



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

int i,j,k,n,buc[15],cake[15];
double box,list[11][11],goal,leng[2];
char sp;

int main(){
	for(i=3;i<=10;i++){
		for(j=3;j<=10;j++){
			list[i][j]=i+j-sqrt((double)((i+j)*(i+j)-(i-j)*(i-j)));
		}
	}

	while(scanf("%lf",&box)!=EOF){
		n=0;goal=0;
		for(i=0;i<11;i++)buc[i]=0;
		while(1){
			scanf("%c",&sp);
			if(sp=='\n')break;
			
			scanf("%d",&k);
			buc[k]++;
			goal+=k*2;
			n++;
		}

		//printf("before:%lf\n",goal);
		goal-=box;
		//printf("after:%lf\n",goal);
		
		if(goal<=0){printf("OK\n");continue;}

		for(i=3,j=0;i<11 && j<n;i++){for(;buc[i]>0;j++,buc[i]--)cake[j]=i;}

		leng[0]=0;leng[1]=0;
		for(k=1,i=0,j=0;k<n;k++){
			leng[0]+=list[cake[i]][cake[n-j-1]];
			leng[1]+=list[cake[j]][cake[n-i-1]];
			if(i<=j)i=j+1;else{j++;i--;}
		}

		if(leng[0]>=goal || leng[1]>=goal)printf("OK\n"); else printf("NA\n");

	}
	return 0;
}

Measured memory_bytes: 612
#include <iostream>

// 1-indexed
long long costL[200020];
long long costLmax[200020];
long long costR[200020];
long long costRmax[200020];

int main(){
    int n;
    long long prev, ans = 0;
    std::cin >> n >> prev;
    for(int i = 1; i < n; i++){
        long long a;
        std::cin >> a;
        if(i % 2){
            int k = i/2+1; // k個目
            costL[k] = costL[k-1] + prev-a;
            ans += a;
        }else{
            costR[i/2] = a-prev;
        }
        prev = a;
    }
    for(int i = (n-1)/2; i > 0; i--){
        costR[i] += costR[i+1];
    }
    for(int i = 1; i <= n/2; i++){
        costLmax[i] = std::max(costL[i], costLmax[i-1]);
    }
    for(int i = (n-1)/2; i > 0; i--){
        costRmax[i] = std::max(costR[i], costRmax[i+1]);
    }
    if(n % 2){ // if odd
        long long M = costRmax[1];
        for(int i = 1; i <= n/2; i++){ // move left
//            M = std::max(M, costL[i] + costRmax[i+1]);
            if(M < costL[i] + costRmax[i+1]){
                M = costL[i] + costRmax[i+1];
            }
        }
        std::cout << M + ans << std::endl;
    }else{ // if even
        std::cout << ans + costLmax[n/2] << std::endl;
    }
}


Measured memory_bytes: 6772
#include <stdio.h>

int main(){
    int a,b,c;
    scanf("%d %d %d", &a,&b,&c);

    if((!(0<=a<=100)) | (!(0<=b<=100)) | (!(0<=c<=100)) | (a==b) | (a==c) | (b==c))return 0;

    if(((a<c) && (c<b) ) | ( (b<c) && (c<a)))printf("Yes");
    else printf("No");

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, ab;
  cin >> a;
  cin >> b;
  
  ab = a*b;
  
  if (ab % 2 == 0){
    cout << "Even" << endl;
  }
  
  else {
	cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a = sorted(a)
b = sorted(b)
c = sorted(c)
ans = 0
for i in range(n):
    at = bisect.bisect_left(a, b[i])
    ct = max(len(c) - bisect.bisect_right(c, b[i]), 0)
    ans += at * ct
print(ans)


Measured memory_bytes: 23328
#include<stdio.h>
int min(int a,int b){
if(a<=b)return a;
return b;
}
int max(int x,int y){
if(x<=y)return y;
return x;
}
int main(){
int a[3001][2];
int i=0,j=0;
while(1){
scanf("%d %d",&a[i][0],&a[i][1]);
if(a[i][0]==0&&a[i][1]==0)break;
i++;
}
while(i>j){
printf("%d %d\n",min(a[j][0],a[j][1]),max(a[j][0],a[j][1]));
j++;
}
}

Measured memory_bytes: 2692
#include <iostream>

using namespace std;

int main () {
	int N;
	char s[101], t[101], ans[201];

	cin >> N >> s >> t;
	for (int i=0; i<N; i++) {
		ans[2*i] = s[i];
		ans[2*i+1] = t[i];
	}
	ans[2*N] = '\0';
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
    string S;
    cin >> S;
    int tmp;
    ll ans = 0;
    ll num = stoll(S);
    REP(i,1<<(S.size()-1)){
        tmp = 0;
        REP(j,S.size()){
            if((i>>j) %2 == 1 || j == S.size()-1){
                ans += num % ll(pow(10,j+1)) / ll(pow(10,tmp));
                tmp = j+1;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
#define PI 3.1415926535
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
//ダイクストラ法
struct edge{int to,cost;};
vector<edge>G[MAX];
int d[MAX];
int prever[MAX];
void dijkstra(int s,int V){
    priority_queue<P,vector<P>,greater<P>>que;
    for(int i=0;i<V;i++)d[i]=INF;
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p=que.top();
        que.pop();
        int v=p.second;
        if(d[v]<p.first)continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                prever[e.to]=v;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
vector<int> get_path(int t){
    vector<int>path;
    for(;t!=-1;t=prever[t])path.push_back(t);
    reverse(ALL(path));
    return path;
}
int main(){
	int n,m;
	cin>>n>>m;
	REP(i,m){
		int a,b;
		cin>>a>>b;
		a--;b--;
		G[a].push_back({b,1});
		G[b].push_back({a,1});
	}
	dijkstra(0,n);
	OUT("Yes");
	for(int i=1;i<n;i++){
		OUT(prever[i]+1);
	}
	return 0;
}

Measured memory_bytes: 34696
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;


int main() {
	ll n, m; cin >> n >> m;
	ll ans = 0;
	for (ll i = 1; i*i <= m; i++) {
		ll j = m / i;
		if (m%i == 0 && m/i >= n) ans = max(ans, i);
		if (m%j == 0 && m/j >= n) ans = max(ans, j);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;
using P = pair<int, int>;
const int MOD = 1e9+7;
const double EPS = 1e-9;

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

  unordered_map<int, vl> G;
  int t, d;

  rep(i,n) {
    cin >> t >> d;
    G[t].push_back(d);
  }

  for (auto &p : G) sort(ALL(p.second), greater<ll>());

  priority_queue<P> next;  // P(d,t)
  for (auto &p : G) next.push(P(p.second[0], p.first));

  unordered_map<int, int> eat;  // <t, number>
  ll satisfaction = 0;

  rep(i,k) {
    tie(d,t) = next.top(); next.pop();
    ++eat[t];
    satisfaction += d;

    if (eat[t] < G[t].size()) next.push(P(G[t][eat[t]], t));
  }

  int variety = eat.size();
  satisfaction += (ll)pow(variety, 2);

  unordered_map<int, ll> bonus;
  bonus[variety] = 0;

  priority_queue<P, vector<P>, greater<P>> twice;  // P(d,t)
  int num;

  for (auto p : eat) {
    tie(t,num) = p;
    if (num != 1) twice.push(P(G[t][num-1], t));
  }

  int nt, nd;

  while (!next.empty() && !twice.empty()) {
    tie(nd,nt) = next.top(); next.pop();

    if (!eat.count(nt)) {
      tie(d,t) = twice.top(); twice.pop();
      bonus[variety+1] = bonus[variety] + (nd - d) + (variety*2 + 1);
      ++variety;
      --eat[t];

      if (eat[t] != 1) twice.push(P(G[t][eat[t]-1], t));
    }
  }

  ll increase = 0;
  for (auto p : bonus) increase = max(increase, p.second);

  ll ans = satisfaction + increase;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11936
x, y = [int(i) for i in input().split()]
 
A = (1, 3, 5, 7, 8, 10, 12)
B = (4, 6, 9, 11)
 
if x in A and y in A:
    print("Yes")
elif x in B and y in B:
    print("Yes")
else:
    print("No")  

Measured memory_bytes: 3060
n, m = map(int,input().split())
students = []
marks = []
for _ in range(n):
    student = list(map(int,input().split()))
    students.append(student)
for i in range(m):
    mark = list(map(int,input().split()))
    mark.append(i+1)
    marks.append(mark)
INF = 10**10 
for a, b in students:
    mdist = INF
    for c, d, m in marks:
        if abs(a-c) + abs(b-d) < mdist:
            move_mark = m
            mdist = abs(a-c) + abs(b-d)
    print(move_mark)

Measured memory_bytes: 3064
pub trait BinarySearch<T> {
    fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, x: &T, mut f: F) -> usize;
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, x: &T, mut f: F) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord + Clone> BinarySearch<T> for Vec<T> {
    fn lower_bound(&self, x: &T) -> usize {
        self.lower_bound_by_key(x, |y| y.clone())
    }

    fn lower_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, x: &T, mut f: F) -> usize {
        let mut high = self.len();
        let mut low = 0;
        while low < high {
            let mid = (low + high) / 2;
            if f(&self[mid]).lt(&f(x)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        self.upper_bound_by_key(x, |y| y.clone())
    }

    fn upper_bound_by_key<B: Ord, F: FnMut(&T) -> B>(&self, x: &T, mut f: F) -> usize {
        let mut high = self.len();
        let mut up = 0;
        while up < high {
            let mid = (up + high) / 2;
            if f(&self[mid]).le(&f(x)) {
                up = mid + 1;
            } else {
                high = mid;
            }
        }
        up
    }
}

fn solve(aa: Vec<isize>) -> usize {
    let n = aa.len();
    let mut dp = vec![std::isize::MAX; n];

    for a in aa {
        let a = -a;
        let p = dp.upper_bound(&a);
        if a < dp[p] {
            dp[p] = a;
        }
    }

    dp.lower_bound(&std::isize::MAX)
}

#[test]
fn upper_bound_test() {
    assert_eq!(vec![1, 1, 2].upper_bound(&1), 2);
    assert_eq!(vec![1, 1, 2, 2, 3].upper_bound(&3), 5);
    assert_eq!(vec![1, 1, 2, 2, 4].upper_bound(&3), 4);
}

#[test]
fn solve_test() {
    assert_eq!(solve(vec![2, 1, 4, 5, 3]), 2);
    assert_eq!(solve(vec![0, 0, 0, 0]), 4);
    assert_eq!(solve(vec![1, 5, 2, 6, 3, 7]), 2);
}

#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        line.pop();
        line
    }};
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        let iter = line.split_whitespace();
        iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
    }};
}

fn main() {
    let n = parse_line!(usize);
    let aa = (0..n).map(|_| parse_line!(isize)).collect::<Vec<_>>();
    println!("{}", solve(aa));
}


Measured memory_bytes: 6396
#include<stdio.h>
#include<math.h>

int main(void){
    int N, M, H[100100] , A[100100] ,B[100100];
    int i, j , k=0 ,sum=0 ;
    int Am[100100]={}, Bm[100100]={};

    scanf("%d%d" ,&N ,&M);
    for( i= 1 ; i<=N ; i++){
        scanf("%d" ,&H[i]);
    };

    for( j=1 ; j<=M ; j++){
        scanf("%d%d" ,&A[j] ,&B[j]);
        if(H[A[j]]>Am[B[j]]){
            Am[B[j]]=H[A[j]];
        };
        if(H[B[j]]>=Bm[A[j]]){
            Bm[A[j]]=H[B[j]];
        }
    };

    for(i=1 ;i<=N ; i++){
        if(H[i]>Am[i]&&H[i]>Bm[i]){
            sum++;
        };
    };
    printf("%d", sum);

    return 0;
}


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

[N, M] = [int(i) for i in input().split()]
a_list = []
for m in range(M):
    a_list.append(int(input()))

stairs_status = [-1] * (N + 1)
stairs_status[0] = 1
for a in a_list:
    stairs_status[a] = 0

for n in range(1, N + 1):
    if n == 1:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1]
    else:
        if stairs_status[n] == -1:
            stairs_status[n] = stairs_status[n - 1] + stairs_status[n - 2]

#print(stairs_status)
print(stairs_status[-1] % 1000000007)



Measured memory_bytes: 460020
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n;
	string s, t, u;
	cin >> n >> s >> t >> u;

	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == t[i]) {
			if (s[i] != u[i]) {
				ans++;
			}
		}
		else if (s[i] == u[i]) {
			ans++;
		}
		else if (u[i] == t[i]) {
			ans++;
		}
		else {
			ans += 2;
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    ll nx=0;
    ll ny=0;
    ll nt=0;
    ll flag=0;
    rep(i,N){
        ll t,x,y;
        cin>>t>>x>>y;
        ll dt=t-nt;
        ll dx=abs(x-nx);
        ll dy=abs(y-ny);
        if(dx+dy>dt || (dx+dy+dt)%2==1){
            flag=1;
        }

        nt=t;
        nx=x;
        ny=y;

    }
    if(flag==1){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }



    return 0;
    

}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdint>

std::uint64_t arr[4][4][4][101];

int main()
{
    for( int i = 0; i < 4; ++i )
    for( int j = 0; j < 4; ++j )
    for( int k = 0; k < 4; ++k )
         if( i == 0 && j == 2 && k == 1 ) arr[i][j][k][3] = 0;
    else if( i == 0 && j == 1 && k == 2 ) arr[i][j][k][3] = 0;
    else if( i == 2 && j == 0 && k == 1 ) arr[i][j][k][3] = 0;
    else arr[i][j][k][3] = 1;
    
    std::size_t N;
    std::cin >> N;
    for( std::size_t t = 4; t <= N; ++t )
    for( int i = 0; i < 4; ++i )
    for( int j = 0; j < 4; ++j )
    for( int k = 0; k < 4; ++k )
         if( i == 0 && j == 2 && k == 1 ) arr[i][j][k][t] = 0;
    else if( i == 0 && j == 1 && k == 2 ) arr[i][j][k][t] = 0;
    else if( i == 2 && j == 0 && k == 1 ) arr[i][j][k][t] = 0;
    else if( i == 2 && k == 1 ) arr[i][j][k][t] = (arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][t-1]) % 1'000'000'007;
    else if( j == 2 && k == 1 ) arr[i][j][k][t] = (arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][t-1]) % 1'000'000'007;
    else arr[i][j][k][t] = (arr[0][i][j][t-1] + arr[1][i][j][t-1] + arr[2][i][j][t-1] + arr[3][i][j][t-1]) % 1'000'000'007;
        
    std::uint64_t sum = 0;
    for( int i = 0; i < 4; ++i )
    for( int j = 0; j < 4; ++j )
    for( int k = 0; k < 4; ++k )
    sum = (sum+arr[i][j][k][N]) % 1'000'000'007;
        
    std::cout << sum;        
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<utility>
#include<queue>
#include<cmath>
#include<cstdio>
using namespace std;
#define REP(i, a,b) for(i=a;i<b;i++) 
#define REP1(i,b,a) for(i=b-1;i>=a;i--)
#define output(x) cout<<x<<endl;
#define pb(x) push_back(x);
typedef long long int ll;


const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i ;
	}

}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	if (k == 0) return 1;
	return n * COM(n - 1, k - 1) / k;
}



int main() {
	COMinit();
	ll i, j, k, l, m, n, sum, flag, cc,N,Ma,Mb,X,A,B;
	sum = 0;
	flag = 0;
	cin >> N >> Ma >> Mb;
	vector<int>a(N);
	vector<int>b(N);
	vector<int>c(N);
	int kanou[401][401];
	REP(i, 0, 401) {
		REP(j, 0, 401) {
			kanou[i][j] = -100;
		}
	}
	kanou[0][0] = 0;
	REP(i, 0, N) {
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(k, 0, N) {
		REP1(i, 401,0 ) {
			REP1(j, 401, 0) {
				if (kanou[i][j] >= 0) {
					if (kanou[i + a[k]][j + b[k]] >= 0) {
						kanou[i + a[k]][j + b[k]] = min(kanou[i][j] + c[k], kanou[i + a[k]][j + b[k]]);
					}
					else {
						kanou[i + a[k]][j + b[k]] = kanou[i][j] + c[k];
					}
				}
			}
		}
	}
	ll ans = 10000000000;
	REP(i, 1, 401) {
		REP(j, 1, 401) {
			if (kanou[i][j] >= 1) {
				if (i%Ma == 0 && j%Mb == 0 && i/Ma == j / Mb) {
					flag = 1;
					if (ans > kanou[i][j]) {
						ans = kanou[i][j];
					}
				}
			}
		}
	}
	if (flag) { output(ans); }
	else { output(-1); }
	return 0;
}

Measured memory_bytes: 8704