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

typedef long long ll;
typedef long double ld;
static const double pi = 3.14159265359;
static const int inf = (1 << 21);
static const int mod = 1000000007;

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>> Graph(N);//隣接行列
    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        Graph.at(A).push_back(B);
        Graph.at(B).push_back(A);
    }
    queue<int> q;
    q.push(0);
    vector<int> parent(N, -1);//ノードの親を判定　-1だと無い
    parent.at(0) = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int n: Graph.at(v)) {
            if (parent.at(n) != -1) {
                continue;
            }
            parent.at(n) = v;
            q.push(n);
        }
    }
    bool J = true;
    for (int i = 1; i < N; i++) {
        if (parent.at(i) == -1) {
            J = false;
        }
    }
    if (J) {
        cout << "Yes" << endl;
        for (int i = 1; i < N; i++) {
            cout << parent.at(i) + 1 << endl;
        }
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 10332
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=200010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
int n,Y;
signed main()
{
    n=read(), Y=read();
    for(ri int i=0;i<=Y/10000;i++)
    for(ri int j=0;j<=Y/5000&&i+j<=n;j++)
    if(i*10000+j*5000+(n-i-j)*1000==Y)
    {
        printf("%lld %lld %lld\n",i,j,n-i-j);
        return 0;
    }
    puts("-1 -1 -1");
    return 0;
}

Measured memory_bytes: 3720
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

vector<pair<ll, ll>>prime_factorize(ll n) {
	vector<pair<ll, ll>>res;
	for (ll 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;
}
const int MAX = 210000;
ll 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%INF;
		inv[i] = INF - inv[INF%i] * (INF / i) % INF;
		finv[i] = finv[i - 1] * inv[i] % INF;
	}
}
ll COM(int n, int k) {
	if (n < k)return 0;
	if (n < 0 || k < 0)return 0;
	return fac[n] * (finv[k] * finv[n - k] % INF) % INF;
}
int main() {
	int n, m; cin >> n >> m;
	COMinit();
	vector<pair<ll, ll>>key = prime_factorize(m);
	ll ans = 1;
	for (int i = 0; i < key.size(); ++i) {
		ans *= COM(n+key[i].second-1, key[i].second);
		ans %= INF;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5120
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
#define FORi(N) for(int i = 0; i < N; ++i)
#define FORj(N) for(int j = 0; j < N; ++j)
#define FORk(N) for(int k = 0; k < N; ++k)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
int main() {
    string S;
    cin >> S;

    sort(S.begin(), S.end());

    if(S[0] == S[1] && S[2] == S[3] && S[1] != S[2]){
        cout << "Yes" << endl;

    }else{
        cout << "No" << endl;
    }

    
            return 0;
}


Measured memory_bytes: 888
temp = input().split(" ")
X = int(temp[0])
Y = int(temp[1])
i = 2
while True:
    tgt = X * i
    if X == Y:
        print(-1)
        break
    elif tgt % Y != 0:
        print(tgt)
        break
    elif i == 100000:
        print(-1)
        break
    else:
        i += 1

Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func main() {
	n := 0
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
		a[i]--
	}
	ans := 0
	for i := range a {
		j := a[i]
		if i < j && a[j] == i {
			ans++
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
object Main extends App{
  override def main(args:Array[String])={
    var nums = readLine.split(" ").map(a => a.toInt)
    nums = nums.sorted
    var res = 0
    for(i <- 1 until nums.length){
      res += nums(i)-nums(i-1)
    }
    println(res)
  }
}

Measured memory_bytes: 25424
N,M = list(map(int, input().split()))

if N%2 == 1:
  for i in range(1,M+1):
    print(i, N-i)
else:
  # N=8 M=3 (8,1), (4,6), (7,2)
  # N=10, M=4 (10,1), (5,7), (9,2), (4,8)
  for i in range(M):
    if i%2 == 0:
      x = i//2
      print(N-x, 1+x)
    else:
      cent = N//2+1
      x = i//2+1
      print(cent-x, cent+x)

Measured memory_bytes: 9276
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
	int x,y;

	scanf("%d %d", &x,&y);

	if (x + y == 0)
	{
		printf("1\n");

	}else if ( x < y )  //ok
	{
		int a;

		a = min(abs(x-y), 1 + abs( abs(x) - abs(y) ) );
		printf("%d\n", a);

	}else if ( x > y )
	{

		if ( (x < 0 && y < 0) || (x > 0 && y > 0))
		{
			printf("%d\n", 2 + abs(x-y) );
		}else
		{
			printf("%d\n", 1 + abs( abs(x) - abs(y) ) );
		}
		/*int b;

		b = min( 2 + abs(x-y), 1 + abs( abs(x) - abs(y) ) );
		printf("%d\n", b);
		*/

	}

	return 0;
}
	

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
typedef long long ll;

using namespace std;
using Graph = vector<vector<int>>;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;

const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

const double PI=3.14159265358979323846; // or M_PI


void Main() {
    ll k, n, max_distance=0, in_a;
    vector<ll> a;

    cin >> k >> n;
    REP(i, n) {
        cin >> in_a;
        a.push_back(in_a);
    }

    REP(i, n - 1) {
        if (max_distance < abs(a[i] - a[i + 1])) {
            max_distance = abs(a[i] - a[i + 1]);
        }
    }
    if (max_distance < abs(k - a[n - 1] + a[0])) {
        max_distance = abs(k - a[n - 1] + a[0]);
    }

    COUT(k - max_distance);
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*
20 3
5 10 15
*/

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

int main(){
  string S;
  cin >> S;
  int N=S.size();
  bool a=false;
  for(int i=0;i<N-1;i++){
    string T=S.substr(i,2);
    if(T.at(0)==T.at(1)){
      a=true;
      cout << i+1 << " " << i+2 << endl;
      break;
    }
    if(i!=N-2){
      string U=S.substr(i,3);
      if(U.at(0)==U.at(2)){
        a=true;
        cout << i+1 << " " << i+3 << endl;
        break;
      }
    }
  }
  if(!a){
    cout << -1 << " " << -1 << endl;
  }
}   

Measured memory_bytes: 3736
use std::cmp::min;
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()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let n:usize = read();
    let an = read_vec::<i64>();
    let sum = an.iter().sum::<i64>();
    let mut x = 0;
    let mut ans = 1e10 as i64;
    for j in 0..n-1{
        x += an[j];
        ans = min(ans,(sum-2 * x).abs());
    }
    // too late 
    // let ans = (1..n).fold(1e10 as i64,|res,i| {
    //     let x:i64 = an.iter().take(i as usize).sum();
    //     let y:i64= sum - x;
    //     min((x-y).abs(),res)
    // });
    println!("{}",ans);
}


Measured memory_bytes: 10492
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner x=new Scanner (System.in);
		int a=x.nextInt();
		int a1[]=new int [a];
		for(int i=0;i<a;i++){
			a1[i]=x.nextInt();
			System.out.print(a1[i]);
			if(i<a1.length-1)
				System.out.print(" ");
		}
		System.out.println();
		for(int i=1;i<a1.length;i++){
			int key=a1[i];
			int j=i-1;
			while(j>=0&&a1[j]>key){
				a1[j+1]=a1[j];
				j--;
				a1[j+1]=key;
			}
			int d=0;
			for(int w=0;w<a1.length;w++){
				System.out.print(a1[w]);
				if(d>=0&&d<a1.length-1)
					System.out.print(" ");
				d++;
				if(d==a){
					System.out.println();
					d=0;
				}
			}
		}
	}
}



Measured memory_bytes: 33960
/*
 _     _    ___  ___  __ __ 
| |   | |  |__ \|__ \/_ /_ |
| |__ | |__   ) |  ) || || |
| '_ \| '_ \ / /  / / | || |
| |_) | |_) / /_ / /_ | || |
|_.__/|_.__/____|____||_||_|

*/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		string s,t;
		cin>>s>>t;
		ll l=0;
		rep(i,0,s.size())
		if(s[i]==t[i])
			l++;
		cout<<l<<endl;
	}
	return 0;
}

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

typedef long long ll;

using namespace std;

int contains(vector<vector<int>> A, int b) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (A[i][j] == b) {
                return i * 3 + j;
            }
        }
    }
    return -1;
}

int main() {
    vector<vector<int>> A(3, vector<int>(3));
    for (int i = 0; i < 3; i++) {
        cin >> A[i][0] >> A[i][1] >> A[i][2];
    }
    int N;
    cin >> N;
    vector<vector<bool>> bingo(3, vector<bool>(3, false));
    for (int k = 0; k < N; k++) {
        int b;
        cin >> b;
        int index = contains(A, b);
        if (index != -1) {
            int i = index / 3;
            int j = index % 3;
            bingo[i][j] = true;
        }
    }
    if (
            (bingo[0][0] && bingo[0][1] && bingo[0][2]) ||
            (bingo[1][0] && bingo[1][1] && bingo[1][2]) ||
            (bingo[2][0] && bingo[2][1] && bingo[2][2]) ||
            (bingo[0][0] && bingo[1][0] && bingo[2][0]) ||
            (bingo[0][1] && bingo[1][1] && bingo[2][1]) ||
            (bingo[0][2] && bingo[1][2] && bingo[2][2]) ||
            (bingo[0][0] && bingo[1][1] && bingo[2][2]) ||
            (bingo[2][0] && bingo[1][1] && bingo[0][2])
       ) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
s = input()
s1 = int(s[:2])
s2 = int(s[2:])

# 01 <= s <= 12 なら MM
# 00 <= s <= 99 なら YY (実質無制限)

# どちらかがMMであるか確かめる
mm_like = [1 <= s <= 12 for s in [s1, s2]]
# print(mm_like)

if mm_like == [True, False]:
    print("MMYY")
elif mm_like == [False, True]:
    print("YYMM")
elif mm_like == [True, True]:
    print("AMBIGUOUS")
elif mm_like == [False, False]:
    print("NA")

Measured memory_bytes: 3064
#include <stack>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;

int main()
{
    int a,b,c;
    int counts;
    cin>>a>>b>>c;
    if(a==b){
        counts++;
    }
    if(a==c){
        counts++;
    }
    if(b==c){
        counts++;
    }
    
    if(counts==3){
        printf("1\n");
    }else if(counts==2){
        printf("2\n");
    }else if(counts==1){
        printf("2\n");
    }else{
        printf("3\n");
    }
    return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const ll M=1000000007;
int n,k,a[100005],b[100005],i;
ll s[100005],s2[100005],ans;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n+1;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(i=1;i<=n;i++)
		if(b[i]<a[i])
			ans+=b[i];
		else
		{
			b[i]-=a[i];
			ans+=a[i];
			a[i]=0;
			if(b[i]<a[i+1])
			{
				ans+=b[i];
				a[i+1]-=b[i];
			}
			else
			{
				ans+=a[i+1];
				a[i+1]=0;
			}
		}
	cout<<ans;
}


Measured memory_bytes: 1024
#include <stdio.h>

using namespace std;

int main(){
    char res[100001];
    int cnt = 0;
    char temp;
    while(scanf("%c", &temp) != EOF){
        if(cnt % 2 == 0){
            printf("%c", temp);
        }
        cnt++;
    }
    printf("\n");

    return 0;
}

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

int main(){
  int N;cin>>N;
  vi A(N);
  rep(i,N)cin>>A[i];
  A.push_back(0);

  ll money = 1000;

  vi list;
  for(int i=0; i<N; i++){
    list.push_back(A[i]); //今日の株価を区域に追加

    if(A[i] <= A[i+1]){
      //明日上がる
      ; //なにもしない
    }else{
      //明日下がる
      ll buy = money / list.front();
      money -= buy * list.front();
      money += buy * list.back();
      list.clear();
    }
  }

  cout<<money<<endl;
}

Measured memory_bytes: 3588
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int A[] = new int[N];
    int count = 0;
    boolean bool = true;
    for(int i=0; i<N; i++) {
      A[i] = sc.nextInt();
      if(A[i] % 2 != 0){
        bool = false;
      }
    }
    while(bool) {
      for(int j=0; j<N; j++) {
        A[j] = A[j] / 2;
          if(A[j] % 2 != 0) {
            bool = false;
          }
      }
      count++;
    }
    System.out.println(count);
  }
}

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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int N; cin >> N;
  int A[N]; rep(i,N) cin >> A[i];
  int even = 0; rep(i,N) even += (A[i]%2==0);
  int result = pow(3,N) - pow(2,even);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int N, M;
	int K;
	cin >> N >> M >> K;

	//読書時間の合計時間表
	int A[200050], B[200050];
	//読まないときは0
	A[0] = 0;
	B[0] = 0;
	//考慮する意味のある範囲
	int A_max = N;
	bool A_check = false;
	int B_max = M;
	bool B_check = false;
	for (int i = 1; i <= N; i++) {
		int Ai;
		cin >> Ai;
		A[i] = Ai + A[i - 1];
		if (A[i] > K && (!A_check)) {
			//i冊目を考える必要は皆無
			A_max = i - 1;
			A_check = true;
		}
	}
	for (int i = 1; i <= M; i++) {
		int Bi;
		cin >> Bi;
		B[i] = Bi + B[i - 1];
		if (B[i] > K && (!B_check)) {
			//i冊目を考える必要は皆無
			B_max = i - 1;
			B_check = true;
		}
	}


	//Aの読む本数を増やして走査
	int ans = 0;
	int Screen_Index[200050]; //Bの操作位置に関する関する情報
	Screen_Index[0] = B_max; //A=0のとき、Bは一番大きいところから走査する。
	for (int i = 0; i <= A_max; i++) {
		for (int j = Screen_Index[i]; j >= 0; j--) {
			//オーバーしなくなったら抜け出す
			if (A[i] <= K - B[j]) {
				if (i + 1 <= N) Screen_Index[i + 1] = j;
				ans = max(ans, i + j);
				break;
			}
		}
	}

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

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

int mpow(int base, int exp);
void ipgraph(int n, int m);
void dfs(int u, int par);

const int mod = 1'000'000'007;
const int N = 3e5, M = N;
//=======================

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

void solve()
{
  double i, j, n, m;
  cin >> i >> j >> m;
  double time = i / m;
  if (time <= j)
  {
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}

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

  int t = 1;
  //cin >> t;
  while (t--)
  {
    solve();
  }

  return 0;
}

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

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

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


Measured memory_bytes: 10748
n=int(input())
a=sorted(list(map(int,input().split())))
b=set()
ans=0
d={}
cnt=0
for i in range(n):
    if i!=0 and a[i]!=a[i-1]:
        d[a[i-1]]=cnt
        cnt=0
    cnt+=1
    if i==n-1:
        x=a.count(a[i])
        d[a[i]]=x
for i in d.keys():
    if d[i]>=i:
        ans+=d[i]-i
    else:
        ans+=d[i]
print(ans)

Measured memory_bytes: 18552
#include<cstdio>

int main()
{
    int ans = 0;
    int a[10005];
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        while(a[i] % 2 == 0){
            ans++;
            a[i] = a[i] >> 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
/*
 * main.c
 *
 *  Created on: 2019/07/21
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


int main()
{
	int N = 0, Y = 0;
	int i10k = 0, i5k = 0, i1k = 0;
	scanf("%d %d", &N, &Y);
	for (i10k = 0; i10k <= N; i10k++) {
		for (i5k = 0; i5k <= N-i10k; i5k++) {
			i1k = N - i10k - i5k;
			if (((i10k*10000) + (i5k*5000) + (i1k*1000)) == Y) {
				printf("%d %d %d\n", i10k, i5k, i1k);
				return 0;
			}
		}
	}
	printf("-1 -1 -1\n");
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(void) {

	int a,b,c,i;
	int y = 0 ;
	
	scanf("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	
	for(i = a ; i <= b ; i++){
		if(!(c%i)){
			y++;
		}
	}

	printf("%d\n",y);

	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
	ll  n;
	cin >> n;
	ll i, count=0, a[n], x[n];
	for(i=0; i<n; i++)
		cin >> a[i], x[i]=a[i];
		
	sort(a,a+n);
	
	for(i=0; i<n; i++)
	{
		if(a[i] != x[i])
		count++;
		if(count > 2)
		break;
	}
	(count==2 || count==0) ? cout << "YES" : cout << "NO";

}

int main(){
	solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  long long int a,b,c=0,d=1000000007;cin>>a>>b;
  for(int i=b;i<a+2;i++)c+=i*(a-i+1)+1;
  cout<<c%d;
}

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

int ans[100000],n;

int main()
{
    cin>>n;

    int arr[n];

    for(int i=0;i<n;i++)
        cin>>arr[i];

    ans[0]=0;
    ans[1]=abs(arr[1]-arr[0]);

    for(int i=2;i<n;i++)
        ans[i]=min(ans[i-2] + abs(arr[i-2]-arr[i]),ans[i-1]+abs(arr[i]-arr[i-1]));

    cout<<ans[n-1];
}

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

int main(){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    cin >> x1 >> y1 >> x2 >> y2;

    x3=x2+y1-y2;
    y3=y2-(x1-x2);
    x4=x1+y1-y2;
    y4=y1-(x1-x2);

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int A[1000001] = {}, X[1000001]={},cnt[1000001]={};
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }
    for(int i=0; i<N; i++) {
        cnt[A[i]] ++;
        if(cnt[A[i]] != 1) continue;
        for(int j = A[i]; j<=1000001; j+=A[i]){
            X[j] += 1;
        }
    }
    int ans = 0;
    for(int i=0; i<N; i++){
        if(X[A[i]] == 1 && cnt[A[i]] == 1) ans ++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 12028
a,b=map(int,input().split())


ans=0

ans+=((b+1)//2-a//2)%2

for i in range(1,50):
  if a//(2**(i+1))==b//(2**(i+1)):
    ci=max(0,b%(2**(i+1))-max(a%(2**(i+1)),2**i)+1)
  else:
    ci=min(2**(i+1)-a%(2**(i+1)),2**i)+max(b%(2**(i+1))-2**i+1,0)
  if ci%2==1:
    ans+=2**i
  
print(ans)
 

Measured memory_bytes: 62080
'''
from math import log10
p = 100
import math
a = int(input()) 
t = math.ceil(log10(a/p)/log10(1.01))
print(t)
'''
p = 100
t = 0
a = int(input()) 
import math
while True:
	it = p * 0.01
	if it < 1:
		it = 0
	p+=math.floor(it)
	t +=1
	#print(p)
	if p>= a:
		break
print(t)


Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> vec(H, vector<char>(W));
  vector<vector<char>> answer(H+2, vector<char>(W+2));
  
  for (char k = 0; k < H; k++) {
    for (char i = 0; i < W; i++) {
      cin >> vec.at(k).at(i);
    }
  }
  for (char k = 0; k < H+2; k++) {
    for (char i = 0; i < W+2; i++) {
      if (i==0 || k==0 || i==W+1 || k==H+1) {
        answer.at(k).at(i) = '#';
      }
      else {
        answer.at(k).at(i) = vec.at(k-1).at(i-1);
      }
    }
  }
  for (char k = 0; k < H+2; k++) {
    for (char i = 0; i < W+2; i++) {
      if(i!=W+1){
        cout << answer.at(k).at(i);
      }
      else
        cout << answer.at(k).at(i) << endl;
    }
  }  
}

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

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

  for(int i=0;i<s.length();i++){
    if(s[i]=='1'){
      if(i==k-1){
	cout << 1 << endl;
	return 0;
      }
    }else{
      cout << s[i] << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
constexpr int MAX = 1e3;
constexpr int VMAX = 1e4;
int n, s, ans{0};
vi a;
vb V(MAX, false);
inline void solve() {
	vi b(all(a)), t(VMAX + 1);
	sort(all(b));
	rep(i, 0, n) t[b[i]] = i;
	rep(i, 0, n) {
		if(V[i]) continue;
		int cur = i;
		int S = 0;
		int m = VMAX;
		int an = 0;
		while(true) {
			V[cur] = true;
			++an;
			int v = a[cur];
			m = min(m, v);
			S += v;
			cur = t[v];
			if(V[cur]) break;
		}
		ans += min(S + (an - 2) * m, m + S + (an + 1) * s);
	}
}
int main() {
	cin >> n;
	a.resize(n);
	rep(i, 0, n) cin >> a[i];
	s = min(VMAX, *min_element(all(a)));
	solve();
	P(ans);
	return 0;
}

Measured memory_bytes: 3264
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

// vectorの重複削除
// std::sort(test.begin(), test.end()); 昇順
// test.erase(std::unique(test.begin(), test.end()), test.end());

using namespace std;
using ll = long long;
using P = pair<int, int>; // vector<P> ba(n); みたいな感じですぐ使える ba[i] = P(a, b); make_pairをしなくてもいい
// typedef vector<int> v;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
#define rep(i, c) for(int i = 0; i < int(c); i++)
#define ALL(x) (x).begin(), (x).end() //sort(ALL(obj))みたいな
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値
#define pb push_back //
// const int MOD = 1000000007;
// string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// printf("%.20f\n", ans); あれ
// const double PI = 3.141592653589793238462643383;



int main() {
  int n; cin>>n;
  std::vector<int> v(n);
  int ans = 0;
  rep(i,n){
    cin>>v[i];
    ans += v[i];
  }
  std::sort(v.rbegin(), v.rend());
  debug(v);
  rep(i,n) {
    if (i%2==1) {
      ans -= 2*v[i];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3172
import java.util.*;

public class Main {

    static final int MOD=1000000007;

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

        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        for(int i=0;i<n;i++){
            b[i]=sc.nextInt();
            d[i] = b[i]-a[i];
        }

        Arrays.sort(d);
        long sum = 0;
        int ans=0;
        for(int i=0;i<n;i++)if(d[i]>0){
            sum+=d[i];
            ans++;
        }
        
        long sum2 = 0;
        for(int i=0;i<n;i++){
            if(sum2>=sum){
                System.out.println(ans+i);
                return;
            }
            sum2 -= d[i];
        }
        System.out.println(-1);




    }
}


Measured memory_bytes: 89284
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int c[3][3];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	rep(i,3)rep(j,3) cin >> c[i][j];
	for(int a1 = 0; a1 <= 100; ++a1){
		vector<int> a(3), b(3);
		a[0] = a1;
		rep(j,3) b[j] = c[0][j] - a[0];
		a[1] = c[1][0] - b[0];
		a[2] = c[2][0] - b[0];
		bool ok = true;
		rep(i,3)rep(j,3){
			if(a[i]+b[j] != c[i][j]) ok = false;
		}
		if(ok){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

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

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

int dp[4040];

int main()
{
  int n;
  rep(i, 1000) rep(j, 1000){
    dp[i + j]++;
  }

  while (cin >> n){
    int ans = 0;
    rep(i, n) ans += dp[i] * dp[n - i];

    cout << ans << endl;
  }
}

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

int main() {
    double x1, y1, x2, y2, x3, y3, xp, yp;
    double ax, ay, bx, by;
    while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp){
        double m,n;
        ax = x2 - x1;
        ay = y2 - y1;
        bx = x3 - x1;
        by = y3 - y1;
        xp = xp - x1;
        yp = yp - y1;
        double point = ax*by - ay*bx;
        m = (by*xp - bx*yp)/point;
        n = (-ay*xp + ax*yp)/point;
        if(point == 0){
            cout << "NO"<<endl;
        }
        else if(m > 0 && m <= 1 && n > 0 && n <= 1 && m+n <= 1 ){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

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

	const int N = 5;
	long long A[N];

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}


	long long ans = 5;
	long long d = 1;
	for (int i = 0; i < N; i++)
	{
		long long x = ceil(M / (double)A[i]);

		if (d < x)
		{
			ans += x - d;
			d = x;
		}
	}

	cout << ans << endl;

	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

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

const ll INF = 1e18;
const ll MOD = 998244353;
const ll MX = 1000001;

void solve() {
    int N, R; cin >> N >> R;
    if (N >= 10) cout << R;
    else cout << R + 100 * (10 - N);
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
    ll T = 1; // cin >> T;
    while (T--) solve();
    return 0;
    // You should actually read the stuff at the bottom
}

/* Stuff to Look For
 * -----------------
 * Int overflow, array bounds
 * Initializing all variables, avoid weird behavior
 * Edge cases(n = 0, n = 1)
 * Just return 0 after result
 */


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

int main()
{
	int array[10];
	for (int i = 0; i < 10; i++) {
		cin >> array[i];
	}
	for (int j = 9; j != 6; j--) {
		for (int i = 0; i < j; i++) {
			if (array[i] > array[i+1]) {
				int spare = array[i];
				array[i] = array[i+1];
				array[i+1] = spare;
			}
		}
		cout << array[j] << endl;
	}
}

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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n, m;cin >> n >> m;
    vector<vector<int>> g(n);
    vector<int> h(n);
    inc(i, 0, n) cin >> h[i];
    inc(i, 0, m){
        int a, b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans = 0;
    inc(i, 0, n){
        bool f = true;
        for(auto j : g[i]){
            if(h[j] >= h[i]) f = false;
        }
        if(f) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8748
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:])) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)


Measured memory_bytes: 61876
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ss second
#define ff first
#define Mem(x,val) memset(x,val,sizeof x)
#define pb push_back
#define all(v) v.begin(),v.end()
#define unik(v)  v.erase(unique(v.begin(),v.end()),v.end())
#define cerr(x) cerr << __LINE__ << " th Line : " << #x << " = " << x << "\n"
#define debug(a,b) cerr << #a<<" = "<<a<<"   |   "<<#b<<" = "<<b<<'\n'
#define endl '\n'
#define SZ(a) ((int)a.size())
using namespace std;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod = 1e9 + 7;
const int nax = 1e6+10;
vi adj[nax];
int vis[nax];
void dfs(int src){
	vis[src] = 1;
	for(auto x : adj[src]){
		if(!vis[x])dfs(x);
	}
}
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   ll n, m;
   cin >> n >> m;
   for(int i=0; i<m; i++){
	   int a, b;
	   cin >> a >> b;
	   adj[a].pb(b);
	   adj[b].pb(a);
   }
   int cnt = 0;
   for(int i=1; i<=n; i++){
	   if(!vis[i]){
		   dfs(i);
		   cnt++;
	   }
   }
   cout << cnt - 1 << endl;
   return 0;
}


Measured memory_bytes: 31104
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define ld long double
using namespace std;

ld x[3], y[3], t[3];

int main() {
	for(int i=0; i<3; ++i) cin >> x[i] >> y[i];
	for(int i=0; i<3; ++i) t[i]=sqrt(pow(x[(i+1)%3]-x[i], 2.0)+pow(y[(i+1)%3]-y[i], 2.0));
	sort(t, t+3, greater<ld>());
	ld b=(t[0]+t[1]+t[2])/2.0;
	ld S=sqrt(b*(b-t[0])*(b-t[1])*(b-t[2]));
	ld ans=(S*2.0)/(t[0]+t[1]+t[2]+(S*4.0)/t[0]);
	cout << setprecision(15) << ans << endl;
	return 0;
}


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

int a[13];

int main()
{
	//fuck
	for(int i=1;i<=3;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+3+1);
	if(a[1]+a[2]==a[3])
	{
		puts("Yes");
	}
	else
	{
		puts("No");
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true)cerr
void print(){cout<<endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {cout<<a<<" ";print(args...);}
lli llipowerp(lli x, lli y, lli p=LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
inline void printvec(vector<T> inp){
    for(auto it:inp) cout<<it<<" ";
    cout << endl;
}
//---------------------------------------------------------------------------------

int main(){
    
    set<int> nums;
    int n,k;
    cin>>n>>k;
    fori(k){
        int d,x;
        cin>>d;
        fori(d){
            cin>>x;
            nums.insert(x);
        }
    }
    cout<<n-nums.size()<<endl;

}


Measured memory_bytes: 3636
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		int N = sc.nextInt();

		List<Integer> A = new ArrayList<>();

		for (int i = 0; i < N + 1; i++)
			A.add(sc.nextInt());

		List<Integer> B = new ArrayList<>();

		for (int i = 0; i < N; i++)
			B.add(sc.nextInt());

		long count = 0;
		for (int i = 0; i < N; i++) {
			if (B.get(i) >= A.get(i)) {
				count += A.get(i);
				if (A.get(i + 1) >= B.get(i) - A.get(i)) {
					A.set(i + 1, A.get(i + 1) - (B.get(i) - A.get(i)));
					count += B.get(i) - A.get(i);
				} else {
					count += A.get(i + 1);
					A.set(i + 1, 0);
				}
			} else
				count += B.get(i);

		}

		System.out.println(count);

	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 30080
n = int(input())
s = list(map(int, input().split()))
q = input()
t = list(map(int, input().split()))

center = int(n / 2)
result = 0

for ti in t:
  if s[center] < ti:
    left = int(n / 2)
    right = n - 1
  elif ti < s[center]:
    left = 0
    right = int(n / 2)
  else:
    result += 1
    continue

  while True:
    tmp = int(left + int((right - left) / 2))
    if 'current' in locals() and current == tmp:
      if right == (n - 1):
        current += 1
      else:
        current -= 1
    else:
      current = tmp

    if s[current] < ti:
      if current < left:
        break
      left = current
    elif ti < s[current]:
      if right < current:
        break
      right = current
    elif ti == s[current]:
      result += 1
      break

print(result)


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

//#define int long long
typedef long long ll;
#define double long double
#define vec vector
#define pb push_back
#define unset unordered_set
#define ii pair<int, int>
#define X first
#define Y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define bitcount(n) __builtin_popcountll(n)
typedef vector<int> vi;
template <typename T,typename U>
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
  return {l.first+r.first,l.second+r.second};
} 
typedef void (*callback_function)(void); // type for conciseness
const long long ZERO = 0LL;
const long long INF64 = 1e18;
const int INF32 = 1e9;
const int MOD = 1e6 + 3;
const double EPS = static_cast<double>(1e-9);
#define min(a, b) (((a)<(b))?(a):(b))
#define max(a, b) (((a)>(b))?(a):(b))

//************************************
//#undef int
int main() {
//#define int long long
	ios_base::sync_with_stdio(false); cin.tie();
	//auto beginProgram = chrono::steady_clock::now();
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);

	int n; cin >> n;
	ll sum=0, minV = LLONG_MAX, cnt=0;
	FOR(i, 0, n) { 
		ll a; cin >> a; 
		if(a < 0) { cnt++; a= -a;}
		sum += a;
		minV = min(minV, a);
		
//		cout << a << ", " << sum << ", " << minV << ", " << cnt << endl;
		
	}
	if(cnt%2==0) cout << sum  << endl;
	else cout << sum - 2*minV << endl;
	
  //auto endProgram = chrono::steady_clock::now();
  return 0;
}


Measured memory_bytes: 256
def main():
    n = int(input())
    ps = list(map(int, input().split()))
    ans = 0
    for i in range(n-2):
        temp_sort = sorted(ps[i:i+3])
        if ps[i+1] == temp_sort[1]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(input())
X, Y = [], []
for i in range(N):
    x, y = map(int,input().split())
    X.append([x, i])
    Y.append([y, i])

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Measured memory_bytes: 96740
n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 10, 3
# A = [5, 1, 3, 2, 4, 1, 1, 2, 3, 4]
# n, k = 4, 4
# A = [1, 1, 2, 2]
D = {}
for a in A:
    try:
        D[a] += 1
    except:
        D[a] = 1
D = sorted(D.values())
print(sum(D[:len(D)-k]))


Measured memory_bytes: 33152
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////
//#include<bits/stdc++.h>
using namespace std;
#define Base1   101LL
#define Base2   10000079LL
#define Base3   10000103LL
#define MOD1    1000000007LL
#define MOD2    1000000009LL
#define MOD3    1000000021LL
#define mx 100000//Number of charter of main string
#define mx1 25000// Number off character of total charcater
#define mx2 500// Number of pattern and number of ch of each pattern
 
 int main(){
     ll x,y;
     cin>>x>>y;
     if(x*500>=y)cout<<"Yes"<<endl;
     else cout<<"No"<<endl;

     return 0;
 }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <set>
#include <map>
#include <stack>
#include <deque>
#include <iterator>
#include <iomanip>
using namespace std;


int main() {
  long long n, m;
  cin >> n >> m;
  map<int, int> mp;
  mp[1] = 2;
  mp[2] = 5;
  mp[3] = 5;
  mp[4] = 4;
  mp[5] = 5;
  mp[6] = 6;
  mp[7] = 3;
  mp[8] = 7;
  mp[9] = 6;
  vector<pair<int, int> > a(m);
  for(int i = 0; i < m; ++i){
    cin >> a[i].second;
    a[i].first = mp[a[i].second];
  }
  sort(a.begin(), a.end());
	vector<pair<int, bool> > d(n + 1, make_pair(0, false));
	vector<pair<int, int> > v(n + 1);
	d[0].second = true;
	d[0].first = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 0; j < m && a[j].first <= i; ++j)
		    if((d[i].first < d[i - a[j].first].first + 1 || (d[i].first == d[i - a[j].first].first + 1 && v[i].second <= a[j].second)) && d[i - a[j].first].second){
			    d[i].first = d[i - a[j].first].first + 1;
				  v[i].first = i - a[j].first;
          v[i].second = a[j].second;
				  d[i].second = true;
			}

 	}
	vector<int> path;
	long long p = n;
	for(int i = n; i != 0; i = v[i].first){
		path.push_back(v[i].second);
		p = v[i].first;
  }
  sort(path.begin(), path.end());
	for(int i = path.size() - 1; i >= 0; --i) cout << path[i];
}

Measured memory_bytes: 512
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;

int main()
{
  int N;
  cin >> N;
  int ans = 1;
  int mx = 0;
  FOR(i,1,N+1) {
    int cnt = 0;
    int n = i;
    while(n > 0) {
      if(n % 2 == 1) break;
      n /= 2;
      cnt++;
    }
    if(cnt > mx) {
      ans = i;
      mx = cnt;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256