akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(){
  int cnt=0;
  string s,alph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  cin >> s;
  if(s[0]!='A'){
    cout << "WA" << endl;
    return 0;
  }
  for(int i=1;i<s.size();i++){
    if(s[i]=='C'){
      if(i<2 or s.size()-2<i){
        cout << "WA" << endl;
        return 0;
      }
      cnt++;
      if(cnt==2){
        cout << "WA" << endl;
        return 0;
      }
    }else{
      for(int j=0;j<alph.size();j++){
        if(s[i]==alph[j]){
          cout << "WA" << endl;
          return 0;
        }
      }
    }
  }
  if(cnt==0){
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;
  // long long a[n],b[n];
  // pair<long long,long long> p[n];
  // for(int i=0;i<n;i++){
  //   cin >> a[i] >> b[i];
  //   tmp=100*(i+1)*a[i];
  //   if(tmp+b[i]>=g){
  //     if(tmp>g){
  //       MIN=min(MIN,(g+100*(i+1)+1)/(100*(i+1)));
  //     }else{
  //       MIN=min(MIN,a[i]);
  //     }
  //   }
  //   p[i]=make_pair((100*(i+1)*a[i]+b[i])/a[i],i);
  // }
  // sort(p,p+n);
  // reverse(p,p+n);
  // while(1){
  //   g-=(p[k].second+1)*100;
  //   a[p[k].second]--;
  //   if(a[p[k].second]==0){
  //     g-=b[p[k].second];
  //     k++;
  //   }
  //   cnt++;
  //   if(g<=0){
  //     break;
  //   }
  // }
  // cout << min(cnt,MIN) << endl;
  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
#include <map>

#include <string.h>
#define inf 0x7fffffff
using namespace std;
//1232
int a,b,c,k,n,m,l[5200][5010],j[100010],o[100200],i,d,dx[10]={0,1,0,-1},dy[10]={1,0,-1,0};
long long x,y,z;
stack<int> s;
struct P
{
    int x;
    int y;
    bool operator<(const P &a)const
    {
        return y>a.y;
    }
};

 map<int, int> p;
queue<P> q;
priority_queue<int> q1;
string r,r1[110];
//char r[2000000],r1[5000000];
vector<P> v[5010];

bool sdf(int a,int b)
{
    if(l[a]!=l[b])
    return l[a]<l[b];
        else
        return l[a+c]<l[b+c];
}

//alohomora
int main()
{
    scanf("%d",&a);
    for(int t=0;t<a;)
        k++,t+=k;
    printf("%d",k);
    return 0;
}

Measured memory_bytes: 384
N = int(input())
a = list(map(int, input().split()))
ans = 0
temp = 0
l = 0
r = 0
while r < N:
  if temp ^ a[r] == temp + a[r]:
    temp += a[r]
    ans += r - l + 1
    r += 1
  else:
    temp -= a[l]
    l += 1
print(ans)

Measured memory_bytes: 26040
#include <iostream>
#include <numeric>
#include <string>
#include <algorithm>
#include <vector>
 
#define repd(i,a,b); for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define ll long long int
 
 
using namespace std;
int main() {
int n,m,x,y; cin >> n >> m >> x >> y;
  int a[n],b[m];
  rep(i,n){
    cin >> a[i];
  }
  rep(j,m){
    cin >> b[j];
  }
    sort(a,a+n);
    sort(b,b+m);
  if(x <= a[n-1] && a[n-1] < b[0] && b[0]<= y){
    cout << "No War";
  } else {
    cout << "War";
  }
 return 0;
}

Measured memory_bytes: 256
h,w,k=map(int,input().split())
mod=10**9+7
F=[1,1,2,3,5,8,13,21,34]
if w==1:
  print(1)
else:
  DP=[[0]*w for _ in range(h+1)]
  DP[0][0]=1
  for i in range(h):
    DP[i+1][0]=(DP[i][0]*F[w-1]+DP[i][1]*F[w-2])%mod
    for j in range(1,w-1):
      DP[i+1][j]=(DP[i][j-1]*F[w-j-1]*F[j-1]+DP[i][j]*F[w-j-1]*F[j]+DP[i][j+1]*F[w-j-2]*F[j])%mod
    DP[i+1][w-1]=(DP[i][w-1]*F[w-1]+DP[i][w-2]*F[w-2])%mod
  print(DP[h][k-1])

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

int main(){
  int n,k;
  cin >> n >> k;
  int a[n];
  for(int i=0;i<n;i++)	cin >> a[i];
  sort(a,a+n);
  int sum=0;
  for(int i=0;i<k;i++)	sum+=a[i];
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;

#define pb push_back
#define mp make_pair

const double PI = acos(-1.0);
const double EPS = 1e-6;
const int INF = 0x3f3f3f3f;

const int MAXN = 200005;

int n, m;
int dp[200][200], dx[] = {0, -1}, dy[] = {-1, 0};

char maps[200][200];


int main() {

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> maps[i][j];

    for (int i = 0; i <= 100; ++i) dp[i][0] = dp[0][i] = INF;

    dp[0][1] = dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
        if (maps[i][j] == '#') {
            dp[i][j] = min(dp[i - 1][j] + (maps[i][j] != maps[i - 1][j]), dp[i][j - 1] + (maps[i][j] != maps[i][j - 1]));

        }
        else {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    /*
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cout << dp[i][j] << " ";
        cout << endl;
    }
    */
    cout << dp[n][m] << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int k = 0;
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++)
    {
        for(int j = i + 1; j < s.size(); j++)
            {
                if(s[i] == s[j])
                k++;
            }
    }
    if(k == 0)
        cout << "yes";
    else
        cout << "no";

    return 0;
}

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

typedef long long LL;

int n;
LL ps[405];
LL memo[405][405];

LL dp(int l, int r){
   if(l==r) return 0LL;
   LL &ret = memo[l][r];
   if(ret!=-1) return ret;
   ret = 1e17;
   for(int i=l;i<r;i++){
      ret = min(ret,dp(l,i)+dp(i+1,r));
   }
   ret += ps[r]-ps[l-1];
   return ret;
}

int main(){
   memset(memo,-1,sizeof(memo));
   scanf("%d",&n);
   for(int i=1;i<=n;i++) scanf("%lld",&ps[i]), ps[i]+=ps[i-1];
   LL ans = dp(1,n);
   printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1536
import numpy as np

N, K = map(int, input().split())

p1 = max(N - K + 1, 0) / N
p2 = 0.
l2K = np.log2(K)
for k in range(1, min(K, N+1)):
    p2 += (0.5) ** np.ceil(l2K - np.log2(k))

print(p1 + p2 / N)

Measured memory_bytes: 12508
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<ll> vec){
    ll n = vec.size();
    rep(i,n) cout << i << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

int main(){
    ll n ; cin >> n;
    ll k = INF; // number of group
    for(int i=2;i<=500;i++){
        if(i * (i-1) == n * 2){
            k = i;
            break;
        }
    }
    if(k!=INF){
        vector<vector<ll>> ans(k,vector<ll>(0));
        ll idx = 1;
        for(int i=0;i<=k-2;i++){
            for(int j=i+1;j<=k-1;j++){
                ans.at(i).emplace_back(idx);
                ans.at(j).emplace_back(idx);
                idx++;
            }
        }
        cout << "Yes" << endl;
        //cout << idx << endl;
        cout << k << endl;
        rep(i,k){
            cout << (ll)(ans.at(i).size()) << " ";
            for(auto j:ans.at(i)) cout << j << " ";
            cout << "\n";
        }
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 5240
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
char a[101][101];
int b[101];
int c[101];

int main() {
  int h,w;
  cin >> h >> w;
  rep(i, h){
    rep(j, w){
      cin >> a[i][j];
    }
  }
  rep(i, h){
    bool f = true;
    rep(j, w) {
      if(a[i][j] == '#') f = false;
    }
    if(f)
      b[i] = 1;
  }
  rep(j, w) {
    bool f = true;
    rep(i, h){
      if(a[i][j] == '#') f = false;
    }
    if(f)
      c[j] = 1;
  }
  rep(i, h){
    bool f =false;
    rep(j, w){
      if(!b[i] && !c[j]){
        cout << a[i][j];
        f = true;
      }
    }
      if(f)
        cout << endl;
  }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

int main() {
	ll n, ans = INF;
	cin >> n;


	for (int i = 1; i <= sqrt(n); ++i) {
		if (n % i == 0) {
			ans = min(ans, i + (n / i) - 2);
		}
	}
	cout << ans << endl;
}


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

int main(){

    int n; cin >> n;    
    //string s; cin >> s;
    int u = 0, d = 0;
    vector<vector<int> > a(2, vector<int> (n));
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
            
            if(i == 1) d += a[i][j];
        }
    }

    u = a[0][0];
    int ans = d + u;
    for(int j = 1; j < n; j++){
        u += a[0][j];
        d -= a[1][j - 1];
        ans = max(ans, d + u);
    }

    cout << ans << endl;

    return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(),greater<int>())
typedef long long ll;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<int> h(n+1),con[n+1];
    rep(i,n)
        cin>>h[i+1];

    rep(i,m)
    {
        int a,b;
        cin>>a>>b;
        con[a].pb(b);
        con[b].pb(a);
    }
    int ans=-1;

    rep(i,n+1)
    {
        if(con[i].size())
        {
          bool ok=true;
          rep(j,con[i].size())
          {
            if(h[i] <= h[ con[i][j] ])
            {
                ok=false;
                break;
            }
          }
          if(ok)
            ans++;
        }
        else
          ans++;
    }

    cout<<ans;

	  return 0;
}


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

#define Bye return 0
#define ll long long
const ll MAX = 1e2;

void solve(){
    for (int i=0; i<3; i++){
        string str; cin>>str;
        printf("%c", toupper(str[0]));
    }
}

int main(){
    solve();
    Bye;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long int
#define pragi(a,b) for(ll i = a;i<b;i++)
#define pragj(a,b) for(ll j = a;j<b;j++)
#define pragk(a,b) for(ll k = a;k>=b;k--)
#define all(v) (v.begin(),v.end())
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define MP make_pair
#define MT make_tuple
#define F first
#define S second
#define KAKA ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int mod = 1e9 + 7;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef long double ld;
typedef pair<int, int> pii;
//typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef pair<ll, ll> pll;

bool predicate(ll x,vector<ll> & ar,ll k)
{
    ll sum = 0;
    ll n = ar.size();
    pragi(0,n)
    {
        ll frac = ar[i]/x;
        if(ar[i] % x) frac++;
        sum += frac;
    }
    sum -= n;
   if(sum <= k) return true;
   else return false;
}
void Compute(ll n,ll k)
{
    KAKA
    vector<ll> ar(n);
    pragi(0,n)
    {
        cin>>ar[i];
    }
    ll mx = *max_element(ar.begin(),ar.end());
    ll lo = 1,hi = mx;
    while(lo < hi)
    {
        ll mid = lo + (hi - lo)/2;
        if(predicate(mid,ar,k)) hi = mid;
        else lo = mid + 1;
    }
    cout<<lo<<"\n";
}
int main()
{
    KAKA
    ll n,k;
    cin>>n>>k;
    Compute(n,k);
}

Measured memory_bytes: 4736
using System;
using static System.Console;

namespace abc175
{
    class Program
    {
        static void Main()
        {
            var s = ReadLine();
            if (s == "RRR")
            {
                WriteLine(3);
            }
            else if (s.Contains("RR"))
            {
                WriteLine(2);
            }
            else if (s.Contains("R"))
            {
                WriteLine(1);
            }
            else
            {
                WriteLine(0);
            }
        }
    }
}


Measured memory_bytes: 25676
#include <bits/stdc++.h>
#define ROOP(i, N) for(int i=0; i<N; i++)
#define RVROOP(i, N) for(int i=N; i>=0; i--)
#define INF 1e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main() {
  string S; cin>>S;
  if(S=="Sunny"){
    cout<<"Cloudy";
  }
  else if(S=="Cloudy"){
    cout<<"Rainy"<<endl;
  }
  else{
    cout<<"Sunny"<<endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//みなさん天才的ですよね

ll num[858200];
const int ma = (1 << 19) - 1;
bool query(ll n) {
	int n2 = (n * 2 & ma) + 1;
	while (num[n2]) {
		if (num[n2] == n + 1) return 1;
		n2 = n2 * 2 % 858101;
	}
	return 0;
}
void add(ll n) {
	int n2 = (n * 2 & ma) + 1;
	while (num[n2]) {
		if (num[n2] == n + 1) {
			return;
		}
		n2 = n2 * 2 % 858101;
	}
	num[n2] = n + 1;
}

int KH[300001], KW[300001];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int H, W, M;
	cin >> H >> W >> M;

	rep(i, M) {
		int h, w;
		cin >> h >> w;

		KH[h]++;
		KW[w]++;
		add(ll(h) * W + w);
	}

	int saidaih = -1;
	int hh[300001], h = 0;
	rep1(i, H) {
		if (saidaih < KH[i]) {
			saidaih = KH[i];
			h = 1;
			hh[0] = i;
		}
		else if (saidaih == KH[i]) {
			hh[h++] = i;
		}
	}
	int saidaiw = -1;
	int ww[300001], w = 0;
	rep1(i, W) {
		if (saidaiw < KW[i]) {
			saidaiw = KW[i];
			w = 1;
			ww[0] = i;
		}
		else if (saidaiw == KW[i]) {
			ww[w++] = i;
		}
	}

	if (ll(h) * w > M) {
		co(saidaih + saidaiw);
		return 0;
	}
	int atta = 0;
	rep(i, h) rep(j, w) {
		if (!query(ll(hh[i]) * W + ww[j])) {
			atta = 1;
			break;
		}
	}

	if (atta) co(saidaih + saidaiw);
	else co(saidaih + saidaiw - 1);

	Would you please return 0;
}

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

int V, E;
ll d[101][101];

bool negative_loop;
void wf() {
    for (int k=0; k<V; ++k) {
        for (int i=0; i<V; ++i) {
            for (int j=0; j<V; ++j) {
                if (d[i][k] != 1e10 and d[k][j] != 1e10) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}

int main() {
    cin >> V >> E;
    fill(d[0], d[101], 1e10);
    rep(i, V) d[i][i] = 0;

    rep(i, E) {
        ll s, t, dist;
        cin >> s >> t >> dist;
        d[s][t] = min(d[s][t], dist);
    }

    wf();

    rep(i, V) {
        if (d[i][i] < 0) negative_loop = true;
    }

    if (negative_loop) {
        puts("NEGATIVE CYCLE");
        return 0;
    }

    rep(i, V) {
        rep(j, V) {
            if (j) cout << " ";
            if (d[i][j] == 1e10) cout << "INF";
            else cout << d[i][j];
        }
        cout << endl;
    }



}



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


int main(){
    
    cout<<setprecision(12);
    
    double N,K,cnt=0.0,n,pt;
    cin>>N>>K;
    
    for(double i = 1.0;i<=N;i+=1.0){
        n=1.0/N;
        pt=i;
        while(pt<K){
            pt*=2;
            n/=2;
        }
        cnt+=n;
    }
    cout<<cnt<<endl;
}




Measured memory_bytes: 256
def divisors(n):
    div = []
    for i in range(1,n+1):
        if n%i == 0:
            div.append(i)
    return div

a,b,n = list(map(int,input().split()))
x = divisors(n)

y = [s for s in x if (s>=a)&(s<=b)]
print(len(y))


Measured memory_bytes: 5604
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	int a, b, c, d, e, f, g, h; cin >> a >> b >> c >> d >> e >> f >> g >> h;
	cout << max(a + b + c + d, e + f + g + h) << endl;
	return 0;
}

Measured memory_bytes: 3116
#include<iostream>
#include<cmath>

using namespace std;

typedef long long ll;


int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin>>n;
	int h[n], dp[n];
	for (int i = 0; i < n; ++i)
	{
		/* code */
		cin>>h[i];
	}
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(int i=2;i<n;i++){
		dp[i]= min((abs(h[i]-h[i-1]) + dp[i-1]) , (abs(h[i]-h[i-2]) + dp[i-2]));
	}
	cout<<dp[n-1]<<'\n';
	return 0;
}

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

using namespace std;

const int maxN = 10000;
const int maxs = 10;

int N;
char s[maxN][maxs + 1];
int c[4];

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

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> s[i];

	int ans = 0;
	for (int i = 0; i < N; i++) {
		int l = strlen(s[i]);
		for (int j = 0; j + 2 <= l; j++) {
			if (s[i][j] == 'A' && s[i][j + 1] == 'B')
				ans++;
		}
		int x = 0;
		if (s[i][0] == 'B')
			x |= 1;
		if (s[i][l - 1] == 'A')
			x |= 2;
		c[x]++;
	}
	
	int z = max(0, min(c[1], c[2]) - 1);
	ans += z;
	c[1] -= z;
	c[2] -= z;

	c[1] = min(c[1], 1);
	c[2] = min(c[2], 1);

	ans += max(0, accumulate(c + 1, c + 4, -1));

	cout << ans << '\n';

	return 0;
}


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

int main(){
  int n, a, b;
  cin >> n;
  vector<int> root(n+1, -1);
  vector<vector<int>> child(n+1);
  vector<int> childofedge (n-1, -1);
  vector<int> color(n+1, -1);
  color.at(1) = 0;
  for (int i = 0; i < n-1; i++){
    cin >> a >> b;
    root.at(b) = a;
    child.at(a).push_back(b);
    childofedge.at(i) = b;
  }
  queue<int> paint;
  paint.push(1);
  
  int now;
  int nowcolor;
  int maxcolor = 1;
  while(!paint.empty()){
    now = paint.front();
    paint.pop();
    nowcolor = 0;
    for(int i : child.at(now)) {
      paint.push(i);
      nowcolor++;
      if (nowcolor == color.at(now)) nowcolor++;
      color.at(i) = nowcolor;
      maxcolor = max(maxcolor, nowcolor);
    }
  }
  
  cout << maxcolor << endl;
  for (int i : childofedge){
    cout << color.at(i) << endl;
  }
}
      
    
    

Measured memory_bytes: 5632
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <math.h>
#include <map>
#define ll long long 
#define PI 3.14159265358979323846
#define INF 10000000000
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;

int main() {
	ll L, R, d, con = 0;
	cin >> L >> R >> d;
	for (ll i = L; i <= R; i++) {
		if (i % d == 0) con++;
	}
	cout << con << endl;
	return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
  
#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed(x) fixed<<setprecision(x)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline lol abs(A &a) { return (a < 0 ? -a : a); }
bool inLine(int x,int y,int mx,int my){return (x>=0&&y>=0&&x<mx&&y<my);}
const lol inf=(1LL<<62);
const lol MOD=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
lol n,m,k,r;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >>n;
  vector<lol> ans(n+10);
  for(int x=1;x<=n;x++){
    lol sum=x*x;
    for(int y=1;y<=n;y++){
      lol sum1=sum+y*y+x*y;
      for(int z=1;z<=n;z++){
        lol sum2=sum1+z*z+x*z+y*z;
        if(sum2>n){ 
          break;
        }
        ans[sum2]++;
      }
    }
  }
  for(int i=1;i<=n;i++) cout <<ans[i]<<'\n';

  return(0);
}

Measured memory_bytes: 3652
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    S=readline().strip()
    T=readline().strip()
    for i in range(len(S)):
        if S[i]!=T[i]:
            print("No")
            break
    else:
        print("Yes")
if __name__=="__main__":
    main()

Measured memory_bytes: 9048
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import fractions
from functools import reduce
from operator import mul
import bisect
import sys
import logging
import heapq
import itertools

#logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)


def main():
	n = int(input())
	s = defaultdict(set)
	for _ in range(n):
		t = input()
		if(t[0] in ['M','A','R','C','H']):
			s[t[0]].add(t)
	s = list(s.values())
	ans = 0
	for i in itertools.permutations(s,3):
		ans += len(i[0]) * len(i[1]) * len(i[2])
	print(ans//6)

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if temp%i==0:
			cnt=0
			while temp%i==0:
				cnt+=1
				temp //= i
			arr.append([i, cnt])

	if temp!=1:
		arr.append([temp, 1])

	if arr==[]:
		arr.append([n, 1])

	return arr

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)

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

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

class PriorityQueue():
	def __init__(self):
		self.queue = []
	def push(self,i):
		heapq.heappush(self.queue,-i)
	def pop(self):
		return -1 * heapq.heappop(self.queue)
	def sum(self):
		return -sum(self.queue)

main()


Measured memory_bytes: 79700
#include <bits/stdc++.h>
using namespace std;
int a[100];
int main(){
	int n;
	scanf("%d",&n);
	int cnt=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=i) cnt++;
	}
	if(cnt<=2){
		printf("YES\n");
	}
	else{
		printf("NO\n");
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    char N[50][50], M[50][50];
    cin>>n>>m;
    for(int i=0; i<n;i++){
        for(int j=0; j<n; j++){
            cin>>N[i][j];
        }
    }
    for(int i=0; i<m;i++){
        for(int j=0; j<m; j++){
            cin>>M[i][j];
        }
    }
    for(int i=0; i<n-m+1; i++){
        for(int j=0; j<n-m+1; j++){
            bool ok=true;
            for(int k=i; k<i+m;k++){
                for(int l=j; l<j+m; l++){
                    if(N[k][l]!=M[k-i][l-j]){ok=false; break;}
                }
            }
            if(ok==true){cout<<"Yes"; return 0;}
        }
    }
    cout<<"No";
    return 0;
}

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

using namespace std;

struct node
{
    int to,len;
    node(){}
    node(int t,int l):to(t),len(l){}
};
int pos[100010];
bool vis[100010];
vector<node>edge[100010];
bool flag;

void dfs(int u,int r)
{
    vis[u]=1;
    for (auto v:edge[u])
    {
        if (!vis[v.to]) 
        {
            pos[v.to]=pos[u]+v.len;
            dfs(v.to,u);
            if (!flag) return;
            continue;
        }
        else if (pos[v.to]==pos[u]+v.len) continue;
        flag=false;
        return;
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) edge[i].clear();
    memset(pos,0,sizeof(pos));
    memset(vis,0,sizeof(vis));
    int x,y,z;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        edge[x].push_back(node(y,z));
        edge[y].push_back(node(x,-z));
    }
    flag=true;
    for (int i=1;i<=n;i++)
    {
        if (!vis[i]) dfs(i,0);
        if (!flag) break;
    }
    if (!flag) printf("No\n");
    else printf("Yes\n");
}

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

int main() {
    int64_t X;
    cin >> X;
    int64_t use500 = X / 500;
    int64_t remainX = X % 500;
    int64_t use5 = remainX / 5;
    int64_t joinous = use500 * 1000 + use5 * 5;

    cout << joinous << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  string s, t;
  cin >> s >> t;

  int N = s.size();
  int M = t.size();

  RREP(i, N-M+1){
    bool flag = true;
    REP(j, M){
      if(s[i+j] == '?') continue;
      if(s[i+j] != t[j]) flag = false;
    }
    if(!flag) continue;
    REP(j, M){
      s[i+j] = t[j];
    }
    REP(j, N) if(s[j] == '?') s[j] = 'a';
    cout << s << "\n";
    return 0;
  }

  cout << "UNRESTORABLE" << "\n";


  return 0;
}

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

using namespace std;

// 最小全域有向木(Edmonds' algorithm) O(VE)
// (強連結成分分解が必要)
// (グラフが壊されることに注意)
// Verified: AOJ 2309, UVA 11183
//
// 注意: 強連結成分分解を重み付きversionに書き換える必要あり．
const int INF = 1000000000;
struct Edge{
    int src, dst, cost;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;
int scc(const Graph& G, const Graph& RG, vector<int>& cmp) {
    int n = G.size();
    int K = 0; // the number of components

    cmp.assign(n, -1); // cmp[v] := component id of vertex v (0, 1, ..., K-1)
    vector<bool> used(n);
    vector<int> order;

    // ordinary dfs
    function<void(int)> dfs = [&](int u) {
        used[u] = true;
        for(Edge e : G[u]) if(!used[e.dst]) {
            dfs(e.dst);
        }
        order.push_back(u);
    };
    for(int u = 0; u < n; u++) if(!used[u]) {
        dfs(u);
    }
    reverse(order.begin(), order.end());

    // reverse dfs
    function<void(int)> rdfs = [&](int u) {
        cmp[u] = K;
        for(Edge e : RG[u]) if(cmp[e.dst] == -1) {
            rdfs(e.dst);
        }
    };
    for(int u : order) if(cmp[u] == -1) {
        rdfs(u);
        K++;
    }

    return K;
}
int MOB(Graph& G, int root){
    int V = G.size();
    int res = 0;

    // 各ノードに入る最小の辺を求める
    vector<Edge> min_edge(V, {-1, -1, INF});
    REP(v, V) REP(i, G[v].size()){
        Edge& e = G[v][i];
        if(min_edge[e.dst].cost > e.cost){
            min_edge[e.dst] = e;
        }
    }

    // コストを足し合わせる
    REP(v, V) if(v != root) {
        if(min_edge[v].cost == INF) return INF; // rootから到達不可能な頂点が存在する
        res += min_edge[v].cost;
    }

    // 各辺のコストを、最小のコスト分だけ減らす
    REP(v, V) REP(i, G[v].size()){
        Edge& e = G[v][i];
        if(e.dst != root) e.cost -= min_edge[e.dst].cost;
    }

    // 強連結成分分解で、ループがあるかどうか調べる
    Graph sG(V);
    Graph sGR(V);
    REP(v, V) if(v != root) {
        Edge& e = min_edge[v];
        sG[e.src].push_back(e);
        sGR[e.dst].push_back({e.dst, e.src, e.cost});
    }
    vector<int> comp;
    int m = scc(sG, sGR, comp); // 強連結成分分解
    if(m == V) return res; // ループがなければ終了

    // 成分の間に辺を張った新しいグラフを作る
    Graph nG(m);
    REP(v, V) REP(i, G[v].size()){
        Edge& e = G[v][i];
        if(comp[v] != comp[e.dst]) nG[comp[v]].push_back({comp[v], comp[e.dst], e.cost});
    }
    return min(INF, res + MOB(nG, comp[root]));
}

int main(){
    int N;
    while(cin >> N && N > 0){
        Graph G(N + 1);
        REP(i, N) REP(j, N + 1) {
            int t;
            cin >> t;
            if(j != i + 1) G[j].push_back({j, i + 1, t});
            //cout << j << " " << i + 1 << " " << t << endl;
        }
        cout << MOB(G, 0) << endl;
    }
    return 0;
}

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

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

  int odd_cnt = 0;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a % 2 != 0) odd_cnt++;
  }

  if (odd_cnt % 2 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    int n = readint;
    int a = readint;
    writeln(n * n - a);
}


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

string copy_string(string s, int first, int end){
  
  string s_copied;
  
  for(int i=first-1;i<end;i++){
    s_copied += s.at(i);
  }
  
  return s_copied;
}

bool is_kaibun(string s){
  
  string reverse_s = s;
  reverse(reverse_s.begin(), reverse_s.end());
  
  if(s==reverse_s){
    return true;
  }else{
    return false;
  }
}
 
int main() {
  
  string S;
  bool kaibun = false;
  
  cin >> S;
  
  kaibun = is_kaibun(S);
  if(!kaibun){
    cout << "No" << endl;
    return 0;
  }
  
  string s1 = copy_string(S, 1, (S.size() -1)/2);
  kaibun = is_kaibun(s1);
  if(!kaibun){
    cout << "No" << endl;
    return 0;
  }
  
  string s2 = copy_string(S, (S.size() +3)/2, S.size());
  kaibun = is_kaibun(s2);
  if(!kaibun){
    cout << "No" << endl;
    return 0;
  }
  
  cout << "Yes" << endl;
}

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

int32_t main() {
  long long int n;
  scanf("%lld", &n);
 // n--;

  std::vector<long long int> ans;

 // if (!n) {
 //   ans.push_back(0);
 // }

  while (n) {
    long long div = n / 26LL;
    long long rem = n % 26LL;

    if (rem == 0) {
      rem = 26;
      div = (n / 26LL) - 1LL;
    }

    ans.push_back(rem);
    n = div;
  }

  std::reverse(ans.begin(), ans.end());

  for (const long long int &d : ans) {
    printf("%c", 'a' + d - 1);
  }

  puts("");

  return 0;
}


Measured memory_bytes: 3700
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
uf = UnionFind(n)
edges=[]
for i in range(m):
  edges.append(list(map(int,input().split())))
current=(n*(n-1))//2
ans=[current]
for i in range(m-1):
  u=edges[m-1-i][0]-1
  v=edges[m-1-i][1]-1
  if uf.same(u,v)==1:
    ans.append(current)
  else:
    size1=uf.size(u)
    size2=uf.size(v)
    current-=size1*size2
    ans.append(current)
    uf.union(u,v)
ans.reverse()
for i in ans:
  print(i)

Measured memory_bytes: 111192
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int NumStr(string str)
{
	int n = str.size();
	int sum = 0;
	for(int i=0; i<n; i++){
		if(str[i] == 'A')sum += pow(4.,i) * 1;
		else if(str[i] == 'C')sum += pow(4.,i) * 2;
		else if(str[i] == 'G')sum += pow(4.,i) * 3;
		else if(str[i] == 'T')sum += pow(4.,i) * 4;
	}
	return sum;
}

void InsertFlag(vector<bool> &flag, string str)
{
	int num_str = NumStr(str);
	flag[num_str] = true;
}
void FindFlag(vector<bool> &flag, string str)
{
	int num_str = NumStr(str);
	if(flag[num_str] == true)cout << "yes" << endl;
	else if(flag[num_str] == false)cout << "no" << endl;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	vector<bool> flag;
	flag.resize(16777216);
	
	for(int i=0; i<n; i++){
		string command, str;
		cin >> command >> str;
		if(command == "insert")InsertFlag(flag, str);
		else if(command == "find")FindFlag(flag, str);
	}
}

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

int main(){
    int n,i;
    long long pop;
    cin>> n;
    queue<long long> q;
    for(i=1;i<10;i++){
        q.push(i);
    }
    for(i=0;i<n-1;i++){
        pop = q.front();
        if(pop%10!=0) q.push(pop*10 + pop%10 -1);
        q.push(pop*10+pop%10);
        if(pop%10 != 9) q.push(pop*10 + pop%10 + 1);
        q.pop();
    }
    cout<< q.front()<<endl;
}

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

using namespace std;

#define int unsigned long long

signed main()
{
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);

	//freopen("output", "w", stdout);

	int n;
	cin >> n;
	vector<pair<int, int>> vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i].second >> vec[i].first;
	sort(vec.begin(), vec.end());
	int cur = 0;
	for (int i = 0; i < n; i++)
	{
		cur += vec[i].second;
		if (cur > vec[i].first)
		{
			cout << "No\n";
			exit(0);
		}
	}

	cout << "Yes\n";

	return 0;
}


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

const int mod = 1e9 + 7;
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	long long  ans = 0;
	for (int i = k; i <= n; i++)
		ans += 1LL * (n - i + 1 + n)*i / 2 - 1LL * (i - 1)*i / 2 +1;
	ans++;
	ans %= mod;
	printf("%lld\n", ans);
}
//int

Measured memory_bytes: 3836
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> nodes(n);
    vector<pair<int, int>> degree(n);
    map<pair<int, int>, int> edges;
    vector<int> color(n - 1, -1);
    for (int i = 0; i < n; i++) {
        degree[i] = {0, i};
    }
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        nodes[a - 1].push_back(b - 1);
        nodes[b - 1].push_back(a - 1);
        degree[a - 1].first++;
        degree[b - 1].first++;
        edges[{a - 1, b - 1}] = i;
        edges[{b - 1, a - 1}] = i;
    }
    sort(degree.begin(), degree.end(), greater<pair<int, int>>());
    int k = degree[0].first;
    queue<pair<int, int>> q;
    q.push({k + 1, 0});
    while (!q.empty()) {
        int prev_color = q.front().first;
        int from = q.front().second;
        q.pop();
        int cnt = 0;
        for (int i = 0; i < nodes[from].size(); i++) {
            int to = nodes[from][i];
            int edge = edges[{from, to}];
            if (color[edge] == -1) {
                cnt++;
                color[edge] = cnt;
                if (color[edge] >= prev_color) {
                    color[edge]++;
                }
                q.push({color[edge], to});
            }
        }
    }
    cout << k << endl;
    for (int i = 0; i < n - 1; i++) {
        cout << color[i] << endl;
    }
}


Measured memory_bytes: 16640
x, y = map(int, input().split())
if (x + y) % 3 != 0:
    print(0)
else:
    n = (x+y) // 3
    nx = x - n
    ny = y - n
    if (nx < 0 ) or (ny < 0):
        print(0)
    else:
        mod = 10 **9 +7
        fac = [1] * 1000000
        for i in range(1,n+1):
            fac[i] = fac[i-1] * i % mod
        print(fac[n] * pow(fac[nx], mod-2, mod) * pow(fac[ny], mod-2, mod) % mod)

Measured memory_bytes: 31988
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<i64>();
    let (n, k) = (v[0] as usize, v[1]);
    let a = read_vec::<i64>().iter().map(|&x| x - 1).collect::<Vec<_>>();

    let mut s = vec![0; n + 1];
    for i in 0..n {
        s[i + 1] = (s[i] + a[i]) % k;
    }
    let mut count = HashMap::new();
    let mut ans = 0i64;
    let mut que = VecDeque::new();
    for i in 0..n + 1 {
        count.entry(s[i]).or_insert(0);
        ans += count[&s[i]];
        *count.entry(s[i]).or_insert(0) += 1;
        que.push_back(&s[i]);
        if que.len() as i64 >= k {
            let out = que.pop_front().unwrap();
            *count.get_mut(&out).unwrap() -= 1;
        }
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 19920
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int n = Integer.parseInt(str[0]);
    int d = Integer.parseInt(str[1]);
    int[][] x = new int[n][d];
    int count = 0;
    for(int i = 0; i < n; i++) {
        str = in.readLine().split(" ");
      for(int j = 0; j < d ; j++) {
        x[i][j] = Integer.parseInt(str[j]);
      }
    }
    for(int i = 1; i < n; i++) {
      for(int j = 0; j < i; j++) {
        long c=0;
        for(int k = 0; k < d; k++) {
          c += Math.abs(x[i][k]-x[j][k]) * Math.abs(x[i][k]-x[j][k]);
        }
        if(Math.sqrt(c) % 1==0){
          count++;
        }
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 25172
#include<stdio.h>
#include<stdlib.h>
typedef struct{
  int p; //parent element
  int l,r;    //child elements
}node;
void Preorder(int);
void Inorder(int);
void Postorder(int);
node *T;
int main(){
  int n, i, x, root;
  scanf("%d",&n);
  T = (node *)malloc(sizeof(node) * n);
  for(i=0; i<n; i++) T[i].p = -1;
  for(i=0; i<n; i++){
    scanf("%d",&x);
    scanf("%d%d",&T[x].l,&T[x].r);
    T[T[x].l].p = T[T[x].r].p = x;
  }
  for(i=0; i<n; i++){     //root search
    if(T[i].p == -1){
      root = i;
      break;
    }
  }
  printf("Preorder\n");
  Preorder(root);
  printf("\nInorder\n");
  Inorder(root);
  printf("\nPostorder\n");
  Postorder(root);
  printf("\n");
  free(T);
  return 0;
}

void Preorder(int x){
  if(x != -1){
    printf(" %d",x);
    Preorder(T[x].l);
    Preorder(T[x].r);
  }
  return;
}

void Inorder(int x){
  if(x != -1){
    Inorder(T[x].l);
    printf(" %d",x);
    Inorder(T[x].r);
  }
  return;
}

void Postorder(int x){
  if(x != -1){
    Postorder(T[x].l);
    Postorder(T[x].r);
    printf(" %d",x);
  }
  return;
}

Measured memory_bytes: 616
#include <cstdio>
#include <iostream>
const int N=2e5+5;
char s[N];
int f[N],g[N];
int main() {
    int n,k,c;
    scanf("%d%d%d%s",&n,&k,&c,s+1);
    f[0]=0;c++;
    for(int i=1;i<=n;i++) {
        if(s[i]=='x') f[i]=f[i-1];
        else f[i]=std::max(f[i-1],1+(i-c>=0?f[i-c]:0));
    }
    g[n+1]=0;
    for(int i=n;i;i--) {
        if(s[i]=='x') g[i]=g[i+1];
        else g[i]=std::max(g[i+1],1+(i+c<=n+1?g[i+c]:0));
    }
    int cnt=0;
    c=std::max(2,c);
    auto getVal=[&](int pos) {
        int res=0;
        if(pos<=n+1) res+=g[pos];
        if(pos-c>=0) res+=f[pos-c];
        return res;
    };
    for(int j=1;j-c<1;j++) if(getVal(j)>=k) cnt++;
    for(int i=1;i<=n;i++) {
        if(getVal(i)>=k) --cnt; 
        if(cnt==0&&s[i]=='o') printf("%d\n",i);
        if(getVal(i+c)>=k) ++cnt; 
    }
    return 0;
}

Measured memory_bytes: 3200
"""
keywords: 最大公約数、ユークリッドの互除法
"""
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def main():
    n = II()
    a_lst = MII()
    print(reduce(gcd, a_lst))

if __name__ == '__main__':
    main()


Measured memory_bytes: 14596
#include<stdio.h>


int main()
{
		int h,w;
		int i,j,k;
		int check = 1;
		while(check){

				scanf("%d %d",&h,&w);

				if( h==0 && w == 0){
						check = 0;
				}else{
						for(j=0;j<w;j++)
								printf("#");
						printf("\n");

						for(i=1;i<h-1;i++){
								printf("#");
								for(j=1;j<w-1;j++){
										printf(".");
								}
								printf("#\n");
						}

						for(j=0;j<w;j++)
								printf("#");
						printf("\n\n");

				}
		}


		return 0;
				
}


Measured memory_bytes: 2100
S = input()
ans = "No"
if S[0] == S[1]:
    if S[2] == S[3]:
        ans = "Yes"
else:
    if S[0] == S[2]:
        if S[1] == S[3]:
            ans = "Yes"
    else:
        if S[0] == S[3]:
            if S[1] == S[2]:
               ans = "Yes" 
if S[0] == S[1] and S[1] == S[2] and S[2] == S[3]:
	ans = "No"
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<atcoder/modint>
#include<atcoder/lazysegtree>

using namespace std;
using ll = long long;
using mint = atcoder::modint998244353; 
istream &operator>>(std::istream &is, mint &a){ll x;is >> x;a = mint(x);return (is);}
constexpr int LEN = 1e6;
vector<mint> ten(LEN), one(LEN);

struct S {
	mint val;
	int len;
};
using F = int;

S op(S l, S r) {return S{l.val * ten[r.len] + r.val, l.len + r.len} ;}
S e() {return S{0, 0}; }
F id() {return 0;}
S mapping(F f, S x) {
	if(f != id())return {one[x.len] * f, x.len};
	return x;
}
F composition(F l, F r) {return (l == id() ? r : l);}


int main()
{
	int N, Q;
	ten[0] = 1, one[0] = 0;
	for(int i = 1; i < LEN; i++) {
		ten[i] = ten[i - 1] * 10, one[i] = one[i - 1] * 10 + 1;
	}

	cin >> N >> Q;
	vector<S> v(N, {1, 1});
	atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> tree(v);

	for(int i = 0;i < Q; i++) {
		int l, r, x; cin >> l >> r >> x;
		tree.apply(l - 1, r, x);
		cout << tree.all_prod().val.val() << endl;
	}

}

Measured memory_bytes: 17784
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int N = in.nextInt();
			int M = in.nextInt();
			int[] X = new int[M];
			for(int i = 0; i < M; i++) {
				X[i] = in.nextInt();
			}
			Arrays.sort(X);
			Integer[] dif = new Integer[M - 1];
			for(int i = 1; i < M; i++) {
				dif[i - 1] = X[i] - X[i - 1];
			}
			Arrays.sort(dif);
			int total = 0;
			for(int i = 0; i < M - N; i++) {
				total += dif[i];
			}
			out.println(total);
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}


Measured memory_bytes: 35216
s = input()
t = input()


u = s + s

flag = False
j = 0

for i in range(len(u)):
    if u[i] == t[j]:
        j += 1
        if j == len(t):
            flag = True
            break
    else:
        j = 0

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 8996