akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

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; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout << "Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
 
typedef long long ll;
typedef pair<int,int> P;
//typedef long long T;
const int INF = 2000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
int main(){
    int n;
    std::cin >> n;
    std::vector<ll>a(n),b(n) ;
    rep(i,n)std::cin >> a[i]>>b[i];
    ll c=0;
    irep(i,n){
        a[i]+=c;
        ll d=b[i]-(a[i]%b[i]);
        if(d==b[i])d=0;
        c+=d;
        //std::cout <<i <<" "<< d << std::endl;
    }
    std::cout << c << std::endl;
}

Measured memory_bytes: 1792
mod = 998244353


N, M, K = map(int, input().split())

power_cache = {}
power_cache[(M-1, 0)] = 1
for i in range(N-1):
    power_cache[(M-1, i+1)] = (power_cache[(M-1, i)]*(M-1)) % mod


def power(x, y):
    return power_cache[(x, y)]


combination_cache = {}
combination_cache[(N-1, 0)] = 1
for i in range(0, K+1):
    i_plus_inverse = pow(i+1, mod-2, mod)
    combination_cache[(N-1, i+1)] = (combination_cache[(N-1, i)
                                                       ]*(N-1-i)*i_plus_inverse) % mod


def combination(n, r):
    return combination_cache[(n, r)]


ans = 0
for i in range(0, K+1):
    ans += M*combination(N-1, i)*power(M-1, N-1-i)
    ans %= mod

print(ans)


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

int main() {
  int h, w; cin >> h >> w;
  vector<vector<string>> s(h, vector<string>(w));
  
  rep(i, h) {
    rep(j, w) {
      cin >> s[i][j];
    }
  }
  int i, j;
  for (i = 0; i < h; i++) {
    for (j = 0; j < w; j++) {
      if (s[i][j] == "snuke") {
        printf("%c%d\n", (char)j+'A', i+1);
        return 0;
      }
    }
  }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

int main(){
  int n;
  cin>>n;
  vector<int>h(n);
  rep(i,n)cin>>h[i];
  vector<int>dp(n,INF);
  dp[0]=0;
  rep(i,n){
    if(i+1<n){
      dp[i+1]=min(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
    }
    if(i+2<n){
      dp[i+2]=min(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
    }
  }
  cout<<dp[n-1]<<endl;
  return(0);
}

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

using namespace std;

string S;

int f(int x) {
    int curt = x;
    int res = 0;

    for (char i : S) {
        if (i - '0' != curt) ++res;
        curt = 1 - curt; //0と1の切り替え
    }
    return res;
}

int main() {
    cin >> S;

    cout << min(f(0), f(1)) << endl;
    return 0;
}


Measured memory_bytes: 512
import math
N=int(input())
A=list(map(int,input().split()))

A.sort()

K=math.floor(N/2)

S=sum( A[K:N] ) *2

if(N%2==0):
  print(S-A[N-1])
else:
  print(S-A[N-1]-A[K])

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

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :
			x((x % mod + mod) % mod) {
	}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod)
			x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod)
			x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		return mint(*this) += a;
	}
	mint operator-(const mint a) const {
		return mint(*this) -= a;
	}
	mint operator*(const mint a) const {
		return mint(*this) *= a;
	}
	mint pow(ll t) const {
		if (!t)
			return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1)
			a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return *this *= a.inv();
	}
	mint operator/(const mint a) const {
		return mint(*this) /= a;
	}
};
istream& operator>>(istream &is, const mint &a) {
	return is >> a.x;
}
ostream& operator<<(ostream &os, const mint &a) {
	return os << a.x;
}

ll sum(ll l, ll r) {
  return (l+r)*(r-l+1)/2;
}

int main() {
	int N, K;
	cin >> N >> K;
	mint cnt;
	for (int i = K; i <= N + 1; i++) {
		ll l = sum(0,i-1), r = sum(N-i+1,N);
		cnt += r-l+1;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3584
#include <iostream>

using namespace std;

int main() {
  int N;
  int A[100];
  
  cin >> N;
  for (int i=0; i<N; i++) cin >> A[i];
  
  for (int i=0; i<N; i++) {
    int v = A[i];
    
    int j;
    for (j = i-1; j >= 0 && A[j] > v; j--) A[j+1] = A[j];

    A[j+1] = v;
    for (int k=0; k<N; k++) {
      cout << A[k];
      if (k != N-1) cout << " ";
    }
    cout << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3088
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    for i in range(1, V+1):
        for (u, v) in G.keys():
            if d[v] > d[u] + G[u, v]:
                d[v] = d[u] + G[u, v]
                if i == V:
                    return 0
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = {}
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[(s, t)] = w
d = sp(G, R, V)
if d == 0:
    print('NEGATIVE CYCLE')
else:
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

Measured memory_bytes: 8656
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;
using ll = long long int;
using ld = long double;
using pll = pair<ll,ll>;
using vll = vector<ll>;

const ll maxs = 1e5+5;
const ll mod = 1e9+7;

int main()
{
	IOS;
	
	int t=1;
	//cin >> t;
	while(t--) {
		int h,a;
		cin >> h >> a;
		cout << (int)ceil(h/(double)a);
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll,ll>
#define P push
#define R return
#define C continue
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define SI size()
#define F first
#define S second
#define B begin()
#define E end()
#define W while
using namespace std;
long long MOD=1e9+7;
long long INF=1e16+7;
ll dp[43][403][403];
int main()
{
    for(int i=0;i<=40;i++){
        for(int j=0;j<=400;j++){
            for(int k=0;k<=400;k++){
                dp[i][j][k]=INF;
            }
        }
    }
    for(int i=0;i<=40;i++)
        dp[i][0][0]=0;
    ll n,x,y;
    cin>>n>>x>>y;
    for(int k=1;k<=n;k++){
        ll a,b,c;
        cin>>a>>b>>c;
        for(int i=0;i<=400;i++){
            for(int j=0;j<=400;j++){
                dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][j]);
                if((i+a)>400)C;
                if((j+b)>400)C;
                dp[k][i+a][j+b]=min(dp[k][i+a][j+b],dp[k-1][i][j]+c);
            }
        }
    }
    ll res=INF*50;
    for(int i=1;i<=400;i++){
        if((i*x)>400||(i*y)>400)break;
        res=min(res,dp[n][i*x][i*y]);
    }
    if(res>=INF)cout<<-1;
    else
    cout<<res;
    return 0;
}


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

using namespace std;


//problem_A
int main(){
    string s;
    cin >> s;
    if (s == "ABC"){
        cout << "ARC" << endl;
    }
    else{
        cout << "ABC" << endl;
    }
}


Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll aa , bb;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->aa - ((fr*)q)->aa;}
/*aのb進数時の桁数*/
ll digits(ll a, ll b){return a/b?1+digits(a/b,b):1;}
/*nをa進数にしたときの、i桁目の数*/
ll a_base2(ll n, ll a, ll i){return i==1?n%a:a_base2(n/a,a,i-1);}

ll RUNRUN[100001];
void runrun(){
    ll a=1,i=1,ok=1;
    while(i<100001){
        ll dig=digits(a,10);
        rep(j,1,dig){
            ll b=a_base2(a,10,j+1), c= a_base2(a,10,j);
            if(ABS(b-c)>1){
                if(b<c){
                    a+=POW(10,j);
                    rep(k,1,j+1){
                        a-=a_base2(a,10,k)*POW(10,k-1);
                    }
                    ok=0;
                    break;
                }
                a+=(b-c-1)*POW(10,j-1);
                ok=2;
                break;
            }
            if(j==dig-1) ok=1;
        }
        // printf("%lld %lld %lld\n",a,ok,i);
        if(ok==1){
            RUNRUN[i]=a;
            a++;
            i++;
        }
    }
}

int main(void){
    // char ;
    ll k;
    scanf("%lld",&k);
    // rep(i,0,n){
    //     scanf("%lld",&[i]);
    // }
    runrun();
    // rep(i,1,k+1){
    //     printf("%lld %lld\n",i,RUNRUN[i]);
    // }
    printf("%lld\n",RUNRUN[k]);
    return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w, k; cin >> h >> w >> k;
    vector<string> s(h); rep (i, h) cin >> s[i];
    int ans = 100000;
    rep (i, (1 << (h - 1))) {
        // 1なら割る
        int count = 0; rep (j, h) count += ((i & (1 << j)) != 0);
        vector<vector<int> > x;
        int tmp = count;
        rep (j, w) {
            vector<int> xtmp;
            int t = 0;
            rep (l, h) {
                if (s[l][j] == '1') t++;
                if ((i & (1 << l))) {
                    xtmp.push_back(t);
                    t = 0;
                }
            }
            xtmp.push_back(t);
            x.push_back(xtmp);
        }
        for (auto a : x) {
            for (auto b : a) {
                eprintf("%d ", b);
            }
            eprintf("\n");
        }
        vector<int> z(count + 1);
        bool breaked = false;
        rep (j, w) {
            rep (l, (int)x[0].size()) {
                if (x[j][l] > k) {
                    eprintf("break\n");
                    breaked = true;
                    l = x[0].size(); j = w;
                    break;
                }
            }
            if (j == w) break;
            bool flg = false;
            rep (l, count + 1) {
                z[l] += x[j][l];
                if (z[l] > k) flg = true;
                eprintf("%d ", z[l]);
            }
            eprintf("\n");
            if (flg) {
                eprintf("cut: %d\n", j - 1);
                tmp++;
                rep (l, count + 1) z[l] = x[j][l];
            }
        }
        if (!breaked) {
            chmin(ans, tmp);
            eprintf("tmp: %d\n", tmp);
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
void swap(int *x,int *y)
{
  int a;
  a=*x;
  *x=*y;
  *y=a;
}
  
int main(){
  int x,y,r;
  scanf("%d%d",&x,&y);
  if(x<y)swap(&x,&y);
  while(y>0){
    r=x%y;
    x=y;
    y=r;
  }
  printf("%d\n",x);
  return 0;
}

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] str = Console.ReadLine().Split(' ');
            int[] num = Array.ConvertAll(str, new Converter<string, int>(s => int.Parse(s)));
            int swap = 0;
            int p1 = 0, p2 = 0;

            for(int i=0;i<n;i++)
            {
                p1 = p2;
                for (int j = n - 1; j > p1; j--)
                    if (num[j - 1] > num[j]) { int tmp = num[j];num[j] = num[j - 1];num[j-1] = tmp; swap++; p2 = j; }
                if (p1 == p2) break;
            }

            str = Array.ConvertAll(num, new Converter<int, string>(k => k.ToString()));
            Console.WriteLine(string.Join(" ",str));
            Console.WriteLine(swap);
        }
    }
}

Measured memory_bytes: 9036
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;
const long long mod=1000000007;
const long long inf=1ll<<61;
int a[100006];

int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}

signed main(){
  int n,k;cin>>n>>k;
  rep(i,n)cin>>a[i];
  sort(a,a+n);
  int g=a[0];
  rep(i,n-1)g=gcd(g,a[i+1]);
  if(k<=a[n-1]&&(a[n-1]-k)%g==0)cout<<"POSSIBLE"<<endl;
  else cout<<"IMPOSSIBLE"<<endl;
}

Measured memory_bytes: 4360
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

int *leftArray;
int *rightArray;

int cnt;

void merge(int *array, int left, int center, int right) {
    int pl, pr, pa;

    for(pa = left, pl = 0; pa <= center; pa++, pl++) {
        leftArray[pl] = array[pa];
    }

    for(pa = center + 1, pr = 0; pa <= right; pa++, pr++) {
        rightArray[pr] = array[pa];
    }

    int lLen = pl;
    int rLen = pr;
    for(pl = 0, pr = 0, pa = left; pl < lLen && pr < rLen; pa++) {
        array[pa] = (leftArray[pl] < rightArray[pr]) ? leftArray[pl++] : rightArray[pr++];
        cnt++;
    }

    while(pl < lLen) {
        array[pa++] = leftArray[pl++];
        cnt++;
    }

    while(pr < rLen) {
        array[pa++] = rightArray[pr++];
        cnt++;
    }
}

void _mergeSort(int *array, int left, int right) {
    if(left < right) {
        int center = (left + right) / 2;

        _mergeSort(array, left, center);
        _mergeSort(array, center + 1, right);

        merge(array, left, center, right);
    }
}   

bool mergeSort(int *array, int n) {
    if((leftArray = malloc(n * sizeof(int))) == NULL) {
        return false;
    }
    if((rightArray = malloc(n * sizeof(int))) == NULL) {
        free(leftArray);
        return false;
    }

    _mergeSort(array, 0, n - 1);

    free(leftArray);
    free(rightArray);
    return true;
}

bool initArray(int **array, int n) {
    if((*array = malloc(n * sizeof(int))) == NULL) {
        return false;
    }

    return true;
}

void printArray(int *array, int n) {
    for(int i = 0; i < n;) {
        printf("%d", array[i]);
        i++;
        if(i < n) {
            printf(" ");
        }
    }
    printf("\n");
}
int main(void) {
    int *array;
    int n;

    scanf("%d", &n);
    
    initArray(&array, n);

    for(int i = 0; i < n; i++) {
        scanf("%d", &array[i]);
    }

    mergeSort(array, n);

    printArray(array, n);

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

    free(array);
    return 0;
}


Measured memory_bytes: 5496
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n,ans,a[2001];
inline int read(){
	char ch=getchar();
	int o=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		o=(o<<3)+(o<<1)+(ch^48);
		ch=getchar();
	}
	return o;
}
int main(){
	n=read();
	for(register int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+1+n);
	for(register int i=1;i<=n;i++){
		for(register int j=i+1;j<=n;j++){
			for(register int k=j+1;k<=n;k++){
				if(a[i]+a[j]>a[k]&&a[j]+a[k]>a[i]&&a[i]+a[k]>a[j])++ans;
				else break;
			}
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#include<iostream>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define VI vector<int>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=1000005;
char ch[MAXN];int len;
int val[MAXN],rmx[MAXN];
int calculate(int lim)
{
	for(int i=1;i<=len;i++)
	{
		if(ch[i]=='1')val[i]=1;else val[i]=-1;
		val[i]+=val[i-1];
	}rmx[len+1]=-1e9;
	for(int i=len;i>=1;i--)rmx[i]=val[i],chkmax(rmx[i],rmx[i+1]);
	int ret=0;
	for(int i=1,sum=0,S=0;i<=len;i++)
	{
		if(ch[i]=='1')++S;
		else if(ch[i]=='0')--S;
		else
		{
			if(rmx[i]+sum+2<=lim)sum+=2,++S;
			else --S;
		}chkmin(ret,S);
	}return ret;
}
int main()
{
	#ifdef Rose
		double BeginJudgeTime=clock();
	#endif
	scanf("%s",ch+1);len=strlen(ch+1);
	int mxp=0;
	for(int i=1,S=0;i<=len;i++)
	{
		if(ch[i]=='1')++S;
		else --S;chkmax(mxp,S);
	}
	int z1=calculate(mxp),z2=calculate(mxp+1);
	pr2(min(mxp-z1,mxp+1-z2));
	#ifdef Rose
		double EndJudgeTime=clock();
		cerr<<"JudgeTime is"<<" ";
		cerr<<(EndJudgeTime-BeginJudgeTime)/CLOCKS_PER_SEC<<endl;
	#endif
	return 0;
}


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  int cnt=0;
  for(int i=0;i<n;i++){
    cin >> h[i];
    if(h[i]>=k){
      cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 640
n=int(input())
l=list(map(int,input().split()))

cnt=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if l[i]==l[j] or l[j]==l[k] or l[i]==l[k]:
                continue
            if abs(l[i]-l[j])<l[k]<l[i]+l[j]:
                cnt+=1

print(cnt)


Measured memory_bytes: 73892
a=0
b=input().rstrip().split()
b=[int(x) for x in b]
cost=0

for ii in range(2):
  a=min(b)
  for i in range(len(b)):
    if min(b)==b[i]:
      del b[i]
      break
  b=[abs(x-a) for x in b]
  cost+=min(b)
print(cost)

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

ll n, m;
vector<ll> v, w;

ll P = 1000000007;
ll dp[2010][2010] = {0};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  v.resize(n);
  w.resize(m);
  for (int i = 0; i < n; i++) cin >> v[i];
  for (int i = 0; i < m; i++) cin >> w[i];

  ll ans = 1;
  dp[0][0] = 1;
  for (int i = 0; i <= m; i++) dp[0][i] = 1;
  for (int i = 0; i <= n; i++) dp[i][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + P) % P;
      if (v[i] == w[j]) {
        ans += dp[i][j];
        ans %= P;
        dp[i + 1][j + 1] += dp[i][j];
        dp[i + 1][j + 1] %= P;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 31744
import java.util.Scanner;

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

		String s = sc.next();

		int ans = 0;
		for (int i = 0; i < 4; i++) {
			if (s.charAt(i) == '+') {
				ans++;
			} else {
				ans--;
			}
		}

		System.out.println(ans);
		sc.close();

	}
}



Measured memory_bytes: 23252
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

char p[10000000];

void prime() {
  fill(p, p+1000000, true);
  p[0] = false;
  p[1] = false;

  for(int i = 2; i < 10000000; i++) {
    if(p[i]) {
      for(int j = 2; i*j < 10000000; j++) {
	p[i*j] = false;
      }
    }
  }
}


int main() {
  int n;

  prime();

  while(1) {
    cin >> n;
    if(!n)break;

    int i = 0, sum = 0;
    for(int j = 2; j < 10000000 && i < n; j++) {
      if(p[j]) {
	sum += j;
	i++;
      }
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 10924
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long people;
    long long min;
    long long Time;
    scanf("%lld",&people);
    for(int i=0; i<5; i++){
        scanf("%lld",&Time);
        if((!i) || min>Time){
            min=Time;
        }
    }
    long long answer;
    answer=people/min+5;
    if(people%min==0) answer--;
    cout<<answer;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int P = 2019;
        final char[] str = in.nextLine().toCharArray();
        final int N = str.length;
        final int[] digits = new int[N + 1];
        for (int i = 0; i < N; i++) {
            digits[i + 1] = Character.getNumericValue(str[i]);
        }
        final int[] residueDP = new int[P];
        // store number of SUFFIXES with a given residue.
        // We can definitely enumerate all N of those, and we leverage
        // the fact that we can SUBTRACT suffixes in a way that
        // allows us to generate all valid substrings! This will be called
        // the substring from suffix trick!
        residueDP[0] = 1; // we can always build on top of the empty suffix!
        // Now we create a running suffix
        int suffix = 0;
        int shift = 1;
        long ans = 0;
        for (int pos = N; pos >= 1; pos--) {
            suffix = (suffix + shift * digits[pos]) % P;
            ans += residueDP[suffix];
            residueDP[suffix]++;
            shift = (shift * 10) % P;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 42592
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int s,n,m;
int x[200000],y[200000],red[200000],cnt[200000];
int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    red[1]=1;
    for (int i=1;i<=n;i++) cnt[i]=1;
    for (int i=1;i<=m;i++) {
        cin >> x[i] >> y[i];
        cnt[x[i]]--;
        cnt[y[i]]++;
        red[y[i]]=max(red[y[i]],red[x[i]]);
        if (red[x[i]]==1 && cnt[x[i]]==0) red[x[i]]=0;
    }
    for (int i=1;i<=n;i++) s+=red[i];
    cout << s << "\n";
    return 0;
}


Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, A, B = map(int, input().split())
# 文字列の入力
#s = input()
#print(s[0:K-1]+s[K-1].lower()+s[K:N])
i=1
ans=0
while(i<=N):
    s=str(i)
    array=list(map(int,s))
    #print(sum(array))
    SUM=sum(array)
    if A<=SUM and SUM<=B:
        #print(i)
        ans=ans+i
    i=i+1

print(ans)


Measured memory_bytes: 3060
#include<stdio.h>
 
#define N1 500000
#define N2 1000000000
            
int Merge(int S[], int, int, int);
int Merge_sort(int S[], int, int);
 
int sum=0;
 
 
 
int main(){
 
int S[N1];
int i, n;
 
scanf("%d",&n);
 
for(i = 0; i < n; i++){
scanf("%d",&S[i]);
}
 
Merge_sort(S, 0, n);
 
 
for(i = 0; i<n; i++){
printf("%d",S[i]);
 
if(i<n-1) printf(" ");
 
}
printf("\n%d\n",sum);
return 0;
 
}
 
int Merge(int S[], int left, int mid, int right){
 
int n1 = mid - left;
int n2 = right - mid;
int L[n1], R[n2];
int i, j, k;
 
for(i = 0; i < n1; i++){
L[i] = S[left + i];
}
 
for(i = 0; i < n2; i++){
R[i] = S[mid + i];
}
 
L[n1] = N2;
R[n2] = N2;
 
i=0;
j=0;
 
for(k=left; k < right; k++){
 
if(L[i] <= R[j]){
S[k] = L[i];
i++;
}
 
else {
S[k] = R[j];
j++;
}
sum++;
}
 
}
 
int Merge_sort(int S[], int left, int right){
 
int mid;
 
if(left + 1 < right){
 mid = (left + right)/2;
        Merge_sort(S,left,mid);
        Merge_sort(S,mid,right);
        Merge(S,left,mid,right);
}
 
}

Measured memory_bytes: 4508
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

typedef long long ll;

#define MAX_L (10)

char S[MAX_L + 1];

void print_array(int *ar, int n) {
  for (size_t i = 0; i < n; i++) {
    printf("%d ", ar[i]);
  }
  printf("\n");
}

ll my_atoi(char *s, int l, int r) {
  ll val = 0;
  for (size_t i = l; i < r; i++) {
    val = 10 * val + (s[i] - '0');
  }
  return val;
}

ll comb(int n, int k) {
  ll c = 1;
  for (size_t i = k + 1; i <= n; i++) {
    c *= i;
  }
  for (size_t i = 2; i <= n - k; i++) {
    c /= i;
  }
  return c;
}

ll search(char *s, int n, int l, int r) {
//  printf("%lld, %d\n", my_atoi(s, l, r), n);
  if (n <= 0) { return my_atoi(s, l, r); }
  ll cost = 0;
  for (size_t i = l + 1; n - 1 < r - i; i++) {
    cost += search(s, 0, l, i) * comb(r - i - 1, n - 1);
    cost += search(s, n - 1, i, r);
  }
  return cost;
}

int main() {
  scanf("%s", S);

  ll cost = 0;
  int L = std::strlen(S);
  for (size_t i = 0; i < L; i++) {
    cost += search(S, i, 0, L);
  }

  printf("%lld\n", cost);
  return 0;
}


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

using namespace std;
typedef long long ll;

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

  ll result = 0;
  for (int i = 0; i <= n; ++i) {
    if (i % 3 != 0 && i % 5 != 0) {
      result += i;
    }
  }

  cout << result;

  return 0;
}


Measured memory_bytes: 3592
class Node
  attr_accessor :left, :right, :parent, :value
  def initialize(value)
    @value = value
  end
end

@root = nil

def insert(node)
  parent = nil
  x = @root
  until x.nil?
    parent = x
    if node.value < x.value
      x = x.left
    else
      x = x.right
    end
  end

  node.parent = parent
  if parent.nil?
    @root = node
  elsif node.value < parent.value
    parent.left = node
  else
    parent.right = node
  end
end

def in_order(node, arr = [])
  in_order(node.left, arr) if node.left
  arr << node.value
  in_order(node.right, arr) if node.right
  arr
end

def pre_order(node, arr = [])
  arr << node.value
  pre_order(node.left, arr) if node.left
  pre_order(node.right, arr) if node.right
  arr
end


gets.to_i.times do
  command, value = gets.split

  case command
  when 'insert'
    insert(Node.new(value.to_i))
  when 'print'
    puts "\s" + in_order(@root).join("\s")
    puts "\s" + pre_order(@root).join("\s")
  end
end



Measured memory_bytes: 61252
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

const long long MOD = 1e9 + 7;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n), b(m);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, m) cin >> b[i];
    vector<ll> lla(n + 1), llb(m + 1);
    rep(i, 0, n) lla[i + 1] = lla[i] + a[i];
    rep(i, 0, m) llb[i + 1] = llb[i] + b[i];
    // cout << endl;
    // rep(i, 0, n + 1) cout << lla[i] << "  ";
    // cout << endl;
    // rep(i, 0, m + 1) cout << llb[i] << "  ";
    // cout << endl;
    ll ans = 0;
    // rep(i, 0, n + 1) cout << max(ll(0), k - lla[i]) << "  diff:" << distance(llb.begin(), upper_bound(all(llb), k - lla[i])) << endl;
    rep(i, 0, n + 1) if (lla[i] <= k) ans = max(ans, i + distance(llb.begin(), upper_bound(all(llb), k - lla[i])) - 1);

    cout << ans << endl;
}


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

int main() {
  int N,kazu;
  cin >> N;
  for(int i=0;i<N;i++) {
    int x,y;
    cin >> x >> y;
    if(x==y) {
      kazu++;
    } else {
      kazu=0;
    }
    if(kazu==3) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3616
using System;
using System.Text;

namespace ALDS1_5_B_mergesort_
{
    class Program
    {
        static int count;


        static void Main(string[] args)
        {
           int n = getint(null);
            var S = getsplit();
            var A = Array.ConvertAll(S, int.Parse);
            mergesort(A, 0, n);
            StringBuilder sort = new StringBuilder();

            foreach (var a in A)
            {
                sort.Append(a+ " ");               
            }
            Console.WriteLine(sort.ToString().Trim());
            Console.WriteLine(count);
        }
        static void merge(int[] A,int left,int mid ,int right)
        {
            int n1 = mid - left;
            int n2 = right - mid;
            var L = new int[n1 + 1];
            var R = new int[n2 + 1];
            int i;
            for (i = 0; i < n1; i++)
            {
                L[i] = A[left + i];
            }
            for (i = 0; i < n2; i++)
            {
                R[i] = A[mid + i];
            }
            L[n1] = int.MaxValue;
            R[n2] = int.MaxValue;
            i = 0;
            int j = 0;
            for (int k = left; k < right; k++)
            {
                if (L[i]<=R[j])
                {
                    A[k] = L[i];
                    i = i + 1;
                }
                else
                {
                    A[k] = R[j];
                    j = j + 1;
                }
                count++;
            }
        } 
        static void mergesort(int[] A,int left,int right)
        {
            if (left+1<right)
            {
               int mid =(left + right) / 2;
                mergesort(A, left, mid);
                mergesort(A, mid, right);
                merge(A, left, mid, right);
            }
        }

        public static string[] getsplit()
        {
            string[] x = Console.ReadLine().Split(' ');
            return x;
        }
        public static int getint(string a)
        {
            if (a == null || a.Length == 0)
            {
                int x = int.Parse(Console.ReadLine());
                return x;
            }
            else
            {
                int x = int.Parse(a);
                return x;
            }
        }

    }
}

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

using namespace std;

int main ()
{
	string s;
	cin >> s;
	int n = s.length();
	int a = 0, b = n-1;
	while(b > a){
		if (s[a++] != s[b--]){
			cout << "No" << endl;
			return 0;
		}
	}
	a = 0, b = ((n-1)/2) - 1;
	while(b > a){
		if (s[a++] != s[b--]){
			cout << "No" << endl;
			return 0;
		}
	}
	a = ((n+3)/2) - 1, b = n - 1;
	while(b > a){
		if (s[a++] != s[b--]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; scanf("%d", &n);
	
	std::map<int, int> mp;
	for(int i = 2; i <= n; i++) {
		int tmp = i;
		for(int j = 2; j * j <= tmp; j++) {
			if(tmp % j) continue;
			while(tmp % j == 0) {
				mp[j]++;
				tmp /= j;
			}
		}
		if(tmp != 1) mp[tmp]++;
	}
	int ans = 0;
	std::vector<std::pair<int, int>> vec;
	for(auto v : mp) vec.push_back(v);
	for(int i = 0; i < vec.size(); i++) {
		for(int j = i + 1; j < vec.size(); j++) {
			for(int k = 0; k < vec.size(); k++) {
				if(k == i or k == j) continue;
				if(vec[i].second >= 4) {
					if(vec[j].second >= 4) {
						if(vec[k].second >= 2) {
							ans++;
						}
					}
				}
			}
		}
	}
	for(int i = 0; i < vec.size(); i++) {
		for(int j = 0; j < vec.size(); j++) {
			if(i == j) continue;
			if(vec[i].second >= 24) {
				if(vec[j].second >= 2) {
					ans++;
				}
			}
			if(vec[i].second >= 4) {
				if(vec[j].second >= 14) {
					ans++;
				}
			}
		}
	}
	for(int i = 0; i < vec.size(); i++) if(vec[i].second >= 74) ans++;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]
use std::io::*;
use std::str::FromStr;
use std::collections::{HashMap, VecDeque};

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut map = HashMap::new();
    let mut ansArr = vec![0; n + 1];
    for _ in 0..m {
        let a: usize = read();
        let b: usize = read();
        (*map.entry(a).or_insert(Vec::new())).push(b);
        (*map.entry(b).or_insert(Vec::new())).push(a);
    }

    let mut q = VecDeque::new();
    q.push_back(1);
 
    while let Some(current) = q.pop_front() {
        for &next in &map[&current] {
            if ansArr[next] == 0 {
                ansArr[next] = current;
                q.push_back(next);
            }
        }
    }



    print!("Yes\n");
    for i in 2..n + 1 {
        print!("{}\n", ansArr[i]);
    }
}


Measured memory_bytes: 13508
#include <stdio.h>
int main()
{
	int r,c,rc[101][101]={0};
	scanf("%d %d",&r,&c);
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)
			scanf("%d",&rc[i][j]);
	}
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++)
			rc[i][c]=rc[i][c]+rc[i][j];
	}
	for(int i=0;i<=c;i++){
		for(int j=0;j<r;j++)
			rc[r][i]=rc[r][i]+rc[j][i];
	}
	for(int i=0;i<=r;i++){
		for(int j=0;j<=c;j++){
			printf("%d",rc[i][j]);
			if(j!=c)
				printf(" ");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1080
import math

A,B,H,M = map(float, input().split())
pi = math.pi
Ak = 360*H/12+360/12*M/60
Bk = 360*M/60
Ak = Ak/180*pi
Bk = Bk/180*pi
# print(Ak)
# print(Bk)
ans = A*A+B*B-2*A*B*math.cos(Ak-Bk)
print(math.sqrt(ans))

Measured memory_bytes: 9396
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = n-1; i >= 0; --i)
#define REP(i, s, n) for (int i = s; i< (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
ll inf = ll(1e18);
using ll1d = vector<ll>;
using ll2d = vector<ll1d>;
using ll3d = vector<ll2d>;

void solve(istream &ccin = cin, ostream &ccout = cout) {
  ll n, s;
  ccin >> n >> s;
  vector<ll> x(n);
  rep(i, n) ccin >> x[i];
  sort(all(x));
  bool isa = false;

  REP(i, 1, n) {
    if (x[i - 1] != x[i]) isa = true;
  }

  if (isa) {
    vector<ll> sa(n - 1);
    sa[0] = x[1] - x[0];
    ll gcds = sa[0];
    gcds = __gcd(gcds, abs(x[0] - s));
    gcds = __gcd(gcds, abs(x[n - 1] - s));
    REP(i, 1, n - 1) {
      sa[i] = x[i + 1] - x[i];
      gcds = __gcd(gcds, sa[i]);
      gcds = __gcd(gcds, abs(x[i] - s));
    }

    ccout << gcds << endl;
  } else
    ccout << abs(x[0]-s) << endl;

}

int main() {
  ios::sync_with_stdio(false);
  solve();
  return 0;
}

Measured memory_bytes: 1792
n, k = map(int, input().split())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7
negs = [-x for x in A if x < 0]
non_negs = [x for x in A if x >= 0]


def inv(a):
    return pow(a, mod - 2, mod)


# 負の数を選ばざるを得ない数を考える
# 選べる負の数の個数の最小
n_min = k - (max(n - len(negs), 0))
# 　選べる負の数の個数の最大
n_max = min(n, k)

# この2数が一致していて、更に奇数のときにのみ負になる。(はず)
if n_max == n_min and n_max % 2 == 1:
    negs.sort()
    non_negs.sort()
    cnt = 0
    ans = 1
    n_idx, nn_idx = 0, 0
    while cnt < k:
        if n_idx == len(negs):
            ans *= non_negs[nn_idx]
            nn_idx += 1
        elif nn_idx == len(non_negs):
            ans *= -negs[n_idx]
            n_idx += 1
        else:
            if non_negs[nn_idx] < negs[n_idx]:
                ans *= non_negs[nn_idx]
                nn_idx += 1
            else:
                ans *= -negs[n_idx]
                n_idx += 1
        ans %= mod
        cnt += 1

    print(ans % mod)
    exit()

negs.sort(reverse=True)
non_negs.sort(reverse=True)

cnt = 0
ans = 1
neg_cnt = 0
n_idx, nn_idx = 0, 0
# idx番号と配列の長さを比較して、その配列から取得可能かをみる
while cnt < k:
    if n_idx == len(negs):
        ans *= non_negs[nn_idx]
        nn_idx += 1
    elif nn_idx == len(non_negs):
        ans *= -negs[n_idx]
        n_idx += 1
        neg_cnt += 1
    else:
        if non_negs[nn_idx] > negs[n_idx]:
            ans *= non_negs[nn_idx]
            nn_idx += 1
        else:
            ans *= -negs[n_idx]
            n_idx += 1
            neg_cnt += 1
    ans %= mod
    cnt += 1

# 動かす余地がない場合→negが偶数個or動かす余裕がない
if neg_cnt % 2 == 0 or n == k:
    # REからここがおかしそう…
    print(ans % mod)
    exit()
else:
    # 次にかけるのはnegs[n_idx] or non_negs[nn_idx]
    # 一つ戻すならnegs[n_idx-1] or non_negs[nn_idx-1]

    # negsが右にずらせるかどうか
    if n_idx == len(negs) or nn_idx == 0:
        ans *= inv(-negs[n_idx - 1])
        ans *= non_negs[nn_idx]
        ans %= mod
    # non_negsが右にずらせるか
    elif nn_idx == len(non_negs) or n_idx == 0:
        ans *= inv(non_negs[nn_idx - 1])
        ans *= -negs[n_idx]
        ans %= mod
    else:
        # 両方ともずらせないのはすでに除外済み(のはず)
        if non_negs[nn_idx] * non_negs[nn_idx - 1] > negs[n_idx] * negs[n_idx - 1]:
            ans *= non_negs[nn_idx]
            ans *= inv(-negs[n_idx - 1])
            ans %= mod
        else:
            ans *= -negs[n_idx]
            ans *= inv(non_negs[nn_idx - 1])
            ans %= mod

    print(ans % mod)
    exit()


Measured memory_bytes: 106940
n = int(input())
a = {}

for i in range(1,n+1):
    b = 2
    while i > 1:
        if i % b == 0:
            if b in a:
                a[b] += 1
            else:
                a[b] = 1
            i = i//b
        else:
            b += 1
ans = 1
for i in a:
    ans *= a[i]+1
print(ans%1000000007)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

int cmp(int *x, int *y)
{
	return (*y - *x);
}

int main(void)
{
	int d[8];
	int i;

	for (i = 0; i < 5; i++) scanf("%d", d + i);
	qsort(d, 5, 4, cmp);
	for (i = 0; i < 5; i++) printf("%d%c", d[i], i == 4 ? '\n' : ' ');
	return (0);
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long 
#define all(v) v.begin() , v.end()
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define tr(con) for(auto it = con.begin(); it!= con.end() ; it++)
#define INF 1e9+7   // 1 * 10^9+ 7
#define rep(l,i,r) for(ll i=l;i<=r;i++)
#define fo(i,n) for(ll i=0;i<n;i++)
using namespace std;

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n; cin >> n;
	ll a[n];
	fo(i,n) cin >> a[i];	
	sort(a , a+n);
	cout << a[n/2] - a[n/2-1];
	return 0;
}


Measured memory_bytes: 1024
m = {3:100000, 2:200000, 1:300000}
def f(a):
    if a <= 3:
        return m[a]
    return 0
def g(a, b):
    return 400000 if (a == 1 and a == b) else 0
x, y = map(int, input().split())
print(f(x) + f(y) + g(x, y))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int a,b,c,d,e,sum1=0,sum2=0;
    cin >> a >> b >> c >> d >> e;

    sum1 = a*60+b;
    sum2 = c*60+d;

    cout << max(0,sum2-sum1-e) << endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
    
int main(){
    int ah, ak, bh, bk, w;
    cin >> ah >> ak >> bh >> bk;
    while(ah > 0 && bh > 0){
        bh -= ak;
        if(bh <= 0){
            w = 0;
            break;
        }
        ah -= bk;
        if(ah <= 0){
            w = 1;
            break;
        }
    }
    if(w == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
    int N,counter;
    cin>>N;
    long long vec[200];
    for(int i=0; i<N; i++){
    cin>>vec[i];}
    while(true){
    for(int i=0; i<N; i++){
    if(vec[i]%2==1){
    goto A;
    }
    else
    vec[i]=vec[i]/2;}
    counter++;}
    A:
    cout<<counter<<endl;}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,count=0;
  cin>>n;
  int a[n];
  for(int i =0;i<n;i++){
    cin>>a[i];
    
    if(a[i]%2==1&&i%2==0)
    count++;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 3608
'''
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
'''
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  v = list(map(int, readline().split()))
  odd = Counter(v[::2])
  even = Counter(v[1::2])
  odd[-1] = 0
  even[-2] = 0
  ev = even.most_common(2)
  od = odd.most_common(2)
  
  answer = n
  for (k1,v1), (k2,v2) in product(ev,od):
    if k1 == k2:
      continue
    x = n-v1-v2
    if answer>x:
      answer = x
      
  print(answer)
    
  
  
  
  
  
if __name__ == '__main__':
  main()

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

const int mod = 1000000007;

int main() {
	int ans = 0, n; scanf("%d", &n);
	long long t = 1;
	for (int i = 0; i < n; ++i)
		t = t * 10 % mod;
	ans += t;
	t = 1;
	for (int i = 0; i < n; ++i)
		t = t * 9 % mod;
	ans -= t << 1;
	t = 1;
	for (int i = 0; i < n; ++i)
		t = t * 8 % mod;
	ans = ((ans + t) % mod + mod) % mod;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3812