akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=205,M=3e4,inf=1e8;
int n,m,i,j,S,T;
int et,he[N];
struct edge{int l,to,flow;}e[M];
char get(){
	char c=getchar();
	for (;c!='.'&&c!='o'&&c!='S'&&c!='T';c=getchar());
	return c;
}
void line(int x,int y,int flow){
	e[++et].l=he[x];he[x]=et;
	e[et].to=y;e[et].flow=flow;
}
void add(int x,int y,int flow){
	line(x,y,flow);line(y,x,flow);
}
int h,t,q[N],d[N];
bool build(){
	for (int i=1;i<=T;i++) d[i]=0;
	h=0;q[t=1]=S;d[S]=1;
	while (h!=t) for (int x=q[++h],y,i=he[x];i;i=e[i].l)
		if (e[i].flow&&!d[y=e[i].to]){
			d[y]=d[x]+1,q[++t]=y;if (y==T) return 1;
		}
	return 0;
}
int dfs(int x,int flow){
	if (x==T) return flow;
	int rest=flow,use,i,y;
	for (i=he[x];i&&rest;i=e[i].l) if (e[i].flow&&
 		d[y=e[i].to]==d[x]+1&&(use=dfs(y,min(rest,e[i].flow))))
			e[i].flow-=use,e[i^1].flow+=use,rest-=use;
	if (rest==flow) d[x]=0;return flow-rest;
}
int dinic(){
	int res=0;
	while (build()) res+=dfs(S,inf);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);S=n+m+1;T=S+1;et=1;
	for (i=1;i<=n;i++) for (j=1;j<=m;j++){
		char c=get();
		if (c=='o') add(i,j+n,1);
		if (c=='S') line(S,i,inf),line(S,j+n,inf);
		if (c=='T') line(i,T,inf),line(j+n,T,inf);
	}
	int ans=dinic();
	if (ans>=inf) puts("-1"); else printf("%d",ans);
}

Measured memory_bytes: 384
#include <iostream>
#include<string>
using namespace std;
int main(void){
   string s;
   cin>>s;
   if(s=="a"){
       cout<<"vowel"<<endl;
   }
   else if(s=="i"){
       cout<<"vowel"<<endl;
   }
   else if(s=="u"){
       cout<<"vowel"<<endl;
   }
   else if(s=="e"){
       cout<<"vowel"<<endl;
   }
   else if(s=="o"){
       cout<<"vowel"<<endl;
   }
   else{
       cout<<"consonant"<<endl;
   }
    
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long int ll;

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

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

int main() {
  int n;
  cin >> n;
  ll ans = 0;
  rep (i, n + 1) {
    if (i % 3 == 0) {
      continue;
    } else if (i % 5 == 0) {
      continue;
    }
    ans += i;
  }
  P(ans);
  return 0;
}

Measured memory_bytes: 3644
// ABC159-D Banned K

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

signed main() {
    int n, a[200001];
    long long sum[200001] = {}, ans, all;

    cin >> n;
    for(int i=0 ;i<n ;i++ ) {
        cin >> a[i];
        sum[a[i]] ++;
    } 

    all = 0;
    for(int i=1 ;i<=n ;i++ ) {
        ans = sum[i];
        all += ans * (ans - 1) / 2;
    }

    for(int i=0 ;i<n ;i++ ) {
        ans = sum[a[i]];
        ans = ans * (ans - 1) / 2;
        cout << all - ans + (sum[a[i]] - 1) * (sum[a[i]] - 2) / 2 << '\n';
    }
    return (0);
}

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

int main() {
  int n,m,preans = 0;
  cin >> n;
  vector<long long>q(n);
  for(int i  = 0;i < n;i++){
    cin >> q.at(i);
    preans += q.at(i);
  }
  cin >> m;
  vector<vector<long long>>d(m,vector<long long>(2));
  for(int i = 0;i < m;i++){
    int ans;
    cin >> d.at(i).at(0) >> d.at(i).at(1);
    ans = preans-q.at(d.at(i).at(0)-1)+d.at(i).at(1);
    cout << ans << endl;
  }
  
}


Measured memory_bytes: 256
def main():
  #n = int(input())
  #s = input()
  #s = input().split("/")
  s = list(map(int,input().split("/")))
  #a = [input() for i in range(n)]
  #a = [int(input()) for i in range(n)]
  #a = [input().split() for i in range(n)]
  #a = [list(map(int,input().split())) for i in range(n)]
  ans = 0
  count = 0
  lis = []
  
  if s[0] < 2019:
    print("Heisei")
  elif s[0] == 2019 and s[1] <= 4 and s[2] <= 30:
    print("Heisei")
  else:
    print("TBD")
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int read() {
	int x=0; char ch;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return x;
}
int da, db, vis[10], p[10], n;
int main() {
	cin>>n;
	p[0]=1;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*i;
	for(int i=1;i<=n;i++) {
		int x=read(), s=0;
		for(int j=1;j<x;j++) {
			if(!vis[j]) s++;
		}
		vis[x]=1;
		da+=s*p[n-i];
	}
	memset(vis, 0, sizeof(vis));
	for(int i=1;i<=n;i++) {
		int x=read(), s=0;
		for(int j=1;j<x;j++) {
			if(!vis[j]) s++;
		}
		vis[x]=1;
		db+=s*p[n-i];
	}
	cout<<abs(da-db);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef		long long       ll;
typedef         long double      dl;
typedef     unsigned long long  ull;
#define		pb              push_back
#define		PB              pop_back
#define		nn              "\n"
#define     O_O             ios_base::sync_with_stdio(false); cin.tie(NULL)
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define		ss              ' '
#define	       MEM(a,b)         memset(a,(b),sizeof(a))
#define	       CLR(p)           memset(p,0,sizeof(p))
#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define         arrsize(a)      (sizeof(a)/sizeof(a[0]))
//#define       arrsize(a)      (sizeof(a)/sizeof(*a))
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
#define		pi              acos(-1.0)
#define	       ff               first
#define	       sc              second
typedef        pair <int, int>   pii;
typedef       pair <ll, ll>      pll;
typedef      vector< pair <ll, ll> >      vpll;
typedef		vector<ll>      vll;
typedef		map<string,ll>      msl;
typedef		map<ll,ll>      mll;
#define yes cout << "YES\n"
#define no cout<<"NO\n"
//memset(ar,-1,sizeof(ar));
//#define sort(x) sort(x.begin(), x.end())
//sort(a,a+n,greater<ll>())
//for (auto it = mp.begin(); it != mp.end(); ++it){}
#define MAX 1000005
#define precision(a) fixed << setprecision(a)

#define mod 1000000007



int main()
{
 //O_O ;
   string s;cin>>s;
   ll l=s.length();
   ll ans=0;
   for(ll i=0;i<l;i++)
    ans+=s[i]-'0';
if(ans%9==0)
    cout<<"Yes"<<nn;
else
    cout<<"No"<<nn;

    return 0;
}


Measured memory_bytes: 3676
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
    static int rank1 = -1;
    static int rank2 = -1;
    static int rank3 = -1;
    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i=0; i < 10; i ++) {

            try {
                int readVal = Integer.parseInt(br.readLine());
                updateRank(readVal);

            } catch (Exception e) {
            }
        }
        System.out.println(rank1);
        System.out.println(rank2);
        System.out.println(rank3);
    }

    static void updateRank(int rank) {

        if (rank > rank1) {
            rank3 = rank2;
            rank2 = rank1;
            rank1 = rank;
        }
        else if ( rank > rank2) {
            rank3 = rank2;
            rank2 = rank;
        }
        else if (rank > rank3) {
            rank3 = rank;
        }
    }
}

Measured memory_bytes: 16864
m = 10**9+7
def nCr(n,r):
  if r*2>n:
      return nCr(n,n-r)
  else:
      a = b = 1
      for i in range(r):
          a = a * (n - i) % m
          b = b * (r - i) % m
      return (a * pow(b,m-2,m)) % m

n,k=map(int,input().split())
for i in range(k):
    if n-k+1>=i+1:
        print((nCr(n-k+1,i+1)%m)*(nCr(k-1,k-1-i)%m)%m)
    else:
        print(0)

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

map<ll, int> mp;

void prime_factorize(long long N) {
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        while (N % a == 0) {
            N /= a;
        }
        ++mp[a];
    }
    if (N != 1) ++mp[N];
}

int main() {
    ll A, B;
    cin >> A >> B;
    prime_factorize(A);
    prime_factorize(B);

    int ans = 1;
    for (auto x : mp) {
        if (x.second >= 2) ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3644
import copy
n,k = map(int,input().split())
ai = [int(i) for i in input().split()]

old_ai = ai
cnt = 0

while 1 == 1:
    old_ai = copy.deepcopy(ai)
    li = [0]*(n+1)
    for i in range(n):
        li[max(0,i-ai[i])] += 1
        li[min(n,i+1+ai[i])] -= 1
        #print(li)
    #print(li)
    rui = [0]*n
    tmp = 0
    for i in range(n):
        if i == 0:
            ai[i] = li[i]
            tmp += ai[i]
        else:
            ai[i] = li[i] + ai[i-1]
            tmp += ai[i]
    #print(rui)
    if ai == old_ai:
        print(*ai)
        exit()
        break
    cnt += 1
    if cnt == k:
        print(*ai)
        exit()
    old_ai = ai

Measured memory_bytes: 181992
#include <stdio.h>

int	main(void)
{
	int		a, b;
	char	op;

	while (1)
	{
		scanf("%d %c %d", &a, &op, &b);
		if (op == '?')
			break ;
		else
		{
			if (op == '+')
				printf("%d\n", a + b);
			if (op == '-')
				printf("%d\n", a - b);
			if (op == '*')
				printf("%d\n", a * b);
			if (op == '/')
				printf("%d\n", a / b);
		}
	}
	return (0);
}



Measured memory_bytes: 2060
def digit_sum(n):
    sum = 0
    for c in str(n):
        sum += int(c)
    return sum

n, a, b = (int(i) for i in input().split())

res = 0
for i in range(1, n+1):
    s = digit_sum(i)
    if a <= s <= b:
        res += i

print(res)


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int now = 0;
            var st = new List<int[]>();
            for (int i = 0; i < n - 1; i++)
            {
                st.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));
            }
            for (int i = 0; i < n; i++)
            {
                now = 0;
                for (int j = i; j < n - 1; j++)
                {
                    if (i == n - 1)
                    {
                        Console.WriteLine("0");
                        break;
                    }
                    else
                    {
                        if (now <= st[j][1])
                        {
                            now = st[j][1] + st[j][0];
                        }
                        else
                        {
                            int x = 0;
                            while (now > st[j][1] + st[j][2] * x)
                            {
                                x++;
                            }
                            now = st[j][1] + st[j][2] * x + st[j][0];
                        }
                    }
                }
                Console.WriteLine(now);
            }
        }
    }
}

Measured memory_bytes: 11220
//============================================================================
// Name        : ProjG.cpp
// Author      : Yong Kiat
// Version     :
// Copyright   : By Algotae.
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>

using namespace std;

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

	int a[N], b[N], c[N];

	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}

	// 3 dimensional DP
	long long dp[N][3];
	dp[N - 1][0] = a[N - 1];
	dp[N - 1][1] = b[N - 1];
	dp[N - 1][2] = c[N - 1];

	for (int i = N - 2; i >= 0; i--) {
		dp[i][0] = a[i] + max(dp[i + 1][1], dp[i + 1][2]);
		dp[i][1] = b[i] + max(dp[i + 1][0], dp[i + 1][2]);
		dp[i][2] = c[i] + max(dp[i + 1][0], dp[i + 1][1]);
	}

	cout << max(dp[0][0], max(dp[0][1], dp[0][2]));

	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n,m;
    ll ans=0;
    cin>>n>>m;
    vector<int> x(m), d(m);
    vector<P> e(m);
    rep(i,m) cin>>x[i];
    sort(btoe(x));
    rep(i,m-1){
        d[i]=x[i+1]-x[i];
        e[i].first=d[i];
        e[i].second=i;
        ans+=d[i];
    }
    sort(etob(e));
    rep(i,min(n-1, m-1)){
        ans-=d[e[i].second];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double T = sc.nextDouble();
        double A = sc.nextDouble();
        int[] H=new int[N];
        double[] tempH=new double[N];
        for(int i=0;i<N;i++){
            H[i]=sc.nextInt();
            tempH[i]=T-0.006*H[i];
        }
        double min=10000;
        int ans=0;
        for(int i=0;i<N;i++){
            if(Math.abs(tempH[i]-A)<min){
                ans=i;
                min=Math.abs(tempH[i]-A);
            }
        }
        System.out.println((int)ans+1);
    }
}


Measured memory_bytes: 26324
#include <iostream>
#include <string>

using namespace std;



int main()
{
    unsigned long long a;
    string b;
    cin >> a >> b;
    int k = 0;
    for (int i = 0; i < 4; i++) {
        if(i!=1)k = k * 10 + b[i] - '0';
    }
    unsigned long long output;
    output = a * k;
    output = output / 100;
    cout << output;

    return 0;
}

Measured memory_bytes: 3180
#include<set>
#include<map>
#include <unordered_map>
#include <unordered_set>
#include<list>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<complex>
#include<sstream>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<numeric>
#include<utility>
#include<functional>
#include<stdio.h>
#include<assert.h>
#include<memory.h>
#include<bitset>
#include<math.h>
#include <strings.h>



#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;





int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    
    if(n < m) swap(n, m);
    if(n == 1) return cout <<1, 0;
    if(m == 1)
        return printf("%d\n", max(n-2, 0)), 0;
    
    printf("%lld\n", 1ll*(n-2ll)*(m-2ll));
    
    
    
    return 0;

}



/*
 */
//freopen("output.txt","w",stdout);
//freopen("input.txt","r",stdin);
//ios::sync_with_stdio(0);cin.tie(0);

Measured memory_bytes: 256
#!/usr/bin/perl

$line = 0;
while(<>) {
    if($line == 0) {
        ($h, $w) = split /\s/, $_;
    } else {
        chomp;
        push @a, $_;
    }
    $line++;
}

foreach (1 .. $w + 2) {
    print "#";
}
print "\n";

foreach (@a) {
    print "#$_#";
    print "\n";
}
foreach (1 .. $w + 2) {
    print "#";
}
print "\n";


Measured memory_bytes: 640
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] V=new int[n], C=new int[n];
        
        for(int i=0; i<n; i++)
            V[i] = sc.nextInt();
        for(int i=0; i<n; i++)
            C[i] = sc.nextInt();
        
        int sum = 0;
        for(int i=0; i<n; i++)
            if(V[i] > C[i])
                sum += V[i] - C[i];
        
        System.out.println(sum);
    }
}


Measured memory_bytes: 21844
N = int(input())
CSF = [list(map(int, input().split())) for _ in range(N-1)]

def F(n):
    time = 0
    for i in range(n, N-1):
        c, s, f = CSF[i]
        if time <= s:
            time = s + c
        else:
            remainder = time % f
            time += (f-remainder)%f+c
    print(time)
for i in range(N-1):
    F(i)
print(0)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  while (true) {
    int e; cin >> e;
    if (e == 0) break;
    int res = 1e9;
    for (int z = 0; z * z * z <= e; ++z) {
      for (int y = 0; y * y + z * z * z <= e; ++y) {
        int x = e - y * y - z * z * z;
        res = min(res, x + y + z);
      }
    }
    cout << res << '\n';
  }
}


Measured memory_bytes: 3104
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int k,tsum;
double s,d[40100],a,b[40100],ans,n,t[100];
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){cin>>t[i];tsum+=t[i];}
    for(int i=0;i<n;i++){
        cin>>a;
        for(int j=0;j<=t[i]*2;j++){
            if(j==0)d[k+j]=min(d[k+j],a);
            else d[k+j]=a;
        }
        k+=2*t[i];
    }
    d[2*tsum]=0;
    for(int i=0;i<2*tsum+1;i++){
        b[i+1]=min(b[i]+0.5,d[i+1]);
        //cout<<i<<d[i]<<endl;
    }
    b[2*tsum]=0;
    for(int i=2*tsum;i>0;i--)b[i-1]=min(b[i-1],min(b[i]+0.5,d[i-1]));
    for(int i=0;i<2*tsum;i++){
        //cout<<i<<" "<<b[i]<<endl;
        ans+=(b[i]+b[i+1]);
        //cout<<iac+1<<" "<<ans/4<<endl;
    }
    cout<<setprecision(10)<<ans/4<<endl;
}


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

int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++){cin >> a[i];}
  
  int q=1000000;
  int ans=0;
  for(int i=0;i<n;i++){
    if(q>a[i]){
      ans++;
      q=a[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << " "; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int main(){
  int n; cin >>n;
  vector<int> v(n);
  int s=0;
  rep(i,n){
    int a; cin >>a;
    v[i]=a;
    s^=a;
  }
  rep(i,n){
    print(s^v[i]);
  }

}


Measured memory_bytes: 3980
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 610
#define MOD 1000000007
int n, m, a[MAXN], b[MAXN], f[MAXN][MAXN];
int g[MAXN], s[MAXN], ans, in, out;
inline void up(int &x, int y) {
	if ((x += y) >= MOD) x -= MOD;
}
int main() {
	scanf("%d%d", &n, &m);
	g[0] = 1;
	for (int i = 2; i <= 2 * n; i += 2) g[i] = 1LL * g[i - 2] * (i - 1) % MOD;
	for (int i = 1; i <= 2 * n; i++) s[i] = 1;
	for (int i = 1; i <= m; i++) scanf("%d%d", a + i, b + i), s[a[i]]--, s[b[i]]--;
	for (int i = 1; i <= 2 * n; i++) s[i] += s[i - 1];
	// for (int i = 1; i <= 2 * n; i++) printf("%d ", s[i]);
	// puts("");
	for (int i = 2 * n; i >= 1; i--) {
		for (int j = i; j <= 2 * n; j++) {
			for (int k = 1; k <= m; k++) {
				if ((i <= a[k] && a[k] <= j) != (i <= b[k] && b[k] <= j)) goto fail;
			}
			in = s[j] - s[i - 1];
			// printf("in %d out %d\n", in, out);
			f[i][j] = 1LL * g[in] * g[out] % MOD;
			for (int k = i; k < j; k++) {
				int rest = s[j] - s[k];
				up(f[i][j], MOD - 1LL * f[i][k] * g[rest] % MOD);
			}
			// printf("f[%d][%d] = %d\n", i, j, f[i][j]);
		fail:;
		}
	}
	for(int i = 1;i <= 2 * n;i++){
		for(int j = i;j <= 2 * n;j++){
			int out = s[2 * n] - s[j] + s[i - 1];
			up(ans, 1LL * f[i][j] * g[out] % MOD);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string.h>
using namespace std;
char c[2002][2002];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
        scanf("%s",c[i]);
    int mx=-1;
    int sum=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {

            if(c[i][j]=='.')
            {
                sum=1;
                for(int k=i-1; k>=0; k--)
                {
                    if(c[k][j]=='#')
                    {
                        sum+=i-1-k;
                        break;
                    }
                    if(k==0)
                        sum+=i-k;
                }
                for(int k=i+1; k<n; k++)
                   {
                       if(c[k][j]=='#')
                    {
                        sum+=k-1-i;
                        break;
                    }
                    if(k==n-1)
                        sum+=k-i;
                   }
                for(int k=j-1; k>=0; k--)
                  {
                      if(c[i][k]=='#')
                    {
                        sum+=j-1-k;
                        break;
                    }
                    if(k==0)
                        sum+=j-k;
                  }
                for(int k=j+1; k<m; k++)
                  {
                      if(c[i][k]=='#')
                    {
                        sum+=k-1-j;
                        break;
                    }
                    if(k==m-1)
                        sum+=k-j;
                  }
                mx=max(mx,sum);
            }
            if(mx==n+m-1)
                break;
        }
    }
    printf("%d\n",mx);
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define ll long long
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define divceil(A, B) ((A + (B - 1)) / B)
#define MODN 998244353
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr

using namespace std;


int main(){

    ll m;
    cin >> m;

    ll sum = 0;
    ll digit = 0;

    rep(i,m){
        int d;
        ll c;

        cin >> d >> c;

        sum += c * d;
        digit += c;
    }

    if(sum == 9) sum = 0;

    cout << (digit - 1) + max(sum - 1, (ll)0) / 9 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
//#define int long long
#define INF 1000000
using namespace std;
set<string> se;
void reversal(string x, string y){
    if(x.size() >= 2) {
        string tmp = x;
        reverse(tmp.begin(),tmp.end());
        se.insert(tmp+y);
        se.insert(y+tmp);
    }
    if(y.size() >= 2) {
        string tmp = y;
        reverse(tmp.begin(),tmp.end());
        se.insert(x+tmp);
        se.insert(tmp+x);
    }
    if(x.size() >= 2 && y.size() >=2){
        string tmp1 = x;
        reverse(tmp1.begin(),tmp1.end());
        string tmp2 = y;
        reverse(tmp2.begin(),tmp2.end());
        se.insert(tmp1+tmp2);
        se.insert(tmp2+tmp1);
    }
}
int main(){
    int n;
    cin >> n;
    rep(i,n){
        se.clear();
        string s;
        cin >> s;
        int divide = s.size()-1;
        rep(j,divide){
            string a = s.substr(0,j+1);
            string b = s.substr(j+1,divide-j);
            se.insert(a+b);
            se.insert(b+a);
            reversal(a,b);
        }
        cout << se.size() << endl;
    }
    return 0;
}



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


YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: int, B: int, S: str):
    print(YES if re.match(r"\d" * A + "-" + r"\d" * B, S) else NO)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(A, B, S)


if __name__ == '__main__':
    main()


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

//binary_search(begin, end, valuetofind)

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define f first
#define s second
#define pb push_back
#define INF 1000000000000000
#define MAX 1000000000
#define MOD 1000000007

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,int> pwi;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector< vector<pair<int,lli> > > wGraph;
typedef vector<vector<int> > graph;
//typedef vector<vector<int> > matrix;


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<std::fixed;
    cout<<std::setprecision(10);

    lli n,m,g,res,k;

    cin>>n;

    vector<lli> h(n),pre(n+1,0),suf(n+1,0);
    rep(i,n){
        cin>>h[i];
    }
    for(int i = 0;i<n;++i){
        pre[i+1] = __gcd(pre[i],h[i]);
    }
    for(int i = n;i>0;i--){
        suf[i-1] = __gcd(suf[i],h[i-1]);
    }

    m = 0;
    for(int i = 0;i<n;++i){
        m = max(m,__gcd(pre[i],suf[i+1]));
    }

    cout<<m<<"\n";

    return 0;

}


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

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

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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto n = load<int>();
	auto k = load<int>();
	auto people = load<string>();
	auto left_cross = people[0] == 'L' ? 1 : 0;
	auto right_cross = people[n-1] == 'R' ? 1 : 0;
	auto crosses = 0;
	auto circles = 0;
	auto calm = 0;
	for (auto i=0; i+1<n; ++i)
		if (people[i] == 'R' and people[i+1] == 'L')
			++crosses;
		else if (people[i] == 'L' and people[i+1] == 'R')
			++circles;
		else if (people[i] == people[i+1])
			++calm;
	auto for_cross = min({k, crosses, circles});
	k -= for_cross;
	crosses -= for_cross;
	auto for_left = min({k, crosses, left_cross});
	k -= for_left;
	crosses -= for_left;
	left_cross -= for_left;
	auto for_right = min({k, crosses, right_cross});
	k -= for_right;
	crosses -= for_right;
	right_cross -= for_right;
	auto for_bad_left = min({k, crosses, 1 - left_cross});
	k -= for_bad_left;
	crosses -= for_bad_left;
	left_cross += for_bad_left;
	auto for_bad_right = min({k, crosses, 1 - right_cross});
	k -= for_bad_right;
	crosses -= for_bad_right;
	right_cross += for_bad_right;
	auto for_dual = min({k, left_cross, right_cross});
	k -= for_dual;
	left_cross -= for_dual;
	right_cross -= for_dual;
	auto score = calm + 2 * for_cross + for_left + for_right + for_bad_left + for_bad_right + for_dual;
	cout << score << '\n';
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define INT(str) stoi((str), 0)
#define INTB(str) stoi((str), 0, 2) // 2進数の文字列を int に
//cout << fixed << setprecision(15);

int main() {
  ll x, k, d;
  cin >> x >> k >> d;
  ull p = min(k-1, abs(x/d));
  ull last = (k - p) % 2;
  
  if(x == 0) {
    if(last == 1)
      cout << d << endl;
    else
      cout << 0 << endl;
  }
  
  else if(0 < x) {
    x -= d * p;
    if(last == 1) {
      cout << abs(x-d) << endl;
    }
    else {
      cout << x << endl;
    }
  }
    
  else {
    x += d * p;
    if(last == 1) {
      cout << abs(x+d) << endl;
    }
    else {
      cout << -x << endl;
    }
  }
}


Measured memory_bytes: 3508
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
int a,b;

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
	
	int n;
	cin >> n;
	int ans = 100000000000000000;
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			int cur = ( n/i ) + i - 2;
			ans = min(ans, cur);
		}
	}
	cout << ans << endl;
    

return 0;
}
///....


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datA, datB, datC, datD, datE, datF) = readLine.split(" ").map(_.toInt)

    val water = for(
      i <- 0 to datF / 100 / datA;
      j <- 0 to datF / 100 / datB;
      k = datA * i + datB * j;
      if((k > 0) && (k <= datF / 100))
    ) yield k
    val sugar = for(
      i <- 0 to datF / 2 / datC;
      j <- 0 to datF / 2 / datD;
      k = datC * i + datD * j;
      if(k <= datF / 2)
    ) yield k

    val ans = water.map(w =>
      sugar.map(s => {
        val total = w * 100 + s
        if((w * datE < s) || (total > datF)) (0.0, 0, 0)
        else ((100.0 * s / total), (w * 100 + s), s)
      } ).maxBy(_._1)
    ).maxBy(_._1)

    println(ans._2 + " " + ans._3)
  }
}


Measured memory_bytes: 110472
import heapq

n,m = map(int, input().split())

c = [[]for i in range(10**5+10)]

for i in range(n):
    a,b = map(int,input().split())
    c[a].append(-b)


h = []
heapq.heapify(h)
ans = 0

for i in range(m):
    for x in c[i+1]:
        heapq.heappush(h,x)
    if h:
        ans += heapq.heappop(h)

print(-ans)


Measured memory_bytes: 72352
#include<stdio.h>
#include<ctype.h>


int main()
{

	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(a+b>c+d){
		printf("Left");
	}
	else if(a+b<c+d){
		printf("Right");
	}
	else{
		printf("Balanced");
	}

}

Measured memory_bytes: 128
arr = gets.chomp.split(" ").map(&:to_i)
count = 0
while true
  if arr.max - arr.min >= 2
    arr[arr.index(arr.min)] += 2
    count += 1
  elsif arr.max - arr.min >= 1
    if arr.select {|n| n == arr.min}.length == 2
      count += 1
      break
    else
      count += 2
      break
    end
  else
    break
  end
end
puts count

Measured memory_bytes: 1788
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
typedef long long int64;
static const int MAXN = 5e5 + 4;

static const int HBASE1 = 983;
static const int64 HMOD1 = 998244353;
static const int HBASE2 = 418;
static const int64 HMOD2 = 1e9 + 7;
typedef std::pair<int64, int64> hash_t;
int64 HBASE1_POW[MAXN], HBASE2_POW[MAXN];

int n;
char s[MAXN];
hash_t h[MAXN];

inline hash_t get_hash(int l, int r)
{
    return hash_t(
        (h[l].first - h[r + 1].first + HMOD1) * HBASE1_POW[n - r] % HMOD1,
        (h[l].second - h[r + 1].second + HMOD2) * HBASE2_POW[n - r] % HMOD2
    );
}

inline int period(int offset, int len)
{
    static std::vector<int> div;
    div.clear();
    for (int i = 1; i * i <= len; ++i) if (len % i == 0) {
        div.push_back(i);
        if (i != 1 && i * i != len) div.push_back(len / i);
    }
    for (std::vector<int>::iterator d = div.begin(); d != div.end(); ++d) {
        if (get_hash(offset, offset + len - *d - 1) == get_hash(offset + *d, offset + len - 1))
            return *d;
    }
    return len;
}

int main()
{
    scanf("%s", s); n = strlen(s);
    HBASE1_POW[0] = HBASE2_POW[0] = 1;
    for (int i = 1; i <= n; ++i) HBASE1_POW[i] = HBASE1_POW[i - 1] * HBASE1 % HMOD1;
    for (int i = 1; i <= n; ++i) HBASE2_POW[i] = HBASE2_POW[i - 1] * HBASE2 % HMOD2;

    h[0] = hash_t(0, 0);
    for (int i = 0; i < n; ++i) {
        h[i + 1] = hash_t(
            (h[i].first + HBASE1_POW[i] * s[i]) % HMOD1,
            (h[i].second + HBASE2_POW[i] * s[i]) % HMOD2
        );
    }

    int p = period(0, n);

    if (p == 1) {
        printf("%d\n1\n", n);
    } else if (p == n) {
        printf("1\n1\n");
    } else {
        int ct = 0;
        for (int i = 1; i < n; ++i)
            if (period(0, i) == i && period(i, n - i) == n - i) ++ct;
        printf("2\n%d\n", ct);
    }

    return 0;
}

Measured memory_bytes: 16384
package main

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

func main() {
	io := NewIo(os.Stdin, os.Stdout)
	defer io.Flush()
	n := io.NextInt()
	a := io.NextInts(n)
	cnt := map[int]int{}
	ans := 0
	for i := range a {
		ans += cnt[i-a[i]]
		cnt[i+a[i]]++
	}
	io.Println(ans)
}

// Io is I/O object
type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

// NewIo returns a new Io instance
func NewIo(r io.Reader, w io.Writer) *Io {
	return &Io{
		reader: bufio.NewReader(r),
		writer: bufio.NewWriter(w),
	}
}

// Flush flushes writer
func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

// NextLine scans a line from stdin
func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

// Next return a word from stdin
func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

// NextInt returns an integer from stdin
func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

// NextInts returns n integers from stdin
func (io *Io) NextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = io.NextInt()
	}
	return ret
}

// Println is a wrapper of fmt.Fprintln
func (io *Io) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


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

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
typedef long long ll;
typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> pii;typedef vector<pii> vpii;

void Main() {
  string s;
  cin >> s;
  map<char, bool> co;
  forr(c, s) co[c]=1;

  if (co['N'] ^ co['S'] || co['W'] ^ co['E']) puts("No");
  else puts("Yes");
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }


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

// IGNORE THE #pragma, just to suppress annoying warnings on IDE

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wuninitialized"
using namespace std;


typedef long long ll;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define per(i, start, end) for(int i = (int)start-1; i >= end; --i)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const double PI = 3.14159265358979323846;
const double eps = (1e-8);

int dcmp(double x, double y)
{ return fabs(x - y) <= eps ? 0 : x < y ? -1 : 1; }

int valid(ll n, vector<int> const &a)
{
    rep(i,0,sz(a))
    {
        if (n < 2)
            return -1;
        n = n - n%a[i];
    }
    if (n == 2)
        return 0;
    return 1;
}

ll bsMin(ll st, ll end, vector<int> const &a)
{
    while (st < end)
    {
        ll mid = st + (end - st) / 2;
        if (valid(mid, a) == 0)
            end = mid;
        else if (valid(mid, a) == 1)
            end = mid - 1;
        else if (valid(mid, a) == -1)
            st = mid + 1;
    }
    return st;
}

ll bsMax(ll st, ll end, vector<int> const &a)
{
    while (st < end)
    {
        ll mid = st + (end - st + 1) / 2;
        if (valid(mid, a) == 0)
            st = mid;
        else if (valid(mid, a) == 1)
            end = mid - 1;
        else if (valid(mid, a) == -1)
            st = mid + 1;
    }
    return st;
}

int main()
{
    ios_base::sync_with_stdio(false);
//    freopen("input.txt", "r", stdin);
    int k;
    cin >> k;
    vector<int> a(k);
    rep(i, 0, k)
    {
        cin >> a[i];
    }
    ll st = 0, end = 1e18;
    ll nMin = bsMin(st, end, a);
    ll nMax = bsMax(st, end, a);
    if (valid(nMin, a) == 0 && valid(nMax, a) == 0)
        cout << nMin << " " << nMax << endl;
    else if (valid(nMin, a) == 0)
        cout << nMin << " " << nMin << endl;
    else if (valid(nMax, a) == 0)
        cout << nMax << " " << nMax << endl;
    else
        cout << -1 << endl;
    return 0;
}

#pragma clang diagnostic pop

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

int main() {
    int n;
    cin >> n;
    if (n % 1000 == 0)
        cout << 0 << endl;
    else {
        int a = n / 1000;
        a++;
        cout << a * 1000 - n << endl;
    }
}

Measured memory_bytes: 3636
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;

//int N, M, K, H, W, L, R;
int N, M, K, H, W, L, R;



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

	string s;
	cin >> s;
	cin >> N;
	int rev = 0;
	vector<string>t(2);
	for (int i = 0; i < N; i++) {
		cin >> K;
		if (K == 1) {
			rev ^= 1;
		}
		else {
			cin >> K;
			K--;
			char a;
			cin >> a;
			t[K^rev].push_back(a);
		}
	}
	if (rev) {
		reverse(t[1].begin(), t[1].end());
		reverse(s.begin(), s.end());
		cout << t[1] + s + t[0] << endl;
	}
	else {
		reverse(t[0].begin(), t[0].end());
		cout << t[0] + s + t[1] << endl;
	}
}

Measured memory_bytes: 1300
#ifndef CLASS_MODINT
#define CLASS_MODINT

#include <cstdint>

template <std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {};
	static constexpr std::uint32_t get_mod() { return mod; }
	std::uint32_t get() const { return n; }
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint inv() const { return (*this).pow(mod - 2); }
	modint pow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
};

#endif // CLASS_MODINT

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
using mint = modint<1000000007>;
int main() {
	int N, A, B;
	cin >> N >> A >> B;
	if (A < B) swap(A, B);
	vector<vector<mint> > dp(N + 1, vector<mint>(2 * N + 1)); // (pos, cont)
	for (int i = 0; i <= N; ++i) {
		mint g = mint(2).pow(N - i);
		for (int j = A; j <= 2 * N; ++j) {
			dp[i][j] = g;
		}
	}
	vector<mint> sum_line1(N + 2);
	sum_line1[N] = dp[N][1];
	vector<vector<mint> > sum_line45(N + 2, vector<mint>(2 * N + 2));
	for (int i = N; i >= 0; --i) {
		for (int j = 2 * N; j >= A; --j) {
			sum_line45[i][j] = sum_line45[i + 1][j + 1] + dp[i][j];
		}
	}
	for (int i = N - 1; i >= 0; --i) {
		for (int j = 0; j < A; ++j) {
			// next = A
			dp[i][j] += dp[i + 1][j + 1];
			// next = BA, BBA, BBBA, ...
			if (min(N - i, B) >= 2) {
				dp[i][j] += sum_line1[i + 2] - sum_line1[i + min(N - i, B) + 1];
			}
			if (N - i >= B + 1) {
				dp[i][j] += sum_line45[i + (B + 1)][j + (B + 1)] - sum_line45[i + (N - i) + 1][j + (N - i) + 1];
			}
			// next = BBBBB...
			if (N - i >= B && j + N - i >= A) {
				dp[i][j] += 1;
			}
			sum_line45[i][j] = sum_line45[i + 1][j + 1] + dp[i][j];
		}
		sum_line1[i] = sum_line1[i + 1] + dp[i][1];
	}
	cout << dp[0][0].get() << endl;
	return 0;
}

Measured memory_bytes: 394508
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();
        int b = 0;
        for(int i=0;i<a-2;i++){if(s.substring(i,i+3).equals("ABC")){b++;
                                                 }
                            }
       
		System.out.println(b);
	}
}


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

/*
L(0) := P
L(n) := B L(n-1) P L(n-1) B

f(n) := L(n) の文字数
g(n) := L(n) のPの個数
*/

ll f(int n){ return n==0 ? 1 : f(n-1)*2+3; }
ll g(int n){ return n==0 ? 1 : g(n-1)*2+1; }

ll calc(int n, ll x){
    if(x<=0) return 0;
    if(n==0) return 1;
    if(x > f(n)/2) return g(n-1) + 1 + calc(n-1, x - (f(n)/2+1));
    else return calc(n-1, x-1);
}

int main(void){
    int n;
    ll x;
    cin >> n >> x;
    cout << calc(n, x) << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
m = (n**0.5).ceil
k = 0
(1..m).reverse_each do |i|
  if n%i == 0 then
    k = n/i
    break
  end
end
if k == 0 then
  puts n.to_s.length
else
  puts k.to_s.length
end

Measured memory_bytes: 2684
#include<bits/stdc++.h>
//#define m 1000000007
using namespace std;
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 
 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define endl '\n'
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
 
typedef long long int ll;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const ll mod =998244353;

int main()
{
	ll n;
	cin>>n;
	cout<<n*(n-1)/2;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  
  int ans = 0;
  for(int i=0;i<n;i++){
    if(0 == i % 2 && !(0 == a.at(i) % 2) ){
      ans++;
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 3592
n = int(input())
a = list(map(int, input().split()))
a = [0] + a + [0]
cost = [abs(a[i+1]-a[i]) for i in range(n+1)]
total = sum(cost)

#print('a: ', a)
#print('cost: ', cost)

for i in range(n):
    ans = total-cost[i]-cost[i+1]
    ans += abs(a[i]-a[i+2])
    print(ans)

Measured memory_bytes: 14048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = 1e17 + 7;
const ll N = 1e5+7;

struct aa{
    ll u,d;
    bool operator < (const aa & a) const{
        return d>a.d;
    }
};

vector<aa>arr[N];

bool vis[N];
ll n,m;
ll d[N];

void Dij(){
    fill(d+1,d+n+1,MAX);
    d[1]=0;
    priority_queue<aa>Q;
    Q.push({1,0});
    while(!Q.empty()){
        aa x=Q.top();
		Q.pop();
        ll u=x.u;
        if(vis[u])continue;
        vis[u]=1;
        for(ll i=0;i<arr[u].size();i++){
            aa e=arr[u][i];
            if(d[e.u]>d[u]+e.d){
                d[e.u]=d[u]+e.d;
                Q.push({e.u,d[e.u]});
            }
        }
    }
}

int main(){
	ll a,b,w;		
	scanf("%lld%lld",&n,&m);
	for(ll i=2;i<=n;i++){
		arr[i].push_back({i-1,0});
	}
	for(ll i=0;i<m;i++){
		scanf("%lld%lld%lld",&a,&b,&w);
		arr[b].push_back({a,w});
		arr[a].push_back({b,w});
	}
	Dij();
	if(d[n]==MAX) d[n]=-1;
	cout<<d[n]<<endl;
	
	
	return 0;
}

Measured memory_bytes: 13304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
const ll MAX = 1001001;
const ll MOD = 1000000007;
ll k;
vector<ll> a;
ll co(ll n)
{
    ll now = n;
    rep(i, k)
    {
        now = now / a[i] * a[i];
    }
    return now;
}
int main()
{
    cin >> k;
    a = vector<ll>(k);
    rep(i, k)
    {
        cin >> a.at(i);
    }
    ll ans = 0;
    ll r = 0;
    ll l = 1000000000000000000;
    while (l - r > 1)
    {
        ll mid = (r + l) / 2;
        if (co(mid) > 2)
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    ll r2 = 0;
    ll l2 = 1000000000000000000;
    while (l2 - r2 > 1)
    {
        ll mid = (r2 + l2) / 2;
        if (co(mid) >= 2)
        {
            l2 = mid;
        }
        else
        {
            r2 = mid;
        }
    }
    if (r2 + 1 < l - 1)
    {
        cout << r2 + 1 << " " << l - 1 << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}


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

using namespace std;

class DisjointSet {
  public:
    vector<int> rank, p;

    DisjointSet() {}
    DisjointSet(int size) {
      rank.resize(size, 0);
      p.resize(size, 0);
      for( int i = 0; i < size; i++ ) makeSet(i);
    }

    void makeSet(int x) {
      p[x] = x;
      rank[x] = 0;
    }

    bool same(int x, int y) {
      return findSet(x) == findSet(y);
    }

    void unite(int x, int y) {
      link(findSet(x), findSet(y));
    }

    void link(int x, int y) {
      if ( rank[x] > rank[y] ) {
        p[y] = x;
      } else {
        p[x] = y;
        if ( rank [x] == rank[y] )
          rank[y]++;
      }
    }

    int findSet(int x) {
      if ( x != p[x] )
        p[x] = findSet(p[x]);
      return p[x];
    }
};

int main() {
  int n, a, b, q;
  int t;

  cin >> n >> q;
  DisjointSet ds = DisjointSet(n);

  for ( int i = 0; i < q; i++ ) {
    cin >> t >> a >> b;
    if ( t == 0 ) ds.unite(a, b);
    else if ( t == 1 ) {
      if ( ds.same(a, b) ) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3168