akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define MAX_V 10
#define INF 1000000000

//ダイクストラ法
//計算量O(|V|^2)
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool used[MAX_V];
int V;

void dijkstra(int s){
    fill(d, d + V, INF);
    fill(used, used + V, false);
    d[s] = 0;

    while(true){
        int v = -1;
        for(int u = 0; u < V; u++){
            if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
        }
        if(v == -1) break;
        used[v] = true;

        for(int u = 0; u < V; u++){
            d[u] = min(d[u], d[v] + cost[v][u]);
        }
    }
}

int main(void){
    ll h, w;
    cin >> h >> w;

    V = 10;

    rep(i, 0, 10){
        rep(j, 0, 10){
            cin >> cost[j][i];
        }
    }

    dijkstra(1);

    ll sum = 0;
    rep(i, 0, h){
        rep(j, 0, w){
            ll tmp;
            cin >> tmp;
            if(tmp != -1){
                sum += d[tmp];
            }
        }
    }

    cout << sum << endl;
    return 0;

}


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

typedef long long ll;
typedef unsigned long long ull;

class ModInt{
public:
    ModInt(){
        x = 0;
    }
    ModInt(int v){
        x = (((v % mod) + mod) % mod);
    }
    ModInt(long long v){
        x = (((v % mod) + mod) % mod);
    }

    ModInt operator-() const {return ModInt(-x);}
    ModInt& operator+=(const ModInt& a){
        x = (x + a.x) % mod;
        return *this;
    }
    ModInt& operator-=(const ModInt& a){
        x = (x + mod - a.x) % mod;
        return *this;
    }
    ModInt& operator*=(const ModInt& a){
        x = (x * a.x) % mod;
        return *this;
    }
    ModInt operator+(const ModInt& a) const{
        ModInt res(*this);
        res += a;
        return res;
    }
    ModInt operator-(const ModInt& a) const{
        ModInt res(*this);
        res -= a;
        return res;
    }
    ModInt operator*(const ModInt& a) const{
        ModInt res(*this);
        res *= a;
        return res;
    }
    ModInt power(long long a) const{
        if(a == 0) return 1;
        auto b = power(a >> 1);
        b *= b;
        if(a & 1) b *= *this;
        return b;
    }
    ModInt inverse() const{
        return power(mod - 2);
    }
    ModInt& operator/=(const ModInt& a){
        (*this) *= a.inverse();
        return *this;
    }
    ModInt operator/(const ModInt& a)const{
        ModInt res(*this);
        res /= a;
        return res;
    }
    friend ostream& operator<<(ostream& os, const ModInt& a){
        os << a.x;
        return os;
    }

    static ModInt add(long long a, long long b){
        ModInt res(a);
        res += b;
        return res;
    }

    static long long get_mod(){ return mod;}

private:
    static const long long mod = 1000000007;
    long long x;
};

int main()
{
    ll N, K;
    cin >> N >> K;
    ModInt res(0);
    vector<ModInt> dp(K, ModInt(0));
    for(int i=K; i>=1; i--){
        ModInt count(0);
        count += ModInt(K/i).power(N);
        for(int j=2; i*j<=K; j++){
            count -= dp[i*j-1];
        }
        dp[i-1] = count;
    }
    for(int i=1;i<=K;i++){
        res += dp[i-1] * i;
    }
    cout<< res << endl;

    return 0;
}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  if( N < 10){
    if( N == 2 || N == 4 || N == 5 || N == 7|| N == 9){
      cout << "hon" << endl;
    }
    if( N == 0 || N == 1 || N == 6 || N == 8){
      cout << "pon" << endl;
    }
    if( N == 3){
      cout << "bon" << endl;
    }
  }
  if( N > 9 && N < 1000){
    N %= 10;
    if( N == 2 || N == 4 || N == 5 || N == 7|| N == 9){
      cout << "hon" << endl;
    }
    if( N == 0 || N == 1 || N == 6 || N == 8){
      cout << "pon" << endl;
    }
    if( N == 3){
      cout << "bon" << endl;
    }
  }
    
}


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

int main(void) {
    int N,M; cin >> N >> M;
    if(N==M) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3576
#!/usr/bin/env python3
import sys


def solve(N: int, D: int, X: "List[int]", Y: "List[int]"):
    a = 0
    dd = D**2
    for xi, yi in zip(X,Y):
        if (xi>D) or (yi>D):
            continue
        else:
            if xi**2+yi**2 <= dd:
                a+=1
    print(a)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    Y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
    solve(N, D, X, Y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 71752
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
#include<ctype.h>
using namespace std;


int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a+b>c+d) {
		cout << "Left" << endl;
	}
	else if (a+b==c+d) {
		cout << "Balanced" << endl;
	}
	else {
		cout << "Right" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INFTY 10000000000
typedef long long int ll;
const int MOD=1000000007;
using Graph = vector<vector<int>>;
using ipair = pair<ll,ll>;
bool operator< (const ipair a, const ipair b){return a.first < b.first;};
#define rep(i,n) for (ll i = 0; i < (n); ++i)
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int main(){
    int n,m;cin>>n>>m;
    vector<string> a(n),b(m);
    rep(i,n)cin>>a[i];
    rep(i,m)cin>>b[i];
    //cout<<a[0]<<endl;
    rep(i,n){
        rep(j,n){
            if(a[i][j]!=b[0][0])continue;
            int ok = 1;
            rep(k,m){
                rep(l,m){
                    if(i+k>=n||j+l>=n||a[i+k][j+l]!=b[k][l]){
                        ok = 0;
                        break;
                    }
                }
            }
            if(ok){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

ll N;
ll ans = 1000000000000;
int main(){
  cin >> N;
  ll a, b;
  rep(i, sqrt(N) + 1){
    if(N % i == 0){
      a = i;
      b = N / i;
      ans = min(ans, a+b);
    }
  }
  cout << ans - 2<<endl;
}

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

def calc(x):
    grp = [[]]
    for a in A:
        if a < x and len(grp[-1]) > 0:
            grp.append([])
        if a >= x:
            grp[-1].append(a)
    L = []
    for g in grp:
        g.sort()
        L += g[:max(0, len(g) - K + 1)]
    L.sort()

    if len(L) < Q or L[0] != x:
        return 10**18
    return L[Q - 1] - x

ans = 10**18
for a in A:
    ans = min(ans, calc(a))
print(ans)


Measured memory_bytes: 3316
n = int(input())

plus = []
minus = []
plus_sum = []
minus_sum = []

s_p = 0
s_m = 0
for i in range(31):
    if i % 2 == 0:
        plus.append(2**i)
        s_p += 2**i
        plus_sum.append(s_p)
    else:
        minus.append(2**i)
        s_m += 2**i
        minus_sum.append(s_m)

def ten_four(num):
    def for_four(num, arr):
        if num == 0:
            if arr == []:
                return '0'
            else:
                arr_str = map(str, arr[::-1])
                ans = (''.join(arr_str))
                return ans
        else:
            s = num // 4
            a = num % 4
            arr.append(a)
            return for_four(s, arr)
    
    arr = []
    return for_four(num, arr)


if n == 0:
    print(0)
elif n == 1:
    print(1)
elif n == -1:
    print(11)
elif n == -2:
    print(10)

elif n > 0:
    for i in range(len(plus_sum)):
        if n <= plus_sum[i]:
            max_4 = i - 1
            n_4 = n - 1 - plus_sum[max_4]
            break
        else:
            pass
    n_4zf = ten_four(n_4).zfill(max_4 + 1)
    n_ans = n_4zf.translate(str.maketrans({'0': '10', '1': '11', '2': '00', '3': '01'}))
    print('1'+n_ans)

elif n < 0:
    n_1 = n % 2
    n = int(abs((n - n_1)/2))
    for i in range(len(plus_sum)):
        if n <= plus_sum[i]:
            max_4 = i - 1
            n_4 = n - 1 - plus_sum[max_4]
            break
        else:
            pass
    n_4zf = ten_four(n_4).zfill(max_4 + 1)
    n_ans = n_4zf.translate(str.maketrans({'0': '10', '1': '11', '2': '00', '3': '01'}))
    print('1'+n_ans+str(n_1))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
typedef long long ll;
int A[MAXN];
ll fmx[MAXN][2],fmn[MAXN][2],gmx[MAXN][2],gmn[MAXN][2],sum[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&A[i]),sum[i]=sum[i-1]+A[i];
    int p=0;
    for(int i=2;i<=n;i++)
    {
        while(p+1<i&&2*sum[p+1]<=sum[i])p++;

        fmx[i][0]=max(sum[p],sum[i]-sum[p]);
        fmn[i][0]=min(sum[p],sum[i]-sum[p]);

        fmx[i][1]=max(sum[p+1],sum[i]-sum[p+1]);
        fmn[i][1]=min(sum[p+1],sum[i]-sum[p+1]);


    }
    p=n;
    for(int i=n-1;i>0;i--)
    {
        while(p-1>i&&2*(sum[n]-sum[p-1])<=sum[n]-sum[i-1])p--;

        gmx[i][0]=max(sum[p-1]-sum[i-1],sum[n]-sum[p-1]);
        gmn[i][0]=min(sum[p-1]-sum[i-1],sum[n]-sum[p-1]);


        //cout<<p-i<<' '<<n-p+1<<'\n';


        gmx[i][1]=max(sum[p]-sum[i-1],sum[n]-sum[p]);
        gmn[i][1]=min(sum[p]-sum[i-1],sum[n]-sum[p]);



        //cout<<gmx[i][0]<<' '<<gmn[i][0]<<'\n';

    }
    ll Ans=1e18;
    for(int i=2;i+1<=n-1;i++)
    {
        for(int k=0;k<=1;k++)
            for(int t=0;t<=1;t++)
                Ans=min(Ans,max(fmx[i][k],gmx[i+1][t])-min(fmn[i][k],gmn[i+1][t]));
        //cout<<i<<' '<<Ans<<'\n';
    }


    cout<<Ans<<'\n';


    return 0;
}


Measured memory_bytes: 15104
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

template<class T> inline void chmax(T& a, const T& b) { if(b > a) a = b;}

constexpr int SIZE = 4;
constexpr int MAX_N = 100;
constexpr int MAX_LEN = 8;

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

unordered_map<string, int> word_idx;

string board[SIZE];
int scores[MAX_N];
int cnt[MAX_N];
int len[MAX_N];
bool visited[SIZE][SIZE];

void dfs(int x, int y, string s = "") {
	s += board[y][x];
	if(word_idx.count(s)) ++cnt[word_idx[s]];
	if(s.size() >= MAX_LEN) return;

	visited[y][x] = true;

	for(int i = 0; i < 8; ++i) {
		const int nx = x + dx[i];
		const int ny = y + dy[i];

		if(nx < 0 || ny < 0 || nx >= SIZE || ny >= SIZE || visited[ny][nx])
			continue;

		dfs(nx, ny, s);
	}

	visited[y][x] = false;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	for(int i = 0; i < n; ++i) {
		string word;
		cin >> word >> scores[i];
		word_idx[word] = i;
		len[i] = (int)word.size();
	}

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

	int t;
	cin >> t;

	memset(visited, false, sizeof(visited));
	for(int i = 0; i < SIZE; ++i) {
		for(int j = 0; j < SIZE; ++j) {
			dfs(j, i);
		}
	}

	vector<int> dp(t + 1, 0);
	for(int i = 0; i < n; ++i) {
		int num = cnt[i];
		for(int j = 1; num > 0; j <<= 1) {
			const int mul = min(j, num);
			const int sum_len = len[i] * mul;
			const int sum_score = scores[i] * mul;
			for(int k = t - sum_len; k >= 0; --k) {
				chmax(dp[k + sum_len], dp[k] + sum_score);
			}
			num -= mul;
		}
	}

	cout << *max_element(dp.begin(), dp.end()) << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1288
#include<stdio.h>
int main()
{
long long int a,b,x,ans;
  scanf("%lld %lld %lld",&a,&b,&x);
if(a%x==0) ans=b/x-a/x+1;
else ans=b/x-a/x;
printf("%lld",ans);
return 0;}  

Measured memory_bytes: 1736
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> vi(N);
  for (int i=0;i<N;i++){
    cin >> vi[i];
  }
  sort(vi.begin(),vi.end());
  double ans = ((double)vi[0] + (double)vi[1])/2.0;
  for (int i=2;i<N;i++){
    ans = (ans + (double)vi[i])/2.0;
  }

  cout << fixed << setprecision(6) << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    string s; cin >> s;
    int p = 0;
    int g = 0;
    int win = 0;
    int lose = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'p'){
            if(p + 1 <= g){
                p++;
            }else{
                g++;
                lose++;
            }
        }else{
            if(p + 1 <= g){
                p++;
                win++;
            }else{
                g++;
            }
        }
    }
    cout << win - lose << endl;
}

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


int main() {
    int r;
    int D;
    int x_2000;
    int out;
    cin >> r >> D >>x_2000;

    int prev_num = x_2000;
    for(int i=2000;i<2010;i++){
        out = r*prev_num - D;
        cout << out << endl;
        prev_num = out;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
    int n,m,l,a,i;
	for(;;){
		scanf("%d",&l);
		if(l==0)break;
		a=0;
		for(i=0;i<12;i++){
			scanf("%d %d",&m,&n);
			l -= (m-n);
			if(l<=0 && a==0)a=i+1;
		}
		if(l>0)puts("NA");
		else printf("%d\n",a);
	}
    return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int main(){
	ll N;
	cin >> N;
	vector<ll> h(N+7),dp(N+7,INF);

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

	dp[1] = 0;
	for(int i=1;i<=N;i++){
		dp[i] = min( dp[i] , dp[i-1]+abs(h[i]-h[i-1]) );
		dp[i] = min( dp[i] , dp[i-2]+abs(h[i]-h[i-2]) );
	}

	cout << dp[N] << endl;
}

Measured memory_bytes: 1792
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
m = sorted(p)
p = tuple(p)
q = tuple(q)

import itertools
b = 0
c = 0
cnt = 1
for i in itertools.permutations(m,n):
    if i == p:
        c += cnt
    if i == q:
        b += cnt
    if c != 0 and b!=0:
        break
    else:
        cnt += 1
#print(c)
#print(b)
print(abs(c-b))

Measured memory_bytes: 3064
object Main extends App{
  val sc = new java.util.Scanner(System.in)
  val inputstring = sc.next
  val inputlist = List.tabulate(inputstring.size)(x=>{inputstring(x).toInt - 48})
  val count = inputlist.sum
  val ans = List(count,inputlist.size - count).min * 2
  println(ans)
}


Measured memory_bytes: 33816
package main

import (
	"fmt"
	"unicode/utf8"
)

var mark = "#"

func main() {
	var H, W int
	fmt.Scan(&H)
	fmt.Scan(&W)

	inputs := scanStrings(H)
	// fmt.Println(inputs)
	dx := [4]int{1, -1, 0, 0}
	dy := [4]int{0, 0, 1, -1}
	res := true
	for i, s := range inputs {
		for j, ss := range s {
			if ss != mark {
				continue
			}
			check := false
			for k := 0; k < 4; k++ {
				if (i+dy[k] >= 0 && i+dy[k] < H) && (j+dx[k] >= 0 && j+dx[k] < W) {
					// fmt.Println(i, j, i+dy[k], j+dx[k])
					if inputs[i+dy[k]][j+dx[k]] == mark {
						check = true
						break
					}
				}
			}
			if !check {
				res = false
				// fmt.Println("No")
				// os.Exit(0)
			}

		}
		if !res {
			break
		}
	}

	if res {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

func scanStrings(len int) (strings [][]string) {
	var str string
	for i := 0; i < len; i++ {
		fmt.Scanf("%s", &str)
		strings = append(strings, spritString(str))
	}
	return
}

func spritString(input string) (res []string) {
	for i := 0; i < utf8.RuneCountInString(input); i++ {
		res = append(res, input[i:i+1])
	}
	return
}


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

int main(){ 
  Int N;
  cin >> N;
  vector<Int> A(N), B(N), C(N-1);
  
  rep(i,N) {
    cin >> A[i];
    A[i]--;
  }
  rep(i,N) cin >> B[i];
  rep(i,N-1) cin >> C[i];
  
  Int ans = 0;
  
  rep(i,N) {
    ans += B[A[i]];
    if (i < N-1) {
      if (A[i+1]-A[i] == 1) {
        ans += C[A[i]];
      }
    }
  }
  
  cout << ans << endl;

}

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

typedef struct{
  char name[10];
  int  t;
} Process;

Process Q[100001];


int n,q,head,tail;


Process dequeue(){
  Process x;
  x=Q[head];
  if((head+1)>n+1) head=1;
  else            head++;
  return x;
}

void enqueue(Process x){
  Q[tail]=x;
  if((tail+1)==n+2)  tail=1;
  else             tail++;
}

int calc(int x,int y){
  if(x>=y) return y;
  else     return x;
}

int main() {
  /* code */
  Process hoz;
  int min_time=0;
  int sum_time=0;
  int i;

  scanf("%d %d\n",&n,&q);

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

  head=1;
  tail=n+1;

  //  printf("%s %d\n",Q[head].name,Q[head].t);
  

  while(head!=tail){
    hoz=dequeue();
    min_time=calc(q,hoz.t);
    hoz.t-=min_time;
    sum_time+=min_time;

    if(hoz.t>0){
      enqueue(hoz);
    }else{
      printf("%s %d\n",hoz.name,sum_time);
    }
  }
  return 0;
}

Measured memory_bytes: 1384
#include <bits/stdc++.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls x << 1
#define rs x << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
using namespace std;
const db pi = acos(-1.0);
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int h, w, n;
ll ans[100010];
map<pii, ll> sum;
 
int main()
{
	h = read();
	w = read();
	n = read();
	rep(i, 1, n)
    {
        int a, b;
        a = read();
        b = read();
        rep(ww, 0, 2)
        	rep(hh, 0, 2)
            {
                int x = a - ww;
                int y = b - hh;
                if(x >= 1 && x <= h - 2 && y >= 1 && y <= w - 2) sum[mp(x, y)] ++;
            }
    }
    ll all = 1ll * (h - 2) * (w - 2);
    ans[0] = all - sum.size();
 
    map< pii, ll > ::iterator it;
    for(it = sum.begin(); it != sum.end(); it ++) ans[it -> Y] ++;
    rep(i, 0, 9) printf("%lld\n",ans[i]);
    return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    if(k >= n){
        int max_number = 2*n-1;
        int MOD = 1e9+7;
        
        vector<ll> fac(max_number+1,1);
        vector<ll> inv(max_number+1,1);
        vector<ll> finv(max_number+1,1);
        vector<ll> nCk(max_number+1,1);
        for(i = 2;i <= max_number;++i){
            inv.at(i) = MOD - inv.at(MOD%i)*(MOD/i)%MOD;
        }
        for(i = 1;i <= max_number;++i){
            fac.at(i) = fac.at(i-1)*i%MOD;
            finv.at(i) = finv.at(i-1)*inv.at(i)%MOD;
        }
        for(i = 1;i <= max_number;++i){
            nCk.at(i) = fac.at(max_number)*finv.at(i)%MOD*finv.at(max_number-i)%MOD;
        }
        cout << nCk.at(n) << endl;
        return 0;
    }else{
        int max_number = n-1;
        int MOD = 1e9+7;
        
        vector<ll> fac(max_number+1,1);
        vector<ll> inv(max_number+1,1);
        vector<ll> finv(max_number+1,1);
        vector<ll> nCk(max_number+1,1);
        for(i = 2;i <= max_number;++i){
            inv.at(i) = MOD - inv.at(MOD%i)*(MOD/i)%MOD;
        }
        for(i = 1;i <= max_number;++i){
            fac.at(i) = fac.at(i-1)*i%MOD;
            finv.at(i) = finv.at(i-1)*inv.at(i)%MOD;
        }
        for(i = 1;i <= max_number;++i){
            nCk.at(i) = fac.at(max_number)*finv.at(i)%MOD*finv.at(max_number-i)%MOD;
        }

        int max_number2 = n;
        
        vector<ll> fac2(max_number2+1,1);
        vector<ll> inv2(max_number2+1,1);
        vector<ll> finv2(max_number2+1,1);
        vector<ll> nCk2(max_number2+1,1);
        for(i = 2;i <= max_number2;++i){
            inv2.at(i) = MOD - inv2.at(MOD%i)*(MOD/i)%MOD;
        }
        for(i = 1;i <= max_number2;++i){
            fac2.at(i) = fac2.at(i-1)*i%MOD;
            finv2.at(i) = finv2.at(i-1)*inv2.at(i)%MOD;
        }
        for(i = 1;i <= max_number2;++i){
            nCk2.at(i) = fac2.at(max_number2)*finv2.at(i)%MOD*finv2.at(max_number2-i)%MOD;
        }
        ll ans = 0;
        for(i = 0;i <= k;++i){
            ans += nCk.at(i)*nCk2.at(i)%MOD;
            ans %= MOD;
        }
        cout << ans << endl;
    }
    
    

    return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#include <utility>
#include <numeric>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	ll n;
	cin >> n;
	ll a = pow(n, 0.5);
	ll b, c;
	for (ll i = 1; i <= a; i++) {
		if (n%i == 0) {
			b = i;
			c = n / b;
		}
	}
	cout << b + c - 2 << endl;
	return 0;
}

Measured memory_bytes: 256
//  ©   ___MRX___

#include <bits/stdc++.h>
    using namespace std;

#define ll long long int

int main()
{
    string a, b, c;

    cin >> a >> b >> c;
    cout << a[0] << b[1] << c[2] << '\n';

    return 0;
}


Measured memory_bytes: 3600
i1 = input()
i2 = input()
i3 = input()

s = i1.split(' ')[0]
t = i1.split(' ')[1]
a = int(i2.split(' ')[0])
b = int(i2.split(' ')[1])
if(i3 == s):
    a -= 1
else:
    b -= 1
print(' '.join([str(a), str(b)]))

Measured memory_bytes: 3064
#include <stdio.h>

int n, A[50];

bool solve(int i, int m)
{
  if (m == 0)
    return true;
  if (i >= n)
    return false;

  bool res = solve(i + 1, m) || solve(i + 1, m - A[i]);
  return res;
}

int main()
{
  int q, m;

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

  scanf("%d", &q);
  for (int i = 0; i < q; i++)
  {
    scanf("%d", &m);
    if (solve(0, m))
    {
      printf("yes\n");
    }
    else
    {
      printf("no\n");
    }
  }

  return 0;
}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    const int INF = 2001001001;
    vector<vector<int>> dist(n, vector<int>(n, INF));
    rep(_, m){
        int s, t, d;
        cin >> s >> t >> d;

        dist[s][t] = d;
    }

    rep(i, n) dist[i][i] = 0;

    rep(k, n) rep(i, n) rep(j, n) {
        if(dist[i][k] == INF || dist[k][j] == INF) continue;
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }

    rep(i, n) if(dist[i][i] != 0) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }

    rep(i, n){
        rep(j, n){
            if(dist[i][j] != INF) cout << dist[i][j];
            else cout << "INF";

            if(j != n-1) cout << " ";
        }
        cout << endl;
    }



    return 0;
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x) cout<<#x<<" = "<<(x)<<endl;
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int x; cin >> x;
  YES(x == 3 || x == 5 || x == 7);
  return 0;
}

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

#define int long long

using namespace std;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007,INF=1e18;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int a,b,c,k;
 
signed main(){
	cin>>a>>b>>c>>k;
	if(abs(a-b)==1e18)cout<<"Unfair"<<endl;
	else if(k%2==0)cout<<a-b<<endl;
	else cout<<b-a<<endl;
	
	
	
	
	
	
	
	return 0;
}

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

typedef long long ll;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define _for(i,a,b) for(int i = (a); i < (b); i++) 
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)

const int kMod = 1e9 + 7;
const int kMaxN = 1e6 + 5;

void taskA(){
    string s; cin >> s;
    int n = s.size();
    cout << (s[2]==s[3] && s[4]==s[5] ? "Yes\n" : "No\n");
    return;
}

void taskB() {
    int n; cin >> n;
    int ans = 0;
    ans += (n/500)*1000; n%=500;
    ans += (n/5)*5;
    cout << ans;
    return;
}
void taskC() {
    int n,k; cin >> k >> n;
    vector<int> a(n);
    _for(i,0,n) cin >> a[i];
    sort(a.begin(), a.end());
    ll ans = 0;
    int ma = 0;
    _for(i,1,n) {
        ans += (a[i]-a[i-1]); 
        ma = max(ma, a[i]-a[i-1]);
    }
    ans += (k-a[n-1]+a[0]);
    ma = max(ma, k-a[n-1]+a[0]);
    cout << ans-ma;
    return;
} 

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    //taskA();
    //taskB();
    taskC();
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, S, E) for (int(X) = (S); (X) < (E); ++(X))
#define rrep(X, S, E) for (int(X) = (E)-1; (X) >= (S); --(X))
#define itrep(X, Y) for (auto(X) = (Y).begin(); (X) != (Y).end(); (X)++)
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll INF = 9 * 1e18;
const ll MOD = 1e9 + 7;

void solve(long long N, long long K, std::vector<long long> t,
           std::vector<long long> d) {
  priority_queue<pll> que;
  rep(i, 0, N) { que.push(mp(d[i], t[i])); }

  vl checked(N + 1);
  ll maxSum = 0;
  ll deli = 0;
  ll neta = 0;
  priority_queue<ll, vl, greater<ll>> canThrowAway;

  rep(i, 0, K) {
    auto p = que.top();
    que.pop();
    ll d = p.first;
    ll t = p.second;

    deli += d;

    if (!checked[t]) {
      neta++;
      checked[t] = true;
    } else {
      canThrowAway.push(d);
    }
  }
  maxSum = deli + neta * neta;

  while (!que.empty() && !canThrowAway.empty()) {
    auto p = que.top();
    que.pop();
    ll d = p.first;
    ll t = p.second;

    if (!checked[t]) {
      neta++;
      checked[t] = true;
      ll d2 = canThrowAway.top();
      canThrowAway.pop();
      deli += d - d2;
    }
    maxSum = max(maxSum, deli + neta * neta);
  }

  print(maxSum);
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> t(N);
  std::vector<long long> d(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &t[i]);
    scanf("%lld", &d[i]);
  }
  solve(N, K, std::move(t), std::move(d));
  return 0;
}


Measured memory_bytes: 4976
/*
  #問題：
  


  #分析：
  #オブジェクト：
  
  #条件：
  

  #要求：
  

  #解法：
  
*/

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
#include <initializer_list>
#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define uLL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;


const unsigned int BIT_FLAG_0 = (1<<0);
const unsigned int BIT_FLAG_1 = (1<<1);
const unsigned int BIT_FLAG_2 = (1<<2);
const unsigned int BIT_FLAG_3 = (1<<3);
const unsigned int BIT_FLAG_4 = (1<<4);
const unsigned int BIT_FLAG_5 = (1<<5);
const unsigned int BIT_FLAG_6 = (1<<6);
const unsigned int BIT_FLAG_7 = (1<<7);


#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;

using Bint = mp::cpp_int;

#define unless(x)   if(!(x))

int main(void){
  int N; cin>>N;                // Nは10^5以下．NはSの長さ．
  int Q; cin>>Q;                // Qも10^5以下．Qは質問の個数を表す．

  string S;                     // Sの長さはN．
  cin>>S;                       // 考察対象の文字列Sを読み込む．
  S=S+"#";

  
  // map<int,int> index_mp;
  vector<int> index_mp(100000,0);
  int now_x =0;
  // cerr<<"i: "<<0<<"  index_mp[i]: "<<index_mp[0]<<endl;
  FOR(i,1,N){
    if(S[i-1]=='A'&&S[i]=='C'){
      index_mp[i] = now_x+1;
      now_x=index_mp[i];    // now_xは「計算時退避用変数」
      
    }else{
      index_mp[i] = now_x;
    }
    // unless(i==N)  cerr<<"i: "<<i<<"  index_mp[i]: "<<index_mp[i]<<endl;
  }
  

  


  
  int left,right;
  FOR(i,0,Q){
    cin>>left>>right;
    left--; right--;
    cout<<index_mp[right]-index_mp[left]<<endl;
  }

  
  return 0;
}



Measured memory_bytes: 1404
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll n,x;
    cin >> n >> x;
    vector<ll>a(n);
    REP(i,n)cin >> a[i];
    SORT(a);
    REP(i,n){
        x-=a[i];
        if(x==0){
            cout << i+1 << endl;
            return 0;
        }
        else if(x < 0){
            cout << i << endl;
            return 0;
        }
    }
    if(x==0)
        cout << n << endl;
    else
        cout << n -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<int,int>m1;
  long long int n,p;
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>p;
    m1[p]++;
  }
  if(m1.size()==n)
    cout<<"YES";
    else cout<<"NO";
  return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n; cin>>n;
    vector<int> a(n),b(n),c(n-1);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n-1) cin>>c[i];
    int ans = 0;
    rep(i,n) {
        ans += b[a[i]-1];
    }
    rep(i,n-1) {
        if (a[i]+1==a[i+1]) ans += c[a[i]-1];
    }
    cout << ans << endl;
    return 0;
}

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

using ll = long long int;
using ull = unsigned long long int;
using P = pair<int, int>;
using P3 = pair<P,int>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9)+7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};
constexpr int di8[] = {0, 1, 1, 1, 0, -1, -1, -1};
constexpr int dj8[] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr double EPS = 1e-9;

ll power(ll x, ll n){
    ll res = 1;
    x %= MOD;
    while(n>0){
        if(n&1) res = res*x%MOD;
        x = x*x%MOD;
        n >>= 1;
    }
    return res;
}

ll mod_inv(ll x){
    return power(x, MOD-2);
}

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n), s(n+1);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
        s[i] = (s[i-1]+mod_inv(i))%MOD;
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans += (s[i+1]+s[n-i]-1)*a[i]%MOD;
    }
    for(int i=2;i<=n;i++){
        ans = ans*i%MOD;
    }
    cout << ans << endl;
    return 0;
}

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

struct node{
	void *data;
	struct node *next;
	struct node *prev;
};

struct point{
	int x;
	int y;
};


typedef struct node *NodePointer;

NodePointer nil;

void init(){
	nil = malloc(sizeof(struct node));
	nil->next = nil;
	nil->prev = nil;
}

void deleteNode(NodePointer t){
	t->prev->next = t->next;
	t->next->prev = t->prev;
	free(t->data);
	free(t);
}

void backInsert(void *p,int len){
	NodePointer t;
	t = malloc(sizeof(struct node));
	t->data = malloc(len);
	memcpy(t->data,p,len);
	t->next = nil;
	t->prev = nil->prev;
	t->prev->next = t;
	nil->prev = t;
}

void deleteFirst(){
	NodePointer t = nil->next;
	if(t == nil){
		return;
	}
	deleteNode(t);
}

void deleteAll(){
	NodePointer t = nil->next;
	while(t != nil){
		deleteNode(t);
	}
}

void pop(void *np,int len){
	memcpy(np,nil->next->data,len);
	deleteFirst();
}

int main(int argc, char **argv)
{
	int *square;
	char temp[1000];
	int count = 0;
	int r = 0;
	int c = 0;
	int i = 0;
	int j = 0;
	struct point dif[4] = {{0,-1},{1,0},{0,1},{-1,0}}; 

	scanf("%d%d",&r,&c);
	init();

	square = malloc(sizeof(int) * (r * c));
	
	for(i = 0;i < r;i++){
		scanf("%s",temp);
		for(j = 0;j < c;j++){
			if(temp[j] == '#'){
				square[i * c + j] = 0;
				struct point *blackPoint = malloc(sizeof(struct node));
				blackPoint->x = j;
				blackPoint->y = i;
				backInsert(blackPoint,sizeof(blackPoint));
			}
			else{
				square[i * c + j] = -1;
			}
		}
	}
	
	while(nil->next != nil){
		struct point currentPoint;
		pop(&currentPoint,sizeof(currentPoint));
		struct point nextPoint;

		for(i = 0;i < 4;i++){
			nextPoint.x = currentPoint.x + dif[i].x;
			nextPoint.y = currentPoint.y + dif[i].y;
			// if((nextPoint.y) * c + (nextPoint.x) < 0 || r * c < (nextPoint.y) * c + (nextPoint.x) ||
			// 	(nextPoint.x) == c || (nextPoint.x) == -1){
			// }
			if((0 <= nextPoint.x) && (nextPoint.x <= (c-1)) &&
					(0 <= nextPoint.y) && (nextPoint.y <= (r-1)) && (square[nextPoint.y * c + nextPoint.x] == -1)){
				struct point pointP;
				pointP.x = nextPoint.x;
				pointP.y = nextPoint.y;
				backInsert(&pointP,sizeof(pointP));
				square[(nextPoint.y) * c + (nextPoint.x)] = square[(currentPoint.y * c) + currentPoint.x] + 1;
				count = square[(nextPoint.y) * c + (nextPoint.x)];
				// printf("%d\n",(((nextPoint.y) * c)));
				// printf("%d\n",((nextPoint.x)));
				// printf("\n");
			}
			
		}
		
	}
	printf("%d\n",count);
	
	//deleteAll();
	free(nil);
	return 0;
}

Measured memory_bytes: 97792
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut hv = vec![0i32; n];
    for i in 0..n - 1 {
        hv[i] = read(&mut stdin_lock, &mut buf, b' ');
    }
    hv[n - 1] = read(&mut stdin_lock, &mut buf, b'\n');

    let mut ans = 0;
    let mut h = 0;
    for i in 0..n {
        if hv[i] > h {
            ans += hv[i] - h;
        }
        h = hv[i];
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
N = int(input())
S = [int(input()) for _ in range(N)]

S.sort()
ssum = sum(S)
if ssum % 10 != 0:
    print(ssum)
else:
    for s in S:
        if s % 10 != 0:
            print(ssum-s)
            quit()
    print(0)

Measured memory_bytes: 3060
const drawRect = function (h, w) {
    console.log(Array(h + 1).join(Array(w + 1).join('#') + '\n'));
};
const isZero = function (a) {return 0 === a;};

const chunk = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = chunk.split('\n');

while (true) {
    var hw = lines.shift().split(' ').map(Number);
    if (hw.every(isZero)) {
        break;
    }
    drawRect(hw[0], hw[1]);
}

Measured memory_bytes: 16456
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;

int main() {
    ll n;
    cin >> n;
    vector<ll> P(n);
    for (auto &p : P) {
        cin >> p;
    }
    ll res = 0;
    for (ll i = 1; i < n-1; ++i) {
        if (P[i-1] > P[i] && P[i] > P[i+1]) ++res;
        if (P[i-1] < P[i] && P[i] < P[i+1]) ++res;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
A = [0] + list(map(int, input().split()))
from itertools import accumulate
acc = accumulate(A)

from collections import Counter
cnt_mod = Counter([a % M for a in acc])
ans = 0
for k in cnt_mod.values():
    ans += k * (k - 1) // 2
print(ans)


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

int main() {
  string S; cin >> S;
  int len = S.length();

  int ans{};
  for (int i{}; i < len; ++i) {
    if (S[i] != (i % 2 == 0 ? '0' : '1')) ++ans;
  }

  cout << min(ans, len - ans) << endl;
  return 0;
}


Measured memory_bytes: 512
#include<cstdio>
#include<iostream>
#include<ctype.h>
#include<string>
using namespace std;
int main(){
	string S;
	cin >> S;
	int a, b, c;
	a = stoi(S.substr(0, 4));
	b = stoi(S.substr(5, 7));
	c = stoi(S.substr(8, 10));
	if(a > 2019){
		cout << "TBD" << endl;
	}
	else if(a == 2019 && b > 4){
		cout << "TBD" << endl;
	}
	else{
		cout << "Heisei" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

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

    cout << n << ":";
    for (auto i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            n /= i;
            cout << " " << i;
        }
    }

    if (n != 1) cout << " " << n;
    cout << endl;
    return 0;
}


Measured memory_bytes: 3092
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N = int(input())
    xy = []
    for i in range(N):
        x,y = map(int, input().split())
        xy.append([x, y, i])
    x_sort = sorted(xy, key=lambda x: x[0])
    y_sort = sorted(xy, key=lambda x: x[1])

    #[cost, 頂点1, 頂点2]
    cost = []
    for i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost.sort()
    #cost = sorted(cost, key=lambda x: x[0])

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Measured memory_bytes: 52556
#define _GLIBCXX_DEBUG
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;

int P[10010];
void init(int n){
    for(int i=0;i<n;++i)P[i]=i;
}
int root(int a) {
    if(P[a]==a)return a;
    return (P[a]=root(P[a]));
}
bool is_same_set(int a,int b){
    return root(a) == root(b);
}
void unite(int a,int b){
    P[root(a)]=root(b);
}//対グラフ

double dot_product(xy_t a, xy_t b) { return (conj(a)*b).real(); }//内積
double cross_product(xy_t a, xy_t b) { return (conj(a)*b).imag(); }//外積
xy_t projection(xy_t p, xy_t b) { return b*dot_product(p,b)/norm(b); }//投影
//対図形

int main(){
    ll n,m;
    cin >>n>>m;
    pair<ll,ll> c[n];//first;価格　second;本数　
    rep(i,n){
        cin >> c[i].first>>c[i].second;
    }
    sort(c,c+n);
    int temp=0;
    int num=0;
    ll sum =0;
    rep(i,n){
        temp=num +c[i].second;
        if(temp>=m){
            sum+=c[i].first*(m-num);
            num=temp;
            
            break;
        }else{
            num=temp;
            sum+=c[i].first*c[i].second;
            
        }
    }
    cout<<sum<<endl;
    return 0;
}

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

int main()
{
  string s;
  cin >> s;
  int a_i_min = s.size();
  int z_i_max = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A' && i < a_i_min) a_i_min = i;
    if (s[i] == 'Z' && z_i_max < i) z_i_max = i;
  }
  cout << z_i_max - a_i_min + 1 << endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    if(s[0] == s[2])cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main() {
	int X,N;
	cin >> X >> N;
	set<int> p;
	for (int i = 0; i <= 101; i++) {
		p.insert(i);
	}
	for (int i = 0; i < N; i++) {
		int P;
		cin >> P;
		if (p.find(P) != p.end()) {
			p.erase(P);
		}
	}

	int minDiff = 1000;
	int i_min = 0;
	for (auto it = p.begin(); it != p.end(); it++){
		int diff = abs((*it) - X);
		if (diff < minDiff) {
			minDiff = diff;
			i_min = *it;
		}
	}
	cout << i_min << endl;
	return(0);
}


Measured memory_bytes: 3636
while True:
    try:
        a,b,c,d,e,f = [int(x) for x in input().split()]
        x = (c*e - b*f)/(a*e - b*d)
        y = (c*d - a*f)/(b*d - a*e)
        if(x == 0): x = 0
        if(y == 0): y = 0

        print("{0:.3f} {1:.3f}".format(x,y))
        
    except:
        break


Measured memory_bytes: 5620
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int placeA,placeZ;
    for(int i=0;i<s.length();++i)
    {
        if(s[i]=='A')
        {
             placeA=i;
             break;
        }
    }
    for(int i=s.length()-1;i>placeA;--i)
    {
        if(s[i]=='Z')
        {
           placeZ=i;
           break;
        }
    }
    cout<<placeZ-placeA+1;
    return 0;
}


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

#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif

//{{{
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
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;} void err(vector<string>::iterator) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}

const int N = 2e5 + 10;
int T;

const int mod = 1e9 + 7;

int d;
char s[10010];
int dp[10010][111];
int len;

int dfs(int pos, int cursum, bool ding)
{
    if (pos == len)
    {
        return cursum == 0;
    }

    if (ding == false && dp[pos][cursum] != -1)
    {
        return dp[pos][cursum];
    }

    int ret = 0;

    int ed = 9;
    if (ding) ed = s[pos] - '0';
    for (int i = 0; i <= ed; i++)
    {
        int v = dfs(pos + 1, (cursum + i) % d, ding && i == ed);
        ret = (ret + v) % mod;
    }

    if (!ding) dp[pos][cursum] = ret;
    return ret;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif

    while (~scanf("%s", s))
    {
        scanf("%d", &d);
        len = strlen(s);

        clr(dp, -1);

        int ans = dfs(0, 0, true);
        ans = (ans - 1 + mod) % mod;
        printf("%d\n", ans);
    }

    return 0;
}


Measured memory_bytes: 8884