akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using o_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define M 1000010

int main(){
	IOS;
	ll a,b,x;cin>>a>>b>>x;
	if(x>=a and x<=a+b)cout<<"YES";
	else cout<<"NO";
	
	
	
	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++)

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> buffer;
    //reserveはstringが最適にメモリを確保できるよう、あらかじめサイズ変更の予定を指示する
    //計算量を削減できる
    buffer.reserve(h);
    rep(i,h){
        string tmp;
        cin >> tmp;
        // emplace_backは要素を追加する
        buffer.emplace_back(move(tmp));
    }
    for (int i = 0; i < 2 * h; i++){
        cout << buffer.at(i / 2) << endl;
    }

    
}

Measured memory_bytes: 256
use rand::prelude::*;

fn main() {
    let start_time = get_time();

    let mut rnd: rand::rngs::StdRng = rand::SeedableRng::from_seed([0; 32]);

    proconio::input! {
        d: usize,
        c: [i64; 26],
        s: [[i64; 26]; d],
    }

    let mut t = make_first_t(d, &c, &s);
    let mut sum_v = calc(d, &c, &s, &t).iter().sum::<i64>();

    while get_time() - start_time < 2000_000_000 - 100_000_000 {
        let dqi = (rnd.gen_range(1, d), rnd.gen_range(1, 26));
        let pret = t[dqi.0 - 1];
        t[dqi.0 - 1] = dqi.1;
        let sum_vi = calc(d, &c, &s, &t).iter().sum::<i64>();
        if sum_vi > sum_v {
            sum_v = sum_vi;
        } else {
            t[dqi.0 - 1] = pret;
        }
    }

    for di in 0..d {
        println!("{}", t[di]);
    }
}

fn get_time() -> u64 {
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    t.as_secs() * 1000_000_000 + t.subsec_nanos() as u64
}

fn make_first_t(
    d: usize,
    c: &Vec<i64>,
    s: &Vec<Vec<i64>>,
) -> Vec<usize> {
    let mut t = vec![0; 365];
    let mut last_d = vec![0; 26];
    let mut prev = 0;
    for di in 0..d {
        let mut max_v = 0;
        let mut max_i = 0;
        for i in 0..26 {
            let pre_last_di = last_d[i];
            last_d[i] = di + 1;
            let v = sum_di(di, prev, &c, &s, i + 1, &last_d);
            last_d[i] = pre_last_di;
            if v > max_v {
                max_v = v;
                max_i = i;
            }
        }
        prev = max_v;
        last_d[max_i] = di + 1;
        t[di] = max_i + 1;
    }
    t
}

fn calc(d: usize,
    c: &Vec<i64>,
    s: &Vec<Vec<i64>>,
    t: &Vec<usize>,
) -> Vec<i64> {
    let mut last_d = vec![0; 26];

    let mut prev = 0;
    let mut v = vec![0; 365];
    for di in 0..d {
        last_d[t[di] - 1] = di + 1;
        prev = sum_di(di, prev, &c, &s, t[di], &last_d);
        v[di] = prev;
    }
    v
}

fn sum_di(
    di: usize,
    prev: i64,
    c: &Vec<i64>,
    s: &Vec<Vec<i64>>,
    t: usize,
    last_d: &Vec<usize>,
) -> i64 {
    let mut v = prev + s[di][t - 1];
    for i in 0..26 {
        v -= c[i] * ((di + 1 - last_d[i]) as i64);
    }
    v
}


Measured memory_bytes: 2320
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(A):
        res = 0
        for a,b,c,d in g:
            if A[b] == A[a]+c:
                res += d
        return res
    N,M,Q = map(int,input().split())
    g = [list(map(int,input().split())) for i in range(Q)]
    #g[i][0] == ai
    for i in range(Q):
        g[i][0] -= 1  #ai -= 1
        g[i][1] -= 1  #bi -= 1
    l = [([i],i) for i in range(1,M+1)]  #[([1],1),([2],2),....,([M],M)]
    for i in range(N-1): #1個目の要素にN桁の数列を生成
        l = [(x+[j], j) for (x,y) in l for j in range(y,M+1)]
    ans = 0
    for A,_ in l:
        s = f(A)
        if ans < s:
            ans = s #得点の最大値を厳選
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 114028
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] cnt = new int[n];
		for (int i = 0; i < n; i++) {
			cnt[sc.nextInt()]++;
		}
		sc.close();

		if (n % 2 == 0) {
			for (int i = 0; i < n; i++) {
				if (i % 2 == 0) {
					if (cnt[i] != 0) {
						System.out.println(0);
						return;
					}
				} else {
					if (cnt[i] != 2) {
						System.out.println(0);
						return;
					}
				}
			}
		} else {
			if (cnt[0] != 1) {
				System.out.println(0);
				return;
			}
			for (int i = 1; i < n; i++) {
				if (i % 2 == 1) {
					if (cnt[i] != 0) {
						System.out.println(0);
						return;
					}
				} else {
					if (cnt[i] != 2) {
						System.out.println(0);
						return;
					}
				}
			}
		}

		long ans = 1;
		for (int i = 0; i < n / 2; i++) {
			ans = ans * 2 % 1000000007;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 50152
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
using namespace std;
typedef long long int ll;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, a[100010], b[100010], c[100010], i, d[100010] = {}, now = 0;
	cin >> n;
	for (i = 0; i < n; i++)cin >> a[i];
	for (i = 0; i < n; i++)cin >> b[i];
	for (i = 0; i < n; i++)cin >> c[i];
	sort(a, a + n); sort(b, b + n); sort(c, c + n);
	for (i = 0; i < n; i++) {
		while (b[i] > a[now]&&now!=n)now++;
		d[i] = now;
	}
	now = 0;
	ll ans = 0, yojo = 0;
	for (i = 0; i < n; i++) {
		while (c[i] > b[now] && now != n)yojo += d[now], now++;
		ans += yojo;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int x,y,z,k;
    cin >> x >> y >> z >> k;
    ll a[x], b[y], c[z];
    REP(i,x){
        cin >> a[i];
    }
    REP(i,y){
        cin >> b[i];
    }
    REP(i,z){
        cin >> c[i];
    }
    sort(a, a + x);
    reverse(a, a + x);
    sort(b, b + y);
    reverse(b, b + y);
    sort(c, c + z);
    reverse(c, c + z);
    vector<tuple<int, int, int>> vec;
    map<tuple<int, int, int>, bool> use;
    cout << a[0] + b[0] + c[0] << endl;
    vec.emplace_back(tuple<int, int, int>(0, 0, 0));
    use[tuple<int, int, int>(0, 0, 0)] = true;
    REP(i,k - 1){
        ll mx = 0;
        int tx, ty, tz;
        REP(j,vec.size()){
            int cx = get<0>(vec[j]), cy = get<1>(vec[j]), cz = get<2>(vec[j]);
            if(cx + 1 < x){
                if(a[cx + 1] + b[cy] + c[cz] > mx && !use[tuple<int, int, int>(cx + 1, cy, cz)]){
                    mx = a[cx + 1] + b[cy] + c[cz];
                    tx = cx + 1;
                    ty = cy;
                    tz = cz;
                }
            }
            if(cy + 1 < y){
                if(a[cx] + b[cy + 1] + c[cz] > mx && !use[tuple<int, int, int>(cx, cy + 1, cz)]){
                    mx = a[cx] + b[cy + 1] + c[cz];
                    tx = cx;
                    ty = cy + 1;
                    tz = cz;
                }
            }
            if(cz + 1 < z){
                if(a[cx] + b[cy] + c[cz + 1] > mx && !use[tuple<int, int, int>(cx, cy, cz + 1)]){
                    mx = a[cx] + b[cy] + c[cz + 1];
                    tx = cx;
                    ty = cy;
                    tz = cz + 1;
                }
            }
        }
        cout << mx << endl;
        vec.emplace_back(tuple<int, int, int>(tx, ty, tz));
        use[tuple<int, int, int>(tx, ty, tz)] = true;
    }
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
    int n,k,i;
    scanf("%d%d", &n, &k);
    double a=0;
    for(i=1;i<=n;i++){
        double b =1.0/n;
        int c =i;
        while(c<k){
            c*=2;
            b/=2;
        }
        a+=b;
    }
    printf("%.12f",a);
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
	char s[27];
	scanf("%s",s);
	int i,j,len=strlen(s),memo[26]={0};
	if(len < 26){
		for(i=0;i<len;i++)memo[s[i]-'a'] = 1;
		for(i=0;memo[i];i++);
		s[len] = 'a'+i;
		s[len+1]='\0';
		printf("%s",s);
		return 0;
	}else{
		for(i=len-1;i>=0;i--){
			memo[s[i]-'a'] = 1;
			for(j=s[i]-'a'+1;j<26&& !memo[j];j++);
			if(j<26){
				s[i] = 'a'+j;
				s[i+1] = '\0';
				printf("%s",s);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(){
    int n,ans; cin >> n;
    if (n<10) ans = n;
    else if (n<100) ans = 9;
    else if (n<1000) ans = n - 90;
    else if (n<10000) ans = 909;
    else if (n<100000) ans = n - 9090;
    else ans = 90909;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100000

typedef struct{
  int A;
  char B;
  int No;
}cards;

cards card[N];

int partition(int,int);
void quickSort(int,int);
int stateJudge(int);
main(){
  int k,r,mid,p=0;
  int i;

  scanf("%d",&k);

  for(i=0; i<k; i++){

    scanf("%s%d",&card[i].B,&card[i].A);

    card[i].No = i;
  }
  
  
  r = k-1;
  quickSort(p, r);
  
  if(stateJudge(r) == 1)printf("Stable\n");
  else printf("Not stable\n");

  
  for(i=0; i<k; i++){
    
    printf("%c %d\n",card[i].B,card[i].A);
  }
  
  return 0;
  
}


int partition(int p,int r){
  
  int i=0,j;
  cards c;
  i = p;
  
  for(j=p; j<r; j++){
    if(card[j].A <= card[r].A){
      
      c = card[i];
      card[i] = card[j];
      card[j] = c;
      i++;
    
    } 
  }
  c = card[r];
  card[r] = card[i];
  card[i] = c;
  return i;
}


void quickSort(int p,int r){
  int q;
  if(p < r){q = partition(p,r);
    quickSort(p,q-1);
    quickSort(q+1,r);
    
  }
}

int stateJudge(int r){
  int i;
  for(i=0; i<r; i++){
    
    if(card[i].A == card[i+1].A){      
      if(card[i].No > card[i+1].No)
	{
	  return 0;
	}   
    }
  }
 return 1;
}

Measured memory_bytes: 1784
import numpy as np
bisect_left = np.searchsorted
input()
a = np.int32(input().split())
b = np.int32(input().split())
ans = 0
for k in range(28, -1, -1):
    low = pow(2, k)
    high = pow(2, k + 1)
    a %= high
    b %= high
    b.sort()
    y = np.hstack((b - high, b))
    left = bisect_left(y, low - a)
    right = bisect_left(y, high - a)
    if np.sum(right - left) % 2:
        ans += low
print(ans)

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if (n == 7 || n == 5 || n == 3) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}


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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 200005;

int n;
int a[N];

bool ball[N];

int main() {

	FAST;

	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = n; i >= 1; i --) {
		int k = n / i;
		int sum = 0;
		for (int j = k; j >= 1; j --) {
			sum += ball[j * i];
		}
		sum %= 2;
		if (sum == a[i]) continue;
		else ball[i] = 1;
	}
	vector <int> ans;
	for (int i = 1; i <= n; i ++) {
		if (ball[i]) {
			ans.push_back(i);
		}
	}
	cout << ans.size() << '\n';
	for (int i : ans) {
		cout << i << ' ';
	}
	return 0;
}

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

using namespace std;

int main(void)
{
    int days;
    cin >> days;

    long long penalties[26];

    for(long long i = 0; i < 26; i++){
        long long p;
        cin >> p;
        penalties[i] = p;
    }

    vector<long long*> satis;

    for(int i = 0; i < days; i++){
        long long *sat = new long long[26];
        for(int j = 0; j < 26; j++){
            long long s;
            cin >> s;
            sat[j] = s;
        }
        satis.push_back(sat);
    }

    int lasts[26][365];

    for(int i = 0; i < 26; i++){
        for(int j = 0; j < 365; j++){
            lasts[i][j] = -1;
        }
    }

    int *selected = new int[days];
    long long satis_sum = 0;
    long long penal_sum = 0;
    for(int i = 0; i < days; i++){
        int cont;
        cin >> cont;
        cont -= 1;

        for(int j = i; j < days && lasts[cont][j] < i; j++){
            lasts[cont][j] = i;
        }
        selected[i] = cont;
        
        satis_sum += satis[i][cont];

        for(int j = 0; j < 26; j++){
            penal_sum += penalties[j] * (i - lasts[j][i]);
        }
    }

    int queries_cnt;

    cin >> queries_cnt;

    for(int i = 0; i < queries_cnt; i++){
        int day;
        int cont;
        cin >> day >> cont;
        day -= 1;
        cont -= 1;

        // process for former contest
        int former_cont = selected[day];
        satis_sum -= satis[day][former_cont];

        int former_last = -1;
        if(day > 0){
            former_last = lasts[former_cont][day - 1];
        }
        int former_next = day;
        while(lasts[former_cont][former_next] == day){
            lasts[former_cont][former_next] = former_last;
            former_next++;
        }

        long long former_reduced_penal = (former_next - day) * (day - former_last) * penalties[former_cont];

        penal_sum += former_reduced_penal;

        // process for new contest
        selected[day] = cont;
        satis_sum += satis[day][cont];

        int new_next = day;
        while(new_next < days && lasts[cont][new_next] < day){
            lasts[cont][new_next] = day;
            new_next++;
        }
        
        int new_last = -1;
        if(day > 0){
            new_last = lasts[cont][day - 1];
        }

        long long newly_reduce_penal = (new_next - day) * (day - new_last) * penalties[cont];
        penal_sum -= newly_reduce_penal;

        cout << satis_sum - penal_sum << endl;
    }

    return 0;
}

Measured memory_bytes: 3676
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def main():
    n = int(std_in())

    mod = 10 ** 9 + 7
    na = 10 ** n
    n8 = 8 ** n
    n9 = 9 ** n * 2
    print((na - n9 + n8) % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 11252
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <string>
#include <tuple>
#include <climits>
#include <cmath>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
const int INF = 987654321;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int arr[200000];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
        scanf("%d",&arr[i]);
    sort(arr,arr+n);
    ll ans = 0;
    for(int i = 0;i<n;i++){
        ans += (ll)arr[n-(i/2)-1];
    }
    printf("%lld\n",ans-arr[n-1]);

}

Measured memory_bytes: 4520
using System;

namespace B___Stone_Monument
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var a = int.Parse(input[0]);
            var b = int.Parse(input[1]);
            var c = 0;
            for (var i = 1; i <= b - a; i++)
            {
                c += i;
            }
            Console.WriteLine(c - b);
        }
    }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
#define rgi register int
#define ll long long
 
ll a,b,c,d;
inline ll solve()
{
	--a,--b,--c,--d;
	ll res=std::abs(a-c)+std::abs(b-d),t=1LL;
	for(rgi i=1;i<=33;++i) t*=3LL;
	for(rgi i=33;i>=0;--i)
	{
		for(rgi j=0;j<2;++j)
		{
			if(a/t==c/t&&(a/t)%3LL==1LL&&std::abs(b/t-d/t)!=1LL&&std::abs(b-d)>=t)
			{
				ll mn=std::min(a,c),mx=std::max(a,c);
				return res+std::min(mn-mn/t*t+1LL,(mx/t+1LL)*t-mx)*2LL;
			}
			std::swap(a,b),std::swap(c,d);
		}
		t/=3LL;
	}
	return res;
}
 
signed main()
{
	rgi q;
	std::cin>>q;
	while(q--)
	{
		std::cin>>a>>b>>c>>d;
		std::cout<<solve()<<std::endl;
	}
	return 0;
}
// ----------------------------
// by imzzy


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

using namespace std;

int main(){

  int n;
  cin >> n;
  bool can = true;

  while(n--){
    int a;
    cin >> a;

    if(a % 2 == 0){
      if(!(a%3 == 0 || a%5 == 0)){
        can = false;
      }
    }
  }
  
  if(can){
     cout << "APPROVED\n";
  }else{
     cout << "DENIED\n";
  }
 

  return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))


flag = None
count = 0
for i in range(1, N):
    if A[i] - A[i - 1] == 0:#同じとき-->なかったとして考える
        pass
    if A[i] - A[i - 1] > 0: #増加しているとき
        if flag == True: #増加中のとき-->何もしない
            pass
        elif flag == False: #減少中のとき-->フラットに戻す
            flag = None
        elif flag == None: #フラットのとき-->カウントが増えて、上昇中になる
            # print (A[i])
            count += 1
            flag = True
    if A[i] - A[i - 1] < 0:
        if flag == False:
            pass
        elif flag == True:
            flag = None
        elif flag == None:
            # print (A[i])
            count += 1
            flag = False
    # print (A[i], flag)
if flag == None:
    count += 1
print (count)


Measured memory_bytes: 15020
n = int(input())
a = list(map(int, input().split()))

abs_a = []
minuses = 0

for _a in a:
	if _a < 0:
		minuses += 1
	abs_a.append(abs(_a))

if minuses % 2 == 0:
	print(sum(abs_a))
else:
	print(sum(abs_a) - 2 * min(abs_a))

Measured memory_bytes: 14252
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);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int[] x = in.Int(5);
            for (int i = 0; i < 5; i++) {
                if (x[i] == 0) {
                    out.println(i + 1);
                }
            }
        }

    }

    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: 32564
N,K = map(int,input().split())
H = [int(input()) for i in range(N)]
H.sort()
ans = H[-1]
for i in range(N-K+1):
    min_h = H[i]
    max_h = H[i+K-1]
    dif = max_h - min_h
    if dif < ans:
        ans = dif
print(ans)

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

def func(a,b,k):
    mn = min(a,b)
    kouyaku = []
    for i in range(1,mn+1):
        if a%i==0 and b%i==0:
            kouyaku.append(i)
    
    kouyaku.sort(reverse=True)
    return kouyaku[k-1]

print(func(a,b,k))

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

signed main() {
	int N;
	cin >> N;
	string S;
	cin >>S;
	vector<int> EL(N,0);
	vector<int> ER(N,0);
	EL[0]=0;
	ER[N-1]=0;
	for(int i=1;i<N;i++){
		EL[i]+=EL[i-1];
		if(S.at(i-1)=='E')EL[i]++;
	}
	
	for(int i=N-2;i>=0;i--){
		ER[i]+=ER[i+1];
		if(S.at(i+1)=='E')ER[i]++;
	}
	int ans=1000000;
	for(int i=0;i<N;i++){
		if(i-EL[i]+ER[i]<ans)ans=i-EL[i]+ER[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 5380
#include <iostream>

int main(){
   int H, W;
   std::cin >> H >> W;
   std::string a[H];
   for(int i=0; i<H; ++i) std::cin >> a[i];

   for(int i=0; i<W+2; ++i) std::cout << "#";
   std::cout << std::endl;
   for(int i=0; i<H; ++i){
      std::cout << "#" << a[i] << "#" << std::endl;
   }
   for(int i=0; i<W+2; ++i) std::cout << "#";
   std::cout << std::endl;
   return 0;
}


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


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    ll n,a,b;
    cin>>n>>a>>b;
    if(a%2 == b%2){
        ll ans = max(a,b) - min(a,b);
        ans /= 2;
        cout << ans << endl;
        return 0;
    }
    else {
        ll ans = max(a,b)-1;
        ans = min(ans, n-min(a,b));
        ll l=a,r=b;
        l=1,r-=a-1;
        r--;
        ans = min(ans,a+(r-l)/2);
        ll cnt = n-b+1;
        a+=n-b;
        b=n;
        a++;
        ans = min(ans,cnt+(b-a)/2);
        cout << ans << endl;
        return 0;
    }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

N = n()
A = ln()

A.sort()

upper = A[N:][::-1]
print sum(upper[1::2])

Measured memory_bytes: 66012
using System;
using System.Linq;

public class Test
{
  static int n;
  static int m;
    
  public static void Main()
  {
    var inputs=Console.ReadLine().Split().Select(int.Parse).ToArray();
    n=inputs[0];
    m=inputs[1];
    
    var onceTime=m*1900+(n-m)*100;
    
    Console.WriteLine(pow(2,m)*onceTime);
  }
  
  static int pow(int b,int exp)
  {
    var result=1;
    for(var i=0;i<exp;i++)
      result*=b;
    return result;
  }
}

Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
long long dp[100010][15] = { 0 };
int main() {
	string s;
	cin >> s;
	dp[0][0] = 1;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '?') {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 13; k++) {
					dp[i + 1][(j + k * 10) % 13] = (dp[i + 1][(j + k * 10) % 13] + dp[i][k]) % 1000000007;
				}
			}
		}
		else {
			int x = s[i] - '0';
			for (int j = 0; j < 13; j++) {
				dp[i + 1][(x + j * 10) % 13] = (dp[i + 1][(x + j * 10) % 13] + dp[i][j]) % 1000000007;
			}
		}
	}
	cout << dp[s.size()][5] << endl;
	return 0;
}


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

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

    vector<int> v(n);
    vector<int> c(n);
    for(int i=0; i<n; i++) cin >> v[i];
    for(int i=0; i<n; i++) cin >> c[i];
    int value = 0;

    for(int i=0; i<n; i++) {
        if(v[i] > c[i]) {
            value += v[i]-c[i];
        }
    }
    cout << value << endl;
}



Measured memory_bytes: 3548
function reverse(a){
  return a === 0 ? 1 : 0;
}

function Main(input) {
  const tmp = input.split("\n")[0].split(" ").map((v) => (parseInt(v)));
  const h = tmp[0];
  const w = tmp[1];
  const a = tmp[2];
  const b = tmp[3];

  const ans = [...Array(h).keys()].map((v) => v < b ? 0 : 1).map((v) => {
    return [...Array(w).keys()].map((x) => x < a ? v : reverse(v))
  })

  console.log(ans.map((v) => v.join("")).join("\n") + "\n");
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 51980
#include<stdio.h>
int main(void){
	int a,b;
	scanf("%d %d",&a,&b);
	if(a>b){
		printf("a > b\n");
	}else if(a == b){
		printf("a == b\n");
	}else printf("a < b\n");
	return 0;
}

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

int main(){
  int n,x; cin>>n >>x;
  int D[n+1];
  D[0]=0;
  for(int i=1;i<n+1;i++){
    int l; cin>>l;
    D[i]=D[i-1]+l;
    if(D[i]>x){
      cout<<i<<endl;
      break;
    }
    if(i==n&&D[i]<=x){
      cout<<n+1<<endl;
      break;
    }
  }
}

Measured memory_bytes: 256
package main

import "fmt"

const mod = 1000000007

var (
	n, k int
	c    [][]int
)

func initCmb() {
	max := n - k + 1
	if v := k - 1; v > max {
		max = v
	}

	c = make([][]int, max+1)
	for i := range c {
		c[i] = make([]int, i+1)
		c[i][0], c[i][len(c[i])-1] = 1, 1
		for j := 1; j < len(c[i])-1; j++ {
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod
		}
	}
}

func cmb(a, b int) int {
	if b > a {
		return 0
	}
	return c[a][b]
}

func main() {
	fmt.Scan(&n, &k)

	initCmb()
	for i := 1; i <= k; i++ {
		fmt.Println(cmb(n-k+1, i) * cmb(k-1, i-1) % mod)
	}
}


Measured memory_bytes: 18432
#include "atcoder/all"
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using namespace atcoder;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VV(T, a, b, c) vector<vector<T>>(a, vector<T>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define VVV(T, a, b, c, d)                                                     \
  vector<vector<vector<T>>>(a, vector<vector<T>>(b, vector<T>(c, d)))
#define SP(a) fixed << setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ll op(ll a, ll b) { return max(a, b); }

ll e() { return 0; }

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll N, K;
  cin >> N >> K;
  vl A(N);
  REP(i, N) cin >> A[i];
  vl B(3e5 + 10, 0);
  segtree<ll, op, e> seg(B);
  REP(i, N) {
    ll po = seg.prod(max(0LL, A[i] - K), min((ll)(3e5 + 5), A[i] + K + 1));
    seg.set(A[i], po + 1);
  }
  cout << seg.prod(0, 3e5 + 6) << endl;

  return 0;
}


Measured memory_bytes: 16152
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    double ar[n];
    double s=0;
    for(int i=1;i<=n;i++){
        scanf("%lf",&ar[i]);
         s+=(1/ar[i]);
        }
     double m=1/s;
    printf("%lf\n",m);
        
}

Measured memory_bytes: 256
N,X = map(int,input().split())
x = list(map(int,input().split()))

x.sort()

def gcd(x,y):
    X = max(x,y)
    Y = min(x,y)
    if Y == 0:
        return X
    else:
        return gcd(Y,X%Y)

keepgcd = 0
maxgcd = 10**9

if N >= 2:
   for i in range(N-1):
       keepgcd = gcd(abs(X-x[i+1]),abs(X-x[i]))
       if maxgcd > keepgcd:
          maxgcd = keepgcd
   print(maxgcd)
else:
    print(max(x[0],X)-min(x[0],X))

Measured memory_bytes: 14252
import scala.io.StdIn._
object Main extends App {
  val n = readInt
  var map = Map('M' -> 0l, 'A' -> 0l, 'R' -> 0l, 'C' -> 0l, 'H' -> 0l)
  for (_ <- 1 to n) {
    val c = readLine()(0)

    map.get(c) match {
      case Some(i) => map = map + (c -> (i + 1))
      case None    =>
    }
  }

  val res = "MARCH".toSeq.combinations(3).foldLeft(0l) { (acc, s) =>
    acc + (map(s(0)) * map(s(1)) * map(s(2)))
  }
  println(res)
}


Measured memory_bytes: 37468
n, l=map(int,input().split())
f = [l+i for i in range(n)]
ans = 0
if l >= 0 :
    ans = sum(f) - f[0]
elif n + l - 1 < 0 :
    ans = sum(f) - f[n-1]
else :
    ans = sum(f)
print(ans)

Measured memory_bytes: 3060
def digits_sum(n):
    st = str(n)
    ans = 0
    for s in st:
        ans += int(s)

    return ans

N = int(input())

if N % 10 == 0:
    a = N//2
else:
    a = N % 10

b = N - a

print(digits_sum(a) + digits_sum(b))


Measured memory_bytes: 2940
//Heaplax
//别让自己后悔
#include<bits/stdc++.h>
#define LL long long
#define LOG(x) cerr<<#x<<" = "<<x<<endl
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;
}
using namespace std;
int x,y;
int main()
{
	re(x),re(y);
	if(y>0)
	{
		if(x<y)
		{
			if(x>=0)printf("%d\n",y-x);
			else printf("%d\n",abs(y+x)+1);
		}
		else if(x>y)printf("%d\n",x-y+2);
	}
	else
	{
		if(x<y)printf("%d\n",y-x);
		else if(x<0 && x>y)printf("%d\n",x-y+2);
		else printf("%d\n",abs(-x-y)+1);
	}

}


Measured memory_bytes: 256
def judge(D):
  n = 0
  while D%4==0:
    n += 1
    D //= 4

  return (lambda x,y: ~((x>>n)^(y>>n))&1) if D%2==1 else (lambda x,y: ~(x>>n)&1)

N,D1,D2 = map(int,input().split())
j1,j2 = judge(D1),judge(D2)
for _,(x,y) in zip(range(N*N),filter(lambda p: j1(*p) and j2(*p), ((x,y) for x in range(N*2) for y in range(N*2)))):
  print(x,y)

Measured memory_bytes: 4280
import math
a, b, d = map(float, input().split())
h = b * math.sin(d*math.pi/180)
s = a * h / 2
l = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(d*math.pi/180)) + a + b
print(s)
print(l)
print(h)


Measured memory_bytes: 5696
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef long long llint;
typedef vector<long long int> vint;
typedef vector< vector<int> > vvint;
typedef vector<string> vstr;


int main(void) {
	llint A, B, T,ans;
	ans = 0;
	cin >> A >> B >> T;
	for (int i = 1; i <= T; i++) {
		if (i%A == 0)ans += B;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
typedef long long ll;
using namespace std;

int main(){
    ll n,q;
    cin >> n >> q;
    vector<ll> in[n];
    vector<ll> ans(n);
    for(int i=0;i<n;i++){
        ans[i] = 0;
    }
    for(int i=0;i<n-1;i++){
        ll a,b;
        cin >> a >> b;
        a--;b--;
        in[a].push_back(b);
        in[b].push_back(a); 
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<in[i].size();j++){
            cout << in[i][j] << " ";
        }
        cout << endl;
    }*/

    for(int i=0;i<q;i++){
        ll p,x;
        cin >> p >> x;
        p--;
        ans[p] += x;
        //cout << "a" << endl;
    }

    queue <ll> queue;
    queue.push(0);
    bool visited[n];
    for(int i=0;i<n;i++){
        visited[i] = false;
    }
    while(!queue.empty()){
        ll now = queue.front();
        //cout << "now=" <<now << endl; 
        queue.pop();
        visited[now] = true;
        for(int i=0;i<in[now].size();i++){
            //cout << in[now][i] << endl;
            if(visited[in[now][i]]){
                continue;
            }
            queue.push(in[now][i]);
            ans[in[now][i]] += ans[now];
        }
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 18160
#include <iostream>
#include <vector>
#include <string>

using namespace std;



int main(){
	int N; string S;
	while(cin >> N >> S){
		vector<int> v(N);
		bool find = false;
		for(int i=0;i<2;i++){
			if(find) break;
			for(int j=0;j<2;j++){
				if(find) break;
				v[0] = i;
				v[1] = j;
				v[2] = ((j==0 && S[1]=='o')||(j==1&&S[1]=='x')) ? i : 1-i;
				for(int k=2;k<N;k++){
					v[k] = (v[k-1]==0 ? S[k-1]=='o' : S[k-1]=='x') ? v[k-2] : 1-v[k-2];
				}
				bool valid = true;
				for(int k=N-1;k<=N;k++){
					if(v[k%N]==0){
						valid &= (S[k%N] == (v[(k-1)%N]==v[(k+1)%N] ? 'o' : 'x'));
					} else {
						valid &= (S[k%N] == (v[(k-1)%N]==v[(k+1)%N] ? 'x' : 'o'));
					}
				}
				if(valid){
					for(int k=0;k<N;k++){
						cout << char(v[k]==0 ? 'S' : 'W');
					}
					cout << endl;
					find = true;
				}
			}
		}
		if(!find) cout << -1 << endl;
	}
}


Measured memory_bytes: 1024
def main(inputs):
    outputs = ''
    dict = {}
    pics = ['S', 'H', 'C', 'D']
    for p in pics:
        dict[p] = list(map(int, range(1, 14)))
    for input in inputs:
        parsed = input.split()
        pic = str(parsed[0])
        num = int(parsed[1])
        dict[pic].remove(num)
    for p in pics:
        for n in dict[p]:
            outputs += '{} {}\n'.format(p, n)
    return outputs


if __name__ == "__main__":
    n = int(input())
    inputs = [input() for i in range(n)]
    print(main(inputs), end='')



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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string a;
  cin >> n >> a;
  map<int,int> mp;
  for (int i = 0; i < n; i++) {
    mp[a[i]]++;
  }
  int ans = 1;
  const int mod = 1e9 + 7;
  for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
    ans = (1LL * ans * (it->second + 1)) % mod;
  }
  cout << ans - 1 << '\n';
  return 0;
}

Measured memory_bytes: 512
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

n =int(input())
a = [int(i) for i in input().split()]
answer = 0
asum = a[0]
xsum = a[0]
r=0
for l in range(0,n):
    while r < n-1:
        asum = asum + a[r+1]
        xsum = xsum ^ a[r+1]
#        print("sum",asum,xsum)
        if asum == xsum:
            r += 1
        else:
            asum = asum - a[r+1]
            xsum = xsum ^ a[r+1]
            break
#    print(l,r)
#    print(answer)
    answer += (r-l + 1)
    asum = asum - a[l]
    xsum = xsum - a[l]

print(answer)


Measured memory_bytes: 34136
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
int a[N],b[N],c[N];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);

    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);

    LL res=0;
    LL ja=0,jc=0;
    for(int i=1;i<=n;i++){
        while(a[ja+1]<b[i]&&ja+1<=n)//满足a[i]<b[i]的个数
            ja++;
        while(c[jc+1]<=b[i]&&jc+1<=n)//不满足b[i]<c[i]的个数
            jc++;
        res+=ja*(n-jc);
    }
    printf("%lld\n",res);

    return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

const int INF = 1e8;
const int MAX = 105;

int dr[MAX]; //dr[????????¨?±??????????] = ?????????bit???????????????
int v[MAX][MAX];
int n, m, k;

bool getBit(int num, int i){
    return ((num & (1 << i)) != 0);
}

int moveto(int v[MAX], int num){
    //show(num)
    int ret = 0;
    //cout << "---------" << num << endl;
    rep(i,n){
        //????????¨?±???????????§??????§??????
        //????????¨?±????bit???1??§??????
        //?§?????????????????????¨?±???§??????
        if(dr[i] != INF && getBit(num,dr[i]) && dr[v[i]] != INF){
            ret |= 1 << dr[v[i]];
        }
    }
    //show(ret)
    return ret;
}

int bfs(){
    int dis[1 << m]; //?????¢
    queue<int> q; //?¨??????????????????\??????
    rep(i,1 << m) dis[i] = INF;

    dis[(1 << m) - 1] = 0;
    q.push((1 << m) - 1);

    int u;
    while(!q.empty()){
        u = q.front(); q.pop();
        if(u == 0) continue;
        rep(i,k){
            //show(i)
            int tmp = moveto(v[i], u);
            //if(tmp == 0){ show(u) show(i) }
            if(dis[tmp] > dis[u] + 1){
                dis[tmp] = dis[u] + 1;
                q.push(tmp);
            }
        }
    }
    return dis[0];
}

int main(){
    int cnt = 0;
    cin >> n >> m >> k;
    rep(i,MAX) dr[i] = INF;
    rep(i,m) {
        int d;
        cin >> d;
        d--;
        dr[d] = cnt++;
    }

    rep(i,n){
        rep(j,k){
            cin >> v[j][i]; //v[j] := j???????????????????????????????§???????
            v[j][i]--;
        }
    }

    cout << bfs() << endl;
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
const long long mod = pow(10, 9) + 7;
const long long INF = 1LL << 60;
template <class T> bool chmin(T& a, T b){if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b){if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, int B) {return (A + (B - 1)) / B;}
long long divCeil(int A, long long B) {return (A + (B - 1)) / B;}
long long divCeil(long long A, long long B) {return (A + (B - 1)) / B;}

int main()
{
  int N;
  cin >> N;
  
  int sum = 0;
  int max = 0;
  for (int i = 0; i < N; i++)
  {
    int L;
    cin >> L;
    chmax(max, L);
    sum += L;
  }
  
  string ans = "No";
  if (max < sum - max) ans = "Yes";
  
  cout << ans << endl;
}

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


int compare_int(const void *a, const void *b)
{
//    return *(int*)a - *(int*)b;
    return *(long long*)a - *(long long*)b;
}
//  qsort(A, b, sizeof(int), compare_int);

//long long  factorial(long long n) {
//    if (n > 0) {
//        return n * factorial(n - 1);
//    } else {
//        return 1;
//    }
//}
long long  factorial(long long n, long long depth) {
    if (n > 1) {
        depth++;
        return factorial(n / 2, depth);
    } else {
        return depth;
    }
}

int min(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

int distance(int a, int b) {
  return abs(a-b)*abs(a-b);
}



//int ()
/*
int triangle(int a, int b, int c){
  if(a<b+c){
    if(b<c+a){
      if(c<a+b){
        printf("1\n");
        return 1;
      }
    }
  }
  printf("1\n");
  return 0;
}
*/

int main()
{
//  int  a ,b, c, d, e, X, Y ,r;
  long long  a, b, c, d, e, X, Y;
  //  double  c;
 long long  A[200003]={};
//  int  A[100003]={};
  int  B[100003]={};
  long long  C[100003][100001]={};

  int  flg=0;

//  char s[101][101]={};
  char s[100001]={};
  char t[100001]={};
//  int N, M;
//  int A[1000000001]={};
//  long long  C[101]={};
  int i,j,k;
  long long p=0,q=0;
//  int flag=0;
//  int tmp=0;
//  char tmp[101]={};
//  long long min=10000000000;
//  long long min=100000001;
  int min =100000001;
  int len=0;
  int l=0;
//  int r=1000001;
  int cnt=0;
  int num=0;
  int num1=0;
  int num2=0;
  int ans=0;
  int ans_ac=0;
  int ans_wa=0;
  int max=0;
  long long sum=0;
  int addr=0;
  int ptn=0;
  int  tmp=0;
  double per=0; 
//  bool on_off[100]={};
  
//  char alp[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

  //  a=0;
  scanf("%lld %lld", &a, &b);
  for(i=0;;i++){
    if(a<pow(b,i)) break;

  }
    printf("%d\n", i); 
  
return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
#define adrep(i,s,n) for (int i=(s);i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
vector<pint> A;
bool cmp(pint a, pint b) { return a.second < b.second; }

int main(){

 
  int N,M;
  cin>>N>>M;
  A.resize(M);
  rep(i,M){

    cin>>A[i].first>>A[i].second;    

  }
  sort(A.begin(),A.end(),cmp);
  
  int ans=0;
  int endtime=0;
  
  rep(i,M){


    if(A[i].first>=endtime){
    
      endtime=A[i].second;
      ans++;
    }
    
  }

  cout<<ans<<endl;
  
}


Measured memory_bytes: 1024
#include <string>
#include <iostream>
#include <set>

using namespace std;

int comp(string a, string b){
    int x = a.length() - b.length();
    if(x!=0){
        return x;
    }
    for(int i=0; i<a.length();i++){
        int x = a.c_str()[i] - b.c_str()[i];
        if(x!=0){
            return x;
        }
    }
    return 0;
}

int main(){
    int n, m;
    cin >> n >> m;
    set<int> a;
    for(int i=0;i<m;i++){
        int x;
        cin >> x;
        a.insert(x);
    }

    int cst[] = {2,5,5,4,5,6,3,7,6}; 

    string s[n+1];
    for(int i=0;i<=n;i++){
        s[i] = "";
    }

    for(int i=0;i<=n;i++){
        if(i>0&&s[i].length()==0){
            continue;
        }
        for(int j: a){
            if(i+cst[j-1]<=n){
                if(comp(s[i]+to_string(j), s[i+cst[j-1]]) >= 0){
                    s[i+cst[j-1]] = s[i]+to_string(j);
                }
            }
        }
    }
    cout << s[n] << endl;
    
    // for(int i=0;i<=n;i++){
    //     cout << i <<" " << s[i] << endl;    
    // }
    return 0;
}



Measured memory_bytes: 33024
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

Q = int(input())
C = []
for i in range(Q):
    v, d, c = map(int, input().split())
    C.append((v - 1, d, c))
dp = [[0, -1] for i in range(N)]


def paint(v, d, c):
    x, y = dp[v]
    if d <= y:
        return
    if x == 0:
        dp[v] = c, d
    else:
        dp[v] = x, d

    if d == 0:
        return
    for i in G[v]:
        paint(i, d - 1, c)


for v, d, c in reversed(C):
    paint(v, d, c)

for k in dp:
    print(k[0])

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

using namespace std;

int main()
{
   int n,i,j;
   cin>>n;
   int h[n],dp[n];
   memset(dp,INT_MAX,n);
   for(i=0;i<n;i++)
   {
     cin>>h[i];
   }
   dp[0] = 0;
   dp[1] = (int)fabs(h[1]-h[0]);
  for(i=2;i<n;i++)
  {
    dp[i] = min(dp[i-1]+(int)fabs(h[i]-h[i-1]),dp[i-2]+(int)fabs(h[i]-h[i-2]));
  }
  cout<<dp[n-1];

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>
#include <cfloat>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
typedef long long int          ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Point {
    double x, y;
};

typedef Point Vector;

struct Segment {
    void set(double x1, double y1, double x2, double y2) {
        p1.x = x1;
        p1.y = y1;
        p2.x = x2;
        p2.y = y2;
    }
    Point p1, p2;
};

typedef Segment Line;

int func(double x1, double y1, double x2, double y2, double xp, double yp) {
    double naiseki, norm1, norm2, gaiseki;
    norm1   = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    norm2   = sqrt((xp - x1) * (xp - x1) + (yp - y1) * (yp - y1));
    naiseki = (xp - x1) * (x2 - x1) + (yp - y1) * (y2 - y1);
    gaiseki = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1);
    if (gaiseki > EPS) {
        return 1;
    } else if (gaiseki < -EPS) {
        return -1;
    }
    if (naiseki < -EPS) {
        return 2;
    }

    if (norm1 < norm2) {
        return -2;
    }
    return 0;
}

double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }

double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }

Point calc_minus(Point a, Point b) {
    Point ret;

    ret.x = a.x - b.x;
    ret.y = a.y - b.y;

    return ret;
}

double calc_len(Vector a) { return sqrt(a.x * a.x + a.y * a.y); }

double getDistanceLP(Line l, Point p) {
    return fabs(cross(calc_minus(l.p2, l.p1), calc_minus(p, l.p1)) /
                calc_len(calc_minus(l.p2, l.p1)));
}

double getDistanceSP(Segment s, Point p) {
    if (dot(calc_minus(s.p2, s.p1), calc_minus(p, s.p1)) < 0.0)
        return calc_len(calc_minus(p, s.p1));
    if (dot(calc_minus(s.p1, s.p2), calc_minus(p, s.p2)) < 0.0)
        return calc_len(calc_minus(p, s.p2));
    return getDistanceLP(s, p);
}

double getDistance(Segment s1, Segment s2) {
    return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
               min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
}

int main() {
    double x1, x2, x3, x4, y1, y2, y3, y4;
    int    q;
    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3,
              &x4, &y4);

        if (func(x1, y1, x2, y2, x3, y3) * func(x1, y1, x2, y2, x4, y4) <= 0 &&
            func(x3, y3, x4, y4, x1, y1) * func(x3, y3, x4, y4, x2, y2) <= 0) {
            printf("0.0000000000\n");
            continue;
        }

        Segment s1, s2;
        s1.set(x1, y1, x2, y2);
        s2.set(x3, y3, x4, y4);

        printf("%.10lf\n", getDistance(s1, s2));
    }

    return 0;
}



Measured memory_bytes: 3248
import heapq


def int_and_reverse(num):
    return int(num) * -1


N, M = map(int, input().split())
Alist = list(map(int_and_reverse, input().split()))
heapq.heapify(Alist)
for _ in range(M):
    x = (heapq.heappop(Alist) * -1) // 2
    heapq.heappush(Alist, -x)
print(-sum(Alist))


Measured memory_bytes: 14180