akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_left, bisect_right
mx = 10**10

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

a, b, q = map(int, input().split())
aa = []
bb = []
for i in range(a):
  aa.append(int(input()))
for i in range(b):
  bb.append(int(input()))

aa.append(mx * 2)
bb.append(mx * 2)
aa.insert(0, -mx * 2)
bb.insert(0, -mx * 2)
#print(f'aa={aa}, bb={bb}')

for i in range(q):
  qi = int(input())
  #print(f'q = {qi}')

  a_low = find_lt(aa, qi)
  a_high = find_gt(aa, qi)

  b_low = find_lt(bb, qi)
  b_high = find_gt(bb, qi)

  len1 = qi - min([a_low, b_low])
  len2 = max([a_high, b_high]) - qi
  len3 = (a_high - qi) + (a_high - b_low)
  len4 = (b_high - qi) + (b_high - a_low)
  len5 = (qi - b_low) + (a_high - b_low)
  len6 = (qi - a_low) + (b_high - a_low)
  lens = [len1, len2, len3, len4, len5, len6]
  print(min(lens))



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

int N, M, K;
map< pair< int, int >, long long > dp;
long long rec(int idx, int sum)
{
  if(idx == N) return(max(1, sum - K));
  if(dp.find({idx, sum}) != dp.end()) return(dp[{idx, sum}]);
  long long ret = 0;
  for(int i = 1; i <= M; i++) ret += rec(idx + 1, sum + i);
  return(dp[{idx, sum}] = ret);
}

int main()
{
  while(cin >> N >> M >> K, N) {
    dp.clear();
    long long ret = 0, power = 1;
    for(int i = 0; i < N; i++) power *= M;
    cout << fixed << setprecision(10) << 1.0 * rec(0, 0) / power << endl;
  }
}

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

string s, t;
//              pos   , ch  = いくつ次に進めばいいか
long long jump[100005][50];

int main(){
	cin >> s >> t;
	string ss = s + s;

	for(char ch = 'a'; ch <= 'z'; ch++){
		long long last_pos = -1;
		for(long long idx = ss.size() - 1; idx >= 0; idx--){
			if(idx < s.size()){
				if(last_pos >= 0) {
					jump[idx][ch-'a'] = last_pos - idx;
				} else {
					jump[idx][ch-'a'] = -1;
				}
			}
			if(ss[idx] == ch){
				last_pos = idx;
			}
		}
	}

	long long ans = 0;
	for(long long i = 0; i < t.size(); i++){
		if(i == 0 && t[0] == s[0]){
			continue;
		}
		if(jump[(ans%s.size())][t[i] - 'a'] == -1){
			cout << -1 << endl;
			return 0;
		}
		ans += jump[(ans%s.size())][t[i] - 'a'];
	}
	cout << ans + 1LL << endl;

	//for(long long i = 0; i < s.size(); i++){
	//	for(char ch = 'a'; ch <= 'z'; ch++){
	//		cout << "jump[" << i << "][" << ch << "] = " << jump[i][ch-'a'] << endl;
	//	}
	//}

}


Measured memory_bytes: 39808
#include <iostream>
#include <algorithm>
#include<string>
#include<cmath>
#include<stack>
#include <vector>
#include<queue>
#include <random>
#include <cstdint>
#include <bitset>
#include <iomanip>
#include<utility>
using namespace std;
using ll = long long;

int main()
{
	int n, l, a[100000];
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; i++) {
		if (a[i] + a[i + 1] >= l) {
			cout << "Possible" << endl;
			for (int j = n-1; j > i+1; j--) {
				cout << j << endl;
			}
			for (int j = 1; j <= i + 1; j++) {
				cout << j << endl;
			}
			return 0;
		}
	}
	cout << "Impossible" << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
	int N, X, i, count = 1;
	int L[101] = {}, ans;
	scanf("%d %d", &N, &X);
	
	for (i = 0; i < N; i++) {
		scanf("%d", &L[i]);
	}

	ans = L[0];

	for (i = 1; i < N + 1; i++) {
		if (ans <= X) {
			count++;
		}

		else {
			break;
		}

		ans += L[i];
	}

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

	return 0;
}

Measured memory_bytes: 128
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::{i32, i64, u32, u64, f64};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{VecDeque, HashMap, BTreeMap, HashSet, BTreeSet};
#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::mem::{swap};

fn main() {
    input! {
        n: usize,
        s: String,
        t: String,
    }
    for i in 0..(n + 1) {
        if s.ends_with(&t[0..(n - i)]) {
            println!("{}", n + i);
            break;
        }
    }
}



Measured memory_bytes: 4352
//49
#include<iostream>
#include<iomanip>
#include<cstring>

using namespace std;

#define tox(c) (((c)-'A')%3)
#define toy(c) (((c)-'A')/3)

int main(){
  for(int n;cin>>n,n;){
    char s,t,b;
    double p[3][3]={};
    cin>>s>>t>>b;
    p[toy(s)][tox(s)]=1;
    while(n--){
      double pt[3][3]={};
      for(int y=0;y<3;y++){
	for(int x=0;x<3;x++){
	  int d[]={0,1,0,-1,0};
	  for(int i=0;i<4;i++){
	    int ny=y+d[i];
	    int nx=x+d[i+1];
	    if(0<=ny&&ny<3&&0<=nx&&nx<3&&!(ny==toy(b)&&nx==tox(b))){
	      pt[ny][nx]+=p[y][x]/4;
	    }else{
	      pt[y][x]+=p[y][x]/4;
	    }
	  }
	}
      }
      memcpy(p,pt,sizeof(p));
    }
    cout<<fixed<<setprecision(6)<<p[toy(t)][tox(t)]<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
import scala.io.StdIn.readInt

object Main {
  def scan(n:Int, cnt:Int):Int = {
    if(n==1) cnt
    else {
      val m = if(n%2==0)n/2 else n*3+1
      scan(m,cnt+1)
    }
  }

  def main(args:Array[String]) = {
    var n = 0
    while( {n=readInt;n} != 0 ){
      println(scan(n,0))
    }
  }
}

Measured memory_bytes: 43652
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF = pow(10, 7);

int main(){
  int n;cin>>n;
  int dn=0, t=n, ans=0;
  while(t>0){dn++;t/=10;}
  for(int i=1;i<dn;i+=2){
    ans+=9*pow(100, (i-1)/2);
  }
  if(dn%2){
    ans+=n-pow(10, dn-1)+1;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
int a[N];
int n;
map<int, int> mp;
bool f(int m) {
    int zeros = 0;
    mp.clear();
    if (m == 1) {
        for (int i = 2; i <= n; i++) {
            if (a[i] <= a[i - 1]) {
                return false;
            }
        }
        return true;
    }
    for (int i = 2; i <= n; i++) {
        if (a[i] > a[i - 1]) {
            while (!mp.empty()) {
                auto it = mp.end();
                --it;
                if (it->first > a[i - 1]) {
                    mp.erase(it);
                } else {
                    break;
                }
            }
            continue;
        } else {
            for (int j = a[i]; j >= 1; j--) {
                int c = 0;
                if (mp.find(j) != mp.end()) {
                    c = mp[j];
                }
                c++;
                if (c != m) {
                    mp[j] = c;
                    break;
                } else {
                    mp.erase(j);
                }
                if (j == 1) {
                    return false;
                }
            }
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int l = 1;
    int r = n;
    while (r - l > 0) {
        int mid = (r + l) / 2;
        if (f(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
    return 0;
}

Measured memory_bytes: 9856
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define LL long long
#define MOD 1000000007
inline int read()
{
	LL x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int n,m,f[100010],head[1010],top,t1,t2,d[1010],l[1010];
bool b[2010]; 
LL ret,p;
int find(int x)
{
	return f[x]==x?x:find(f[x]);
}
inline bool merge(int x,int y)
{
	int X=find(x),Y=find(y);
	if(X==Y)return 0;
	f[X]=Y;
	return 1;
}
struct data
{
	LL u,v,w;
	data(int _u=0,int _v=0,LL _w=0):u(_u),v(_v),w(_w){}
	friend bool inline operator<(const data &e1,const data &e2)
	{
		return e1.w<e2.w;
	}
}a[100010];
struct edge
{
	int v,p;
	LL l;
	edge(int _v=0,int _p=0,LL _l=0):v(_v),p(_p),l(_l){}
}e[100010];
inline void addedge(int u,int v,int l)
{
	e[++top]=edge(v,head[u],l);
	head[u]=top;
	e[++top]=edge(u,head[v],l);
	head[v]=top;
} 
void dfs(int u,int fa)
{
	d[u]=d[fa]+1;
	f[u]=fa;
	for(int i=head[u];i;i=e[i].p)
	{
		if(e[i].v==fa)
		{
			l[u]=e[i].l;
			continue;
		}
		dfs(e[i].v,u);
	}
}
int query(int u,int v)
{
	int ret=0;
	if(d[v]>d[u])swap(u,v);
	while(d[u]!=d[v])
	{
		ret=max(ret,l[u]);
		u=f[u];
	}
	while(u!=v)
	{
		ret=max(ret,max(l[u],l[v]));
		u=f[u];
		v=f[v];
	}
	return ret;
}
LL pow(LL x,int y)
{
	LL ret=1;
	while(y)
	{
		if(y&1)ret=ret*x%MOD;
		x=x*x%MOD;
		y>>=1; 
	}
	return ret;
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		a[i]=data(u,v,w);
	}
	sort(a+1,a+m+1);
	for(int i=1,j=0;i<=m&&j<=n;i++)
	{
		if(merge(a[i].u,a[i].v))
		{
			ret+=a[i].w;
			addedge(a[i].u,a[i].v,a[i].w);
			b[i]=1;
		}
	}
	if(ret>p)
	{
		cout<<0<<endl;
		return 0;
	}
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		if(b[i])continue;
		if(a[i].u==670&&a[i].v==22)
		{
			a[i].u=a[i].u;
		}
		LL t=ret+a[i].w-query(a[i].u,a[i].v);
		if(t>p)t1++;
		if(t==p)t2++;
	}
	if(ret==p)cout<<(1LL*(pow(1LL*2,n-1+t2)-2+MOD)*pow(1LL*2,t1))%MOD<<endl; 
	else cout<<(1LL*pow(1LL*2,t1+1)*(pow(1LL*2,t2)-1+MOD))%MOD<<endl;
	return 0;	
} 

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

int main() {
  int A;//,B,C,D;
    int B;
  int C;
 int D;
   cin >>A;//,B,C,D;
  cin >>B;
  cin >>C;
  cin >>D;
    if  ((A+B)==(C+D)){
      
  cout << "Balanced" << endl;
    }
  else if ((A+B)<=(C+D)){
    cout << "Right" << endl;
  }
  else {
    cout << "Left" << endl;
  }
}

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

using namespace std;

const int NS = (int)1e5+4;
int N, M;
struct UN{
    int par, rk;
}un[NS];
int arr[NS][3];
long long out[NS];

int fd(int x){
    return x==un[x].par? x:un[x].par=fd(un[x].par);
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i=0;i<M;++i) scanf("%d %d", arr[i], arr[i]+1);
    for(int i=1;i<=N;++i) un[i].par = i, un[i].rk = 1;
    long long ans = (long long)N*(N-1)/2;
    for(int i=M-1;i>=0;--i){
        out[i] = ans;
        int pa = fd(arr[i][0]), pb = fd(arr[i][1]);
        if(pa!=pb){
            ans -= (long long)un[pa].rk*un[pb].rk;
            if(un[pa].rk>un[pb].rk){
                un[pb].par = pa, un[pa].rk += un[pb].rk;
            }
            else{
                un[pa].par = pb, un[pb].rk += un[pa].rk;
            }
        }
    }
    for(int i=0;i<M;++i) printf("%lld\n", out[i]);
    return 0;
}


Measured memory_bytes: 4096
#include<iostream>

using namespace std;

int main()
{
    int a, b, c;
    cin>>a>>b>>c;
    int n = a * 10;
    n += b;
    n *= 10;
    n += c;
    if(n % 4 == 0) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 3588
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let h: usize = itr.next().unwrap().parse().unwrap();
    let w: usize = itr.next().unwrap().parse().unwrap();
    let mut dp: Vec<Vec<u64>> = (0..10)
        .map(|_| {
            (0..10)
                .map(|_| itr.next().unwrap().parse().unwrap())
                .collect()
        })
        .collect();
    for k in 0..10 {
        for i in 0..10 {
            for j in 0..10 {
                dp[i][j] = std::cmp::min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }

    let mut ans: u64 = 0;
    for _ in 0..h * w {
        let a: isize = itr.next().unwrap().parse().unwrap();
        if a != -1 {
            ans += dp[a as usize][1];
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4476
'use strict'

const main = input => {
	const args = input.trim().split('\n')
	const s = args[0].split('').sort((a, b) => a.charCodeAt() - b.charCodeAt()).join('')
	const t = args[1].split('').sort((a, b) => b.charCodeAt() - a.charCodeAt()).join('')
	if (s < t) console.log('Yes')
	else console.log('No')
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


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

main(){
    int a,b;
    char s;
    while(1){
    cin >> a >> s >> b;
      switch(s){
        case '+':
          cout << a + b << endl;
          break;
        case '-':
          cout << a - b << endl;
          break;
        case '*':
          cout << a * b << endl;
          break;
        case '/':
          cout << a / b << endl;
          break;
        
      }
      if(s == '?'){
          break;
      }
    }
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);

const ll MOD = 1000000007;

ll power(ll a, ll b, ll mod) {
  ll tmp=a;
  ll tmpp=1;
  ll ret=1;
  while(1){
    if(b%(tmpp*2)){
      ret=ret*tmp%mod;
      b-=tmpp;
    }
    if(b==0) break;
    tmp=tmp*tmp%mod;
    tmpp*=2;
  }
  return ret;
}

int main() {
  ll m,n;cin>>m>>n;
  cout<<power(m,n,MOD)<<endl;
}

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

#define int long long
#define pb push_back 
#define pf push_front 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i, n) for ( int i = 0 ; i < (n); i++ )
#define All(v) v.begin(), v.end()

typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;


signed main() {
  string S, T;
  cin >> S >> T;

  bool flag = true;
  int s = 0, t = 0, p = 0;;
  while ( 1 ) {
    if ( p == S.size() ) break;
    if ( flag ) {
      if ( s == S.size() ) break;
      while ( 1 ) {
	if ( S[s] == S[p] ) {
	  s++; p++;
	  break;
	}
	s++;
	if ( s == S.size() ) break;
      }
      flag = false;
    } else {
      if ( t == T.size() ) break;
      while ( 1 ) {
	if ( T[t] == S[p] ) {
	  t++; p++;
	  break;
	}
	t++;
	if ( t == T.size() ) break;
      }
      flag = true;
    }
  }

  if ( p == S.size() ) {
    cout << "Yes" << endl;
    return 0;
  }

  
  flag = false;
  s = 0; t = 0; p = 0;;
  while ( 1 ) {
    if ( p == S.size() ) break;
    if ( flag ) {
      if ( s == S.size() ) break;
      while ( 1 ) {
	if ( S[s] == S[p] ) {
	  s++; p++;
	  break;
	}
	s++;
	if ( s == S.size() ) break;
      }
      flag = false;
    } else {
      if ( t == T.size() ) break;
      while ( 1 ) {
	if ( T[t] == S[p] ) {
	  t++; p++;
	  break;
	}
	t++;
	if ( t == T.size() ) break;
      }
      flag = true;
    }
  }
  
  if ( p == S.size() ) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int gcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  string s;
  cin>>s;
  bool flag=true;
  map<char,int> mp;
  rep(i,s.size()) mp[s[i]]++;
  for(auto a:mp){
    if(a.second%2!=0){
      flag=false;
      break;
    }
  }
  if(flag){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  
  
}
///////////////////////////



Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a[1000],n,i,sum;
    scanf("%d",&n);
    
    for(i=0;i<n-1;i++)
        scanf("%d",&a[i]);
    
    sum=a[0];

    for(i=0;i<n-2;i++)
    {
        if(a[i]>=a[i+1])
           sum+=a[i+1];
        else
           sum+=a[i];
    }
    
    sum+=a[n-2];
    printf("%d\n",sum);
   
    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import java.util.Scanner;
import java.io.*;
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
 
public class Main
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    public static void main (String[] args) 
	{
        //code by sushant kumar
        FastReader in=new FastReader();
        int n=in.nextInt();
        int k=in.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i]=in.nextInt();

        }
        Arrays.sort(arr);
        int sum=0;
        for(int i=0;i<=k-1;i++)
        {
            sum+=arr[i];
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 26040
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;
const int MOD = 1000000007;

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

void COMinit()
{
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++)
  {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

int64_t COM(int n, int k)
{
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
  int64_t N, idx1, idx2;
  cin >> N;
  vector<int64_t> A(N + 1);
  vector<int> C(N + 1, -1);
  for (int i = 0; i < N + 1; i++)
  {
    cin >> A[i];
    if (C.at(A[i]) != -1) // 既出
    {
      idx1 = C.at(A[i]); // 1回目のiを保存
      idx2 = i;          // 2回目のiを保存
    }
    C[A[i]] = i;
  }
  COMinit();
  cout << N << endl;
  for (int k = 2; k <= N + 1; k++)
  {
    int64_t all = COM(N + 1, k);
    int64_t ex1 = (idx1 > 0 && idx1 >= k - 1) ? COM(idx1, k - 1) : 0;
    int64_t ex2 = (N - idx2 > 0 && N - idx2 >= k - 1) ? COM(N - idx2, k - 1) : 0;
    int64_t ex3 = (idx1 + N - idx2 > 0 && idx1 + N - idx2 >= k - 1) ? COM(idx1 + N - idx2, k - 1) : 0;
    cout << (all - ex1 - ex2 - (ex3 - ex1 - ex2) + MOD) % MOD << endl;
  }
}


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

int N, M, Q;

unsigned long max = 0;

std::vector<int> A_array;
std::vector<int> B_array;
std::vector<int> C_array;
std::vector<unsigned long> D_array;

unsigned long calc_point(const std::vector<int>& my_array) {
  unsigned long sum = 0;
  for (int i = 0 ; i < Q; ++i) {
    if (C_array.at(i) == my_array.at(B_array.at(i)) - my_array.at(A_array.at(i))) {
      sum += D_array.at(i);
    }
  }
  return sum;
}


void dfs(int node, int depth, std::vector<int>& my_array) {
  if (depth == N) {
    max = std::max(max, calc_point(my_array));
    return;
  }

  for (int i = node; i <= M; ++i) {
    my_array.at(depth) = i;
    dfs(i, depth + 1, my_array);
  }
}

int main() {
  std::cin >> N >> M >> Q;

  A_array.resize(Q);
  B_array.resize(Q);
  C_array.resize(Q);
  D_array.resize(Q);
  for (int i = 0; i < Q; ++i) {
    std::cin >> A_array.at(i) >> B_array.at(i) >> C_array.at(i) >> D_array.at(i);
    A_array.at(i) -= 1;
    B_array.at(i) -= 1;
  }

  std::vector<int> my_array(N, 0);

  dfs(1, 0, my_array);

  std::cout << max << std::endl;

  return 0;
}


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

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline T gcd(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T lcm(T a,T b){return a*b/gcd(a,b);}

const int INF=1e9;
const double eps=0.0000000001;



int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int siro=0,kuro=0;
  FOR(i,n){
    if(s[i]=='#'){
      kuro++;
    }else{
      siro++;
    }
  }
  int kuro2[1000000];
  if(s[0]=='#'){
    kuro2[0]=1;
  }
  for(int i=1;i<n;i++){
    if(s[i]=='#'){
      kuro2[i]=kuro2[i-1]+1;
    }else{
      kuro2[i]=kuro2[i-1];
    }
  }
  int ans;
  ans=min(kuro,siro);
  FOR(i,n-1){
    chmin(ans,kuro2[i]+siro-(i+1-kuro2[i]));
  }
  cout << ans << endl;
}


Measured memory_bytes: 3204
n = int(input())
#n, k = list(map(int, input().split()))
#A = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# q = int(input())
# a = list(map(int, input().split()))
# b = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
#ab = [list(map(int, input().split())) for i in range(n)]
# print(min(15*n, 100*(n//10+1), 100*(n//10)+15*(n % 10)))

if n % 1000 == 0:
    print(0)
    exit()

for i in range(11):
    if n > 1000*i and n < 1000*(i+1):
        print(1000*(i+1)-n)
        exit()
print(0)


Measured memory_bytes: 9160
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons, std.uni;

void main() {
    const tmp = readln.split.to!(int[]);
    const N = tmp[0], K = tmp[1];
    const S = readln.chomp;
    S.enumerate.map!(c => c.index + 1 == K ? c.value.toLower : c.value).array.to!string.writeln;
}



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

using namespace std;

int main() {
    int A,B,C,D;
    cin >> A >> B >> C >> D;
    int S,T;
    S = A * B;
    T = C * D;
    int ans;
    if(S > T){
        ans = S;
    }
    else if(S < T){
        ans = T;
    }
    else if(S == T){
        ans = S;
    }
    cout << ans << endl;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> h(N);
  for(int i = 0; i < N; i++){
    cin >> h.at(i);
  }
  
  vector<bool> A(N, true);
  
  int a, b;
  for(int i = 0; i < M; i++){
    cin >> a >> b;
    if(h.at(a - 1) > h.at(b - 1)) swap(a, b);
    A.at(a - 1) = false;
    if(h.at(a - 1) == h.at(b - 1)) A.at(b - 1) = false;
  }
  
  int count = 0;
  
  for(int i = 0; i < N; i++){
    if(A.at(i)) count++;
  }
  
  cout << count << endl;
  
}

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

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

  string s;
  cin >> s;
  if (s.size() <= K) {
    cout << s << endl;
  } else {
    string output = s.substr(0, K) + "...";
    cout << output << endl;
  }
}

Measured memory_bytes: 3632
from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
acc=list(accumulate(a))
left=0; right=2
ans=float('inf')
for center in range(1,n-1):
    while abs(acc[center]-acc[left]-acc[left]) > abs(acc[center]-acc[left+1]-acc[left+1]):
        left+=1 
    while abs(acc[n-1]-acc[right]-(acc[right]-acc[center])) > abs(acc[n-1]-acc[right+1]-(acc[right+1]-acc[center])):
        right+=1
    score=acc[left], acc[center]-acc[left], acc[right]-acc[center], acc[n-1]-acc[right]
    ans=min(ans, max(score)-min(score))

print(ans)


Measured memory_bytes: 24180
#include <bits/stdc++.h>
using namespace std;
template<typename T>
//外に隣接行列必須
T Warshall(int n,T graph){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    return graph;
}

#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
const ll inf = 1e18+7;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,l;
    cin >> n >> m >> l;
    vector<vector<ll>> graph(n,vector<ll>(n,inf));
    rep(i,0,n) graph[i][i] = 0;
    rep(i,0,m){
        ll a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        graph[a][b] = c;
        graph[b][a] = c;
    }
    graph = Warshall(n,graph);
    rep(i,0,n){
        rep(j,0,n){
            if(i==j) continue;
            else if(graph[i][j] <= l) graph[i][j] = 1;
            else graph[i][j] = inf;
        }
    }
    graph = Warshall(n,graph);
    ll q;
    cin >> q;
    rep(i,0,q){
        int s,t;
        cin >> s >> t;
        s--;t--;
        if(graph[s][t] == inf) cout << -1 << endl;
        else cout << graph[s][t]-1 << endl;
    }
}

Measured memory_bytes: 1664
import java.util.Scanner;

public class Main{
	public static void main(String[]args){

		Scanner sc=new Scanner(System.in);

		int n=sc.nextInt();
		double x[]=new double[n];
		String v[]=new String[n];
		int jpy=0;
		double btc=0;

		for(int i=0;i<n;i++){
			x[i]=sc.nextDouble();
			v[i]=sc.next();
		}

		for(int i=0;i<n;i++){
			if(money(v[i])){
				jpy+=x[i];
			}else{
				btc+=x[i];
			}
		}

		System.out.println((double)jpy+btc*380000.0);

	}

	public static boolean money(String a){
		if(a.equals("JPY")){
			return true;
		}else{
			return false;
		}
	}

}


Measured memory_bytes: 22996
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <set>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define repp(i,k,n) for(int i=k;i<(int)n;i++)
#define rei(n) for(int i=0;i<(int)n;i++)
#define rel(n) for(int l=0;l<(int)n;l++)
#define al(s) s.begin(),s.end()
#define INT_MAX 2147483647
#define debug(x) cout<<#x<<": "<<x<<endl;
#define PI 2*acos(0,0)
#define pb push_back
#define inin(x) int x; cin>>x;
struct Calendar
{
	long long year;
	long long month;
	long long day;
	long long dat[2][13];
	Calendar(long long y, long long m, long long d)
	{
		year = y;
		month = m;
		day = d;
		dat[0][0] = dat[1][0] = 0;
		dat[0][1] = dat[1][1] = 31;
		dat[0][2] = dat[1][2] = 28;
		dat[0][3] = dat[1][3] = 31;
		dat[0][4] = dat[1][4] = 30;
		dat[0][5] = dat[1][5] = 31;
		dat[0][6] = dat[1][6] = 30;
		dat[0][7] = dat[1][7] = 31;
		dat[0][8] = dat[1][8] = 31;
		dat[0][9] = dat[1][9] = 30;
		dat[0][10] = dat[1][10] = 31;
		dat[0][11] = dat[1][11] = 30;
		dat[0][12] = dat[1][12] = 31;
		dat[1][2] = 29;
	}
	int uruu()
	{
		if (year % 4 == 0)
		{
			if (year % 400 != 0 && year % 100 == 0)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		return 0;
	}
	int uruu(long long y)
	{
		if (y % 4 == 0)
		{
			if (y % 400 != 0 && y % 100 == 0)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		return 0;
	}
	long long pday(long long d)
	{
		day += d;
		for (;; month++)
		{
			if (month >= 13)
			{
				year++;
				month = 1;
			}

			if (dat[uruu()][month] < day)
			{
				day -= dat[uruu()][month];
			}
			else
			{
				break;
			}
		}
		pmonth(0);
		return d;
	}
	long long pmonth(long long m)
	{
		month += m;
		for (;; year++)
		{
			if (month > 12)
			{
				month -= 12;
			}
			else
			{
				break;
			}
		}
		return m;
	}
	long long pyear(long long y)
	{
		year += y;
		return y;
	}
	long long dif(Calendar c)
	{
		long long ans = 0;
		Calendar a(year, month, day);
		ans -= a.day;
		ans += c.day;
		a.day = 0;
		c.day = 0;
		for (; a.month >= 1; a.month--)
		{
			ans -= dat[a.uruu()][a.month-1];
		}
		for (; c.month >= 1; c.month--)
		{
			ans += dat[c.uruu()][c.month-1];
		}
		for (; a.year != c.year; a.year++)
		{
			ans += 365;
			if (a.uruu())ans++;
		}
		return ans;
	}


};



int main()
{
	int m;
	while (cin >> m&&m)
	{
		bool ans = true;
		inin(n);
		int sugoroku[256] = {};
		int cost[256][256];
		rei(256)rel(256)cost[i][l] = INT_MAX;
		rei(n)
		{
			cin >> sugoroku[i+1];
		}

		for (int i = 0;i<=n+1; i++)
		{
			cost[i][i] = 1;
			for (int l = 1; l <= m; l++)
			{
				cost[max(0, min(n + 1, i + l + sugoroku[min(n+1,i + l)]))][i] = 1;
			}
		}
		for (int k = 0; k <= n + 1; k++)
		{
			for (int i = 0; i <= n + 1; i++) 
			{
				for (int l = 0; l <= n + 1; l++)
				{
					if (cost[i][k] + cost[k][l] == 2)
					{
						cost[i][l] = 1;
					}
				}
			}
		}

		for (int i = 0; i <= n + 1; i++)
		{
			if (cost[i][0] == 1 && cost[n + 1][i] != 1)
			{
				ans = false;
			}
		}
		cout << ((ans) ? "OK" : "NG") << endl;
	}
}

Measured memory_bytes: 1412
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N,M,X = LI()
C = [0]*N
A = []
for i in range(N):
    x = LI()
    C[i] = x[0]
    A.append(x[1:])

Z = list(product([False,True],repeat=N))
ans = float('inf')
for z in Z:
    cost = 0
    rikai = [0]*M
    for i in range(len(z)):
        if z[i]:
            cost += C[i]
            for j in range(M):
                rikai[j] += A[i][j]
    flag = False
    for i in range(M):
        if rikai[i] < X:
            flag = True
            break
    if not flag:
        if cost < ans:
            ans = cost

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 69316
class Main{
	public static void main(String[] a){
		for(int i = 1; i < 10; i++){
			for(int j = 1; j < 10; j++){
				System.out.println(i + "x" + j + "=" + i*j);
				//System.Console.WriteLine(i + "x" + j + "=" + i*j);
			}
		}
	}
}

Measured memory_bytes: 16852
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;
typedef pair<int,int> P;
typedef long long ll;
ll n,m,k,ans;
string s;

int main(){
  cin >> n >> k;
  int ans = 0;
  if(n == 1) ans+= 300000;
  else if(n==2) ans+=200000;
  else if(n == 3) ans+=100000;
  if(k == 1) ans+= 300000;
  else if(k == 2) ans += 200000;
  else if(k == 3) ans += 100000;
  if(n == 1 && k == 1) ans += 400000;
  cout << ans << "\n";
}

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

int main() {
    char b, c[128];
    c['A'] = 'T';
    c['G'] = 'C';
    c['C'] = 'G';
    c['T'] = 'A';

    cin >> b;
    cout << c[(int)b] << endl;
    return 0;
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

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

int main()
{
    ios::sync_with_stdio(false);

    int h, w;
    cin >> h >> w;
    string s[h];
    REP(i, h) cin >> s[i];

    queue<pii> q;
    vvi b(h, vector<int>(w, 1e9));

    // startの設定
    int left = h * w;
    REP(i, h) REP(j, w) {
        if(s[i][j] == '#') {
            q.push(pii(i,j));
            b[i][j] = 0;
            --left;
        }
    }
    
    while(!q.empty()) {
        pii p = q.front(); q.pop();
        int i = p.first, j = p.second;

        // goalの設定
        if(!left) break;

        // update用関数
        auto update = [&](int i, int j, int x) {
            if(b[i][j] != 1e9) return;
            b[i][j] = x;
            q.push(pii(i,j));
            --left;
        };
        
        // 全方向検索
        REP(dir, 4) {
            int ni = i + di[dir];
            int nj = j + dj[dir];
            if(ni < 0 || nj < 0 || ni >= h || nj >= w) continue;
            
            // 壁の設定
            if(s[ni][nj] == '#') continue;
            update(ni, nj, b[i][j] + 1);
        }
    }
    int ans = 0;
    REP(i, h) REP(j, w) ans = max(ans, b[i][j]);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 13456
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

/**
 * Cards
 */
public class Main {

	static final int INF = 1 << 29;

	static int S, T;
	static List<List<Edge>> G;
	static boolean[] used;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int m, n;
			m = parseInt(line.substring(0, line.indexOf(' ')));
			n = parseInt(line.substring(line.indexOf(' ') + 1));
			if ((m | n) == 0) break;

			S = m + n;
			T = S + 1;

			int[] ms = new int[m];
			int[] ns = new int[n];

			for (int i = 0; i < m; ) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				while (st.hasMoreTokens()) {
					ms[i] = parseInt(st.nextToken());
					i++;
				}
			}

			for (int i = 0; i < n; ) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				while (st.hasMoreTokens()) {
					ns[i] = parseInt(st.nextToken());
					i++;
				}
			}

			//
			G = new ArrayList<>();
			used = new boolean[T + 1];

			for (int i = 0; i <= T; i++) {
				G.add(new ArrayList<>());
			}

			//S -> blue
			for (int i = 0; i < m; i++) {
				G.get(S).add(new Edge(i, 1, G.get(i).size()));
				G.get(i).add(new Edge(S, 0, G.get(S).size() - 1));
			}

			//red -> T
			for (int i = m; i < m + n; i++) {
				G.get(i).add(new Edge(T, 1, G.get(T).size()));
				G.get(T).add(new Edge(i, 0, G.get(i).size() - 1));
			}

			//blue -> red
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (gcd(ms[i], ns[j]) > 1) {
						G.get(i).add(new Edge(m + j, 1, G.get(m + j).size()));
						G.get(m + j).add(new Edge(i, 0, G.get(i).size() - 1));
					}
				}
			}

			int ans = 0;

			while (true) {
				used = new boolean[T + 1];
				int f = rec(S, T, INF);
				if (f == 0) break;
				ans += f;
			}

			System.out.println(ans);
		}
	}

	static int rec(int u, int v, int f) {

		if (u == v) return f;

		used[u] = true;

		for (Edge e : G.get(u)) {
			if (!used[e.to] && e.cap > 0) {
				int d = rec(e.to, v, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}

		return 0;
	}

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

class Edge {
	int to, cap, rev;

	public Edge(int to, int cap, int rev) {
		this.to = to;
		this.cap = cap;
		this.rev = rev;
	}
}

Measured memory_bytes: 90856
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
int N, L, a[100000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> L;
    for (int i = 0; i < N; i++) cin >> a[i];
    int x = 1;
    for (int i = 1; i < N; i++) x = (a[i] + a[i - 1] > a[x] + a[x - 1]) ? i : x;
    if (a[x] + a[x - 1] < L) {
        cout << "Impossible\n";
    } else {
        cout << "Possible\n";
        for (int i = 1; i < x; i++) cout << i << '\n';
        for (int i = N - 1; i >= x; i--) cout << i << '\n';
    }
    return 0;
}


Measured memory_bytes: 1280
h,w = gets.split.map(&:to_i)
squares = []
h.times do
  squares << gets.chomp.split("")
end
dp = Array.new(h){[0]*w}
(0...w).each do |j|
  break if squares[0][j] == "#"
  dp[0][j] = 1
end
(0...h).each do |i|
  break if squares[i][0] == "#"
  dp[i][0] = 1
end

squares.each_with_index do |line,i|
  line.each_with_index do |a,j|
    next if i == 0 || j == 0 || a == "#"
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
  end
end
p dp[h-1][w-1] % (10**9+7)


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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}

#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

void err(vector<string>::iterator it) {}

template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> inline T tabs(T a) { return (a > 0) ? a : -a; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n, t;

	cin >> n >> t;
	vector<int> a(n), mini(n, INT_MAX), maxi(n, INT_MIN);
	REPU(i, 0, n) cin >> a[i];
	mini[0] = a[0], maxi[n - 1] = a[n - 1];
	REPU(i, 1, n) {
		mini[i] = min(a[i], mini[i - 1]);
	}
	REPD(i, n - 2, -1) {
		maxi[i] = max(a[i], maxi[i + 1]);
	}
	int ans = 0, diff = INT_MIN;
	REPU(i, 1, n) {
		amax(diff, maxi[i] - mini[i - 1]);
	}
	set<int> st;
	REPU(i, 1, n) {
		if (maxi[i] - mini[i - 1] == diff) {
			st.insert(maxi[i]);
		}
	}
	cout << st.size() << endl;

	return 0;
}


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

using namespace std;

#define sz(x) ((int) ((x).size()))
typedef long long ll;
typedef long double ld;

int n, m, d[200000];
vector<int> e[200000];
vector<pair<int, int>> r;
bool v[200000], s[200000];
bool pos = true;

void dfs(int i = 0, int p = -1) {
  v[i] = true, s[i] = true;
  for (int j : e[i]) {
    if (j == p)
      continue;
    if (!v[j])
      dfs(j, i);
    else if (s[j]) {
      d[j]++;
      r.push_back({j, i});
      // cerr << j << " " << i << "\n";
    }
  }
  if (d[i] % 2 != 0 && p != -1) {
    d[i]++;
    // cerr << i << " " << p << "\n";
    r.push_back({i, p});
  } else if (d[i] % 2 == 0 && p != -1) {
    d[p]++;
    r.push_back({p, i});
    // cerr << p << " " << i << "\n";
  }
  if (d[i] % 2 != 0)
    pos = false;
  s[i] = false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> m;
  int a, b;
  for (int i = 0; i < m; i++) {
    cin >> a >> b, a--, b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs();
  if (!pos)
    cout << -1 << "\n";
  else {
    for (auto p : r)
      cout << p.first + 1 << " " << p.second + 1 << "\n";
  }
}


Measured memory_bytes: 17012
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,k; 
  cin>>n>>k;

  cout<<n-k+1<<endl;
}


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

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

    vector<int> L(N);

    for (int i = 0; i < N; i++)
    {
        cin >> L.at(i);
    }

    int l1, l2, l3;

    int cnt = 0;

    vector<int> line(3);
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            for (int k = j + 1; k < N; k++)
            {
                l1 = L.at(i);
                l2 = L.at(j);
                l3 = L.at(k);
                if (l1 == l2 || l1 == l3 || l2 == l3)
                {
                    continue;
                }

                line = {l1, l2, l3};
                sort(line.begin(), line.end());

                if (line.at(0) + line.at(1) <= line.at(2))
                {
                    continue;
                }

                cnt++;
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<" ";

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    double a,b,c,d;
    cin>>a>>b>>c>>d;
    doublecout(a*b/2);
    if(a/2==c&&b/2==d){
        cout << 1<<endl;
    }else{
        cout << 0<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
D, G = map(int, input().split())
p = [0] * (D + 1)
c = [0] * (D + 1)
for i in range(1, D+1):
    p[i], c[i] = map(int, input().split())
ans = float('inf')


def dfs(i, g):
    global ans
    if i == 0:
        return ans
    cnt = min(g // (100 * i), p[i])
    score = 100 * i * cnt
    if cnt == p[i]:
        score += c[i]
    if g > score:
        cnt += dfs(i - 1, g - score)
    return min(cnt, dfs(i - 1, g))


print(dfs(D, G))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

signed main(){
   IOS;
   string s; cin >> s;
   int n = s.size();
   vector<int> ans(n), l(n), r(n);
   for(int i = 0, cur = 0; i < n; i++) {
      if(s[i] == 'R') cur = 0;
      else cur++;
      r[i] = cur;
   }
   for(int i = n - 1, cur  = 0; i >= 0; i--) {
      if(s[i] == 'L') cur = 0;
      else cur++;
      l[i] = cur;
   }
   for(int i = 0; i < n - 1; i++) {
      if(l[i] == 0) continue;
      if(l[i]%2 == 0) {
         ans[i + l[i]]++;
      }
      else ans[i + l[i] - 1]++;
   }
   for(int i = n - 1; i > 0; i--) {
      if(r[i] == 0) continue;
      if(r[i]%2 == 0) {
         ans[i - r[i]]++;
      }
      else ans[i - r[i] + 1]++;
   }
   for(auto x : ans) cout << x << " ";
}

Measured memory_bytes: 5800
d = {}
N = int(input())
for _ in range(N):
    s = input()
    if s in d:
        d[s] += 1
    else:
        d[s] = 1
M = int(input())
for _ in range(M):
    t = input()
    if t in d:
        d[t] -= 1
    else:
        d[t] = -1
print(max(0, *d.values()))


Measured memory_bytes: 3060
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		if(InRange(B, A, A + W + 1)){
			Console.WriteLine(0);
			return;
		}
		if(InRange(A, B, B + W + 1)){
			Console.WriteLine(0);
			return;
		}
		if(A < B){
			Console.WriteLine(B - (A + W));
		} else {
			Console.WriteLine(A - (B + W));
		}
		
	}
	
	bool InRange(int t, int l, int r){
		return l <= t && t < r;
	}
	
	int W, A, B;
	public Sol(){
		var d = ria();
		W = d[0]; A = d[1]; B = d[2];
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


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

#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

int isEmpty();
int isFull();
void enqueue(P x);
P dequeue();

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++)
    {
      scanf("%s", Q[i].name);
      scanf("%d", &Q[i].t);
    }

  head = 1;
  tail = n+1;

  while(!isEmpty())
    {
      u = dequeue();
      u.t -= q;

      /*プロセスが終わらないとき、エンキューしてクオンタム分の時間を加算*/
      if(u.t>0)
	{
	  //printf("least %d\n", u.t);
	  enqueue(u);
	  elaps += q;
	}
      /*プロセスが終わったら、処理した分の時間を加算*/
      else
	{
	  elaps += q + u.t;
	  printf("%s %d\n", u.name, elaps);
	}
    }
 
  return 0;
}

int isEmpty()
{
  if(head == tail)return 1;
  else return 0;
}

int isFull()
{
  if(head == tail+1%n)return 1;
  else return 0;
}

void enqueue(P x)
{
  if(/*isFull()*/0)
    {
      printf("Queue Over Flow!\n");exit(1);
    }
  Q[tail] = x;
  if(tail == n+1)tail = 1;
  else tail++;
}

P dequeue()
{
  P x;
  
  if(/*isEmpty()*/0)
    {
      printf("Queue Under Flow!\n");exit(2);
    }
  x = Q[head];
  if((head) == n+1)head = 1;
  else head++;
  return x;
}



Measured memory_bytes: 6772
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind
#print(killingrange)
cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
        monstershp[i]=monstershp[i]-A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    #print(monstershp,imos)
print(cnt)

Measured memory_bytes: 146660