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

int main(){
    int n ;
    string s;
    while( cin >> n >> s ){
            int cnt =0;
        for( int i = 0; i < n; i++ ){
            string t = s.substr(i,3);
            if( t == "ABC" ){
                cnt++;
            }
        }
    cout << cnt << "\n";
    }
}
/*
7 2
0 1 0 0 0 1 0
*/


Measured memory_bytes: 256
#include <stdio.h>

int get_uint() {
    int n = 0;
    int c = getchar_unlocked();
    if(c < 48 || 57 < c) return c;
    while(47 < c && c < 58) {
        n = 10 * n + (c & 0xf);
        c = getchar_unlocked();
    }
    return n;
}
void put_uint(int n) {
    if(!n) {
        putchar_unlocked('0');
        return;
    }
    char buf[11];
    int i = 0;
    while(n) buf[i++] = (char)(n % 10 + '0'), n /= 10;
    while(i--)putchar_unlocked(buf[i]);
}
int *partition(int *first, int *last) {
    int pivot = *(last - 1);
    int *p = first - 1;
    for(int *it = first; it != last - 1; ++it) {
        if(*it <= pivot) {
            p++;
            int tmp = *p;
            *p = *it;
            *it = tmp;
        }
    }
    int tmp = *++p;
    *p = pivot;
    *(last - 1) = tmp;
    return p;
}
int main(int argc, char **argv) {
    int n = get_uint();
    int a[n];
    for(int i = 0; i < n; ++i) a[i] = get_uint();
    int *piv = partition(a, a + n);
    for(int *it = a; it != piv; ++it) put_uint(*it), putchar_unlocked(' ');
    putchar_unlocked('['), put_uint(*piv), putchar_unlocked(']'), putchar_unlocked(' ');
    for(int *it = piv + 1; it != a + n - 1; ++it) put_uint(*it), putchar_unlocked(' ');
    put_uint(a[n-1]), putchar_unlocked('\n');
    return 0;
}



Measured memory_bytes: 2144
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 10005

int main(){
  while(1){
    int N,M;
    scanf("%d %d",&N,&M);
    if(M==0&&N==0)break;
    vector<int> Min(N,0);
    vector<int> Max(N,0);
    for(int i=0;i<M;i++){
      int p,k,id;
      scanf("%d %d",&p,&k);
      for(int j=0;j<k;j++){
        scanf("%d",&id);
        id--;
        if(k==1){
          Min[id]+=p;
        }
        Max[id]+=p;
      }
    }

    int mini=1e9,maxm=-1e9,ans=0;

    for(int i=0;i<N;i++){

      if(Max[i]>mini)
        ans=max(ans, abs(Max[i]-mini) );
        
      if(maxm>Min[i])
        ans=max(ans, abs(maxm-Min[i]) );

      mini=min(mini,Min[i]);
      maxm=max(maxm,Max[i]);
    }
    cout<<ans+1<<endl;
  }
  return 0;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main()
{
    int A, B;
    cin >> A >> B;
    if(A == B){
        cout << A+B << endl;
    }else if(A-1 >= B){
        cout << 2*A-1 <<endl;
    }else if(B-1 >= A){
        cout << 2*B-1 <<endl;
    }
    return 0;
}


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

int main()
{
	int H, W, K;
	cin >> H >> W >> K;
	vector<string> c(H);
	for (int i = 0; i < H; ++i) cin >> c[i];


	int ans = 0;
	for (int ic = 0; ic < 1 << H; ++ic)
	{
		for (int jc = 0; jc < 1 << W; ++jc)
		{
			int cnt = 0;
			for (int i = 0; i < H; ++i)
			{
				for (int j = 0; j < W; ++j)
				{
					if (ic >> i & 1) continue;
					if (jc >> j & 1) continue;
					if (c[i][j] == '#') ++cnt;
				}
			}
			if (cnt == K) ans++;
		}
	}
	cout << ans << endl;
}		

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

#define rep(i, n) for(int i = 0; i < n;i++)
#define F(A, B) max(A.length(), B.length())
int main()
{
    long N;
    cin >> N;
    long min = LONG_MAX;
    for (long i = 1; i * i <= N;i++){
        if(N % i == 0){
            long tmp = F(to_string(i), to_string(N / i));
            if(min > tmp){
                min = tmp;
            }
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const double PI = acos(-1);  

int main(){
  int n, k; cin >> n >> k;
vector<bool> a(n, false);

  for(int i=0; i<k; i++){
    int x;  cin >> x;
    for(int i=0; i<x; i++){
      int p;  cin >> p;
      a[p-1] = true;
    }
  }
  int cnt=0;
  for(int i=0; i<n; i++){
    if(!a[i]) cnt += 1;
  }
  cout << cnt << endl;

}

Measured memory_bytes: 3632
n,m,x = map(int,input().split())
A = list(map(int,input().split()))

M = [0]*101
ans1 = 0
ans2 = 0
for a in A:
    M[a] = 1
for i in range(x,n+1):
    ans1 += M[i]
for j in range(x,-1,-1):
    ans2 += M[j]
print(min(ans1,ans2))

Measured memory_bytes: 3064
#include<cstdio>

int main(void) {
	int H,W,N, i,j;
	int a[10000],dir,color,ans[100][100];

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

	dir = 1; color = 0;
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (i % 2 == 0) {
				ans[i][j] = color + 1;
			}
			else {
				ans[i][W - 1 - j] = color + 1;
			}
			a[color]--;
			if (a[color] == 0) { color++; }
		}
	}
	
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			printf("%d ", ans[i][j]);
		}
		printf("\n");
	}

}

Measured memory_bytes: 256
/*
Author: CNYALI_LK
LANG: C++
PROG: D.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprllf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll a[333][333];
const ll mn=0xefffffff;
int main(){
#ifdef cnyali_lk
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	ll n;
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i)for(ll j=1;j<=n;++j){
		scanf("%lld",a[i]+j);
	}
	for(ll i=1;i<=n;++i)for(ll j=1;j<=n;++j)for(ll k=1;k<=n;++k)
		if(a[i][j]>a[i][k]+a[k][j]){
			printf("-1\n");
			return 0;
		}
	for(ll k=1;k<=n;++k)for(ll i=1;i<=n;++i)for(ll j=1;j<=n;++j){
		if(i!=j&&i!=k&&j!=k&&a[i][j]==a[i][k]+a[k][j]){
			a[i][j]=mn;
		}
	}
	ll ans=0;
	for(ll i=1;i<=n;++i)for(ll j=i+1;j<=n;++j)if(a[i][j]!=mn){
		ans+=a[i][j];
		
	}
	printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(void)
{
  int N, K;
  char S[51];

  cin >> N >> K >> S;
  switch(S[K-1])
  {
    case 'A': S[K-1] = 'a'; break;
    case 'B': S[K-1] = 'b'; break;
    case 'C': S[K-1] = 'c'; break;
  }
  cout << S;
  return 0;
}


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

int main() { 
    int a, b, c, d, L, R;
    cin >> a >> b >> c >> d;
    L = a+b;
    R = c+d;

    if ( L > R)
    cout << "Left" << endl;
    else if ( L < R)
    cout << "Right" << endl;
    else
    cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll INF = 1e9;
int MOD = 1e9+7;
main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,A[100000],B[100000];
    ll cnt = 0;
    cin >> N;
    for(int i = 0;i < N;i++)cin >> A[i] >> B[i];
    for(int i = N-1;i >= 0;i--){
        ll sub = (A[i]+B[i]+cnt-1) / B[i] * B[i];
        cnt += sub - A[i] - cnt;
        /*
        // cnt <= dif+Bkを満たす最小値
        int dif = (B[i]-A[i]%B[i]) % B[i];
        //にぶたん
        ll ng = -1,ok = INF;
        while(llabs(ok-ng)>1){
            ll mid = (ok+ng)/2;
            if(cnt <= dif+mid*B[i]) ok = mid;
            else ng = mid;
        }
        cnt = dif+ok*B[i];
        */
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
  int n,i,j,a[200010],ans[200010]={},s;
  cin >> n;
  for (i=1;i<=n;i++) cin >> a[i];
  for (i=n;i>=1;i--){
    s=0;
    for (j=1;i*j<=n;j++) s+=ans[i*j];
    if (s%2!=a[i]) ans[i]=1;
  }
  
  int m=0;
  vector<int> v;
  for (i=1;i<=n;i++){
    if (ans[i]){
      m++;
      v.push_back(i);
    }
  }
  cout << m << endl;
  for (i=0;i<m;i++) cout << v[i] << endl;
  return 0;
}

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

int max(int a,int b){
	if(a<b)a=b;
	return a;
}
int max(int a,int b,int c){
	if(a<b)a=b;
	if(a<c)a=c;
	return a;
}
int min(int a,int b){
	if(a>b)a=b;
	return a;
}
int min(int a,int b,int c){
	if(a>b)a=b;
	if(a>c)a=c;
	return a;
}

int check(int a,int b){
	int c[3];
	int s[2];
	c[0]=(a/3)*b;
	c[1]=(a-a/3)*(b/2);
	c[2]=a*b-c[0]-c[1];
	s[0]=max(c[0],c[1],c[2])-min(c[0],c[1],c[2]);
	c[0]=(a/3+1)*b;
	c[1]=(a-a/3-1)*(b/2);
	c[2]=a*b-c[0]-c[1];
	s[1]=max(c[0],c[1],c[2])-min(c[0],c[1],c[2]);
	s[0]=min(s[0],s[1]);
	return s[0];
}

int main(){
	int a,b;
	int s;
	cin>>a>>b;
	if(a%3==0 || b%3==0)s=0;
	else s=min(a,b);
	s=min(s,check(a,b),check(b,a));
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  cin >> N >> M;
  vector<bool> like(M, false);
  vector<bool> every(M, true);
  for(int i = 0; i < N; i++) {
    int K;
    cin >> K;
    for(int j = 0; j < K; j++) {
      int A;
      cin >> A;
      like[A - 1] = true;
    }
    for(int k = 0; k < M; k++) {
      if(like[k] == false) {
        every[k] = false;
      }
      like[k] = false;
    }
  }
  int ans = 0;
  for(int i = 0; i < M; i++) {
    if(every[i]) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <stack>
#include <limits.h>
#include <ios>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define f(k,n)    for( ll i=k;i<n;i++)
#define ll long long int
#define mp make_pair
//#define edge pair<ll, pair<ll, int>> 
using namespace std;

int main() {
	IOS
	int n;
	cin>>n;
	ll g ;
	cin>>g;
	ll a;
	f(1, n){
	    cin>>a;
	    g = __gcd(a, g);
	}
	cout<<g<<endl;
	return 0;
}

Measured memory_bytes: 888
x, y = map(int, input().split())

mod = 10**9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
N = 10**6
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

if (x + y) % 3 != 0:
    print(0)
    exit()

k = (x + y) // 3
n = x - k
m = y - k
ans = cmb(n + m, n, mod)
print(ans)

Measured memory_bytes: 122048
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
#include <complex>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 

static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-10;

int total_players;
int total_messages;

int find(int idx,int parent[21]){
  if(parent[idx] == idx) return idx;
  else return find(parent[idx],parent);
}


vector<int> child[21];
int level[21];
bool visited[21];

class State {
public:
  int node;
  int level;
  State(int _n,int _l)
    : node(_n), level(_l) {}
  bool operator<(const State& s) const{
    return level < s.level;
  }
  bool operator>(const State& s) const{
    return level > s.level;
  }
};

int bfs(int root){
  queue<State> que;
  que.push(State(root,0));
  while(!que.empty()){
    State current = que.front();
    que.pop();

    for(int i=0;i<child[current.node].size();i++){
      int next = child[current.node][i];
      // if(current.level + 1 != level[next]) continue;
      level[next] = max(current.level + 1,level[next]);
      que.push(State(next,current.level + 1));
      
    }
  }
}

int main(){
  while(~scanf("%d %d",&total_players,&total_messages)){
    for(int i=1;i<=20;i++){
      child[i].clear();
    }

    bool has_parent[21];

    memset(has_parent,false,sizeof(has_parent));
    for(int i=1;i<=20;i++){
      level[i] = 1;
    }
    
    for(int message_idx = 0; message_idx < total_messages; message_idx++){
      int x,y;
      //x entered the room earlier than y
      scanf("%d %d",&x,&y);
      child[x].push_back(y);
      has_parent[y] = true;
    }

    memset(visited,false,sizeof(visited));

    for(int i=1;i<=total_players;i++){
      if(has_parent[i]) continue;
      child[0].push_back(i);
    }

    bfs(0);
    
    vector<State> res;
    for(int i=1;i<=total_players;i++){
      res.push_back(State(i,level[i]));
    }
    sort(res.begin(),res.end());
    for(int i=0;i<res.size();i++){
      printf("%d\n",res[i].node);
    }
  }
}

Measured memory_bytes: 1216
#include<stdio.h>

int main(void){
	int n,x,min,m,i;
	scanf("%d %d %d",&n,&x,&min);
	x-=min;
	for(i=1;i<n;i++){
		scanf("%d",&m);
		x-=m;
		if(min>m){
			min=m;
		}
	}
	printf("%d\n",n+x/min);
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
long long c[100007];
int main(){
    int n;
    scanf("%d",&n);
    long long ans=0;
    int a,b;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        c[i]=a+b;
        ans-=b;
    }
    sort(c+1,c+1+n);
    for(int i=n;i>=1;i--)
        ans+=(n-i)&1?0:c[i];
    printf("%lld",ans);
    return 0;
}


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

const double pi = 3.14159265358979323846;
const ll mod = 1000000007;


int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n; cin >> n;
	int a = 0, b = 0, c = 0, d = 0;
	rep(i,n){
		string s; cin >> s;
		if(s == "AC") a++;
		else if(s == "WA") b++;
		else if(s == "TLE") c++;
		else if(s == "RE") d++;
	}
	cout << "AC x " << a << endl;
	cout << "WA x " << b << endl; 
	cout << "TLE x " << c << endl; 
	cout << "RE x " << d << endl; 
} 

Measured memory_bytes: 3664
#include <bits/stdc++.h>
typedef long long int ll;
//std::fill_n(arr, 100, 0); 
using namespace std;


int main()
{
    ll n,w;
    cin>>n>>w;

    vector<pair<ll,ll>> v;;
    ll dp[n+1][w+1];

    for(ll i=0;i<n;i++)
    	{ ll x,y;
    		cin>>x>>y;
    		v.push_back(make_pair(x,y));
    	}

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


for(ll i=0;i<=n;i++)
{
    for(ll j=0;j<=w;j++)	
    {
     if(j==0|| i==0)
     	dp[i][j]=0;

     else if(v[i-1].first<=j)
       dp[i][j]=max(v[i-1].second+dp[i-1][j-v[i-1].first],dp[i-1][j]);
      // cout<<"pp"<<v[i-1].second<<"  "<<dp[i-1][j-v[i-1].first]<<"---";
       
      else
        dp[i][j]=dp[i-1][j];
        	//cout<<"yy";}    
    
    //cout<<dp[i][j]<<" ";
    }
    //cout<<endl;
}


cout<<dp[n][w];
	return 0;
}

Measured memory_bytes: 79104
function Main(input) {
    input = input.split(" ");
    var K = parseInt(input[0],10);
    var X = parseInt(input[1],10);
    var res = [];
    for(var i = X - (K - 1); i < X + (K - 1) + 1;i++){
        res.push(i);
    }
    console.log(res.join(' '));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <string>
#include<algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;
int main()
{
	int x = 1;
	string yn[2] = { "vowel","consonant" };
	char c;
	char v[5] = { 'a','i','u','e','o' };
	cin >> c;
	for (int i = 0; i < 5; i++) {
		if (c == v[i]) x = 0;
	}
	cout << yn[x] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#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 inf 1e16
#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 IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define M 1000010

int main(){
	IOS;
	string s,t;cin>>s>>t;
	ll cnt=0;
	rep(i,0,min(s.length(),t.length()))if(s[i]==t[i])cnt++;
	cout<<cnt;
	return 0;
}



Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;


pub 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() {
  // 2019/04/30
  let s = read::<String>();

  let year = &s[0..4];
  let month = &s[5..7];

  let year_num = year.parse::<i32>().unwrap();
  let month_num = month.parse::<i32>().unwrap();

  if year_num < 2019 {
    println!("Heisei");
  } else if year_num == 2019 && month_num <= 4 {
    println!("Heisei");
  } else {
    println!("TBD");
  }
}



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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n;
LL xma = 0, xmi = 1000000001;
LL yma = 0, ymi = 1000000001;
PQ<pair<LL, LL>> q;

int main() {
	cin >> n;
	inc(i, n) {
		LL x, y;
		cin >> x >> y;
		
		if(x < y) { swap(x, y); }
		
		setmax(xma, x);
		setmin(xmi, x);
		setmax(yma, y);
		setmin(ymi, y);
		
		q.emplace(x, y);
	}
	
	LL ans = (xma - xmi) * (yma - ymi);
	while(! q.empty()) {
		auto e = q.top(); q.pop();
		if(e.FI <= e.SE) { break; }
		q.emplace(e.SE, e.FI);
		
		setmin(xmi, e.SE);
		setmax(yma, e.FI);
		xma = q.top().FI;
		
		setmin(ans, (xma - xmi) * (yma - ymi));
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 6512
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
B, W = map(int, input().split())
p = 0
q = 0
for i in range(1, B+W+1):
  ans = 1 - p + q
  ans %= MOD
  ans *= pow(2, MOD-2, MOD)
  ans %= MOD
  print(ans)
  p += comb(i-1, B-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  p %= MOD
  q += comb(i-1, W-1) * pow(pow(2, i, MOD), MOD-2, MOD) % MOD
  q %= MOD

Measured memory_bytes: 55384
import sys
from collections import defaultdict
input = sys.stdin.readline
n, k = [int(x) for x in input().strip().split()]
p = {a:b for a, b in zip(['s', 'p', 'r'], [int(x) for x in input().strip().split()])}
p['b'] = 0
t = input().strip()
pre_ = ['b'] * k
cnt = [0] * k
ans = 0
for i, tt in enumerate(t, start=1):
    if tt != pre_[i%k-1]:
        ans += p[pre_[i%k-1]] * ((cnt[i%k-1] + 1) // 2)
        cnt[i%k-1] = 1
        pre_[i%k-1] = tt
    else:
        cnt[i%k-1] += 1
else:
    for i in range(k):
        ans += p[pre_[i%k-1]] * ((cnt[i%k-1] + 1) // 2)
print(ans)

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

using namespace std;
typedef long long ll;

ll n, cou = 0;
void dfs(ll x, int a, int b, int c){
    if(x > n)
        return;
    if(a&b&c)
        cou++;
    dfs(10*x + 3, 1, b, c);
    dfs(10*x + 5, a, 1, c);
    dfs(10*x + 7, a, b, 1);
    return;
}

int main(){
    cin >> n;
    dfs(0,0,0,0);
    cout << cou << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 10000
int total;
int counting(int A[],int B[],int a){
  int i,j;
  int C[a];
  for(i=0;i<=a;i++){
    C[i]=0;
  }
  for(j=1;j<=total;j++){
    C[A[j]]++;
  }
  for(i=1;i<=a;i++){
    C[i]=C[i]+C[i-1];
  }
  for(j=total;j>0;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }
  return 0;
    }
   int main(){
       scanf("%d",&total);
  int i,A[total],B[total];
  for(i=1;i<=total;i++){
    scanf("%d",&A[i]);
  }
  counting(A,B,N);
  for(i=1;i<=total;i++){
    if(i>1)printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 17516
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()

tree = defaultdict(list)

# ノードの重み

cnt = [0] * N

# tree 隣接リスト
for i in range(N-1):
    a, b = LIST()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for i in range(Q):
    node, point = LIST()
    cnt[node-1] += point

ans = [0] * N
q = deque([])
# 始点
q.append(0)
# 各頂点を見たかどうかのフラグ
checked = [0] * N
checked[0] = 1

while q:
    v = q.pop()
    checked[v] = 1
    for u in tree[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt)


Measured memory_bytes: 93212
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;


int main() {
    
    ll n;
    cin >> n;
    vector <ll> dic;
    for(ll i=1;i<=n;i++){
        dic.push_back(i);
    }
    vector <ll> p,q;
    for(ll i=1;i<=n;i++){
        ll tmp;
        cin >> tmp;
        p.push_back(tmp);
    }
    for(ll i=1;i<=n;i++){
        ll tmp;
        cin >> tmp;
        q.push_back(tmp);
    }
    ll a,b;
    ll i=1;
    do{
        if(dic == p){
            a = i;
        }
        i++;
    }while(next_permutation(dic.begin(), dic.end()));
    ll j=1;
    do{
        if(dic == q){
//            for(ll i=0;i<n;i++){
//                cout << dic[i] << endl;
//            }
            b = j;
        }
        j++;
    }while(next_permutation(dic.begin(), dic.end()));

    cout << abs(b-a) << endl;
}

Measured memory_bytes: 256
# D - Semi Common Multiple

import fractions
from functools import reduce

N, M = map(int, input().split())
a = list(map(int, input().split()))
a_d = [x//2 for x in a]

def lcm(x,y):
    return x*y//fractions.gcd(x,y)

l = reduce(lcm, a_d)

for i in a_d:
    if (l//i) % 2 == 0: # 含まれる因数2の個数が異なるa_i, a_jがあるとき
        print(0)
        break
else:
    if (M//l) % 2 == 0:
        print((M//l)//2)
    else:
        print((M//l)//2 + 1)


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

taste = [l + i - 1 for i in range(1, n + 1)]
taste_all = sum(taste)
if taste[n - 1] < 0:
    taste_min = taste[n - 1]
elif taste[0] > 0:
    taste_min = taste[0]
else:
    taste_min = 0
print(taste_all - taste_min)


Measured memory_bytes: 9160
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}


int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	//dp[n][k][nより大きいの数]を求めていけばよい!!!
	//天才レッドコーダーか?
	//半分全列挙?
	static llint dp[51][1251][51]={0};
	int n,K,h,i,j;cin>>n>>K;
	if(K%2){cout<<0<<endl;return 0;}
	dp[1][0][0]=1;
	dp[1][0][1]=1;
	for(h=1;h<n;h++){
		for(i=0;i<=h*h/2;i++){
			for(j=0;j<=h;j++){
				//cerr<<"dp["<<h<<"]["<<i<<"]["<<j<<"]="<<dp[h][i][j]<<endl;
				dp[h][i][j]%=mod;
				if(j>0){dp[h+1][i+j][j-1]+=dp[h][i][j]*j*j;}
				dp[h+1][i+j][j]+=dp[h][i][j]*(1+j+j);
				dp[h+1][i+j][j+1]+=dp[h][i][j];
			}
		}
	}
	cout<<dp[n][K/2][0]%mod<<endl;
	return 0;
}
/*
1 2 3|4 5
5 3 1|4 2

k=2+1+2+1
dp[3][6][1]にカウントされる

1 2 3

2 1 3
1 3 2

3 2 1
3 1 2
2 3 1
*/

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

using namespace std;

#define int long long

bool codejam = 0;

typedef long long li;
typedef long double ld;

void solve();

int32_t main () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	int t = 1;
	// int t; 
	// cin >> t;
	int tt = t;
	while (t--) { 
		if (codejam) cout << "Case #" << tt - t << ": ";
		solve();
	}
	return 0;
}
bool taken[2005][2005];
int mx[2005][2005][4];
void solve() {
	for (int i = 0; i <= 2004; i++) for (int j = 0; j <= 2004; ++j) taken[i][j] = true;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; ++j) {
			char c;
			cin >> c;
			if (c == '#') taken[i][j] = true;
			else taken[i][j] = false;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (taken[i][j - 1]) mx[i][j][0] = 0;
			else mx[i][j][0] = mx[i][j - 1][0] + 1;
			if (taken[i - 1][j]) mx[i][j][1] = 0;
			else mx[i][j][1] = mx[i - 1][j][1] + 1;
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 1; j--) {
			if (taken[i][j + 1]) mx[i][j][2] = 0;
			else mx[i][j][2] = mx[i][j + 1][2] + 1;
			if (taken[i + 1][j]) mx[i][j][3] = 0;
			else mx[i][j][3] = mx[i + 1][j][3] + 1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (!taken[i][j]) ans = max(ans, 1 + mx[i][j][0] + mx[i][j][1] + mx[i][j][2] + mx[i][j][3]);
	cout << ans;
}	
 	

Measured memory_bytes: 129792
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
bool comp(pair<int,int> a, pair<int,int> b) {
	if(a.second == b.second) {
		return a.first<b.first;
	}
	return a.second<b.second;
}
int main() {
	int n;
	cin>>n;
	vector<pair<int,int>> v;
	for(int i=0;i<n;++i) {
		int x,y;
		cin>>x>>y;
		v.pb(mp(x,y));
	}
	sort(v.begin(), v.end(), comp);
	int t = 0;
	for(int i=0;i<n;++i) {
		t+=v[i].first;
		if(t>v[i].second)
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 2420
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i;
  string s;
  cin>>s;
  bool ans=true;
  rep(i,s.size())
    if(s[i]=='A'){
      while(i<s.size()&&s[i]!='Z')i++;
      if(s[i]=='Z'){
	ans=false;
	cout<<"AZ";
      }
    }
  if(ans)cout<<-1;
  cout<<endl;
}

Measured memory_bytes: 3224
#include <iostream>
#include <complex>
using namespace std;
typedef complex<double> P;

int n;
double x[300], y[300];

int main() {
    while (cin >> n && n) {
        for (int i=0; i<n; ++i) {
            cin >> x[i] >> y[i];
        }
        int ret = 1;
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                if (i == j) continue;
                P a = P(x[i], y[i]);
                P b = P(x[j], y[j]);
                P m = (a + b) / 2.0;
                double h = sqrt(1.0 - norm(a - m));
                P u = (a - b) / abs(a - b);
                u = P(-u.imag(), u.real());
                P c = (a + b) / 2.0 + u * h;
                int cnt = 0;
                for (int k=0; k<n; ++k) {
                    P t(x[k], y[k]);
                    if (norm(c - t) < 1.0 + 1e-8) {
                        cnt ++;
                    }
                }
                ret = max(ret, cnt);
            }
        }
        cout << ret << endl;
    }
    return 0;
}

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

A.sort(reverse=True)

j=0
prev=A[0]

longer_edge=0

for i,a in enumerate(A+[0,0,0,0,-1]):
  if a==prev:
    pass
  else:
    if not longer_edge:
      if (i-j)>=4:
        print(prev**2)
        exit()
      elif (i-j)>=2:
        longer_edge=prev
    elif longer_edge:
      if (i-j)>=2:
        print(prev*longer_edge)
        exit()
    prev=a
    j=i


Measured memory_bytes: 14224
A,B,C,X,Y = (int(i) for i in input().split()) 
money = 0


if A+B >= C*2:
    if X > Y:
        if X*2*C >= Y*2*C+(X-Y)*A:
            money += Y*2*C+(X-Y)*A
        else:
            money += X*2*C
    else:
        if Y*2*C >= X*2*C+(Y-X)*B:
            money += X*2*C+(Y-X)*B
        else:
            money += Y*2*C
else:
    money += A*X + B * Y

print(money)

Measured memory_bytes: 3064
def bubbleSort(a, n):
    number = 0
    flag = 1
    while flag:
        flag = 0
        for j in range(n - 1, 0, -1):
            if a[j] < a[j - 1]:
                a[j], a[j - 1] = a[j - 1], a[j]
                flag = 1
                number += 1
    return number


n = int(input())
ls = list(map(int, input().split()))
num = bubbleSort(ls, n)
for i in range(len(ls)):
    if i:
        print(" ", end="")
    print(ls[i], end="")
print()
print(num)


Measured memory_bytes: 5624
import java.util.Arrays;
import java.util.Scanner;
public class Main {

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

		String s1 = scan.next();
		String s2 = scan.next();

		char[] chars1 = s1.toCharArray();
		Arrays.sort(chars1);
		char[] chars2 = s2.toCharArray();
		Arrays.sort(chars2);

		String ns1 = new String(chars1);
		String ns2 = new String(chars2);
		StringBuilder sb = new StringBuilder(ns2);
		ns2 = sb.reverse().toString();

		if(ns1.compareTo(ns2) < 0){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		scan.close();
	}

}

Measured memory_bytes: 22740
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int f(vector<int> v, int val){
//	REP(i,v.size()) cerr << v[i] << " ";
//	cerr << endl;
	for (int i = 0; i < v.size(); ++i) {
		if(v[i]==val){
			return i;
		}
	}
	return -1;
}
ll fact(int n){
	if(n<=0) return (ll)0;
	if(n==1) return (ll)1;
	return (ll)(n*fact(n-1));
}

int main(int argc, const char * argv[]) {
	int n;
	cin >> n;
	int p[n],q[n];
	vector<int> pv,qv;
	ll ip=0,iq=0;

	REP(i,n) cin >> p[i];
	REP(i,n) cin >> q[i];
	REP(i,n){
		pv.push_back(i+1);
		qv.push_back(i+1);
	}

	REP(i,n){
		int pos = f(pv,p[i]);
		int fct =fact(n-i-1);
//		cerr << fct << " * " << pos << "=" << (fct*pos) << endl;
		ip += fct*pos;
		pv.erase(pv.begin()+pos);
	}
//	println(ip);
	REP(i,n){
		int pos = f(qv,q[i]);
		int fct =fact(n-i-1);
//		cerr << fct << " * " << pos << "=" << (fct*pos) << endl;
		iq += fct*pos;
		qv.erase(qv.begin()+pos);
	}
//	println(iq);
	println(abs(ip-iq));

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K;cin>>K;
  vector<int> A(32);
  A={1,1,1,2,1,2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout<<A[K-1]<<endl;
}

Measured memory_bytes: 384
n,c,k = map(int,input().split())
t = [0]*n
for i in range(n):
    t[i] = int(input())
t = sorted(t)
ans = 0
s = 0
u = float("Inf")
for i in range(n-1):
    s += 1
    u = min(u, t[i])
    if s == c or t[i+1] > u + k:
        ans += 1
        s = 0
        u = float("Inf")
print(ans+1)

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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define dbg(x) cout<<#x<<"="<<x<<endl

vector<bool> vis;

int main(){
  int N;
  cin>>N;
  vis.resize(N,false);
  vector<int> A(N),B(N);
  vector<int> p(N,-1);

  rep(i,N){
    cin>>A[i]>>B[i];
    A[i]--; B[i]--;
  }

  rep(i,N)p[A[i]]=B[i];

  rep(i,N){
    if(p[i]==-1){
      cout<<-1<<endl;
      return 0;
    }
  }

  int res=0;
  rep(i,N){
    if(vis[i])continue;
    int v=i;
    int cnt=0;
    while(!vis[v]){
      cnt++;
      vis[v]=true;
      v=p[v];
    }
    res+=cnt-1;
  }
  cout<<res<<endl;

  return 0;
}



Measured memory_bytes: 4100
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j;
  int a[100001],b[100001],p,n;
  int sm;
  a[0]=1;
  while(cin>>n&&n){
    memset(b,0,sizeof(b));
    j=0;
    for(i=1;i<n+1;i++){
      cin>>p;
      if(i%2){
	if(a[j]==-p)
	  b[j]++;
	else{
	  j++;
	  a[j]=-p;
	  b[j]=1;
	}  
      }else{
	if(a[j]==-p)
	  b[j]++;
	else{
	  b[j]++;
	  if(a[j-1]==-p){
	    j--;
	    a[j]=-p;
	    b[j]+=b[j+1];
	  }else
	    a[j]=-p;
	}
      }
    }
    sm=0;
    for(i=1;i<j+1;i++){
      if(a[i]==0)
	sm+=b[i];
    }
    cout<<sm<<endl;
  }
  return 0;
}

Measured memory_bytes: 1264
#include <cstdio>

#define MAX_N 100001
typedef long long ll;

/* -----------------------------------------------------------------------------
	大域データ
----------------------------------------------------------------------------- */
int N;			// 街の個数(1≦N≦10^5)
int A[MAX_N];	// 怪獣の数(1≦A[i]≦10^9)
int B[MAX_N];	// 勇者が倒せる怪獣の数(1≦B[i]≦10^9)

int main () {

	ll cnt = 0;

	// 整数の数の読込み
	scanf("%d", &N);

	// 怪獣数と勇者の限界値の読込み
	for(int i = 0; i <= N; i++) scanf("%d", A + i);
	for(int i = 0; i < N; i++) scanf("%d", B + i);

	for(int i = 0; i < N; i++) {
		// 街i
		if(A[i] <= B[i]) { B[i] -= A[i]; cnt += A[i]; A[i] = 0; }
		else { A[i] -= B[i]; cnt += B[i]; B[i] = 0; }
		// 街 i+1
		if(B[i] == 0) continue;

		if(A[i+1] <= B[i]) { B[i] -= A[i+1]; cnt += A[i+1]; A[i+1] = 0; }
		else { A[i+1] -= B[i]; cnt += B[i]; B[i] = 0; }		
	}

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

	return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <deque>
#include <iterator>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
  ll n, t; cin >> n >> t;
  vll a(n); REP(i, n) cin >> a[i];
  vll accmin(n), accmax(n);
  accmin[0] = a[0], accmax[n-1] = a[n-1];
  rep(i, 1, n) accmin[i] = min(a[i], accmin[i-1]);
  for (ll i=n-2; i>=0; i--) accmax[i] = max(a[i], accmax[i+1]);
  ll diff = 0;
  REP(i, n) chmax(diff, accmax[i]-accmin[i]);
  ll ans = 0;
  REP(i, n) {
    if (accmax[i] - a[i] == diff) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < b.size(); ++i)
        cout << a[i] << b[i];
    if (a.size() - b.size())
        cout << a.back();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define db double
#define pb push_back
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define all(a) a.begin(),a.end()
using namespace std;

 ll mod=1e9 +7;
const ll M=500006;
ll f[M],inv[M];
ll expo(ll base,ll exponent){
    ll ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}
void compute(){
    f[0]=1;
    rep(i,1,M-1){
        f[i]=(1LL*i*f[i-1])%mod;
    }
    inv[M-1]=expo(f[M-1],mod-2);
    for(ll i=M-2;i>=0;i--){
        inv[i]=(1LL*(i+1)*inv[i+1])%mod;
    }
}
ll C(ll n,ll r){
    return (1LL*((1LL*f[n]*inv[r])%mod)*inv[n-r])%mod;
}

vector<bool>  prime(1000002,true);
void Sieve() 
{ 
   
    for (int p=2; p*p<=1000001; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=1000001; i += p) 
                prime[i] = false; 
        } 
    } 
}

int main()
{
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
    // freopen("alchemy_input.txt", "r", stdin);
 //    // for writing output to output.txt
    // freopen("output.txt", "w", stdout);
 //    #endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // compute();
    ll tests=1,t=1;
   // cin>>tests;
    while(tests--)
    {
    	ll i,j,n;
    	cin>>n;
    	string s;
    	cin>>s;
    	i=0;j=n-1;
    	ll cnt=0;
    	while(i<j)
    	{
    		if(s[j]=='W') {j--;continue;}
    		else
    		{
    			while(i<j && s[i]!='W') i++;
    			if(i<j) {swap(s[i],s[j]);cnt++;}
    			else break;
    			j--;
    		}
    	}
    	cout<<cnt;
    }

	return 0;
}

Measured memory_bytes: 3900
#include <iostream>

using namespace std;

int main(){
	int A, B, K;
	cin >> A >> B >> K;

	for (int i = min(A, B), cnt = 0; cnt < K; i--){
		if (A % i == 0 && B % i == 0){
			cnt++;
			if (cnt == K){
				cout << i << endl;
			}
		}
	}

	return 0;
}


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


int main(){
	int n, ans = 0;
	ll a[10000];
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];

	for(int i = 0;i < n;i++){
		int count = 0;
		while(a[i] % 2 == 0) {
			a[i] /= 2;
			count++;
		}
		ans += count;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 384
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

class Graph {
	private int totalVertex;
	//adjMatrix[u][v] = 1 if there is an edge from u to v, otherwise 0
	private int[][] adjMatrix;
	//adjWeight[u][v] -- the weight of the edge from u to v if there is one
	private int[][] adjWeight;
	//if a node is settled (e.g., processed in the Dijkstra's algorithm)
	private Boolean[] ifSettled;
	public Graph() { totalVertex = 0; }
	public int getTotalVertex() { return totalVertex; }
	//load graph from standard input
	public void loadAdjMatrix() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjMatrix = new int[totalVertex][totalVertex];
		adjWeight = new int[totalVertex][totalVertex];
		ifSettled = new Boolean[totalVertex];
		int i, j;
		for(i = 0; i < totalVertex; i ++) {
			ifSettled[i] = false;
			for(j = 0; j < totalVertex; j ++) {
				adjMatrix[i][j] = adjWeight[i][j] = 0;
			}
		}
		int u, v;
		for(i = 0; i < totalVertex; i ++) {
			u = in.nextInt();
			int degree = in.nextInt();
			for(j = 0; j < degree; j ++) {
				v = in.nextInt(); 
				adjMatrix[u][v] = 1;
				adjWeight[u][v] = in.nextInt();
			}	
		}
		in.close();
	}
	//return weight of the edge from u to v if there is one
	public int getWeight(int u, int v) {
		return adjWeight[u][v];
	}
	//return neighbors of u as a LinkedList
	public LinkedList<Integer> getNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if(adjMatrix[u][v] == 1) tmp.add(v);
		}
		return tmp;
	}
	//return unsettled neighbors of u as a LinkedList
	public LinkedList<Integer> getUnsettledNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if((adjMatrix[u][v] == 1) && (ifSettled[v] == false)) tmp.add(v);
		}
		return tmp;
	}
	//return the unsettled node that has the smallest dist
	public int getUnsettledNearest(int[] dist) {
		int md = Integer.MAX_VALUE;
		int mv = -1;
		int v;
		for(v = 0; v < totalVertex; v ++) {
			if((ifSettled[v] == false) && (dist[v] < md)) {
				md = dist[v];
				mv = v;
			}
		}
		return mv;
	}
	//implement the following	
	public int[] Dijkstra(int s) {
		ArrayList<Integer> S = new ArrayList<Integer>();
		int[] dist = new int[totalVertex];
		for(int i = 0; i<dist.length;i++) {
			dist[i]=999999999;
		}
		dist[s]=0;
		while(S.size()<totalVertex) {
			//int n = getUnsettledNearest(dist);
			int v = getUnsettledNearest(dist);
			LinkedList<Integer> tmp = getUnsettledNeighbors(v);
			for (int i = 0;i<tmp.size();i++) {
				dist[tmp.get(i)]= Math.min(dist[v]+getWeight(v,tmp.get(i)), dist[tmp.get(i)]);
			}
			ifSettled[v]=true;
			S.add(v);
		}
		return dist;
	}
}

public class Main {
	public static void main(String[] argv) {
		Graph g = new Graph();
		g.loadAdjMatrix();
		int[] dist = g.Dijkstra(0);
		for(int i = 0; i < g.getTotalVertex(); i ++) {
			System.out.println(i + " " + dist[i]);
		}
	}
}


Measured memory_bytes: 39924
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<complex>
#include<stack>
#include<cmath>

using namespace std;

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



int main(){
	
	string sss;
	getline(cin,sss);
	
	while(1){
		string a;
		getline(cin,a);
		if(cin.eof())break;
		
		reps(alpha,2,100){
			reps(beta,2,100){
				
				bool ok = true;
				map<int,int> visit;
				rep(j,26){
					int next = (j*alpha+beta)%26;
					if(visit[next]==0){
						visit[next]=1;
					}else{
						ok=false;
					}
				}
				if(!ok)continue;
				
				string b;
				rep(j,a.size()){
					if('a'<=a[j]&&a[j]<='z')b+=((a[j]-'a')*alpha+beta)%26+'a';
					else b+=a[j];
				}
				if(b.find("this")!=-1 || b.find("that")!=-1){
					cout<<b<<endl;
					goto A;
				}
			}
		}
		A:;
	}
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
int n,k;
int a[maxn];
bool check(int x)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i]/x;
		if(a[i]%x==0)
			sum--;
	}
	if(sum>k)
		return 0;
	else
		return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>k;
	int maxv=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxv=max(maxv,a[i]);
	}
	int l=1,r=1000000000,ans;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}




Measured memory_bytes: 4324
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#define mp make_pair
#define ii pair < ll, ll >
#define F first
#define S second
#define mod ((ll)(1e9+7))
#define ll long long int

using namespace std;

vector < vector < ll > > g, W;
vector < ll > d;
vector < ll > path;

void djkstra(ll nodo){
    priority_queue < ii, vector < ii >, greater < ii > > pq;
    pq.push( mp(0, nodo) );
    d[nodo] = 0;
    while(!pq.empty()){
        ll u = pq.top().S;
        pq.pop();
        for(int i = 0 ; i < g[u].size() ; i++){
            ll v = g[u][i];
            ll cost = W[u][i];
            if(d[v] > d[u] + cost){
                d[v] = d[u] + cost;
                path[v] = u;
                pq.push( mp(d[v], v) );
            }
        }
    }
}

int main()
{
    ll n, m, a, b, c;
    cin >> n >> m;
    map < ii, bool > M;
    g.assign( n, vector < ll > (0) );
    W.assign( n, vector < ll > (0) );
    vector < ii > v;
    while(m--){
        cin >> a >> b >> c;
        a--;b--;
        ii z = mp( min(a, b), max(a, b) );
        v.push_back( z );
        g[a].push_back(b);
        g[b].push_back(a);
        W[a].push_back(c);
        W[b].push_back(c);
    }
    for(ll i = 0 ; i < n ; i++){
        d.assign(n, (1LL<<62) );
        path.assign(n, -1);
        djkstra(i);
        for(ll j = 0 ; j < n ; j++){
            if(i == j) continue;
            ii z = mp( min(path[j], j), max(path[j], j) );
            M[z] = true;
        }
    }
    int res = 0;
    for(int i = 0 ; i < v.size() ; i++){
        if( !M[ v[i] ] )res++;
    }
    cout << res;
    return 0;
}












Measured memory_bytes: 384