akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = [int(i) for i in input().split()]
flg = 1
if n == 0 and a[0] != 1:
    print(-1)
elif n == 0:
    print(1)
else:
    acc = [0]
    for i in range(n,-1,-1):
        acc.append(acc[-1] + a[i])
    ans = 0
    s = 1

    for i in range(n+1):
        if i != 0:
            s = min(s*2,acc[-i-1])
        ans += s
        s -= a[i]
        if s < 0:
            flg = 0
        #print(s,ans)
    if flg:
        print(ans)
    else:
        print(-1)


Measured memory_bytes: 90880
#include <bits/stdc++.h>
using namespace std;
#define Maxn 200007
int n,a[Maxn],b[Maxn];
priority_queue<pair<int,int> >pq;
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    while (!pq.empty()) pq.pop();
    for (int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        if (b[i]!=a[i]) pq.push(make_pair(b[i],i));
    }
    long long ans=0LL;
    while (!pq.empty())
    {
        int i=pq.top().second;
        pq.pop();
        if (b[i]-b[(i+1)%n]-b[(i+n-1)%n]<a[i])
        {
            printf("%d\n",-1);
            return 0;
        }
        int tmp=b[(i+1)%n]+b[(i+n-1)%n],t;
        if (a[i]>=max(b[(i+1)%n],b[(i+n-1)%n]))
        {
            if (b[i]%tmp!=a[i]%tmp)
            {
                printf("%d\n",-1);
                return 0;
            }
            t=(b[i]-a[i])/tmp;
        } else t=(b[i]-max(b[(i+1)%n],b[(i+n-1)%n]))/tmp+1;
        b[i]-=t*tmp;
        if (b[i]<a[i])
        {
            printf("%d\n",-1);
            return 0;
        }
        if (b[i]!=a[i]) pq.push(make_pair(b[i],i));
        ans+=t;
    }
    printf("%lld\n",ans);
    return 0;
}

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

int main() {
  vector<int> antenna(5);
  int k;
  for (int i = 0; i < 5; i++) {
    cin >> antenna.at(i);
  }
  cin >> k;
  bool communicable = true;
  for (int i = 0; i < 5; i++) {
    for (int j = i+1; j < 5; j++) {
      int interval = antenna.at(j) - antenna.at(i);
      if (interval > k) {
        communicable = false;
        break;
      }
    }
  }
  if (communicable == true) {
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define x first
#define y second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define newline cout<<"\n"
#define yes cout<<"yes"<<"\n"
#define no cout<<"no"<<"\n"
#define INF (int)1e4
#define nax (int)1e5+3
#define eps (double)1e-9
#define all(x) x.begin(),x.end()
#define MAX_N 3005
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> pdbs;
// look for  all edge cases
//search for a pattern


int main(){
	fast;
	ll n,k;
	cin >> n >> k;
	vector<ll> v(n+1);
	for(ll i = 1;i<=n;i++){
		cin >> v[i];
	} 
	ll cycle = 1;
	vector<bool> vis(n+1,false);
	vis[1] = true;
	ll next = v[1];
	vector<int> len(n+1,0);
	int m = 1;
	int rem = 0;
	while(vis[next] == false){
		len[next] = m++;
		vis[next] = true;
		int prev = len[next];
		next = v[next];
		if(vis[next] == true){
			cycle = prev - len[next] + 1;
			rem = len[next] - 0;
 		}
	}
	//deb(cycle);
	ll ans = 1;
	if(k <= n){
		ll cnt =0 ;
		while(cnt != k){
			cnt++;
			ans = v[ans];
		}
	}
	else{
		k -= rem;
		k = k % cycle;
		ans = next;
		ll cnt = 0;
		while(cnt != k){
			cnt++;
			ans = v[ans];
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 5576
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

fn main(){
    let line: Vec<u64> = read_as_vec();
    let n = line[0];
    let mut m = line[1];
    
    let mut shops: Vec<(u64, u64)> = Vec::new();

    for _ in 0..n{
        let line: Vec<u64> = read_as_vec();
        shops.push((line[0], line[1]));
    }
    shops.sort_by_key(|x| (x.0));
    //println!("shops = {:?}", shops);
    let mut cost: u64 = 0;

    for (price, num) in shops{
        if m  >= num{
            cost += price*num;
            m -= num;
        }else{
            cost += price*m;
            println!("{}", cost);
            return;
        }
    }
    println!("{}", cost);
}


Measured memory_bytes: 6396
#include<stdio.h>
#include<string.h>
int main(void){
char s[101];
  int i,count=0,len;
  scanf("%s",s);
  len=strlen(s);
  for(i=0;i<len/2;i++){
if(s[i]!=s[len-i-1])count++;
  }
printf("%d",count);
  
  return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll INF=1e18;
const ll mod=1e9+7;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    deque<ll> d,ans;
    rep(i,n){
        d.push_back(a[i]);
    }
    ll be=*d.begin();
    d.pop_front();
    ans.push_back(be);
    rep(i,n-1){
        ll val=-1;
        if((i/2)%2==0){
            val=*d.rbegin();
            d.pop_back();
        }
        else{
            val=*d.begin();
            d.pop_front();
        }
        if(i%2==0){
            ans.push_back(val);
        }
        else{
            ans.push_front(val);
        }
    }
    ll sum=0;
    ll v=*ans.begin();
    ans.pop_front();
    rep(i,n-1){
        ll x=*ans.begin();
        ans.pop_front();
        sum+=abs(v-x);
        v=x;
    }
    
    rep(i,n){
        d.push_back(a[i]);
    }
    ll st=*d.rbegin();
    d.pop_back();
    ans.push_back(st);
    rep(i,n-1){
        ll val=-1;
        if((i/2)%2==1){
            val=*d.rbegin();
            d.pop_back();
        }
        else{
            val=*d.begin();
            d.pop_front();
        }
        if(i%2==1){
            ans.push_back(val);
        }
        else{
            ans.push_front(val);
        }
    }
    ll tot=0;
    ll w=*ans.begin();
    ans.pop_front();
    rep(i,n-1){
        ll x=*ans.begin();
        ans.pop_front();
        tot+=abs(w-x);
        w=x;
    }
    cout << max(sum,tot) << endl;
    return 0;
}


Measured memory_bytes: 5064
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

string S = "";

int main() {
	cin >> S;
	ll ans = 1e18;
	ll cnt = 0;
	for(int i = 0; i < S.size(); i++) {
		if(i & 1) {
			if(S[i] == '1') {
				cnt++;
			}
		}
		else {
			if(S[i] == '0') {
				cnt++;
			}
		}
	}
	ans = min(cnt, ans);
	cnt = 0;
	for(int i = 0; i < S.size(); i++) {
		if(i & 1) {
			if(S[i] == '0') {
				cnt++;
			}
		}
		else {
			if(S[i] == '1') {
				cnt++;
			}
		}
	}
	ans = min(ans, cnt);
	printf("%lld\n", ans);

	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
   ll n;
   cin>>n;
   string flag="No";
   int Max=pow(10,6);
   ll res=pow(10,13);
   for(int i=1;i<=Max;i++)
    {
        if(n%i==0)
            {
                ll ans=n/i+i-2;
                res=min(res,ans);
            }
    }
    cout<<res<<endl;
    // cout<<flag<<endl;
}

Measured memory_bytes: 256
from math import factorial


def combination2(num: int) -> int:
    return int(factorial(num) / (2 * factorial(num - 2)))


n = int(input())
ss = [input() for _ in range(n)]

dictionary = {}

for s in ss:
    sorted_string = "".join(sorted(s))
    count = dictionary.get(sorted_string)
    if count is None:
        dictionary[sorted_string] = 1
    else:
        dictionary[sorted_string] = count + 1

counter = 0

for count in dictionary.values():
    if count > 1:
        counter += combination2(count)

print(counter)


Measured memory_bytes: 24972
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		sc.close();
		int r = -1;
		String s = "";
		long ans = 0;
		for(int l=0;l<N;l++) {
			while(l-1>r) {
				r++;
			}
			while(r+1<N && S.lastIndexOf(s + S.charAt(r+1))>r+1) {
				s += S.charAt(r+1);
				r++;
			}
			ans = Math.max(r-l+1,ans);
			if(s.length()>=2) s = s.substring(1);
			else if (s.length()==1) s = "";
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 88516
N=int(input())

List=list(map(int,input().split()))

arr = []

a = 0
total = sum(List)

for i in range(N):
  a = a + List[i]
  b = total - a
  
  if a == b:
    ans = 0
  elif a > b:
    ans = a - b
  elif b > a:
    ans = b - a
  
  arr.append(ans)


print(min(arr))

Measured memory_bytes: 26268
#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
signed main(){
	double a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<a*b/2;
	cout<<" ";
	if(c==a/2&&d==b/2){
		c(1)
	}
	else{
		c(0)	
	}	
}	

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
an = 0

for i in range(n):
    if b[i] > a[i]:
        an+=a[i]
        b[i]-=a[i]
        
        if b[i] >= a[i+1]:
            an+=a[i+1]
            a[i+1]=0
        else:
            an+=b[i]
            a[i+1]-=b[i]
            
    else:
        an+=b[i]

print(an)

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

int main() {

  int N, M;
  cin >> N >> M;

  vector<int> A(M);

  for (int i = 0; i < N; i++) {
    int K;
    cin >> K;
    for (int j = 0; j < K; j++) {
      int a;
      cin >> a;
      A[a - 1]++;
    }
  }

  int answer = 0;

  for (int i = 0; i < M; i++) {
    if (A[i] == N) {
      answer++;
    }
  }

  cout << answer << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    ll n;
    cin >> n;
    vector<ll> a(n,0);rep(i,n)cin >> a[i];sort(a.begin(),a.end());
    vector<ll> b(n,0);rep(i,n)cin >> b[i];sort(b.begin(),b.end());
    vector<ll> c(n,0);rep(i,n)cin >> c[i];sort(c.begin(),c.end());
    ll res = 0;
    rep(j,n){
        res += (lower_bound(a.begin(),a.end(),b[j]) - a.begin()) * (c.end() - upper_bound(c.begin(),c.end(),b[j]));
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 5624
#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#define ll long long
const int N=1e6+10;
using namespace std;
int n;
string  s;
int ans=0;
int main(){
    cin>>n;
    cin>>s;
    for(int i=0;i<n-2;i++){
        if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') {
            ans++;
            i=i+2;
        }
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include <vector>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long ll;

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

ll ans, mx, sum, mn = 1e8, cnt;

int main(){
	ll r;
	cin>>r;
	double ans = 2*3.14159265359*r;
	cout<<fixed<<setprecision(20)<<ans<<endl;
}


Measured memory_bytes: 3780
using System;
using System.Linq;
public class Program {
  public static void Main() {
    int N = int.Parse(Console.ReadLine());
    string[] s = new string[N];
    for (int i = 0; i < N; i++) s[i] = Console.ReadLine();
    int M = int.Parse(Console.ReadLine());
    string[] t = new string[M];
    for (int i = 0; i < M; i++) t[i] = Console.ReadLine();

    string[] words = s.Concat(t).Distinct().ToArray();
    int maxBalance = 0;
    foreach (var word in words) {
      int balance = s.Count(x => x == word) - t.Count(x => x == word);
      maxBalance = (maxBalance < balance) ? balance : maxBalance;
    }

    Console.WriteLine(maxBalance);
  }
}


Measured memory_bytes: 13280
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <list>
#include <algorithm>
#include <numeric>
using namespace std;

int main(void){
  int K,N;
  cin >> K >> N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  
  vector<int64_t> D(N);
  D[0] = A[0] + K-A[N-1];
  for(int i=1;i<N;i++){
    D[i] = A[i] - A[i-1];
  }
  
  sort(D.begin(),D.end());
  D.pop_back();
  
  int64_t total = accumulate(D.begin(), D.end(), 0);

  cout << total << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

template< typename T >
T extgcd(T a, T b, T &x, T &y) {
  T d = a;
  if(b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

int main() {

  ll N;
  cin >> N;
  vector<ll> A;
  ll temp_in;
  REP(i, 0, N) {
    cin >> temp_in;
    A.push_back(temp_in);
  }

  ll gcd = A[0];
  REP(i, 1, N) {
    ll x, y;
    extgcd(gcd, A[i], x, y);
    gcd = gcd*x + A[i]*y;
  }

  cout << gcd << endl;

  return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

#define P 1000000007
#define N_MAX 10000000
typedef long long int ll;
ll fac[N_MAX+1];
ll inv[N_MAX+1];
ll finv[N_MAX+1];

ll comb(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (((fac[n]*finv[n-k])%P)*finv[k])%P;
}

void init(){
  fac[0] = finv[0] = fac[1] = finv[1] = inv[1] = 1;
  for(int i = 2; i <= N_MAX; i++){
    fac[i] = (fac[i-1]*i)%P;
    inv[i] = ((-(P/i)*inv[P%i])%P+P)%P;
    finv[i] = (finv[i-1]*inv[i])%P;
  }
}
ll pp(ll a, ll b){
  return (a * b)%P;
}
ll mpow(ll a, ll b, ll p = -1){
  ll ret = 1, num = a;
  if(p==-1){
    while(b>0){
      if(b%2) ret *= num;
      num = num * num;
      b /= 2;
    }
  }else{
    while(b>0){
      if(b%2) ret = (ret*num)%p;
      num = (num*num)%p;
      b /= 2;
    }
  }
  return ret;
}
struct UF{
  std::vector<int> par, dep, sz;
  UF(int n){
    par.resize(n+1), dep.resize(n+1), sz.resize(n+1);
    init(n);
  }
  void init(int nu) {
    for(int iu=0;iu<=nu;iu++){
      par[iu] = iu;
      dep[iu] = 0;
      sz[iu] = 1;
    }
  }
  int find(int xu){
    if(par[xu] == xu) return xu;
    return par[xu] = find(par[xu]);
  }
  void unite(int xu, int yu){
    xu=find(xu);
    yu=find(yu);
    if(xu == yu) return;
    if(dep[xu] < dep[yu]){
      sz[yu] += sz[xu];
      par[xu] = yu;
    }else{
      par[yu] = xu;
      sz[xu] += sz[yu];
      if(dep[xu] == dep[yu]) dep[xu]++;
    }
  }
  bool same(int xu, int yu){ return find(xu) == find(yu);}
  int get_size(int x){return sz[find(x)];}
};

int main(int argc, char const *argv[]) {
  init();
  ll n;std::cin >> n;
  vll p(n);
  vll k;
  UF uf(n+1);
  ll cnt = 0;

  re(i, n) {
    scanf("%lld", &p[i]);
    if(p[i]==-1) k.push_back(i);
    if(p[i]!=-1) {
      p[i]--;
      if(uf.same(i, p[i])) cnt++;
      uf.unite(i, p[i]);
    }
  }
  ll m = k.size();
  ll ans = pp(n, mpow(n-1, m, P));
  vvl dp = VV(m+1, 5001, 0, ll);

  dp[0][0] = 1;
  for(int i=1;i<=m;i++){
    ll sz = uf.sz[uf.find(k[i-1])];
    for(int j=0;j<=5000;j++){
      dp[i][j] = dp[i-1][j];
      if(j!=0) dp[i][j] = (dp[i][j] + (dp[i-1][j-1]*sz)%P)%P;
    }
  }
  dp[m][1] = 0;
  for(int i=1;i<=m;i++){
    ll sz = uf.sz[uf.find(k[i-1])];
    dp[m][1] = (dp[m][1] + (sz-1))%P;
  }

  ll s = 0;
  for(ll i=1;i<=m;i++) {
    ll tmp = pp(pp(dp[m][i], fac[i-1]), mpow(n-1, m-i, P));
    s = (s + tmp)%P;
  }
  ll ad = pp(cnt, mpow(n-1, m, P));
  std::cout << (ans - s - ad + 2*P)%P << '\n';
  return 0;
}


Measured memory_bytes: 433164
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7;

int main()
{
	IO_OP;
	
	int a, b, k;
	cin >> a >> b >> k;
	int ct = 1;
	for(int i=min(a, b);i>=1;i--) {
		if(a % i == 0 && b % i == 0) {
			if(ct == k) {
				cout << i << endl;
				return 0;
			}
			ct++;
		}
	}
	
}



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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N;
int A[100010];

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

	cin >> N;
	rep(i, 0, N)
	{
		cin >> A[i];
		A[i]--;
	}

	int p = 0;
	int cnt = 1;
	while (A[p] != 1)
	{
		p = A[p];
		cnt++;
		if (cnt > 2*N)
		{
			cout << -1 << endl;
			return 0;
		}
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b){return !b ? a : gcd(b, a % b);}
ll modP(ll a, ll b) {return (!b ? 1 : (modP(a, b / 2) * modP(a, b / 2) * (b % 2 ? a : 1)) % MOD);}

ll alpha[26];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	string s;
	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++){
		alpha[s[i] - 'a'] += 1;
	}
	ll ans = 1;
	for (int i = 0; i < 26; i++){
		ans = (ans * (alpha[i] + 1)) % MOD;
	}
	cout << (ans - 1 + MOD) % MOD << endl;
	return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long LL;
LL f1[200005], f2[200005];
LL P(LL x, LL y){
    LL z=1;
    while(y){
        if(y%2) z=z*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return z;
}
LL XX(int a, int b){
    return f1[a]*f2[b]%mod*f2[a-b]%mod;
}
int main(){
    f1[0] = f2[0] = 1;
    for(int i=1;i<=200000;i++) f1[i] = f1[i-1]*i%mod, f2[i] = P(f1[i], mod-2);
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    LL ans = 0;
    for(int i=(n-1)-k;i<=n-1;i++){
        ans = (ans + XX(n-1, i)*m%mod*P(m-1, i))%mod;
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 6952
#include <stdio.h>
#include <string.h>
int main(void)
{
  char a[1001];
  int i,l;
  scanf("%s",a);
  l=strlen(a);
  for(i=0;i<l;i++){
    if(a[i]=='A')
      a[i]='X';
    else if(a[i]=='B')
      a[i]='Y';
    else if(a[i]=='C')
      a[i]='Z';
    else 
      a[i]=a[i]-3;
  }
  printf("%s\n",a);
  return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
int main(){
    double a, b;
    cin >> a >> b;
    double x = (a + b) / 2.0;
    if(x - (int)x >= 0.5)
        x += 1;
    cout << (int)x << endl;
    return 0;
}

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

int main() {
  int x, y;
  cin >> x >> y;

  while(!(x==0&&y==0)) {
    if(x < y)
    cout << x << " " << y << endl;
    else
    cout << y << " " << x << endl;
    cin >> x >> y;
  }
  return 0;
}


Measured memory_bytes: 2980
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,i;cin >> n >> m;
    vector<int> dp(n+1,100000);int c[m];dp[0] = 0;
    for(i=0;i<m;i++) cin >> c[i];
    for(i=0;i<=n;i++){
        for(auto x:c){
            if(i>=x) dp[i] = min(dp[i],dp[i-x]+1);
        }
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 3164
#include <vector> 
#include <list> 
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;

const LL mod = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	VI A(N+2);
	FOR(i,1, N+1)cin >> A[i]; 
	LL sumALL=0;

	FOR(i,1, N+2) {
		sumALL += abs(A[i - 1] - A[i]);
	}

	FOR(pass,1, N+1) {
		LL sum = sumALL;
		
		sum -= abs(A[pass - 1] - A[pass]);
		sum -= abs(A[pass] - A[pass + 1]);
		sum += abs(A[pass - 1] - A[pass + 1]);
		cout << sum << endl;
	}

}

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

int main(){
  long long a,b,c,d;	cin >> a >> b >> c >> d;
  long long ans=a*c;
  ans=max(ans,a*d);
  ans=max(ans,b*c);
  ans=max(ans,b*d);
  cout << ans;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
//freopen("transmitters.in","r",stdin);
//cout<<fixed<<setprecision(6)<<n<<endl;
// transform(s.begin(), s.end(), s.begin(), ::tolower);
//double PI=3.14159265359,c=0;
#define all(v) v.begin(),v.end()
#define endl '\n'
#define ll long long
//#define f(n) for(int i=;i<n;i++)
double PI = acos(-1);
using namespace std;
void fast()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
ll arr[100000];
int main()
{
    fast();
    ll n,t,x,mn=0;
    cin>>n;
    vector<ll>v(n,1e12);
    for(int i=0;i<n;i++)
      cin>>arr[i];
    for(int i=0;i<n;i++)
    {
        x=v[i];
        if(i+1<n)
        {
            if(i==0)
              x=0;
            mn=x+abs(arr[i]-arr[i+1]);
            v[i+1]=min(v[i+1],mn);
        }
         if(i+2<n)
        {
            if(i==0)
              x=0;
            mn=x+abs(arr[i]-arr[i+2]);
            v[i+2]=min(v[i+2],mn);
        }
        //cout<<v[i]<<" ";
    }
    cout<<v[v.size()-1]<<endl;

    return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class B
{
	public static void Main()
	{
		string[] args = Console.ReadLine().Split(' ');
		int N = Int32.Parse(args[0]);
		int X = Int32.Parse(args[1]);

		int freeX = X;
		List<int> m = new List<int>(N);
		for(int i = 0; i < N; i++)
		{
			m.Add(Int32.Parse(Console.ReadLine()));
			freeX -= m[i];
		}
		m.Sort();
		int ans = N;

		for(int i = 0; i < N; i++)
		{
			if(m[i] > freeX)
				break;
			
			int add = freeX / m[i];
			ans += add;
			freeX -= add * m[i];
		}

		Console.WriteLine(ans);
	}
}





Measured memory_bytes: 11092
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev


def main():
    from itertools import accumulate
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk = dijkstra(n, g)

    vis = [False] * (n + 1)

    def f(now, c):
        if vis[now]:
            return 0
        vis[now] = True
        cnt = 1
        for _, nxt in g[now]:
            cnt += f(nxt, c)

        return cnt

    nw = dk[1]

    cnt = []
    vis[1] = True
    vis[n] = True
    while nw != n:
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw, 0)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    *a, = accumulate(cnt)
    l = len(a)
    k = l // 2 - 1 if l % 2 == 0 else l // 2
    fn += a[k] if l > 0 else 0
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()


Measured memory_bytes: 50016
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k,c=0;
    cin>>n;
    int a[n+2];
    vector<int>vc;
    for(i=0; i<n; i++)
    {
        cin>>a[i];
        vc.push_back(a[i]);
    }
    sort(vc.begin(),vc.end());
    for(i=0;i<vc.size();i++)
    {
              for(j=i+1;j<vc.size();j++)
                    for(k=j+1;k<vc.size();k++)
              {
                        if((vc[i]+vc[j]>vc[k]) && (vc[i]!=vc[j] && vc[j]!=vc[k] && vc[i]!=vc[k]))
                             c++;
              }
    }
    cout<<c;
}


Measured memory_bytes: 3580
n=int(input())
a=[0]*n
b=[0]*n
c=[0]*n
for i in range(n):
    a[i],b[i],c[i]=map(int, input().split())
dpa=[0 for i in range(n+1)]
dpb=[0 for i in range(n+1)]
dpc=[0 for i in range(n+1)]

for i in range(n):
    dpa[i+1]=max(dpb[i]+a[i],dpc[i]+a[i])
    dpb[i+1]=max(dpa[i]+b[i],dpc[i]+b[i])
    dpc[i+1]=max(dpa[i]+c[i],dpb[i]+c[i])
#print(dpa,dpb,dpc)
print(max(dpa[n],dpb[n],dpc[n]))

Measured memory_bytes: 55128
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		long x = Math.abs(scan.nextLong());
		long k = scan.nextLong();
		long d = scan.nextLong();
		scan.close();
		long ans ;
		if(x/d>=k) { x = x-d*k;}
		else {
			long e = x/d;
			long k2 = k - e;
			x -= e*d;
			if(k2%2==1) { x = Math.abs(x-d);}
		}
		ans = x;
		System.out.println(ans);
	}
}

Measured memory_bytes: 35664
#include<iostream>
#include<cmath>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;

int n;
int a[211],k[211];
int ans[211];

int gao(int a,int k)
{
    int ans;
    
    if(a<k)
    {
        return 0;
    }
    
    int i,j;
    if((double)a/k<=(double)k*log(a))
    {
        while(a%k!=0 && a>k)
        {
            int p=a/k*k;
            
            //cout<<a<<' '<<p<<"   "<<k<<endl;
            
            if((a-p)%(a/k+1)==0)
            {
                a=p;
                break;
            }
            
            int t=(a-p)/(a/k+1)+1;
            //cout<<t<<"   ttt"<<endl;
            a-=t*(a/k+1);
        }
        ans=a/k;
    }
    else
    {
        while(a%k!=0 && a>k)
        {
            a=a-a/k-1;
        }
        ans=a/k;
    }
    
    return ans;
}

int main()
{
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i]>>k[i];
    }
    
    int p=0;
    for(i=1;i<=n;i++)
    {
        ans[i]=gao(a[i],k[i]);
        p^=ans[i];
        //cout<<ans[i]<<endl;
    }
    if(p==0)
    {
        cout<<"Aoki"<<endl;
    }
    else
    {
        cout<<"Takahashi"<<endl;
    }
    
    return 0;
} 


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a,b,c;
int ans;
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	if(a<b)swap(a,b);
	if(a<c)swap(a,c);
	if(b<c)swap(b,c);
	if((a-b)&1)b++,c++,ans++;
	ans+=(a-b)/2;b=a;
	if((b-c)&1)a++,b++,ans++;
	ans+=(b-c)/2;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
package main

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

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	b := make([]int, n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		a[i] = nextInt(sc)
		b[i] = a[i]
	}
	sort.Ints(b)
	cnt := 0
	for i := 0; i < n; i++ {
		if a[i] != b[i] { // a[i]とb[i]が異なっている
			if cnt < 2 {
				cnt++
				for j := i + 1; j < n; j++ {
					if a[j] == b[i] {
						a[i], a[j] = a[j], a[i]
					}
				}
			} else {
				break
			}
		}
		if cnt > 1 {
			break
		}
	}
	if cnt < 2 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

ll solve() {
    ll N, M, a, b;
    cin >> N >> M;
    vector<vector<ll>> G(N);
    for ( int i = 0; i < M; i++ ) {
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ll NN = (1 << N);

    function<int(int,int)> dfs = [&](int v, int b) {
        int r = 0;
        for ( int u : G[v] ) {
            int nb = b | (1<<u);
            if ( nb == b ) continue;
            if ( nb != NN-1 ) {
                r += dfs(u, nb);
            } else {
                r += 1;
            }
        }
        return r;
    };
    
    ll ans = dfs(0,1);
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
object Main extends App {
	val N = scala.io.StdIn.readLong

	var ans = 0L
	for(i<-1L to N; j<-1L to N; k<-1L to N){
		val tp = gcd(i, j)
		ans += gcd(k, tp)
	}

	println(ans)

	def gcd(a: Long, b: Long): Long = {
		if(b == 0L) return a
	  	else return gcd(b, a%b)
	}
}

Measured memory_bytes: 57184
#include <bits/stdc++.h>
#define ll long long

using namespace std;


int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    int n;
    ios::sync_with_stdio(false);
    cin >> n;
    if(n % 10 == 9 || n / 10 == 9)
          cout << "Yes";
    else
          cout << "No";
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 256
/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd
#define prev asdgSHJsfgsdfhdsh
#define hash asdgasdgasdgdfrywewery

#define eps 1e-9
#define M_PI 3.141592653589793
#define bsize 300

#define ldouble long double
using namespace std;

#define bs 1000000007

const int N = 610031;

int n;
string st[N];
int ans;

int insd(string st){
	int ret=0;
	for (int i=0;i+1<st.size();i++){
		if (st[i]=='A'&&st[i+1]=='B')
			++ret;
	}
	return ret;
}

int c1,c2;

int both;

int main(){
//    freopen("apache.in","r",stdin);
//    freopen("apache.out","w",stdout);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin>>n;
    for (int i=1;i<=n;i++){
    	cin>>st[i];
    	ans+=insd(st[i]);
    	if (st[i][0]=='B')
    		++c2;
    	if (st[i][st[i].size()-1]=='A')
    		++c1;
    	if (st[i][0]=='B'&&st[i][st[i].size()-1]=='A')
    		++both;
    }

    int c11=both;
    int c01=c1-both;
    int c10=c2-both;

    ans+=min(c01,c10);
    if (c01==0&&c10==0&&both>0)
    	ans+=both-1;
    else
    	ans+=both;

    cout<<ans<<endl;


//    cin.get(); cin.get();
    return 0;
}


Measured memory_bytes: 5504
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<math.h>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
//#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll;
const int INF=0x3f3f3f3f;
inline int mul(int a,int b){ return (a*1ll*b)%mod; }
inline int add(int a,int b){ a+=b;if(a>=mod) a-=mod; return a;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1) rt=rt*a;a=mul(a,a);b>>=1;} return rt;}
//for(int i=0;i<n;i++)
ll mxm(ll a,ll b){
    if(a>b) return a;
    else return b;
}

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
//for(int i=0;i<n;i++)

void solve(){
   int n;cin>>n;
   ll ans=0,a[n];
   for(int i=0;i<n;i++) cin>>a[i];
   for(int i=0;i<n-1;i++){
      if(a[i]>a[i+1])
        ans+=a[i]-a[i+1],a[i+1]=a[i];
   }
   cout<<ans<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;//cin>>t;
    while(t--)
    solve();
    return 0;
}

Measured memory_bytes: 5204
h, n = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(n)]
m = max(A for A, B in AB)
dp = [0]*(h+m)

for i in range(1, h+1):
    dp[i] = min(dp[i-A]+B for A,B in AB)

print(dp[h])

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

int main()
{
	ll n,sum = 0;
	scanf("%lld",&n);
	if(n & 1) printf("0\n");
	else{
		ll ans = 0;
		
		ll m,t = 10,k = n;
		while(m = k/t){
			ans += m;
			t *= 10;
		}
		t = 50,k = n;
		while(m = k/t){
			ans += m;
			t *= 5;
		}
		t = 100,k = n;
		while(m = k/t){
			ans -= m;
			t *= 10;
		}
		
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
  int a[26]={};
  string s;
  while(getline(cin,s)) {
      for(int i=0; i<s.size(); i++) {
          if(s[i]>='a'&&s[i]<='z') {
              a[s[i]-'a']++;
          }
          else if(s[i]>='A'&&s[i]<='Z') {
              a[s[i]-'A']++;
          }
      }
  }
  for(int i=0; i<26; i++) {
      cout << (char)('a'+i) << " : " << a[i] << endl;
  }
}


Measured memory_bytes: 3176
#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

char X, Y;

int main() {
  cin >> X >> Y;

  if (X > Y)
    cout << ">" << endl;
  else if (X < Y)
    cout << "<" << endl;
  else
    cout << "=" << endl;

  return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <iomanip>

using namespace std;
using pii = pair<int, int>;
using ti = tuple<int, int, int>;

const double eps=1e-14;
const int mod = 1e9 + 7;
const int inf = ((1<<30));
const long long linf = (1LL<<60);

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans = 0;
    int n = s.size();
    s = s.substr(0, n-2);
    while(true)
    {
        int tmp = s.size();
        if(s.substr(0,tmp/2) == s.substr(tmp/2, tmp/2))
        {
            ans = tmp;
            break;
        }
        s = s.substr(0, tmp-2);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 2010;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x,y;
    cin >> x >> y;
    if (abs(x-y) <= 1) PRINT("Brown");
    else PRINT("Alice");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const int mod = 1000000007;

int X1, X2, Y1, Y2;

int main() {
	cin >> X1;
	cout << ((X1 - 1) / 111 + 1) * 111 << endl;
}

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

int main() {
  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;
  int rAC[500000];
  rAC[0]=0;rAC[1]=0;
  rep(i,n){
    if(i==0)continue;
    if(s[i-1]=='A'&&s[i]=='C'){
      rAC[i+1]=rAC[i]+1;
    }else{
      rAC[i+1]=rAC[i];
    }
  }
  rep(i,q){
    int l,r;
    cin>>l>>r;
    cout<<rAC[r]-rAC[l]<<endl;
  }
}

Measured memory_bytes: 1408
n = int(input())
A = [int(input()) for _ in range(n)]
G = [1]
a=1
while True:
    a = 3*a+1
    if a>=n:
        break
    G.append(a)
if len(G)>1:
    G.sort(reverse=True)
m = len(G)
cnt = 0

def shellSort(A,n):
    cccnt = 0
    for k in range(m):
        cccnt += insertionSort(A,n,G[k])
    return cccnt

def insertionSort(A,n,g): #Aはリスト　nは要素数　gは間隔
    ccnt = 0
    for i in range(g,n):
        v = A[i]
        j = i-g
        while j>=0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            ccnt += 1
        A[j+g] = v
    return ccnt

cnt = shellSort(A,n)

print(m)
print(' '.join(map(str,G)))
print(cnt)
for _ in range(n):
    print(A[_])


Measured memory_bytes: 45524
// http://algorithms.blog55.fc2.com/blog-entry-66.html

#include <iostream>
using namespace std;
#include <stdio.h>

#define MAX 100
#define INFTY (1 << 21)

int SIZE;
int R[MAX + 2];
int C[MAX+1][MAX+1]; // cost table
int B[MAX+1][MAX+1]; // best table

void compute(){
    for ( int i = 0; i <= SIZE; i++ )
    for ( int j = 0; j <= SIZE; j++ ) C[i][j] = INFTY;
    
    for ( int i = 0; i <= SIZE; i++ ) C[i][i] = 0;
    
    for ( int j = 1; j <= SIZE - 1; j++ ){
        for ( int i = 1; i <= SIZE - j; i++ ){
            for ( int k = i; k < i + j; k++ ){
                // C[i][i+j] = min( C[i][i+j], 
                //                  C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]);
                int cost = C[i][k] + C[k+1][i+j] + R[i]*R[k+1]*R[i+j+1];
                if ( cost < C[i][i+j] ){
                    C[i][i+j] =  cost;
                    B[i][i+j] = k;
                }
                
            }
        }
    }
}

void order( int i, int j ){
    if ( i == j ) cout << "M" << i;
    else{
        cout << "(";
        order( i, B[i][j]-1 ); order(B[i][j], j);
        cout << ")";
    }
}

void input(){
    cin >> SIZE;
	int z,i=1;
    for (; i <= SIZE; i++ ) cin >> R[i]>>z;
	R[i]=z;
	//SIZE++;
}

void output(){
    cout <<  C[1][SIZE] << endl;
    //order(1, SIZE);
    //cout << endl;
}

main(){
    input();
    compute();
    output();
}

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

int main(){
  int n,k;
  cin>>n>>k;
  
  long long int ans,tmp;
  if(n!=1){ans=k*pow(k-1,n-1);}
  else{ans=k;}
  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))
using d = double;

int K, S;
int ans = 0;

int main() {
  cin >> K >> S;
  for(int i = 0; i <= K; ++i) {
    for(int j = 0; j <= K; ++j) {
      int X = i, Y = j, Z = S - X - Y;
      if(X + Y <= S && Z <= K) ++ans;
    }
  }

  cout << ans << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t N;
  cin >> N;
  vector<int64_t> vec(N+1);
  int64_t sum = 0;
  for(int i=0; i<N+1; i++){
    cin >> vec[i];
    sum += vec[i];
  }
  
  bool flag = true;
  int64_t ans = 0;
  int64_t bottom = 1;
  for(int i=0; i<N+1; i++){
    bottom -= vec[i];
    if(bottom < 0){
      flag = false;
    }
    ans += bottom;
    ans += vec[i];
    sum -= vec[i];
    if(bottom < sum){
      bottom = min(bottom*2,sum);
    }
  }
  if(!flag){
    ans = -1;
  }
  cout << ans << endl;
}

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

int dfs(int st, int gl, int cv, int p, vector<vector<int>> &g){
  int res = 0;
  rep(i,g[cv].size()){
  // for(auto nx : g[cv]){
    int nx = g[cv][i];
    if(nx == p) continue;
    if(nx == st) continue;
    if(nx == gl) res++;
    else res += dfs(st,gl,nx,cv,g);
  }
  return res;
}

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

  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n,vector<int>());
  rep(i,m){
    int a,b;
    cin >> a >> b;
    --a;--b;
    g[a].push_back(b);
    g[b].push_back(a);    
  }
  int cnt = 0;
  int po = 0;
  rep(i,n){
    if(g[i].size()%2==1){
      cout << "No" << endl;
      return 0;
    }
    cnt += g[i].size()/2 - 1;
    if(g[i].size()/2 == 2) po++;
  }
  if(cnt == 2 && po == 2){
    vector<int> st;
    rep(i,n){
      if(g[i].size()/2 == 2) st.push_back(i);
    }
    if(st.size()==2){
      if(dfs(st[0],st[1],st[0],-1,g)==2) cnt = 2;
      else cnt = 0;
    }
  }
  if(cnt>=2) cout <<"Yes" << endl;
  else cout <<"No" << endl;



  return 0;
    

}


Measured memory_bytes: 8064
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#define KAKUDO 30
#define KYORI 100
using namespace std;
#define rep(i,a) for(i=0;i<a;i++)
int main(void)
{
	int i,j,k;
	int n,iti,kaku,x,y,xy,amari,amari2;
	cin>>n;
	while(n--) {
		cin>>iti>>kaku;
		if((iti==0||iti%KYORI==0)&&kaku%KAKUDO==0) {
			y=iti/KYORI;x=kaku/KAKUDO;
			xy=y+x*5;
			cout<<xy<<endl;
		}
		else if(iti%KYORI==0&&kaku%KAKUDO!=0) {
			y=iti/KYORI;x=kaku/KAKUDO;
			amari=kaku%KAKUDO;xy=y+x*5;
			cout<<xy<<" "<<xy+5<<endl;
		}
		else if(iti%KYORI!=0&&kaku%KAKUDO==0) {
			y=iti/KYORI;x=kaku/KAKUDO;
			amari=iti%KYORI;xy=y+x*5;
			cout<<xy<<" "<<xy+1<<endl;
		}
		else {
			y=iti/KYORI;x=kaku/KAKUDO;
			amari=iti%KYORI;amari2=kaku%KAKUDO;xy=y+x*5;
			cout<<xy<<" "<<xy+1<<" "<<xy+5<<" "<<xy+6<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll a[55];
ll b[55];
ll l=1,r=1e16+1000;
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    sort(a+1,a+1+n,greater<ll>());
    while(a[1]>=n)
    {
        ll t=0;
        t+=a[1]/n;
        a[1]%=n;
        for(int i=2;i<=n;i++)
            a[i]+=t;
        ans+=t;
        sort(a+1,a+1+n,greater<ll>());
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))

cnt = 0
for i in range(N - 1):
    if A[i] == i:
        cnt += 1
        A[i], A[i + 1] = A[i + 1], A[i]

if A[N - 1] == N - 1:
    cnt += 1

print(cnt)

Measured memory_bytes: 14452
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<string,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> P(m), Y(m);
    rep(i, m) {
        cin >> P[i] >> Y[i];
        P[i]--;
    }
    vector<vector<int>> A(n);
    rep(i, m) {
        A[P[i]].push_back(Y[i]);
    }
    rep(i, n) {
        sort(ALL(A[i]));
    }

    rep(i, m) {
        printf("%06d", P[i] + 1);
        int id = lower_bound(ALL(A[P[i]]), Y[i]) - A[P[i]].begin();
        printf("%06d\n", id + 1);
    }

    return 0;
}

Measured memory_bytes: 7808