akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu

const ll INF=1e9+7;
const ll N = 1002;
ll n,x,m[N],mm=INF,ans=0;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>x;
	FOR(i,0,n){
		cin>>m[i];
		x-=m[i];
		ans++;
		if(m[i]<mm)mm=m[i];
	}
	ans+=x/mm;
	cout<<ans<<endl;
	return 0;
}

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

int a[100005]={0}, b[100005]={0};
int dx[9]={0,1,1,1,0,-1,-1,-1,0}, dy[9]={-1,-1,0,1,1,1,0,-1,0};


int main(){
    long long int h, w, n;
    cin >> h >> w >> n;
    set<pair<int, int> > p;
    for(int i=0;i<n;++i){
        cin >> a[i] >> b[i];
        p.insert(pair<int, int>(a[i], b[i]));
    }

    set<pair<int, int> > st[10];
    for(int i=0;i<n;++i){
        for(int j=0;j<9;++j){
            int cx = a[i] + dx[j], cy = b[i] + dy[j];
            if(cx > 1 && cx < h && cy > 1 && cy < w){
                int cnt = 0;
                for(int k=0;k<9;++k){
                    if(p.count(pair<int,int>(cx+dx[k], cy+dy[k])))cnt++;
                }
                st[cnt].insert(pair<int,int>(cx, cy));
            }
        }
    }

    long long int tmp = 0;
    for(int i=1;i<10;++i)tmp += st[i].size();
    cout << (h-2)*(w-2) - tmp << endl;
    for(int i=1;i<10;++i){
        cout << st[i].size() << endl;
    }

    return 0;
}


Measured memory_bytes: 47872
package main

import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  var line, buffer []byte
  var isPrefix bool = true
  var err error
  for isPrefix {
    line, isPrefix, err = reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
  }
  return string(buffer)
}
func NextInt() int {
  var n int
  n, _ = strconv.Atoi(NextLine())
  return n
}
func NextIntVec() []int {
  L := strings.Split(NextLine(), " ")
  N := make([]int, len(L))
  for i := range N {
    N[i], _ = strconv.Atoi(L[i])
  }
  return N
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func Output() {
  _ = writer.Flush()
}

func Sum(A *[]int) int {
  s := 0
  for _, a := range (*A) {
    s += a
  }
  return s
}

func main() {
  N := NextInt()
  A := NextIntVec()
  if Sum(&A) % (N * (N + 1) / 2) > 0 {
    Write("NO")
    Output()
    return
  }
  M := Sum(&A) / (N * (N + 1) / 2)
  A = append(A, A[0])
  K := make([]int, N + 1)
  ans := ""
  for i := 0; i < N; i++ {
    D := A[i + 1] - A[i]
    if M < D {
      ans = "NO"
      break
    }
    K[i + 1] = (M - D) / N
    if (M - D) % N > 0 {
      ans = "NO"
      break
    }
  }
  sample := 0
  for i := 0; i < N; i++ {
    sample += K[N - i] * (i + 1)
  }
  if ans == "" && Sum(&K) == M && sample == A[0] {
    ans = "YES"
  } else {
    ans = "NO"
  }
  Write(ans)
  Output()
}

Measured memory_bytes: 7168
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Score{
	int team_num;
	int ac=0;
	int time=0;
	int miss_tmp[20]={0};
	int miss_sum=0;
};

bool asc(const Score& left, const Score& right) {
	return left.ac == right.ac ? (left.time == right.time ?  left.team_num > right.team_num : left.time < right.time) :
		   left.ac > right.ac;
}

int main(){
	while(1){
		int M, T, P, R; cin>>M>>T>>P>>R;
		if(!M && !T && !P && !R) break;
		vector <Score> score(T);
		for(int i=0; i<T; i++) score[i].team_num = i;
		int m, t, p, j;
		for(int i=0; i<R; i++){
			cin>>m>>t>>p>>j;
			t=t-1;//0オリジン
			if(j == 0){
				score[t].ac++;
				if(score[t].miss_tmp != 0){
					score[t].miss_sum += score[t].miss_tmp[p];
				}
				score[t].time += m+(score[t].miss_tmp[p]*20);
			} else{
				score[t].miss_tmp[p]++;
			}
		}
		sort(score.begin(), score.end(), asc);
		for(int i=0; i<T; i++){
			cout << score[i].team_num+1;
			if(i!=T-1){
				if(score[i].ac == score[i+1].ac && score[i].time == score[i+1].time) cout << "=";
				else cout << ",";
			}
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] alp = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        String s = sc.next();
        for(char c : alp){
            if(s.indexOf(c) == -1){
                System.out.println(c);
                return;
            }
        }
        System.out.println("None");
    }
}


Measured memory_bytes: 24148
from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))
ds = [-1]*n
dq = deque([0])
ds[0] = 0
while dq:
    t = dq.popleft()
    for i in g[t]:
        if ds[i[0]] == -1:
            ds[i[0]] = ds[t] + i[1]
            dq.append((i[0]))
for i in ds:
    if i%2 == 0:
        print(0)
    else:
        print(1)

Measured memory_bytes: 47736
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var n = lines[0].split('');
 var ans = n.indexOf('7');
 if(ans!==-1){
   console.log('Yes');
 }else{
   console.log('No');
 }
});


Measured memory_bytes: 30080
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;

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

void solve() {
    int n;
    cin >> n;
    int p = pow(3,9);
    int ans = 0;
    map<int,int> v;
    REP(i,0,p) {
        int x = 0;
        VI c(3);
        REP(j,0,9) {
            int t = i / (int)pow(3,j) % 3;
            ++c[t];
            if (t == 0) x += pow(10,j) * 3;
            if (t == 1) x += pow(10,j) * 5;
            if (t == 2) x += pow(10,j) * 7;
            if (x > n) continue;
            if (v[x] != 0) continue;
            v[x] = 1;
            //dump(x);
            //dump(c[0]);
            //dump(c[1]);
            //dump(c[2]);
            if (c[0] > 0 && c[1] > 0 && c[2] > 0) ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)n; i++)
#define REPR(i, n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=(int)m; i<(int)n; i++)
#define FORR(i, m, n) for(int i=(int)m-1; i>=(int)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
typedef long long ll;
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
//struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;


void solve(std::string S){
	ll res = 0;
	REP(i, S.size()/2) {
		ll e = S.size()-i-1;
		if (S[i] != S[e]) res++;
	}
	cout << res << "\n";
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,h,w,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	cin >> h >> w >> k;
	vector<string>	c(h);
	for(i=0;i<h;i++) cin >> c[i];

	for(i=0;i<(1<<h);i++) {
		for(j=0;j<(1<<w);j++) {
			a = 0;
			for(x=0;x<h;x++) for(y=0;y<w;y++) {
				if (c[x][y]=='#') {
					if ( ((i & (1<<x)) == 0) && ((j & (1<<y)) == 0) ) a++; 
				}
			}
			if (a==k) ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


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

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int main() {
    int a,b,c; cin>>a>>b>>c;
    int K; cin>>K;
    int best = 0;
    vector<int> g(11, 1);
    rep1(i,10) g[i] = g[i-1]*2;
    for(int i=0;i<=K;++i){
        for(int j=0;j<=K-i;++j){
            int k=K-i-j;
            int s = a*g[i] + b*g[j] + c*g[k];
            best = max(best, s);
        }
    }
    cout << best << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#include <stack>
#include <regex>
 
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;

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

int main(int argc, char const *argv[])
{
  int n;
  cin >> n;
  vector<int> a(n+1,0);
  REP(i,n){
    cin >> a[i+1];
  }
  vector<int> l(n+2,0), r(n+2,0);
  REP(i,n+1){
    l[i+1] = gcd(max(l[i],a[i]),min(l[i],a[i]));
    r[n-i] = gcd(max(r[n-i+1],a[n-i]),min(r[n-i+1],a[n-i]));
  }
  int res = 0;
  for(int i = 1; i <= n; i++){
    res = max(gcd(max(l[i],r[i+1]),min(l[i],r[i+1])),res);
  }
  cout << res << endl;
  
  return 0;
}


Measured memory_bytes: 1408
# -*- coding: utf-8 -*-

s = input()

lis = set(list(s))

dic = ["a","b","c","d","e","f","g","h","i","j","k", "l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

for i in lis:
    dic.remove(i)

if len(dic) == 0:
    print("None")
else:
    print(dic[0])
    



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

Measured memory_bytes: 3712
import math

n = int(input())
#a = int(input())
#a,b = list(map(int,input().split(" ")))
ls = list(input().split(" "))
#ls = list(map(int,input().split(" ")))
#a,b = list(input().split())
#string = input()
#ls = [int(input()) for i in range(n)]
#ls1 = [input() for i in range(n)]
#m = int(input())
#ls2 = [input() for i in range(m)]
if ls.count("Y") > 0:
  print("Four")
else:
  print("Three")

Measured memory_bytes: 2940
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=1e6+10;
const LL mod=1e4+7;
const double pi=acos(-1.0);
LL n,q;
LL a[maxn];
LL c[maxn];
inline LL read()
{
	LL X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

int main()
{
    char op;
    scanf("%c",&op);
    if(op>='a'&&op<='z'){
        printf("a\n");
    }
    else{
        printf("A\n");
    }
    return 0;
}


Measured memory_bytes: 3756
Q,H,S,D=map(int,input().split())
N=int(input())

r1=[4*Q,2*H,S,D/2]

if N%2==0:
    print(round(min(r1)*2)*N//2)
else:
    if r1.index(min(r1))<=2:
        print(round(min(r1)*N))
    else:
        print(N//2*D+min(r1[:3]))

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

int main() {
  int N;
  cin >> N;
  vector<int> data(N);
  for(int i = 0; i < N; i++){
    cin >> data[i];
  }
  
  int flag = 0;
  int count = 0;
  
  while(true){
    for(int i = 0; i < N; i++){
      int tmp = data[i];
      if(tmp % 2 == 1){
        flag = 1;
        break;
      }
      else{
        data[i] = tmp / 2;
      }
    }
    if(flag == 0) count++;
    else break;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);

void solve(){
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a << "\n";
}

int main(){
   int t = 1;
//    cin >> t;
   while(t--){
       solve();
   }
   return 0;
}

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

class Solve {
private:
	std::string str;
	int str_i{};
	long long rc()
	{
		str_i++;
		if ('0' <= str[str_i] && str[str_i] <= '9')
		{
			long long ret{};
			while (str[str_i] != ']')
			{
				ret = 10 * ret + str[str_i] - '0';
				str_i++;
			}
			str_i++;
			return (ret + 1) / 2;
		}
		std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq;
		while (str[str_i] != ']')
			pq.push(rc());
		str_i++;
		int num{((int)pq.size() + 1) / 2};
		long long sum{};
		for (int i{}; i < num; i++)
		{
			sum += pq.top();
			pq.pop();
		}
		return sum;
	}
public:
	Solve()
	{
		std::cin >> str;
		printf("%lld\n", rc());
	}
};

int main()
{
	int n;
	scanf("%d", &n);
	for (int i{}; i < n; i++)
		Solve();

	return 0;
}



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

int main() {
    int n;
    string s;
    std::cin >> s;
    n = s.size();
    std::vector<int> ans(n);

    for ( int ri = 0; ri < 2; ri++ ) {
        int cnt = 0;
        for ( int i = 0; i < n; i++ ) {
            if ( s[i] == 'R' ) cnt++;
            else {
                ans[i] += cnt / 2;
                ans[i-1] += (cnt+1) / 2;
                cnt = 0;
            }
        }
        std::reverse(ans.begin(), ans.end());
        std::reverse(s.begin(), s.end());
        for ( int i = 0; i < n; i++ ) {
            if ( s[i] == 'L' ) s[i] = 'R';
            else s[i] = 'L';
        }
    }

    for ( int i = 0; i < n; i++ ) {
        printf("%d%c", ans[i], i==n-1?'\n':' ');
    }
    
    return 0;
}


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


#define int long long int
#define ff first
#define ss second
#define pb push_back

#define N 1010

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for(int i = 1; i < 10; ++i)
    {
		if(n % i == 0 && n / i < 10)
		{
			cout << "Yes\n";
			return 0;     	
		}
    }
    cout << "No\n";
    return 0;	
}

Measured memory_bytes: 256
A,B,C,D=map(int,list(input()))
o=["+","-"]
if A+B+C+D==7:
    strings="A{}B{}C{}D=7".format(o[0],o[0],o[0])
elif A+B+C-D==7:
    strings="A{}B{}C{}D=7".format(o[0],o[0],o[1])
elif A+B-C+D==7:
    strings="A{}B{}C{}D=7".format(o[0],o[1],o[0])
elif A+B-C-D==7:
    strings="A{}B{}C{}D=7".format(o[0],o[1],o[1])
elif A-B+C+D==7:
    strings="A{}B{}C{}D=7".format(o[1],o[0],o[0])
elif A-B+C-D==7:
    strings="A{}B{}C{}D=7".format(o[1],o[0],o[1])
elif A-B-C+D==7:
    strings="A{}B{}C{}D=7".format(o[1],o[1],o[0])
elif A-B-C-D==7:
    strings="A{}B{}C{}D=7".format(o[1],o[1],o[1])
strings=list(strings)
strings[0]=str(A)
strings[2]=str(B)
strings[4]=str(C)
strings[6]=str(D)
print("".join(strings))


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

using namespace std;

#define F first
#define S second
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << ": "; for (auto& xxxx: a) cerr << xxxx << " "; cerr << endl;
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()
#define pw(n) (1ll << (n))
#define equal equalll
#define less lesss

typedef double dbl;
typedef long long ll;
const int N = -1;
const int INF = 1.01e9;
typedef vector<int> vi;



int main() {
#ifdef HOME 
    assert(freopen("in", "r", stdin));
#endif
    string s;
    cin >> s;
    string t = "AKIHABARA";
    int cur = 0; 
    for (int i = 0; i < sz(t); i++) {
        if (cur < sz(s) && s[cur] == t[i]) {
            cur++;
        }
        else {
            if (t[i] != 'A') {
                puts("NO");
                return 0;
            }
            s.insert(s.begin() + cur, 'A');
            cur++;
        }
    }
    if (cur == (int)s.size()) {
        puts("YES");
    }
    else {
        puts("NO");
    }



    
#ifdef HOME 
    epr("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
#endif
    return 0;
}


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

int main(){
	list<int>L[114514];
	list<int>::iterator it;
	int n,q;
	cin>>n>>q;
	while(q--){
		int a,b,c;
		cin>>a;
		if(a==0){
			cin>>b>>c;
			L[b].push_back(c);
		}
		if(a==1){
			cin>>b;
			for(it=L[b].begin();it!=L[b].end();it++){
				if(it!=L[b].begin())cout<<' ';
				cout<<*it;
			}
			cout<<endl;
		}
		if(a==2){
			cin>>b>>c;
			L[c].splice(L[c].end(),L[b]);
		}
	}
}


Measured memory_bytes: 20492
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int f[maxn];
int main()
{
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                int pre=i*i+j*j+k*k+i*j+j*k+k*i;
                if(pre<=maxn-5){
                f[pre]++;
                }
            }
        }
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        printf("%d\n",f[i]);
    }
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i, x, N) for (int i = x; i < (N); i++)
using namespace std;
int main()
{
	string S;
	cin >> S;
	if (S == "ABC")
	{
		cout << "ARC" << endl;
	}
	else
	{
		cout << "ABC" << endl;
	}
}


Measured memory_bytes: 3596
#include <stdio.h>

int main(void){
  char s[3];
  int a[3]={0,0,0};
  int i;
  scanf("%s",s);
  for(i=0;i<3;i++){
    if(s[i]=='a'){
      a[0]++;
    }
    if(s[i]=='b'){
      a[1]++;
    }
    if(s[i]=='c'){
      a[2]++;
    }
  }
  if(a[0]==1 && a[1]==1 && a[2]==1)
    printf("Yes");
  else
    printf("No");
  
  return 0;
}

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

#define MAX_N 2000

// int A = 12;
// int B = 4;
int A, B;
int main() {
    cin >> A >> B;
    int ans = A - (B * 2);
    if (ans < 0) {
        ans = 0;
    }
    cout << ans;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#define INF 1000000010
#define ll long long
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define db double
#define EPS 1e-5
using namespace std;
char *fs,*ft,buf[1<<15];
inline char getc()
{
	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=100010,maxn=20;
int n,top;
int a[MAXN],b[maxn],c[maxn];
int ans;
int f[1<<maxn];
inline int calc(int x)
{
	int cnt=0,last=0;
	for(int i=1;i<=top;++i)
	{
		if(x&(1<<(i-1)))
		{
			if(last)
			{
				last=last^c[i];
				++cnt;
			}
			else last=c[i];
		}
	}
	if(last)return INF;
	return cnt;
}
int main()
{
	//freopen("1.in","r",stdin);
	n=read();
	for(int i=1;i<n;++i)
	{
		int x,y,z;
		x=read()+1;y=read()+1;z=read();
		a[x]^=z;a[y]^=z;
	}
	for(int i=1;i<=n;++i)++b[a[i]];
	for(int i=1;i<=15;++i)
	{
		ans+=b[i]>>1;
		b[i]=b[i]&1;
		if(b[i])c[++top]=i;
	}
	memset(f,0x3f,sizeof(f));f[0]=0;
	for(int i=1;i<(1<<top);++i)
	{
		f[i]=calc(i);
		for(int s=i;s;s=i&(s-1))
			f[i]=min(f[i],f[s]+f[s^i]);
	}
	printf("%d\n",ans+f[(1<<top)-1]);
	return 0;
}


Measured memory_bytes: 4736
#include<stdio.h>
#define N 10000
#define INF 10000
#define NIL NULL
#define W 0
#define B 2
#define G 1
int prim(int );
int A[N][N];

int main(){
    int a,i,j;

    scanf("%d",&a);
    for(i = 0;i < a;i++){
        for(j = 0;j < a;j++){
            scanf("%d",&A[i][j]);
            if(A[i][j] == -1)A[i][j] = INF;
        }
    }
    printf("%d\n",prim(a));
    return 0;
}

int prim(int a){
    int i,v,u = 0,min,d[100],p[100],color[100],n = 0;

    for(i = 0;i < a;i++){
        d[i] = INF;
        p[i] = -1;
        color[i] = W;
    }
    d[0] = 0;
    while(1){
        min = INF;
        u = -1;
        for(i = 0;i < a;i++){
            if(min > d[i] && color[i] != B){
                u = i;
                min = d[i];
            }
        }
        if(u == -1)break;
        color[u] = B;
        for(v = 0;v < a;v++){
            if(color[v]!= B && A[u][v] != INF){
                if(d[v] > A[u][v]){
                    p[v] = u;
                    d[v] = A[u][v];
                    color[v] = G;
                }
            }
        }
    }
    for(i = 0;i < a;i++){
        if(p[i] != -1){
            n += A[i][p[i]];
        }
    }
    return n;
}


Measured memory_bytes: 2164
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
using namespace std;

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

const long long INF = 1LL << 60;
int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	int res = 0;
	for (int i = 0;;i++) {
		if (a == b && a == c) {
			break;
		}
		if (a % 2 == b % 2&&a%2!=c%2) {
			a++;b++;res++;
		}
		else if (a % 2 == c % 2 && a % 2 != b % 2) {
			a++;c++;res++;
		}
		else if (b % 2 == c % 2 && a % 2 != b % 2) {
			b++;c++;res++;
		}
		else if (a % 2 == b % 2 && a % 2 == c % 2) {
			int n = a;
			chmin(n, b);
			chmin(n, c);
			if (n == a) {
				a += 2;
			}
			else if (n == b) {
				b += 2;
			}
			else if (n == c) {
				c += 2;
			}
			res++;
		}

		if (a == b && a == c) {
			break;
		}
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define x first
#define y second
#define ld long double
#define pii pair<int, int>
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
const int mod = 1e9 + 7;
using namespace std;
#ifndef ONLINE_JUDGE
#define tr(...) {__l(__LINE__);__f(#__VA_ARGS__, __VA_ARGS__);}
inline void __l(int line) { cerr << "#" << line << ": "; }template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << std::endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define tr(...)
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}
const int N = 1e6 + 10;
// make sure N size is correctttt!!!!!!!!!

int power(int a, int b, int m = mod){if(b < 0)b += m-1; int r = 1; while(b){if(b&1)r=(r*a)%m; a = (a*a)%m; b>>=1;}return r;}

pii a[N];
int fact[N+10], ifact[N+10];

void pre(int N){
   fact[0] = 1;
   for (int i = 1; i <= N; ++i)
   {
      fact[i] = (i*fact[i-1])%mod;
   }
   ifact[N] = power(fact[N], -1);
   for (int i = N-1; i >= 0; --i)
   {
      ifact[i] = ((i+1)*ifact[i+1])%mod;
   }
}

int nCr(int n, int r){
   if(n < r or n < 0 or r < 0)return 0;
   return ((fact[n]*ifact[r])%mod * ifact[n-r])%mod;
}

int formula(int x1, int x2, int y1, int y2){
   if(x1 > x2 or y1 > y2)
      return 0;
   return nCr(x2-x1+y2-y1,x2-x1);
}

int h, w, n, total, badPaths[N];

int calculate(){
   int sum = 0;
   for (int i = 1; i <= n; ++i)
   {
      badPaths[i] = formula(1,a[i].x,1,a[i].y);
      int remove = 0;
      for (int j = 1; j < i; ++j){
         remove += (badPaths[j] * formula(a[j].x,a[i].x,a[j].y,a[i].y)) % mod;
         remove %= mod;
      }
      badPaths[i] -= remove;
      badPaths[i] += mod;
      badPaths[i] %= mod;//no of distinct badPaths paths from (1,1) to (x,y)
   }

   for (int i = 1; i <= n; ++i)
   {
      sum += (badPaths[i] * formula(a[i].x,h,a[i].y,w))%mod;
      sum %= mod;
   }
   return (total-sum+mod)%mod;
}

int32_t main(){_
   pre(N);

   const int mod2 = 1e8 + 7;
   int faltu;
   cin>>h>>w>>n;

   int ptr = 1;
   for (int i = 1; i <= n; ++i)
   {
      cin>>a[i].x>>a[i].y;
   }

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

   total = formula(1,h,1,w);
   cout<<calculate();

   //make sure N size is correct!!!!!!!!!
   return 0;
}


Measured memory_bytes: 18816
X,N= map(int,input().split())
P = list(map(int,input().split()))
a = range(X-101,X,1)
a1 = sorted(a,reverse=True)
b = range(X,X+101,1)
A = []
B = []
for i in range(len(a1)):
    C = a1[i] not in P
    if C==True:
        A.append(a1[i])
    else:
        continue
for i in range(len(b)):
    D = b[i] not in P
    if D==True:
        B.append(b[i])
    else:
        continue
if X-A[0] <= B[0]-X:
    print(A[0])
else:
    print(B[0])

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

int main()
{
  int n, h;
  cin >> n >> h;
  int maxa = 0;
  vector<int> bv(n);
  for(int i = 0; i < n; ++i){
    int a;
    cin >> a >> bv[i];
    maxa = max(maxa, a);
  }
  sort(bv.rbegin(), bv.rend());
  int ret = 0;
  for(auto& b : bv){
    if(maxa < b){
	  ++ret;
      h -= b;
      if(h <= 0){
        cout << ret << endl;
        return 0;
      }
    }else{
      break;
    }
  }
  
  if(h % maxa == 0){
    cout << ret + h / maxa << endl;
  }else{
    cout << ret + h / maxa + 1 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 640
import java.util.*;

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

        while(sc.hasNextLine()){
            String s = sc.nextLine();

            s = s.replaceAll("apple", "\n\n\n\n\n");
            s = s.replaceAll("peach", "apple");
            s = s.replaceAll("\n\n\n\n\n", "peach");

            System.out.println(s);
        }
    }
}

Measured memory_bytes: 12000
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
#define F(i,x,n) for(int i=x;i<=n;++i)
#define F_(i,x,n) for(int i=x;i>=n;--i)
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline int  Rem() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
inline void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
const int N=2e3+5;
int n,ans,a[N];
/**/
int main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    // a[1]=2,a[2]=3,a[3]=5,a[4]=9,a[5]=13;
    // int tmp=lower_bound(a+1,a+1+5,4)-a;
    // cout<<tmp;
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+1+n);
    // for(int i=1;i<=n;i++) cout<<a[i]<<' ';en dl;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int pp=lower_bound(a+1+j,a+1+n,a[i]+a[j])-a;
            ans+=pp-1-j;
            // cout<<i<<' '<<j<<' '<<pp<<'\n';
        }
    }
    cout<<ans;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, T;
    cin >> N >> T;

    vector<ll> A(N);

    ll mina;
    ll ans = 0;
    ll diff = 0;
    REP(i, N){
        cin >> A[i];
        if(i == 0){
            mina = A[i];
            ans = 0;
            diff = 0;
        }
        mina = min(mina, A[i]);
        if(A[i]- mina == diff){
            ans++;
        }
        if(A[i]- mina > diff){
            ans = 1;
            diff = A[i] - mina;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4056
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
using namespace std;

typedef pair<double, double> point;

void koch(point p1, point p2, int n){
    if(n==0) printf("%lf %lf\n",p1.first,p1.second);
    else{
        point s,t,u;
        s.first = (2*p1.first+p2.first)/3;
        s.second = (2*p1.second+p2.second)/3;
        t.first = (p1.first+2*p2.first)/3;
        t.second = (p1.second+2*p2.second)/3;
        u.first = (p1.first+p2.first)/2 - (p2.second-p1.second)*sqrt(3)/6;
        u.second = (p1.second+p2.second)/2 + (p2.first-p1.first)*sqrt(3)/6;
        koch(p1,s,n-1);
        koch(s,u,n-1);
        koch(u,t,n-1);
        koch(t,p2,n-1);
    }
}

int main(){
    int n;
    cin >> n;
    point p1,p2;
    p1.first = 0;
    p1.second = 0;
    p2.first = 100;
    p2.second = 0;
    koch(p1,p2,n);
    printf("%lf %lf\n",p2.first,p2.second);
}


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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;
const ll MOD = 1e9 + 7;

bool check(string s)
{
   int k = s.size()/2;
   for(int i = 0; i <k; i++)
   {
      if(s[i] != s[i+k])
         return false;
   }
   return true;
}
int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   int a, b, c ,d; cin >> a >> b >> c >> d;
   int t =  min(b, d) - max(a, c);
   if(t<= 0)
      cout << 0;
   else
      cout << t;

   return 0;
}


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

int main(void){
    int n, x, sum = 0;
    cin >> n >> x;
    int m[100010];
    for(int i=0;i<n;++i){
        cin >> m[i];
        sum += m[i];
    }
    sort(m, m+n);
    n += (x-sum)/m[0];
    cout << n << endl;
}

Measured memory_bytes: 256
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1,n):
            l1 = l[i]
            l2 = l[j]
            l3 = l[k]
            if (l1 != l2) &(l2 != l3)&(l1 + l2 > l3):
                count += 1
print(count)

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

// http://noshi91.hatenablog.com/entry/2019/03/31/174006
template <uint_fast64_t Mod>
struct modint {
  using u64 = uint_fast64_t;

  u64 n;

  modint(const u64 x = 0) : n(x % Mod) {}
  modint operator+(const modint r) const { return modint(*this) += r; }
  modint operator-(const modint r) const { return modint(*this) -= r; }
  modint operator*(const modint r) const { return modint(*this) *= r; }
  modint operator/(const modint r) const { return modint(*this) /= r; }
  modint &operator+=(const modint r) {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  }
  modint &operator-=(const modint r) {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  }
  modint &operator*=(const modint r) {
    n = n * r.n % Mod;
    return *this;
  }
  modint &operator/=(modint r) {
    n = n * inv();
    return *this;
  }
  modint pow(u64 x) const {
    modint<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    }
    return ret;
  }
  modint inv() const {
    return pow(Mod-2);
  }
};

// T modint
template<class T>
struct Combination {
  vector<T> fact, inv_fact;
  Combination(ll n) : fact(n+1), inv_fact(n+1) {
    fact[0] = T(1);
    for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * static_cast<T>(i);
    inv_fact[n] = fact[n].inv();
    for (ll i = n; i > 0; i--) inv_fact[i-1] = inv_fact[i] * static_cast<T>(i);
  }

  T P(ll n, ll k) const {
    return fact[n] * inv_fact[n-k];
  }

  T C(ll n, ll k) const {
    return fact[n] * inv_fact[n-k] * inv_fact[k];
  }

  T H(ll n, ll k) const {
    cerr << "H: " << n+k-1 << " " << k << endl;
    return C(n+k-1, n-1);
  }
};

map<ll, ll> PrimeFactorization(ll n) {
  map<ll, ll> m;
  for (int i = 2; i*i <= n; i++) {
    while (n%i == 0) {
      m[i]++;
      n /= i;
    }
  }
  if (n != 1) m[n]++;
  return m;
}

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

  constexpr ll mod = 1e9+7;
  using mint = modint<mod>;

  mint n, m;
  cin >> n.n >> m.n;

  mint ans = 1;
  Combination<mint> c(1000000);
  auto ma = PrimeFactorization(m.n);

  for (auto &i : ma) {
    ans *= c.H(n.n, i.second);
  }

  cout << ans.n << endl;
}


Measured memory_bytes: 15872
#include<iostream>
using namespace std;
int main() {
	int n, ans;
	cin >> n;
	ans = 100000;
	for (int i = 1; i <= n; i++) {
		ans = ans * 1.05;
		if (ans % 1000 != 0) {
			ans = ans + 1000-ans%1000;
		}
	}
	cout << ans << endl;
}


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

const int N = 3010;
const int moder = 1e9 + 7;

int dp[N][N], a[N], pre[N], r[N], n, m;
char s[N];

int main(){
	scanf("%d%d%s", &n, &m, s);
	for (int i = 1; i <= n; ++ i){
		r[i] = i;
	}
	for (int i = 0, l, right; i < m; ++ i){
		scanf("%d%d", &l, &right);
		for (int j = l; j <= right; ++ j){
			r[j] = std::max(r[j], right);
		}
	}
	for (int i = 1; i <= n; ++ i){
		a[i] = s[i - 1] - '0';
		pre[i] = pre[i - 1] + (a[i] == 1);
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n + 1; ++ i){
		for (int j = 0; j <= i - 1; ++ j){
			int restone = pre[r[i]] - j;
			if (restone < 0){
				continue;
			}
			if (restone > 0){
				dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j]) % moder;
			}
			if (restone != r[i] - i + 1){
				dp[i][j] = (dp[i][j] + dp[i - 1][j]) % moder;
			}
		}
	}
	printf("%d\n", dp[n][pre[n]]);
	return 0;
}

Measured memory_bytes: 21504
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,s=-99999999,t;
  cin >> n;
  string a[n];
  for(int i=0;i<n;i++)cin >> a[i];
  cin >> m;
  string b[m];
  for(int i=0;i<m;i++)cin >> b[i];
  for(int i=0;i<n;i++){
    t=0;
    for(int j=0;j<n;j++){
      if(a[i]==a[j])t++;
    }
    for(int j=0;j<m;j++){
      if(a[i]==b[j])t--;
    }
    if(t>s)s=t;
  }
  cout << max(0,s);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
struct fenwick_tree {
	vector<pair<int, int> > x;
	fenwick_tree(int n) : x(n, make_pair(0, 0)) { }
	pair<int,int> sum(int j) {
		pair<int,int> S = make_pair(0, 0);
		for (j; j >= 0; j = (j & (j + 1)) - 1) S = max(S, x[j]);
		return S;

	}
	void add(int k, pair<int,int> a) {
		for (; k < x.size(); k |= k + 1) x[k] = max(x[k], a);
	}
};
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<pair<int,int> > A(N);
	fenwick_tree ft(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i].first;
		A[i].second = -i;
	}

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

	pair<int, int> res = make_pair(0, 0);
	for (int i = 0; i < N; i++) {
		int pos = -A[i].second;
		int val = A[i].first;
		pair<int, int> p = ft.sum(pos);

		p.first++;
		p.second += val;

		ft.add(pos, p);
		res = max(res, p);
	}



	cout << res.second << endl;
}


Measured memory_bytes: 5988
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
mod=10**9+7
A.sort(reverse=True)

n_max=2*10**5
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

ans=0
for i in range(n-k+1):
  ans=(ans+(A[i]-A[n-i-1])*comb(n-i-1,k-1))%mod
print(ans)


Measured memory_bytes: 23976
N, K = [int(x) for x in input().split()]
A = [int(x)-1 for x in input().split()]
past = 0
history = [0]
s = set()
while True:
    na = A[past]
    if na in s: 
        break
    s.add(na)
    history.append(na)
    past = na
s = history.index(na)
e = len(history)
loop = e - s
if K <= s: # ループ前終了
    print(history[K]+1)
else:
    k = K - s
    print(history[s+(k%loop)]+1)


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

int main() {
  int n, k;
  cin >> n >> k;
  
  if(n%k != 0) cout << 1 << endl;
  else cout << 0 << endl;
  
  
  return 0;
}


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

typedef long long ll;

int main(){
    char s[200000];
    scanf("%s",s);
    for(int i=0;i<strlen(s);i++){
        if(s[i]=='?') s[i]='D';
    }
    printf("%s",s);

    return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 1000000007;
using ld = long double;

int main(){
  ll N,K;cin >> N >> K;
  vector<ll> P(N,0);
  for(int i=0;i<N;i++){
    cin >> P[i];
  }
  vector<ll> S(N-K+1,0);
  for(int i=0;i<K;i++){
    S[0] += P[i];
  }
  ll sum=S[0];
  for(int i=0;i<N-K;i++){
    S[i+1] = S[i]-P[i]+P[i+K];
    sum = max(sum,S[i+1]);
  }
  ll ans = sum+K;
  cout << ans/2;
  if(ans%2!=0){
    cout << ".5";
  }
  cout << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define uint unsigned long long
#define ll long long
#define db long double
#define ls rt << 1
#define rs rt << 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 totor<int>
#define vl totor<ll>
#define rep(i, x, y) for(register int i = x; i <= y; i ++)
#define rrep(i, x, y) for(register int i = x; i >= y; i --)
#define eps 1e-15
#define lb(x) x & -x
#define sz(x) (x).size()
using namespace std;
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;
}
inline ll read1()
{
	ll 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;
}
const int mod = 1e9 + 7;
char ch[300010];
int n;
ll k, dp[300010][5][3];
int main()
{
	scanf("%s", ch);
	n = strlen(ch);
	dp[0][2][0] = 1;
	rep(i, 0, n - 1)
	{
        if (ch[i] != '0')
        {
            (dp[i + 1][4][1] += dp[i][4][1]) %= mod;
            (dp[i + 1][4][1] += dp[i][3][1]) %= mod;
            (dp[i + 1][3][1] += dp[i][2][0]) %= mod;
            (dp[i + 1][3][1] += dp[i][2][1]) %= mod;
            (dp[i + 1][2][0] += dp[i][1][0]) %= mod;
            (dp[i + 1][2][1] += dp[i][1][1]) %= mod;
            (dp[i + 1][1][0] += dp[i][0][0]) %= mod;
        }
        if (ch[i] != '1')
        {
            (dp[i + 1][4][1] += dp[i][4][1]) %= mod;
            (dp[i + 1][2][1] += dp[i][3][1]) %= mod;
            (dp[i + 1][1][0] += dp[i][2][0]) %= mod;
            (dp[i + 1][1][1] += dp[i][2][1]) %= mod;
            (dp[i + 1][0][0] += dp[i][1][0]) %= mod;
            (dp[i + 1][2][1] += dp[i][1][1]) %= mod;
            (dp[i + 1][1][0] += dp[i][0][0]) %= mod;
        }
    }
    cout << (dp[n][3][1] + dp[n][4][1]) % mod << endl;
    return 0;
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

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

    for(int i=1; i<= 100000; i++){
        if(((8*i) / 100 == A) && ((10*i) /100 == B)){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i , j , n) for(long long i = j ; i <= n ; i++)
#define per(i , j , n) for(long long i = j ; i >= n ; i--)
const ll N = 123456;
const ll mod = 1e9 + 7;

ll power(ll a , ll b) {
    if(b == 0) return 1LL;
    ll d = power(a , b / 2);
    d *= d;
    d %= mod;

    if(b % 2 != 0) d *= a;

    d %= mod;

    return d;
}

ll inverse_mod(ll a) {
    return power(a , mod - 2);
}

ll f[N];

ll ncr(ll no , ll r) {
    if(r == 0) return 1LL;
    if(r > no) return 0LL;
    if(r == no) return 1LL;
    ll ans = f[no];
    ans *= inverse_mod(f[r]);
    ans %= mod;
    ans *= inverse_mod(f[no - r]);
    ans %= mod;
    return ans;
}

vector < int > a[5 * N];
int dis[5 * N];
int vis[5 * N];

void bfs(int s , int t) {
    queue < ll > q;

    vis[s] = 1;

    q.push(s);

    dis[s] = 0;

    ll cnt = 0;
    while(!q.empty()) {
        ll u = q.front();
        q.pop();

        cnt++;

        for(auto i : a[u]) {
            if(vis[i] == 0) {
                dis[i] = dis[u] + 1;
                vis[i] = 1;
                q.push(i);

                if(i == t) {
                    return ;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n , m;

    cin >> n >> m;

    rep(i , 1 , m) {
        int x , y;
        cin >> x >> y;

        a[x].push_back(y + N);
        a[x + N].push_back(y + 2 * N);
        a[x + 2 * N].push_back(y);
    }

    int s , t;

    cin >> s >> t;

    dis[t] = -1;

    bfs(s , t);

    cout << (dis[t] == -1 ? -1 : dis[t] / 3) << endl;

    return 0;
}


Measured memory_bytes: 28032
#include<stdio.h>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#define Max (int)1e9
#define MAX2 (int)1e5+5
#define MOD ((int)1e9+7)
using namespace std;

long long int gcd(long long int a,long long int b){

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


int main(){
	long long int a,b,c,d,x,right,left,mixed;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	long long int tmp = (c>d)?gcd(c,d):gcd(d,c);
	long long int total = ((b/c)-((a-1)/c))+((b/d)-((a-1)/d));
	//printf("%lld\n",total);
	
	if(tmp > 1){
		x = c/tmp;
		x *= d;
		right = b/x;
		left = (a-1)/x;
		mixed = right-left;
	}else{
		x = c*d;
		right = b/x;
		left = (a-1)/x;
		mixed = right-left;
	}
	tmp = total-mixed;
	//printf("%lld\n",tmp);
	printf("%lld\n",(b-a+1)-tmp);
	return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import itertools

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

l = [i for i in range(1, N + 1)]
permutation = list(itertools.permutations(l, N))
for i in range(len(permutation)):
    if list(permutation[i]) == P:
        a = i + 1
    if list(permutation[i]) == Q:
        b = i + 1

print(abs(a - b))


Measured memory_bytes: 8052