akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
int t[MAXN*16][2],hd[MAXN*16],ver[MAXN*24],nx[MAXN*24],pos[MAXN*8][2],vis[MAXN*16];
int ra,rb,tot,eg,op,x,y,u,v,n,m,s;
ll edge[MAXN*24],dis[MAXN*16],w;
priority_queue < pair<ll,int> > q;
void add_edge (int x,int y,ll z) {
	ver[++eg]=y;
	nx[eg]=hd[x],edge[eg]=z;
	hd[x]=eg;
	return;
}
int buildt (int l,int r,int op) {
	int cur=++tot;
	if (l==r) {pos[l][op]=cur;return cur;}
	int mid=(l+r)>>1;
	t[cur][0]=buildt(l,mid,op),t[cur][1]=buildt(mid+1,r,op);
	if (!op) {add_edge(t[cur][0],cur,0),add_edge(t[cur][1],cur,0);}
	else {add_edge(cur,t[cur][0],0),add_edge(cur,t[cur][1],0);}
	return cur;
}
void init (int p1,int p2,int l,int r) {
	if (l==r) {add_edge(p2,p1,0);return;}
	int mid=(l+r)>>1;
	init(t[p1][0],t[p2][0],l,mid),init(t[p1][1],t[p2][1],mid+1,r);
	return;
}
void addin (int l,int r,int p,int xl,int xr,int s,ll w) {
	if (xr<l||r<xl) {return;}
	if (xl<=l&&r<=xr) {add_edge(p,s,w);return;}
	int mid=(l+r)>>1;
	addin(l,mid,t[p][0],xl,xr,s,w);
	addin(mid+1,r,t[p][1],xl,xr,s,w);
	return;
}
void addout (int l,int r,int p,int s,int xl,int xr,ll w) {
	if (xr<l||r<xl) {return;}
	if (xl<=l&&r<=xr) {add_edge(s,p,w);return;}
	int mid=(l+r)>>1;
	addout(l,mid,t[p][0],s,xl,xr,w);
	addout(mid+1,r,t[p][1],s,xl,xr,w);
	return;
}
void add (int l1,int r1,int l2,int r2,ll w) {
	int pos1=tot+1,pos2=tot+2;
	tot+=2;
	addin(1,n,ra,l1,r1,pos1,0);
	add_edge(pos1,pos2,w);
	addout(1,n,rb,pos2,l2,r2,0);
	return;
}
void dijkstra (int x) {
	q.push(make_pair(0,x));
	dis[x]=0;
	while (!q.empty()) {
		pair<ll,int> a=q.top();
		q.pop();
		if (vis[a.second]) {continue;}
		vis[a.second]=1;
		for (int i=hd[a.second];i;i=nx[i]) {
			if (dis[ver[i]]>dis[a.second]+edge[i]) {
				dis[ver[i]]=dis[a.second]+edge[i];
				q.push(make_pair(a.first-edge[i],ver[i]));
			}
		}
	}
	return;
}
int main () {
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d",&n,&m);
	s=1;
	ra=buildt(1,n,0),rb=buildt(1,n,1);
	init(ra,rb,1,n);
	for (int i=1;i<=m;i++) {
		scanf("%d%d%lld",&x,&y,&w);
		add(x,y,x,y,w);
	}
	dijkstra(pos[s][0]);
	printf("%lld\n",dis[pos[n][1]]>1e17?-1:dis[pos[n][1]]);
	return 0;
}

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

using namespace std;
#define fori(n) for(int i=0;i<n;i++)
#define ll long long

int main()
{
    //freopen("dulieu","r",stdin);
    int n,m,x;
    ll kq=1,mod=1000000007;
    int sc=0,sh=0;
    bool ax,bx;
    cin>>n>>m;
    set<int> A,B;
    fori(n)
    {
        cin >> x;
        A.insert(x);
    }
    fori(m)
    {
        cin >> x;
        B.insert(x);
    }
    int sl=0;
    for (int x=n*m; x>0; x--)
    {
        ax=A.count(x)>0;
        bx=B.count(x)>0;
        if(ax)sh++;
        if(bx)sc++;
        if(ax)
        {
            if(!bx) kq=kq*sc % mod;
        }
        else
        {
            if (bx) kq=kq*sh % mod;
            else kq=kq*(sc*sh-sl) % mod;
        }
        sl++;
        //if (sl>10) break; cout <<x<<" "<< kq<<endl;
    }
    cout << kq;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
// ミント
const int mod = 1e9+7 ;
//998244353;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
//昆布
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}   ;
 
mint modpow(ll a,ll b){
 if(b==0) return 1 ;
 mint c= modpow(a,b/2) ;
 if(b%2==1) return c*c*a ;
 else return c*c ;
}

int main(){
  ll n ;cin>> n ;
 vector<ll> A(n) ; rep(i,n) cin>>A[i] ;
 mint ans= 0 ;
 rep(i,60){
   ll k= 0 ;
   rep(j,n){
     if(A[j]>>i&1) k++ ;
   }
  mint dk= (n-k)*k ;
  mint pl= dk*modpow(2,i) ;
  ans+= pl ;
 }
    cout<<ans<<endl ;
       return 0;
  }
   

Measured memory_bytes: 5608
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

int H, W;
char m[50][50];
int dist[50][50];

int main() {
  cin >> H >> W;
  rep(i, H) {
    rep(j, W) {
      cin >> m[i][j];
    }
  }

  queue<pair<int, int>> que;
  que.push(make_pair(0, 0));

  dist[0][0] = 1;

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

  while(que.size()) {
    pair<int, int> p = que.front();
    que.pop();
    int x = p.first;
    int y = p.second;
    if(x == H-1 && y == W-1) break;

    for(int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(0 <= nx && nx < H && 0 <= ny && ny < W && dist[nx][ny] == 0 && m[nx][ny] == '.') {
        dist[nx][ny] = dist[x][y] + 1;
        que.push(make_pair(nx, ny));
      }
    }
  }

  int black;

  rep(i, H) {
    rep(j, W) {
      if(m[i][j] == '#') {
        black++;
      }
    }
  }
  

  if(dist[H-1][W-1] != 0) {
    int ans = H * W - dist[H-1][W-1] - black;
    cout << ans << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#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>;


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

  vector<int> A(N);
  rep(i, N) cin >> A[i];

  vector<int> D(N);
  rep(i, N - 1) D[i] = A[i + 1] - A[i];
  D[N - 1] = K + A[0] - A[N - 1];

  int maxl = 0;
  rep(i, N) maxl = max(maxl, D[i]);
  
  cout << K - maxl << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

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

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


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する


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

    vector<int> v(3);
    cin >> v[0] >> v[1] >> v[2];
    int k;
    cin >> k;

    sort(all(v));
    rep(i,0,k){
        v[2] <<= 1;
    }
    cout << v[0] + v[1] + v[2] << endl;

    return 0;
}


Measured memory_bytes: 888
N = int(input())
l = [int(input())-1 for _ in range(0,N)]

i = 0;
flg = False

for n in range(0,N):
  if l[i] == 1 :
    print(n+1)
    flg = True
    break
  else:
    i = l[i]


if not flg:
  print("-1")

Measured memory_bytes: 12948
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int  n, k;
	string s;
	cin >> n >> k;
	cin >> s;

	s[k - 1] -= 'A';
	s[k - 1] += 'a';
	cout << s << '\n';
	return 0;
}

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

typedef long long ll;
const int maxn = 1e6+10;
const int mod = 1e9+7;

int a[maxn];

int n;

int prime[maxn/10];
bool vis[maxn];
int cnt = 0;

bool book[maxn];
bool flag  = 0;
void Init(){
	for(int i = 2; i <= maxn ; i++){
		if(vis[i]==0){
			prime[cnt++] = i;
			for(int j = i+i; j <= maxn; j += i){
				vis[j] = 1;
			}
		}
	}
}
void getFactor(int x){
	for(int i = 0; i < cnt&&prime[i]*prime[i]<=x; i++){
		if(x%prime[i]==0){
			if(book[prime[i]]==0) book[prime[i]] = 1;
			else{
				flag = 1;
				return ;
			}
			while(x%prime[i]==0) x /= prime[i];
		}
	}
	if(x>1){
		if(book[x]==0) book[x] = 1;
		else{
			flag = 1;
			return ;
		}
	}
}
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(void){
	Init();
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ans = gcd(ans,a[i]);
		getFactor(a[i]); 
	}
	if(flag==0){
		cout<<"pairwise coprime"<<endl;
	}
	else{
		if(ans>=2){
			cout<<"not coprime"<<endl;
		}else cout<<"setwise coprime"<<endl;
	}
	return 0;
}



Measured memory_bytes: 9536
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;


int main(){
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());
    int N;
    cin >> N;
    vector <ll> H(N);

    REP(i,N)
    {
      cin >> H[i];
    }
    int iMax = 0;
    int cnt = 0;
    ll ima = H[0];
    for(int i = 1; i < N; ++i)
    {
      if(ima >= H[i])
      {
        ++cnt;
      }
      else
      {
        iMax = max(iMax, cnt);
        cnt = 0;
      }
      ima = H[i];
    }

    iMax = max(iMax, cnt);
    cout << iMax << endl;

    return 0;    

}



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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void MAIN() {
  int n; cin >> n;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int t; cin >> t;
    if (t % 2 && i % 2) ans++;
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define R register int 
#define ll long long
#define inf 2147483647
using namespace std;
const int N=500000;
int gi(){
    R x=0,k=1;char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
	if(c=='-')k=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*k;
}
int main(){
	int n;
	cin>>n;
	if(n==1)cout<<"Hello World";
	else {
		int a,b;
		cin>>a>>b;
		cout<<a+b;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
using namespace std;
 
signed main() {
  int N;
  cin >> N;
  
  vector<int> A(N);
  for( int i = 0; i < N; i++ ) cin >> A.at(i);
  sort(A.begin(), A.end());
  
  vector<int> sum(N+1, 0);
  for( int i = 0; i < N; i++ ) sum.at(i+1) = sum.at(i) + A.at(i);
  
  int ans = 0;
  for( int i = 0; i < N; i++ ){
    if( sum.at(i)*2 >= A.at(i) ) ans++;
    else ans = 0;
  }
  
  
  cout << ans+1 << endl;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string p;
  cin>>p;
  if(p=="MON")
  cout<<"6";
  else if(p=="TUE")
  cout<<"5";
  else if(p=="WED")
  cout<<"4";
  else if(p=="THU")
  cout<<"3";
  else if(p=="FRI")
  cout<<"2";
  else if(p=="SAT")
  cout<<"1";
  else cout<<"7";
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  rep(i, n) a[i] -= i+1;
  sort(all(a));

  ll b = a[n/2];

  ll ans = 0;
  rep(i, n) ans += abs(a[i] - b);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1920
from itertools import product, combinations

# 入力
N = int(input())
D = list(map(int, input().split()))

# N >= 24 ならば鳩の巣原理より、max(s)=0である
# N <= 23 ならば全探索で解を求める
ans = (
    0 if N >= 24 else
    int(
        (0 not in D) and
        (D.count(12) <= 1) and
        all(
            D.count(i) <= 2
            for i in range(1, 12)
        )
    ) if 12 <= N < 24 else
    max(
        min(
            min(abs(a - b), 24 - abs(a - b))
            for a, b in combinations(t, 2)
        )
        for t in (
            product(
                (0,),
                *(
                    (d, 24 - d)
                    for d in D
                )
            )
        )
    )
)

# 出力
print(ans)


Measured memory_bytes: 3064
from math import gcd
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k=II()
    ans=0
    for a in range(1,k+1):
        for b in range(1,k+1):
            g=gcd(a,b)
            for c in range(1,k+1):
                ans+=gcd(g,c)
    print(ans)

main()

Measured memory_bytes: 9216
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class Main {

	private static List<long[]>[] g;
	private static long[] cost;

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		g = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			g[i] = new ArrayList<>();
		}

		for (int i = 0; i < N - 1; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			long c = sc.nextLong();
			g[a].add(new long[]{b, c});
			g[b].add(new long[]{a, c});
		}

		int Q = sc.nextInt();
		int K = sc.nextInt() - 1;

		cost = new long[N];
		Arrays.fill(cost, Long.MAX_VALUE);
		dfs(K, -1, 0);

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			sb.append(cost[x] + cost[y]).append("\n");
		}

		System.out.print(sb.toString());
	}

	private static void dfs(int v, int from, long c) {
		cost[v] = c;
		for (long[] i : g[v]) {
			if (i[0] == from) continue;
			if (cost[(int) i[0]] != Long.MAX_VALUE) continue;
			dfs((int) i[0], v, c + i[1]);
		}
	}
}


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

int main(){
    int n,l,ans=0,t=0;
    cin >> n >> l;
    for (int i=0;i<n;i++){
        ans+=l+i;
        if (l+i==0) t=1;
    }
    if (t==0 && l>0) ans=ans-l;
    if (t==0 && l<0) ans=ans-(l+n-1);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))

class comb{
	vector<ll> f,fr;
	ll MOD_;
	public:
	//a^(p-1) = 1 (mod p)(p->Prime numbers)
	//a^(p-2) = a^(-1)
	ll calc(ll a,ll b,ll p){//a^(b) mod p   
		if(b==0)return 1;
		ll y = calc(a,b/2,p);y=(y*y)%p;
		if(b & 1) y = (y * a) % p;
		return y;
	}
	void init(ll n,ll mod){//input max_n
		MOD_ = mod;
		f.resize(n+1);
		fr.resize(n+1);
		f[0]=fr[0]=1;
		for(ll i=1;i<n+1;i++){
			f[i] = (f[i-1] * i) % mod;
			fr[i] = calc(f[i],mod-2,mod);
		}
	}
	ll nCr(ll n,ll r){
		if(n<0||r<0||n<r)return 0;
		return f[n] * fr[r] % MOD_ * fr[n-r] % MOD_;
	}
};


int main(){
	ll x,y,ans=0;
	cin >> x >> y;
	if((x+y)%3){
		cout << 0 << endl;
		return 0;
	}
	ll z = (x+y)/3;
	comb co;
	co.init(1000009,MOD);
	ll xc = x-z;//x no kaisuu
	ll yc = y-z;
	ans = co.nCr(xc+yc,xc);
	cout << ans << endl;
}

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

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n+1);
    rep(i,n+1) {
        cin >> a[i];
    }
    //cout << a.size() << endl;

    vector<ll> tree_sum(n+1);
    repll(i,n+1) {
        if (i == 0) {
            tree_sum[i] = 1;
        } else {
            tree_sum[i] = tree_sum[i-1] + int(pow(2,i));
        }
    }

    bool outflag = false;
    ll next_max;
    vector<ll> alive_leaf(n+1);
    alive_leaf[0] = 1;
    repll(i,n+1) {
        if(i == 0) {
            if (a[i] == 0) {
                next_max = 2;
            } else if (a[i] == 1) {
                if  (a.size() == 1) {
                    break;
                } else {
                    outflag = true;
                    break;
                }
            } else {
                outflag = true;
                break;
            }
        } else {
            if (next_max < a[i]) {
                outflag = true;
                break;
            } else if (next_max == a[i]) {
                if (a.size() == i+1) {
                    break;
                } else {
                    outflag = true;
                    break;
                }
            } else {
                //ok
                if (i == n) {
                    alive_leaf[i] = next_max;
                } else {
                    alive_leaf[i] = (next_max - a[i]);
                    next_max = (next_max - a[i])*2;
                }
                //cout << alive_leaf[i] << endl;
            }
        }
    }
    if (outflag == true) {
        cout << "-1" << endl;
    } else {
        ll ans = 0;
        ll last_leaf;
        repll(i,n+1) {
            if (i==0) {
                ans += a[n-i];
                last_leaf = a[n-i];
            } else {
                //ans += min(a[n-i+1], alive_leaf[n-i]);
                ans += min(last_leaf+a[n-i], alive_leaf[n-i]+a[n-i]);
                last_leaf = min(last_leaf+a[n-i], alive_leaf[n-i]+a[n-i]);
            }
        }
        /*
        rep(i,n+1) {
            if(i!=n) {
                ans += a[i];
            }
        }
        */
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 6004
#define ll long long
#define lld long double
#define cn(n)  ll n;cin >> n;
#define tes(t) ll t;cin>>t;while(t--) 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define al(v) v.begin(), v.end()
#define oset(X) tree<X, null_type, less<X>, rb_tree_tag, tree_order_statistics_node_update>
#define roset(X) tree<X, null_type, greater<X>, rb_tree_tag, tree_order_statistics_node_update>
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll INF = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 7;
const ll MOD2 = 998244353;
const long double PI = 3.141592653589793;
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
ll power(ll x, ll y, ll p){ll res = 1;x %= p;while (y > 0){if (y & 1)res = (res * x) % p;y = y >> 1;x = (x * x) % p;}return res;}
ll po(ll base, ll powerRaised){if (powerRaised != 0)return (base * po(base, powerRaised - 1));else return 1;}
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll lcm(ll a, ll b){return (a * b) / gcd(a, b);}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
// #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
// #endif //*
	// tes(t)
  // {
    
  // }
    int prime[1000001];
    ll MAXN=1000001;
    for (int i = 2; i <= MAXN; i++)
    prime[i] = i;
    for (int i = 2; i * i <= MAXN; i++)
    {
    if (prime[i] == i)
    {
      for (int j = i * i; j <= MAXN; j += i)
          if (prime[j] == j)
              prime[j] = i;
    }
    }
    int n;
    cin>>n;
    ll ans=1;
    for(int i=2;i<=n-1;i++)
    {
    map<int,int>mpp;
    int num=i;
    while(num>1)
    {
      mpp[prime[num]]++;
      num=num/prime[num];
    }
    
    ll x=1;
    for(auto itr:mpp)
    x*=(itr.ss+1);

    // if(i==6)
    // cout<<x;

    ans+=x;
    }
    cout<<ans;
	
	
}
	

  


Measured memory_bytes: 7564
package main

import(
    "fmt"
)



func main() {
    var a,b,c int
    fmt.Scan(&a,&b,&c)
    var m = make(map[int]int)
    m[a]++
    m[b]++
    m[c]++
    fmt.Println(len(m))
}





func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}


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

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  int bk[n][m+1];
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= m; j++) {
      cin >> bk[i][j];
    }
  }
  int res = 100000000, sk[m], tempres;
  bool flag;
  for(int bit = 0; bit < (1<<n); bit++) {
    tempres = 0;
    flag = true;
    for(int i = 0; i < m; i++) {
      sk[i] = 0;
    }
    for(int i = 0; i < n; i++) {
      if(bit & (1<<i)) {
        tempres += bk[i][0];
        for(int j = 0; j < m; j++) {
          sk[j] += bk[i][j+1];
        }
      }
    }
    for(int i = 0; i < m; i++) {
      if(sk[i] < x) flag = false;
    }
    if(flag) res = min(res, tempres);
  }
  switch (res) {
    case 100000000:
      cout << -1 << endl;
      break;
    default:
      cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 3644
n = int(input())
a = list(map(int, input().split()))
ans = 3 ** n
ahj = 0
for i in range(n):
	if a[i] % 2 == 1:
		ahj += 1
if ahj == 0 or ahj == n:
	ah = max(1, 2 ** (n - ahj) )
else:
	ah = (2 ** (n - ahj))
print(ans-ah)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
struct point {
	int x;
	int y;
};

double dis(point a, point b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main() {
	int n;
	cin >> n;
	cout << fixed;
	cout.precision(10);
	point arr[8];
	int perm[8];
	for (int i = 0; i < n; i++) {
		perm[i] = i;
	}
	for (int i = 0; i < n; i++) {
		cin >> arr[i].x >> arr[i].y;
	}
	double fact = 1;
	for (int i = 1; i <= n; i++)
		fact *= i;
	double sum = 0;
	do {
		for (int i = 0; i < n - 1; i++)
			sum += dis(arr[perm[i]], arr[perm[i + 1]]);
	} while (next_permutation(perm, perm + n));
	cout << sum / fact << '\n';
	return 0;
}

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

int main(){
    int r, d, x2000;
    cin >> r >> d >> x2000;

    for(int i=0; i<10; i++){
        x2000=r*x2000-d;
        cout << x2000 << endl;
    }

    return 0;
}

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

int main()
{
 	long long n;
  	long long sum=0;
  	cin>>n;
  	for(long long i=1;i<=n;i++)
    {
      if(i%5!=0 && i%3!=0)
        sum+=i;
    }
  cout<<sum<<"\n";
  return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define REP(i,N) for(int i=0;i<N;i++)
int main(){
    int a,b,c; cin>>a>>b>>c;
    if((a-c)*(b-c)<0){
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll inf = 1e9+7;
ll func[1010] = {0};
ll inv[1010] = {0};

ll mult(ll n, ll m){
    if(m==0) return 1;
	if(m==1) return n%inf;
	else if(m%2==0){
		ll t = mult(n,m/2);
		return (t*t)%inf;
	}else{
		ll t = mult(n,m-1);
		return (t*n)%inf;
	}
}

void factorial(ll N){
	for(ll i=0;i<=N;i++){
		if(i==0){
			func[i] = 1;
			inv[i] = 1;
		}
		else{
			func[i] = (i*func[i-1])%inf;
			inv[i] = mult(func[i],inf-2);
		}
	}
}

ll comb(ll n,ll k){
	if(n<k) return 0;
	if(n<0 || k<0) return 0;
	else return (((func[n]*inv[k])%inf)*inv[n-k])%inf;
}

ll permutation(ll n,ll k){
    return (comb(n,k)*func[k])%inf;
}

int N,A,B,C,D;
ll dp[1010][1010] = {};

int main(){
    cin >> N >> A >> B >> C >> D;
    factorial(N);
    for(int i=0;i<=B;i++) dp[i][0] = 1;
    ll ans = 0;
    for(int i=A;i<=B;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<=D;k++){
                if(j-i*k<0) break;
                if(0<k && k<C) continue;
                ll v = (mult(inv[i],k)*inv[k])%inf;
                ll r = (permutation(N-j+i*k,i*k)*v)%inf;
                (dp[i][j] += (dp[i-1][j-i*k]*r)%inf)%=inf;
            }
        }
//        (ans += dp[i][N])%=inf;
    }
/*    for(int i=0;i<=B;i++){
        for(int j=0;j<=N;j++){
            cerr << dp[i][j] << " ";
        }
        cerr << endl;
    }*/
    // cout << dp[1][1] << endl;
    cout << dp[B][N] << endl;
}


Measured memory_bytes: 8192
mod = int(1e9+7)
dp = [-1]*(3000)
def cnt(n):
    if(n<3):
        return (n==0)
    if(dp[n]!=-1):
        return dp[n]
    dp[n]=0
    for i in range(3,n+1):
        dp[n]=(dp[n]+cnt(n-i))%mod
    return dp[n]

s = int(input())
print(int(cnt(s)))   


Measured memory_bytes: 9408
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

from collections import deque
def dfs(G, a, b):
    #(a, b)は除外する辺
    q=deque()
    q.append((1, -1, 0))
    log = [0] * n
    log[0] = 1
    while q:
        V,P,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            #q.append((V,P,1))
            for new_v in G[V-1]:
                if {a, b} == {new_v, V}:continue
                if new_v==P:continue
                if log[new_v - 1]:continue
                log[new_v - 1] = 1
                q.append((new_v,V,0))

    return sum(log) != n

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)
'''
ab一個を除いた時に連結かどうか調べる
'''

ans = 0
for a, b in ab:
    if dfs(G, a, b):ans += 1
print(ans)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int mx=1e5+777;

vector<bool> flag;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	flag.resize(mx,true);
	flag[0]=flag[1]=false;
	for (int i=2; i*i<mx; i++)
		if(flag[i])
			for (int j=i; j*i<mx; j++)
				flag[i*j]=false;
	vector<int> sim(mx,0);
	for (int i=1; i<mx; i+=2)
		if(flag[i]&&flag[(i+1)/2])
			sim[i]=1;
	vector<int> cum(mx,0);
	for (int i=1; i<mx; i++) {
		cum[i]+=cum[i-1];
		if(sim[i])
			cum[i]++;
	}
	
	int q; cin>>q;
	while(q--) {
		int l,r; cin>>l>>r;
		cout<<cum[r]-cum[l-1]<<"\n";
	}
	return 0;
}

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

int main()
{
    int N, cnt = 0;
    cin >> N;
    vector<long long> vec(N);

    for (int i = 0; i < N; i++) {
        cin >> vec[i];
        if (vec[i] % 2 != 0) {
            cout << cnt << endl;
            return 0;
        }
    }

    while (true) {
        for (int i = 0; i < N; i++) {
            if (vec[i] % 2 != 0) {
                cout << cnt << endl;
                return 0;
            } else {
                vec[i] /= 2;
            }
        }
        cnt++;
    }
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int n;
    cin >> n;
    vector<int> v(n), c(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    int ans = 0;
    for (int i = 0; i < n; i++){
        ans += max(0, (v[i] - c[i]));
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(int argc, char **argv)
{
    int N, M;
    int p[100000];
    string S[100000];
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> p[i];
        cin >> S[i];
    }

    bool isClear[N];
    int nPena[N];
    for (int i = 0; i < N; ++i) {
        isClear[i] = false;
        nPena[i] = 0;
    }

    for (int i = 0; i < M; ++i) {
        p[i]--;
        if (S[i] == "AC") {
            isClear[p[i]] = true;
        }
        else {
            if (!isClear[p[i]]) nPena[p[i]]++;
        }
    }
    int sumClear = 0, sumPena = 0;
    for (int i = 0; i < N; ++i) {
        if (isClear[i]) {
            sumClear++;
            sumPena += nPena[i];
        }
    }
    cout << sumClear << " " << sumPena;
    return 0;
}


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

int main() {
  int A, B;
  cin >> A >> B;
  
  int ans = 0;
  
  for(int i = A ; i < B + 1 ; i++){
    int a,b,c,d,e,x;
    x = i;
    a = x%10;
    x = x/10;
    b = x%10;
    x = x/10;
    c = x%10;
    x = x/10;
    d = x%10;
    x = x/10;
    e = x;
    if(a == e && b == d){
      ans += 1;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define int long long
#define ve vector<int>
#define mod 1000000007
#define eb emplace_back
#define inf ((long long) 1e18 )
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << '>' << #x << ':' << x << '\n';
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug2(x,y) cout << '>' << #x <<" = "<< x <<" & "<< #y <<" = "<< y << '\n';
#define fileIO freopen("input.txt", "r", stdin); freopen("output1.txt", "w", stdout);
using namespace std;
const int N = 2e5 + 7;

int32_t main() {
	IOS
#ifndef ONLINE_JUDGE
	fileIO
#endif
	auto start = std::chrono::high_resolution_clock::now();
	int test;
	test = 1;
	// cin >> test;
	while (test--) {
		string a;
		cin >> a;
		int s = 0;
		for(auto i : a)
			s += (i - '0');
		if(s % 9 == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;

	}

	auto stop = std::chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);

	cerr << "Time taken : " << ((long double)duration.count()) / ((long double) 1e9) << "s " << endl;

	return 0;
}

Measured memory_bytes: 3916
N, A, B = map(int, input().split())

result = 0
for i in range(1, N+1):
    num = i//(10**4) + i//(10**3)%10 + i//(10**2)%10 + i//10%10 + i%10
    if A <= num <= B:
        result += i
print(result)

Measured memory_bytes: 9020
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    if (a <= 0 && b >= 0)
        return cout << "Zero", 0;
    if (a > 0)
        return cout << "Positive", 0;

    b = min(-1, b);
    if (abs(b - a) % 2 != 0)
        return cout << "Positive", 0;
    return cout << "Negative", 0;
}


Measured memory_bytes: 256
/*
 * atcoder/abc130/a.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

int x[5];

void input() {
  loop(n,0,5) cin >> x[n];
}

void solve() {
  int last = 0;
  int min_ = 10;
  loop(n,0,5) {
    if (x[n]%10==0) continue;
    if (chmin(min_, x[n]%10)) {
      last = n;
    }
  }

  int t=0;
  loop(n,0,5) {
    if (n==last) continue;
    t += (x[n] % 10 == 0) ? x[n] : ((x[n] / 10) + 1) * 10;
  }

  t += x[last];
  cout << t << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	string s; cin >> s;
	rep(i, 0, s.size()) {
		if (i != s.size() - 1 && s[i] == s[i + 1]) {
			cout << i + 1 << " " << i + 2 << endl;
			return 0;
		}
		else if (i != s.size() - 1 && s[i] == s[i + 2]) {
			cout << i + 1 << " " << i + 3 << endl;
			return 0;
		}
	}
	cout << -1 << " " << -1 << endl;

	return 0;
}

Measured memory_bytes: 512
#include <iostream>

using namespace std;

int main() {
  for (;;) {
    int b, r, g, c, s, t;
    cin >> b >> r >> g >> c >> s >> t;
    if (!b && !r && !g && !c && !s && !t) return 0;
    cout << 100+b*15+r*15+g*7+c*2+(b*5+r*3)*(15-2)-(t-b*5-r*3-s)*3 << endl;
  }
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

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

	vector<queue<int>> player(N + 1);
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < N - 1; j++) {
			int a;
			cin >> a;
			player[i].push(a);
		}
	}

	ll day = 1;
	bool flag = true;
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}
	for (day = 1; flag;day++) {
		flag = false;
		vector<bool> visit(N + 1);
		int sz = q.size();
		for (int j = 0; j < sz;j++) {
			int i = q.front();
			q.pop();
			if (player[i].empty()) {
				continue;
			}
				

			int opp = player[i].front();
			if (visit[i] || visit[opp])
				continue;
			if (i == player[opp].front()) {
				player[i].pop();
				player[opp].pop();
				flag = true;
				visit[i] = true;
				visit[opp] = true;
				q.push(i);
				q.push(opp);
			}
		}
	}

	flag = true;
	for (int i = 1; i <= N; i++) {
		if (!player[i].empty()) {
			flag = false;
			break;
		}
	}
	if (flag)
		cout << day-2 << endl;
	else
		cout << -1 << endl;
}

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

int main()
{
	int n,i;
	int sum = 0;
	int d = 10000000;
	int a,b,c;
	int x;
	cin >> n;
	
	
	for(i = 0 ; i < 8 ; i++)
	{
		a = d*10;
		b = n/a;
		c = b*10;
		sum += n/d - c ;
		d /= 10;
	}
	x = n/sum;
	if (sum != 0 && x*sum == n)
	cout << "Yes" << endl;
	
	else 
	cout << "No" << endl;
	
	

}

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

using namespace std;

int main()
{
	string s[3];
	cin >> s[0] >> s[1] >> s[2];
	int now = 0;
	while (true)
	{
		if (s[now].length() == 0)
			break;
		int tmp = s[now][0] - 'a';
		s[now].erase(0, 1);
		now = tmp;
	}
	cout << (char)('A' + now) << endl;

	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (N, Q) = listOfInt()
    val S = next()
    val T = Array(N + 1) { 0 }
    for (n in 0 until N) {
        T[n + 1] = T[n] + (if (n + 1 < N && S[n] == 'A' && S[n + 1] == 'C') 1 else 0)
    }
    repeat(Q) {
        val (l, r) = listOfInt(-1)
        println(T[r] - T[l])
    }
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }

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

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N, K;
	cin >> N >> K;
	string str;
	cin >> str;
	char a = 'A', b = 'B';
	int at = 0;
	rep(i,0,K) {
		if (str[at] == a) str[at] = b;
		else {
			swap(a, b);
			str += a;
			at++;
		}
		if (i >= 2*N + 10 && i + 20 < K) {
			i += (K - i - 10) / 2 * 2;
		}
	}
	str = str.substr(at, N);
	if (a != 'A') rep(i,0,N) str[i] = (str[i] == 'A' ? 'B' : 'A');
	cout << str << endl;
	exit(0);
}


Measured memory_bytes: 1176
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) int((v).size())
#define ALL(vec) begin(vec), end(vec)

typedef long long i64;
template<typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}
template<typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}
#ifdef Rahul
# define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#else
# define error(...) 42;
#endif
string to_string(char c) { return "'" + string(1, c) + "'";}
string to_string(string s) { return '"' + s + '"';}
string to_string(const char* s) { return to_string((string) s);}
template<typename A> string to_string(A);
template<typename A, typename B> string to_string(pair<A, B> p){
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";}
template<typename A> string to_string(A v) {bool f = false; string r = "{"; 
  for (auto x: v) {if (f) r += ", "; r += to_string(x); f = true;} return r += "}";}
template<typename A> string to_string(vector<vector<A>> v) {string r; 
  for (auto x: v) r += "\n" + to_string(x); return r;}
int Nerr;
template<typename A> string to_string(A *p) {return to_string(vector<A>(p, p + Nerr));}
void err(istream_iterator<string>) { cerr << endl; }
template<typename T,typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << to_string(a) << "; "; err(++it, args...); }
template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}
int const MOD = 1e9 + 7;
long long const INF = 1e18 + 42;
/***********************************************************************/
int a[3][3];
int b[200];
int32_t main() {
  cin.tie(nullptr) -> sync_with_stdio(false);
  
  int n = 3;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  cin >> n;
  while (n--) {
    int x; cin >> x;
    b[x] = 1;
  }
  n = 3;
  vector<int> col(3, 1);
  int d1 = 1, d2 = 1;
  for (int i = 0; i < n; ++i) {
    int row = 1;
    for (int j = 0; j < n; ++j) {
      row &= b[a[i][j]];
      col[j] &= b[a[i][j]];
      if (i + j == 2) d1 &= b[a[i][j]];
      if (i - j == 0) d2 &= b[a[i][j]];
    }
    if (row) kek("Yes");
  }
  if (accumulate(ALL(col), 0)) kek("Yes");
  if (d1 or d2) kek("Yes");
  kek("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int W,H,N;
int cnt;
int grid[105][105];

int main(){ 

cin.tie(0);
ios::sync_with_stdio(false);


cin>>W>>H>>N;

for(int i=0; i<N; i++){
	int x,y,a;
	cin>>x>>y>>a;
	if(a==1){
		for(int w=1; w<=W; w++){
			for(int h=1; h<=H; h++){
				if(w<=x) grid[w][h]=1;
			}
		}
	}
	if(a==2){
		for(int w=1; w<=W; w++){
			for(int h=1; h<=H; h++){
				if(w>x) grid[w][h]=1;
			}
		}
	}
	if(a==3){
		for(int w=1; w<=W; w++){
			for(int h=1; h<=H; h++){
				if(h<=y) grid[w][h]=1;
			}
		}
	}
	if(a==4){
		for(int w=1; w<=W; w++){
			for(int h=1; h<=H; h++){
				if(h>y) grid[w][h]=1;
			}
		}
	}
}

for(int i=1; i<=W; i++){
	for(int j=1; j<=H; j++){
		if(grid[i][j]==0){
			cnt++;
		}
	}
}

cout<<cnt<<endl;

}



Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
long long a, b, c;
int main() {
    DAU
    cin >> a >> b;
    c = a * b / __gcd(a, b);
    cout << c;
    PLEC
}


Measured memory_bytes: 3648
def main():
	n, q = map(int, input().split())
	s = input()
	acs = [0]*(n)
	for i in range(1, n):
		if s[i-1] == "A" and s[i] == "C":
			acs[i] = acs[i-1] + 1
		else:
			acs[i] = acs[i-1]
	results = [0]*q
	for i in range(q):
		l, r = map(int, input().split())
		if l == r:
			continue
		results[i] = acs[r-1] - acs[l-1]
	for result in results:
		print(result)

if __name__ == '__main__':
    main()

Measured memory_bytes: 10312
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.List

main :: IO ()
main = do
  (n:m:_) <- fmap (map read . words) getLine :: IO [Int]
  as <- fmap (map read . words) getLine :: IO [Integer]
  bcs <- replicateM m $ (\(a:b:_) -> (a,b)) . map read . words <$> getLine :: IO [(Integer, Integer)]
  print $ solve as bcs

solve as bcs = go 0 (sort as) (reverse $ sortOn snd bcs)
  where
    go s [] _ = s
    go s as [] = s + sum as
    go s (a:as) ((b, c):bcs) = 
      if b == 0 
      then go s (a:as) bcs
      else if a < c
           then go (s + c) as ((b-1, c):bcs)
           else s + a + sum as 


Measured memory_bytes: 165116
#include<bits/stdc++.h>                          
using namespace std;
int c[505],s[505],f[505],n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i]>>s[i]>>f[i];
    for(int i=1;i<=n;i++)
	{
        ans=0;
        for(int j=i;j<n;j++)
		{
            if(ans<s[j]) ans=s[j];
            if(ans%f[j]!=0) ans=ans+f[j]-ans%f[j];
            ans+=c[j];
        }
        cout<<ans<<endl;
    }
    return 0;
}
//68871358
//76140264
//25446011
//200841159
//914174775

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

int main()
{
  int N;
  int Y;
  int count=1;
  int tmp;

  cin >> N >> Y;
  for(int i=0;i<N+1;i++){
    for(int j=0;j<N-i+1;j++){
      if(10000*i + 5000*j + 1000*(N-i-j) == Y){
        cout << i << " " << j << " " << (N-i-j) << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <queue>

template<typename T>
class TBinaryHeap
{
    std::vector<T> FArray;
    void BubbleUp(int Index)
    {
        assert(FArray.size() > Index);
        if(Index == 1) return;
        int Parent = Index / 2;
        if(FArray[Index] <= FArray[Parent]){
            return;
        }
        std::swap(FArray[Index], FArray[Parent]);
        BubbleUp(Parent);
    }
    void BubbleDown(int Index)
    {
        assert(FArray.size() > Index);
        int Left  = Index * 2;
        int Right = Index * 2 + 1;
        if(Left  >= FArray.size()) return;
        
        int Target = Right >= FArray.size() ? Left : FArray[Left] > FArray[Right] ? Left : Right;
        if(FArray[Target] > FArray[Index]){
            std::swap(FArray[Index], FArray[Target]);
            BubbleDown(Target);
        }
    }
public:
    TBinaryHeap()
    {
        FArray.resize(1); // dummy
    }
    void push(const T& Value)
    {
        FArray.push_back(Value);
        BubbleUp(FArray.size()-1);
    }
    void pop()
    {
        assert(FArray.size() >= 1);
        FArray[1] = FArray.back();
        FArray.pop_back();
        if(FArray.size() == 1) return; // dummy???????????????
        BubbleDown(1);
    }
    const T& top()
    {
        return FArray[1];
    }
};
int main()
{
    char Line[19];
    int Value;

    // std::priority_queue<int> S;
    TBinaryHeap<int> S;
    while(1){
        std::fgets(Line, 19, stdin);
        if(Line[0] == 'i'){
            S.push(std::atoi(&Line[7]));
        }else
        if(Line[1] == 'x'){
            std::printf("%d\n", S.top());
            S.pop();
        }else{
            break;
        }
    }
    return 0;
}

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

using namespace std;

#define ll long long
#define fix cout << fixed; cout << setprecision(0)





void solve() {

	string s;
	cin >> s;
	if(s[2] == s[3] && s[4] == s[5]) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";

	}




	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	fix;
	solve();

	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

#define UNIT 400
#define ULIMIT 3200
#define COLORS_MAX 8
int main(void) {
    int num;
    cin >> num;
    vector<int> arr(num);
    cins(arr);
    vector<int> map(COLORS_MAX+1);
    for(int i = 0; i < num; i++) {
        int color = min(arr[i], ULIMIT)/UNIT;
        map[color]++;
    }

    int ans = 0;
    for(int i = 0; i < COLORS_MAX; i++) {
        ans += (map[i]>0);
    }
    cout << max(1, ans) << " ";
    cout << ans+map[COLORS_MAX] << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
    using namespace std;
    #define rep(i, a, b) for (ll i = (a); i < (b); i++)
    #define rep2(r, aa, bb) for (ll r = (aa)-1; r >= (bb); r--)
    #define be(x) (x.begin(), x.end())
    #define pb(t) push_back(t)
    #define ll long long
    int main()
    {
        int n;
        cin>>n;
        vector<pair<int,int>>A(n);
        rep(i,0,n)
        {
            cin>>A[i].first;
            A[i].second=i+1;
        }
        sort be(A);
        rep(i,0,n)cout<<A[i].second<<" ";
    }

Measured memory_bytes: 1536