akhauriyash/Code-Regression huggingface dataset:
n=parse(Int,readline())
a=map(x->parse(Int,x),split(readline()))
r=maximum(a)
l=-1
while r-l>1
	b=zeros(2*n)
	m=div(r+l,2)
	s=n
	b[s]=1
	N=c=0
	for i=1:n
		if a[i]>m
			s+=1
			N-=b[s]
		else
			N+=b[s]
			s-=1
		end
		c+=N
		b[s]+=1
	end
	if c*4>n*(n+1)
		r=m
	else
		l=m
	end
end
println(r)


Measured memory_bytes: 167656
// base: https://atcoder.jp/contests/agc031/submissions/7912574

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll n) { // like pow(x, n)
  ll r = 1;
  while (n) {
    if (n & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return r;
}

int main(int argc, char** argv) {
  int N;
  cin >> N;
  vector<ll> c(N);
  rep(i, N) {
    cin >> c[i];
  }

  // dp[i] = sum of all dp[j] where c[j] != c[j+1] && c[j+1] == c[i].
  // When c[i], c[i+1], ..., c[k] are same, then we consider dp[i], dp[i+1], ... d[k] as same.
  vector<ll> dp(N);
  ll dpsum[200010]; // dpsum is the summerized count of each colors at each step i.
  memset(dpsum, 0, sizeof(dpsum));
  dpsum[c[0]] = 1; // initial value is 1.
  rep(i, N) {
    dp[i] = dpsum[c[i]];
    if ((i < N-1) && (c[i] != c[i+1])) {
      dpsum[c[i+1]] += dp[i];
      dpsum[c[i+1]] %= MOD;
    }
  }

  cout << dp[N-1] << endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;

int main(){
    ll n;
    cin>>n;
    if(n%2==1){
        cout<<0<<endl;
        return 0;
    }
    ll ans=0,t=10;
    while(t<=n){
        ans+=n/t;
        t*=5;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
def sieve(n):
    '''
    :param n:
    :return: n以下の素数のリストを返す
    エラトステネスの篩→O(n log log n)
    '''
    prime = []
    is_prime = [True] * (n + 1) #is_prime[i] = Trueならiは素数
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return prime

dp_memo = [0] * 50
def f(x):
    #f(x) = (x + N -1) C (N - 1)
    if dp_memo[x] > 0:
        return dp_memo[x]
    elif x == 0:
        return 1
    else:
        return (f(x - 1) * (x + N - 1)) // x

N, M = map(int, input().split())
P = sieve(4 * 10 ** 4)
index = []
i = 0
while M > 1 and i < len(P):
    cnt = 0
    while M % P[i] == 0:
        cnt += 1
        M //= P[i]
    i += 1
    if cnt > 0:
        index.append(cnt)

if M > 1:
    index.append(1)

ans = 1
for i in index:
    ans = ans * f(i) % (10 ** 9 + 7)

print(ans)

Measured memory_bytes: 3444
mod = 10**9+7
def powmod(x,y):
    res = 1
    for i in range(y):
        res = res*x%mod
    
    return res

N = int(input())
ans = powmod(10,N)-powmod(9,N)-powmod(9,N)+powmod(8,N)
ans %=mod
ans = (ans+mod)%mod
print(ans)

Measured memory_bytes: 9160
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
char a[105], b[105];
int x[105], y[105];

int main() 
{
	scanf("%s", a);
	scanf("%s", b);
	int lena = strlen(a);
	int lenb = strlen(b);
	int flag = 0;
	
	for(int j = 99; j >= 0; j--)//从后往前放置（0000...123，0000...23847）
	{
		if(lena != 0)
		{
			x[j] = a[lena-1];
			lena--;
		}
		if(lenb != 0)
		{
			y[j] = b[lenb-1];
			lenb--;
		}
		if(lena == 0 && lenb == 0)		
			break;
	}
	
	for(int i = 0; i < 105 ;i++)//从a【0】位判断，若a(x)【i】》b(y)【i】，则flag=1，反之=-1，等于则仍=0
	{
		if(x[i] > y[i])		{flag = 1;break;}
		else if(x[i] < y[i])	{flag = -1;break;}
		else flag = 0;
	}
	
	if(flag == 1) printf("GREATER");
	else if(flag == -1) printf("LESS");
	else printf("EQUAL");
	
	return 0;
}

Measured memory_bytes: 256
def gcd(a, b):  # a >= b
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def makelist(n, m):
    return [[0 for i in range(m)] for j in range(n)]

N = int(input())
A = [0] + list(map(int, input().split()))

toRight = [0]*(N+1)
toRight[1] = A[1]
for i in range(2, N+1):
    toRight[i] = gcd(toRight[i-1], A[i])

toLeft = [0]*(N+1)
toLeft[N] = A[N]
for i in reversed(range(1, N)):
    toLeft[i] = gcd(toLeft[i+1], A[i])

# print(toRight)
# print(toLeft)
    
ans = max(toRight[-2], toLeft[2])
for i in range(2, N-1 + 1):
    now = gcd(toRight[i-1], toLeft[i+1])
    ans = max(ans, now)

print(ans)


Measured memory_bytes: 63980
#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <iostream>
#include <fstream>
#include <numeric>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <iterator>
#include <iomanip>
#include <unordered_map>
#include <bits/stdc++.h>

using namespace std;

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

    int n,a,b,i=0;
    cin>>n;

    string p1,p2="",s="";
    char ch;
    vector<string> vs;

    for(int i=0; i<n; i++)
    {
        cin>>ch;
        s+=ch;
    }
    for(int i=0; i<n; i++)
    {
        cin>>ch;
        p2+=ch;
    }

    p1=s;
    sort(s.begin(),s.end());

    do
    {
        i++;
        if(s==p1)
            a=i;
        if(s==p2)
            b=i;
    }
    while(next_permutation(s.begin(),s.end()));

    cout<<abs(a-b);
}


Measured memory_bytes: 256
S = input()
T = input()

n = len(S)
n1 = len(T)
ans = n1
for i in range(n - n1 + 1):
  
  x = 0
  
  for j in range(n1):
    
    if T[j] != S[i + j]:
      
      x += 1
      
  ans = min(ans, x)
  
print(ans)

Measured memory_bytes: 67492
///created: 11/Jul/2019 16:33:09

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
const int modulo = 1e9 + 7;

#ifdef LOCAL_DEBUG_NTV1612
template<class __Ty>
string to_string(__Ty a) {
	string res = "[ ";
	bool f = true;
	for (auto &p : a) { res += (f ? string("") : string(", ")) + to_string(p); f = false;	}
	return res + " ]";
}
void _debug() { fprintf(stderr, "\n"); }
template<typename __Ty_head, typename... __Ty_tail>
void _debug(__Ty_head head, __Ty_tail... tail) { fprintf(stderr, "%s ", to_string(head).c_str()); _debug(tail...); }
#define debug(...) fprintf(stderr, "DEBUG [%s]: ", #__VA_ARGS__), _debug(__VA_ARGS__)
#else
#define debug(...) 0
#endif

template<class __Ty> bool mini(__Ty& a, __Ty b) { return a > b ? ((a = b) | 1) : (0); }
template<class __Ty> bool maxi(__Ty& a, __Ty b) { return a < b ? ((a = b) | 1) : (0); }
template<class __Ty> __Ty add(__Ty a, __Ty b) { return (a + b) % (__Ty(modulo)); }
template<class __Ty> __Ty sub(__Ty a, __Ty b) { __Ty m(modulo); return ((a - b) % m + m) % m; }

const int N = 1e5 + 5;
int n, k;
ll x[N];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> x[i];
	ll ans = 1e18;
	for (int i = 1; i <= n - k + 1; ++i) {
		int l = i, r = i + k - 1;
		if (x[l] <= 0 && 0 <= x[r]) {
			ans = min(ans, min(x[r], -x[l]) + x[r] - x[l]);
		}
		if (x[r] <= 0) {
			ans = min(ans, x[r] - x[l] + 0 - x[r]);
		}
		if (x[l] >= 0) {
			ans = min(ans, x[r] - x[l] + x[l] - 0);
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 1024
N, M = map(int, input().split())
H = tuple(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)


ans = 0
for i in range(N):
    now = H[i]
    if all([now > H[nv] for nv in to[i]]):
        ans += 1
print(ans)

Measured memory_bytes: 29860
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    int n, k; cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int res = 0;

    // d より上位は k と一致, d は 1 じゃないとダメ, k より下は貪欲
    for(int d = 60; d >= -1; d--){

        if(d != -1 && !(k & (1LL << d))) continue;
        int tmp = 0;
        for(int e = 60; e >= 0; e--){
            int mask = (1LL << e);
            int num = 0;

            for(int i = 0; i < n; i++) if(a[i] & mask) num++;

            if(e > d){
                if(k & mask) tmp += mask * (n - num);
                else tmp += mask * num;
            }
            else if(d == e){
                tmp += mask * num;
            }
            else{
                tmp += mask * max(num, n - num);
            }
        }

        res = max(tmp, res);
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>

typedef long long ll;
typedef long double ld;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
  
using namespace std;
 
const ll inf = 1e18;
const ll N = 2e5+1;
const ll bits = 20;
const ld pi = 3.14159265358979323846;
const ll mod = 1e9+7;
const ll p = 29;


int main(){

    FASTIO;
    PRECISION; 

    int q;
    cin>>q;

    int t;
    ll a,b;
    ll c = 0;
    ll median;
    priority_queue<ll>less;
    priority_queue<ll,vector<ll>,greater<ll>>more;
    ll n = 0;
    ll less_sum = 0, more_sum = 0;

    while(q--){
        cin>>t;

        if(t==1){
            cin>>a>>b;
            c+=b;

            if(more.size()<less.size()){
                more.push(a);
                more_sum+=a;
            }else{
                less.push(a);
                less_sum+=a;
            }

            if(more.size()&&less.size()){
                while(more.top()< less.top()){
                    ll mt = more.top(); more.pop();
                    ll lt = less.top(); less.pop();
                    more_sum+=lt-mt; more.push(lt);
                    less_sum+=mt-lt; less.push(mt); 
                }
            }

        }else{
            ll x = less.top();
            ll ans1 = more_sum - x*more.size();
            ll ans2 = x*less.size() - less_sum; 
            cout<< x <<" "<< ans1 + ans2 + c <<"\n";
        }
    }


}


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,rd[N],dep[N],fa[N],head[N],flg;bool vis[N];
struct edge{int to,next;}e[N<<1];
inline void add(int x,int y){e[++flg].to=y;e[flg].next=head[x];head[x]=flg;}
void bfs(int x){
	queue<int>wait;wait.push(x);
	while(!wait.empty()){
		int v=wait.front();wait.pop();
		for(int i=head[v];i;i=e[i].next){
			int to=e[i].to;
			--rd[to];if(!rd[to])fa[to]=v,wait.push(to);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin>>n>>m;int x,y;
	for(int i=1;i<n+m;++i)cin>>x>>y,++rd[y],add(x,y);
	for(int i=1;i<=n;++i)if(!rd[i])bfs(i);
	for(int i=1;i<=n;++i)cout<<fa[i]<<"\n";return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------

//F9でブレークポイントを付ける
//( 条件式 ? Trueの処理:Falseの処理 )

void _main() {
	int N[5];
	int sum = 0;
	int sumFinal = 10;
	for (int i = 0; i < 5; i++) {
		cin >> N[i];
		sum += N[i] / 10 * 10;
		if (N[i] % 10 != 0) {
			sum += 10;
			//余りがある数の中で、1の位がもっとも大きいものを最後にする。
			if (N[i] % 10 < sumFinal) {
				sumFinal = N[i] % 10;
			}
		}
	}
	cout << sum+sumFinal-10 << endl;//-10は最後の物を余計に作ってしまった分
}

Measured memory_bytes: 256
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
	int a, b, n;
	cin >> n >> a >> b ;
    cout << min(n*a, b) << endl;
}

Measured memory_bytes: 256
n=int(input())

a=n//105
b=n//100

ans=False
for k in range(a,b+1):
    #print(str(k)+"個")
    nokori=n-k*100
    #print(nokori)
    lis=[5,4,3,2,1]
    tukai=0
    for a in lis:
        kau=nokori//a
        tukai+=kau
        nokori-=kau*a
    #print(nokori,tukai)
    if(tukai<=k):
        ans=True

if(ans):
    print(1)
else:
    print(0)



Measured memory_bytes: 3060
#include <iostream>
using namespace std;
#define ll long long 
#define mod 1000000007
#define max 10000000

ll factorial[max + 1];
void init () {
  factorial[0] = 1;
  for (ll i = 1; i <= max; i++) {
    factorial[i] = ((factorial[i - 1] % mod) * (i % mod)) % mod;  
  }   
}

// n^k
ll pow (ll n, ll k ) {
  if (k == 1) {
    return n % mod;  
  }    
  if (k % 2 == 0) {
    ll sub = pow (n, k / 2);
    return ((sub % mod) * (sub % mod)) % mod;  
  }
  else {
    return ((pow(n, k - 1) % mod) * (n % mod)) % mod;  
  }
}

// n C k
ll c (ll n, ll k) {
  ll ans;
  ans = factorial[n] % mod;
  ans = ((ans % mod) * (pow(factorial[n - k], mod - 2) % mod)) % mod;
  ans = ((ans % mod) * (pow(factorial[k], mod - 2) % mod)) % mod;
  return ans % mod;    
}

int main () {
  ll i, j;
  cin >> i >> j;
  init();
  ll x = 2 * i - j;
  ll y = 2 * j - i;
  if (x % 3 != 0 || y % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  if (x >= 0 && y >= 0) {
    x = x / 3;
    y = y / 3;
    cout << c(x + y, x) << endl;
  }
  else {
    cout << 0 << endl;
  }
}

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

class Solve {
private:
	using vd = std::vector<double>;
	using vvd = std::vector<vd>;
	using dii = std::pair<double, std::pair<int, int>>;

public:
	bool is_last_query{};
	Solve()
	{
		int N, M, P, A, B;
		scanf("%d%d%d%d%d", &N, &M, &P, &A, &B);
		if (N == 0)
		{
			is_last_query = true;
			return;
		}
		A--;
		B--;
		vd tickets(N);
		for (auto& e: tickets) scanf("%lf", &e);
		
		std::vector<std::vector<std::pair<int, double>>> edge(M);
		for (int i{}; i < P; i++)
		{
			int x, y;
			double z;
			scanf("%d%d%lf", &x, &y, &z);
			x--;
			y--;
			edge[x].push_back({y, z});
			edge[y].push_back({x, z});
		}

		vvd distance(M, vd(1 << N, 1e9));
		distance[A][0] = 0;
		std::priority_queue<dii, std::vector<dii>, std::greater<dii>> dij;
		dij.push({0.0, {A, 0}});
		while (!dij.empty())
		{
			auto now{dij.top()};
			dij.pop();
			if (now.first > distance[now.second.first][now.second.second])
				continue;
			if (now.second.first == B)
				break;
			for (int digit{}; digit < N; digit++)
			{
				if (now.second.second >> digit & 1) continue;
				for (auto& to: edge[now.second.first])
				{
					auto next{now};
					next.first += to.second / tickets[digit];
					next.second.first = to.first;
					next.second.second |= 1 << digit;
					if (next.first >= distance[next.second.first][next.second.second])
						continue;
					distance[next.second.first][next.second.second] = next.first;
					dij.push(next);
				}
			}
		}
		double min{1e9};
		for (auto& e: distance[B]) min = std::min(min, e);
		if (min == 1e9) puts("Impossible");
		else printf("%lf\n", min);
	}
};

int main()
{
	while (!Solve().is_last_query);

	return 0;
}


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

#define pb push_back
#define mp make_pair

typedef long long ll;

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

  int ans = 1e9;
  for(int i = -100; i <= 100; i++){
    int cost = 0;
    for(int j = 0; j < n; j++){
      cost += (a[j] - i)*(a[j] - i); 
    }
    ans = min(ans, cost);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
"use strict";

function main(input){
  const args = input.trim().split('\n').map(_=>_.split(' ').map(_=>parseInt(_,10)));
  const n = args[0][0];
  const w = args[0][1];
  const items = args.slice(1);
  
  const dp = Array(w+1).fill(0); // 容量をi使うときの最大価値
  for(let i=0; i<n; i++){
    const weight = items[i][0];
    const value = items[i][1];
    for(let k=w; k>=weight; k--){
      dp[k] = Math.max(dp[k-weight] + value, dp[k]);
    }
  }
  
  console.log(dp.reduce((acc,cur)=>Math.max(acc,cur)));
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

Measured memory_bytes: 15408
// file creato da gio il 2020-06-24 21:46:28.896077

#include <bits/stdc++.h>
#define FAST 

#ifdef FAST
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define MOD 1000000007
#define S second
#define F first
#define PB push_back
using namespace std;

int mcd(int a,int b){

    if(a<b)swap(a,b);
    if(b==0)return a;
    return mcd(b,a%b);

}


int main(){
	//freopen("output","w",stdout);
	//freopen("input","r",stdin);
#ifdef FAST
	ios::sync_with_stdio(0);
  	cin.tie(0);
#endif

	int n;
	cin >> n;
    if(360%n){
//        cout <<"360";
 //       return 0;
        int r=mcd(n,360);
        cout <<(360)/r; 

    }else{
        cout << 360/n;

    }


}


Measured memory_bytes: 3572
#include <iostream>

using namespace std;

int main() {
    int min;
    int max_delta = -999999999;
    int n, i;

    cin >> n;

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

    for (i = 0; i < n; i++) {
        if (i == 0) {
            min = input[i];
        } else {
        
            if (max_delta < input[i] - min) {
              max_delta = input[i] - min;
            }
            if (min > input[i]) {
                min = input[i];
            }
        }
        
    }
    cout << max_delta << endl;

    return 0;
}


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

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
  ll small = std::min(a, b);
  ll large = std::max(a, b);
  if (small == 0)
  {
    return large;
  }
  else
  {
    return gcd(small, large % small);
  }
}

int main()
{
  int n;
  cin >> n;
  vector<ll> a;

  ll st;
  for (int i = 0; i < n; i++)
  {
    cin >> st;
    a.push_back(st);
  }

  ll res = a[0];
  for (int i = 1; i < n; i++)
  {
    res = gcd(res, a[i]);
  }

  cout << res << endl;
}


Measured memory_bytes: 1400
from sys import stdin
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N,K = [int(x) for x in stdin.readline().rstrip().split()]
data = [int(x) for x in stdin.readline().rstrip().split()]

M = max(data)
G = gcd_list(data)

if K <= M and K % G == 0:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Measured memory_bytes: 16268
const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {
    const rows = input.split('\n')
    const [X, N] = rows[0].split(' ').map(n => n - 0)
    const P = rows[1].split(' ').map(n => n - 0)

    for (let i = 0; i < 52; i++) {
        if (P.indexOf(X - i) === -1) {
            console.log(X - i)
            break
        }
        if (P.indexOf(X + i) === -1) {
            console.log(X + i)
            break
        }
    }

})(input)


Measured memory_bytes: 29656
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] mask = new int[20];
		int curm = 1;
		for(int i = 0; i < 20; i++)
		{
			mask[i] = curm;
			curm*=2;
		}
		
		int[] lasto = new int[20];
		for(int i = 0; i < 20; i++)
			lasto[i] = -1;
		
		//dont forget singles
		long sco = 0;
		int forbid = -1;
		for(int i = 0; i < n; i++)
		{
			long cura = sc.nextLong();
			
			for(int j = 0; j < 20; j++)
			{
				if((mask[j] & cura) > 0)
				{ //has this bit
					if(lasto[j] != -1)
					{
						forbid = Math.max(forbid, lasto[j]);//+1
					}
				}
			}
			sco += i - forbid;
			
			
			for(int j = 0; j < 20; j++)
			{
				if((mask[j] & cura) > 0)
				{ //has this bit
					lasto[j] = i;
				}
			}
		}
		System.out.println(sco);
	}

}


Measured memory_bytes: 71020
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		char[] c=s.next().toCharArray();
		int[] b=new int[26];
		Arrays.fill(b,1);
		long r=0;
		for(int i=n-1;i>=0;--i){
			++b[c[i]-'a'];
			long t=1;
			for(int j=0;j<26;++j) {
				if(j!=c[i]-'a') {
					t*=b[j];
					t%=mod;
				}
			}
			r+=t;
			r%=mod;
		}
		System.out.println(r);
	}
	static int mod=1000000007;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int r; cin>>r;
	cout<<r*r<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define MAX 510000
#define Rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep(i, n) for(ll i = 1; i <= (ll)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

//cout << fixed << setprecision(10);//
//最小公倍数//
ll gcd(ll x, ll y) {
	if (x == 0) return y;
	return gcd(y%x, x);
}
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

//べき//
ll squ(ll n, ll p, ll m){
	if(p==0) return 1;
	if(p%2==0){
		ll t=squ(n, p/2, m);
		return t*t%m;
	}
	return n*squ(n,p-1,m);
	
}


//逆元mod(mを法とするaの逆元)//
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//Cmonp//
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
ll COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//nが大

ll com(ll n,ll m){
	if(n<=0 || m<=0 || n==m){
		return 1;
	}
	if(n<m){
		return 0;
	}
	ll k=1;
	for(ll i=1;i<=m;i++){
       k*=(n-i+1); 
	   k%=MOD;
	   k*=modinv(i,MOD);
	   k%=MOD;
	}

	return k;
}


//


////////////////////////////////////////////////////////////////////

int main(){
ll n;
cin>>n;
string s;
cin>>s;
ll q;
cin>>q;

set <int> ind[26]{};

for(int i=0;i<=n-1;i++){
char rr;
rr=s[i];
ind[rr-'a'].insert(i+1);
}

for(int j=1;j<=q;j++){
int r;
cin>>r;
if(r==1){
char m1,m2;
int u;
cin>>u>>m1;
m2=s[u-1];
s[u-1]=m1;
auto itr=ind[m2-'a'].erase(u);
ind[m1-'a'].insert(u);	
}

if(r==2){
    int l,r;
    cin>>l>>r;
int ans=0;
for(int k=0;k<=25;k++){
if(ind[k].upper_bound(r)!=ind[k].lower_bound(l)){
    ans++;
}

}
cout<<ans<<endl;
}


}


return 0;
}

Measured memory_bytes: 24196
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> arr;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		arr.push_back(a);
	}
	int dp[n];
	memset(dp,0,sizeof(dp));
	dp[0] = 0;
	for(int i=1;i<n;i++)
	{
		dp[i] = dp[i-1] + abs(arr[i] - arr[i-1]);
		if(i > 1)
			dp[i] = min(dp[i], dp[i-2] + abs(arr[i] - arr[i-2]));
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1144
#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 n;
    cin >> n;
    vector<int> b(n-1);
    rep(i,n-1){
        cin >> b[i];
    }
    vector<int> a(n);
    a[0] = b[0];
    for(int i=1;i<n-1;i++){
        a[i] = min(b[i-1], b[i]);
    }
    a[n-1] = b[n-2];
    int ans = 0;
    rep(i,n) ans += a[i];
    cout << ans << endl;
    return 0;
}


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

int main(){
  int k, a, b;
  cin >> k >> a >> b;

  for(int i = a; i <= b; ++i){
    if(i % k == 0){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
  return 0;
}

Measured memory_bytes: 3620
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}

func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

func getSum(a []int64, start, end int) int64 {
	ans := a[end-1]
	if start != 0 {
		ans -= a[start-1]
	}
	return ans
}

func renew(a []int64, start, prev, end int) int {
	i := prev
	for i < len(a) {
		lv := getSum(a, start, i)
		rv := getSum(a, i, end)
		j := i + 1
		nlv := getSum(a, start, j)
		nrv := getSum(a, j, end)
		if absInt64(lv-rv) < absInt64(nlv-nrv) {
			break
		}
		i = j
	}
	return i
}

func calc(a []int64, b, c, d, e int) int64 {
	var min, max int64
	min = getSum(a, b, c)
	max = min
	for _, v := range []int64{getSum(a, c, d), getSum(a, d, e), getSum(a, e, len(a))} {
		if v < min {
			min = v
		}
		if max < v {
			max = v
		}
	}
	return max - min
}

func main() {
	defer stdout.Flush()

	n := readInt()
	a := make([]int64, n)
	a[0] = readInt64()
	for i := 1; i < n; i++ {
		a[i] = readInt64() + a[i-1]
	}

	b := 0
	c := 1
	d := 2
	e := renew(a, 2, 3, n)
	min := calc(a, b, c, d, e)
	for d < n-1 {
		d++
		c = renew(a, b, c, d)
		e = renew(a, d, e, n)
		min = minInt64(min, calc(a, b, c, d, e))
	}
	println(min)
}


Measured memory_bytes: 4864
a, b = map(int, input().split())
c = 0
for i in range(1, 10 ** 4):
    if int(i * 1.08) == a + i and int(i * 1.1) == b + i:
        print(i)
        c = 1
        break
if c == 0:
    print(-1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  string s;
  cin >> s;
  ll k=s.size();
  ll cnt=0;
  rep(i,k-1){
    if(s[i]!=s[i+1]){
      cnt++;
    }
  }
  cout << cnt << endl;
}

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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    cout << max(0, A-2*B) << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repn(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define bac(i,a,b) for(ll i=a;i>=b;i--)
#define sz(v) (ll)v.size()
using namespace std;

ll MOD=1e9+7;
ll g,h,l;
const ll N=100005;

ll add(ll a,ll b); ll mul(ll a,ll b); ll binpo(ll a,ll b);

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    vector<pair<ll,ll> > v;
    repn(i,a){
        cin>>g;
        v.push_back({g,1});
    }
    repn(i,b){
        cin>>g;
        v.push_back({g,2});
    }
    repn(i,c){
        cin>>g;
        v.push_back({g,3});
    }

    sort(all(v));
    reverse(all(v));

    ll tot=0,ans=0;
    ll limit = x+y;
    repn(i,a+b+c){
        if(tot==limit){
            break;
        }
        if(v[i].second==1){
            if(x){
                ans+=v[i].first;
                x--;
                tot++;
            }
        }
        else if(v[i].second==2){
            if(y){
                ans+=v[i].first;
                y--;
                tot++;
            }
        }
        else{
            ans+=v[i].first;
            tot++;
        }
    }
    cout<<ans;
}

ll add(ll a,ll b)
{
    return (a%MOD+b%MOD)%MOD ;
}
ll mul(ll a,ll b)
{
    return (a* 1ll *b)%MOD ;
}
ll binpo(ll a,ll b)
{
    int ans = 1 ;
    while(b)
    {
        if( b % 2 != 0)
        {
            ans = mul(ans,a);
        }
        a = mul(a,a);
        b = b/2;
    }
    return ans;
}

Measured memory_bytes: 10476
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] line1 = br.readLine().split(" ");
    int n = Integer.parseInt(line1[0]);
    int m = Integer.parseInt(line1[1]);
    
    int[] cities = new int[n];
    int a;
    int b;
    String[] data;
    for (int i=0; i<m; i++){
      data = br.readLine().split(" ");
      a = Integer.parseInt(data[0])-1;
      b = Integer.parseInt(data[1])-1;
      cities[a]++;
      cities[b]++;
    }
    for (int i : cities){
      System.out.println(i);
    }
  }
}


Measured memory_bytes: 21332
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

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; }
template<class T>
T GCD(T a, T b) { if (b == 0) return a; else return GCD(b, a % b); }
template<class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	double a, b, c;
	cin >> a >> b >> c;
	if (a / c <= b) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 3712
N = 200
fac = [0]*(N)
for i in range(N):
    fac[i] = pow(i,5)
# print(fac[-1],fac[-2],fac[-1]-fac[-2])
# print(fac[-1]-fac[-2] > 10**9)
X = int(input())
for a in range(N):
    for b in range(N):
      if fac[a] - fac[b] == X:
          print(a,b)
          exit()
      if -fac[a] - fac[b] == X:
          print(-a,b)
          exit()
      if fac[a] + fac[b] == X:
          print(a,-b)
          exit()
      if -fac[a] + fac[b] == X:
          print(-a,-b)
          exit()

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

// #include "../../template-proj/myMente.h"

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

#define MOD 1000000007
#define rp(i,n) for(int i=0;i<(n);i++)
#define up(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define ot(x) cout<<(x)
#define ote(x) cout<<(x)<<endl

int main(){
	int n;cin>>n;
	int ans = 0;
	vi h(n);
	int maxi = 1;
	rp(i,n){
		cin>>h[i];
		if(maxi<=h[i]){
			maxi = h[i];
			++ans;
		}
	}

	ote(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;


int main(){
    ll a, b, n;
    cin >> a >> b >> n;
    n = min(n, b-1);
    ll ans = a*n/b;
    
    
    
    cout << ans << endl;
    return 0;
}


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

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> a(h + 2, vector<char>(w + 2, '*'));
    for (int i = 1; i < h + 1; i++) {
        for (int j = 1; j < w + 1; j++) {
            cin >> a[i][j];
        }
    }

    deque<tuple<int, int, int>> q;
    for (int i = 1; i < h + 1; i++) {
        for (int j = 1; j < w + 1; j++) {
            if (a[i][j] != '#') {
                continue;
            }
            q.emplace_back(i, j, 0);

        }
    }
    int mx = 0;
    while (!q.empty()) {
        auto x = q.front(); q.pop_front();
        int i = get<0>(x);
        int j = get<1>(x);
        int c = get<2>(x);

        bool ok = true;
        if (a[i - 1][j] == '.') {
            a[i - 1][j] = '#';
            ok = false;
            q.emplace_back(i - 1, j, c + 1);
        }
        if (a[i + 1][j] == '.') {
            a[i + 1][j] = '#';
            ok = false;
            q.emplace_back(i + 1, j, c + 1);
        }
        if (a[i][j - 1] == '.') {
            a[i][j - 1] = '#';
            ok = false;
            q.emplace_back(i, j - 1, c + 1);
        }
        if (a[i][j + 1] == '.') {
            a[i][j + 1] = '#';
            ok = false;
            q.emplace_back(i, j + 1, c + 1);
        }
        if (ok) {
            mx = max(mx, c);
        }
    }

    cout << mx << endl;
}


Measured memory_bytes: 13328
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
#define mp std::make_pair
#define pb push_back
using ll = long long;
int main()
{
	// freopen("keyence2019-B.in", "r", stdin);
	std::string str, goal = "keyence";
	std::cin >> str;
	if (str.size() < goal.size())
	{
		puts("NO");
		return 0;
	}
	for (int i = 0; i < str.size(); i++)
	{
		if (i < goal.size() && str.substr(0, i + 1) + str.substr(str.size() - (goal.size() - i - 1)) == goal)
		{
			puts("YES");
			return 0;
		}
	}
	puts("NO");
	return 0;
}


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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int p=0;
    int q =0;

    while( (A > 0) or (C > 0)){
        C = C - B;
        if(C <= 0){
            cout << "Yes" << endl;
            break;
        }

        A = A - D;
        if(A <= 0){
            cout << "No" << endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 3620
n,k=map(int,input().split())
cost=[10**15]*n;cost[0]=0
h=list(map(int,input().split()))
for i in range(n-1):
  for j in range(1,k+1):
    if i+j>n-1:break
    cost[i+j]=min(cost[i]+abs(h[j+i]-h[i]),cost[i+j])
print(cost[n-1])

Measured memory_bytes: 53216
#include <iostream>

 

using namespace std;

 

int main()
{
    int i, ans, a, b, c;
    
    cin >> a >> b >> c;
    ans = 0;
    for(i=a; i<=b; i++)
    {
        if( c % i ==0 )
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3100
n = gets.to_i

n.times do
  x1, y1, x2, y2, x3, y3 = gets.split.map(&:to_f)

  a1 = 2 * (x2 - x1)
  b1 = 2 * (y2 - y1)
  c1 = x1**2 - x2**2 + y1**2 - y2**2
  a2 = 2 * (x3 - x1)
  b2 = 2 * (y3 - y1)
  c2 = x1**2 - x3**2 + y1**2 - y3**2

  px = (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1)
  py = (c1 * a2 - c2 * a1) / (a1 * b2 - a2 * b1)

  a = Math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
  b = Math.sqrt((x3 - x2)**2 + (y3 - y2)**2)
  c = Math.sqrt((x1 - x3)**2 + (y1 - y3)**2)

  s = (a + b + c) / 2

  r = a * b * c / (4 * Math.sqrt(s * (s - a) * (s - b) * (s - c)))

  printf("%4.3f %4.3f %4.3f\n", px, py, r)
end

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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//==================================

template <typename _Ty>
class UnionFind {
private:
    vector<_Ty> par;
    vector<_Ty> sz;

public:
    UnionFind(_Ty N) : par(N), sz(N, 1) {
        for (_Ty i = 0; i < N; ++i) par[i] = i;
    }

    _Ty root(_Ty x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }

    bool same(_Ty x, _Ty y) {
        return root(x) == root(y);
    }

    void unite(_Ty x, _Ty y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
    }

    _Ty size(_Ty x) {
        return sz[root(x)];
    }
};

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

    int N, M;
    cin >> N >> M;
    vector<Vi> ng(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        ng[a].push_back(i);
        ng[b].push_back(i);
    }

    UnionFind<int> uf(N);
    unordered_set<int> st;
    for (const auto& p : ng[0]) {
        st.insert(p);
    }
    for (int i = 1; i < N; i++) {
        bool ok = true;
        for (const auto& p : ng[i]) {
            if (st.find(p) != st.end()) {
                ok = false;
                break;
            }
        }
        if (ok) {
            uf.unite(i - 1, i);
        }
        else {
            st.clear();
        }
        for (const auto& p : ng[i]) {
            st.insert(p);
        }
    }

    st.clear();
    for (int i = 0; i < N; i++) {
        st.insert(uf.root(i));
    }

    cout << st.size() - 1 << endl;

    return 0;
}

Measured memory_bytes: 8844
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>

using namespace std;

int main()
{
    int n, t, ans; cin >> n >> ans; --n;
    while( n -- ) { cin >> t; ans = __gcd( ans ,t); }
    cout << ans << endl;
}

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

int main(){
  int n, c, k;
  cin >> n >> c >> k;
  vector<int> t(n,0);
  rep(i, n) cin >> t.at(i);
  sort(t.begin(), t.end());
  ll ans = 0;
  int passenger = 1;
  int begin = 0, end=1;
  while(end < n){
    //cout << t.at(begin) << endl;
    if(t.at(end)-t.at(begin)<=k && passenger<c){
      passenger++;
      end++;
    }
    else{
      begin = end;
      end+=1;
      ans+=1;
      passenger = 1;
    }
    //cout << begin << endl;
  }
  ans +=1; 
  cout << ans;
  }


Measured memory_bytes: 3672
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
		long n = long.Parse(Console.ReadLine());//long.Parseはstringをlongに変換。
		long answer = 0;
    long[] nums = new long[n];
    long[] differences = new long[n-1];
    long l = 0;

    for(long i = 0; i < n; i++)
    {
      nums[i] = long.Parse(Console.ReadLine());
    }
    Array.Sort(nums);//ソート
    
    for(long i = 0; i < n-1; i++)
    {
      differences[i] = nums[i+1] - nums[i];
    }

    l = differences.Length;
    if(l % 2 == 1)
    {
      for(long i = 0; i <= l/2 - 1; i++)
      {
        answer += differences[i] * 2 * (i+1);
      }
      answer += differences[l/2] * l;
      for(long i = (l+1)/2; i < l; i++)
      {
        answer += differences[i] * 2 * (l-i);
      }
    }else
    {
      for(long i = 0; i <= l/2 - 1; i++)
      {
        answer += differences[i] * 2 * (i+1);
      }
      answer -= Math.Min(differences[l/2 - 1], differences[l/2]);
      
      for(long i = l/2; i < l; i++)
      {
        answer += differences[i] * 2 * (l-i);
      }
    }
    
		Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Measured memory_bytes: 16732
N = int(input())
d = list(map(int, input().split()))

sd = sorted(d)
leng = len(sd)
lenha = int(leng/2)
if sd[lenha-1] == sd[lenha]:
    ans = 0
else :
    ans = sd[lenha] - sd[lenha-1]

print(ans)

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

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int NN = 1e3 + 7;
const int N = 2e5 + 7;
const int M = 22;
const ll mod = 2019;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);

ll d[N];
ll m[N];

ll bnp( ll x , ll y )
{
    if( y == 0 )return 1;
    if( (y & 1) ){
        return x * bnp( x , y - 1 ) % mod;
    }else{
        ll b = bnp( x , y / 2 );
        return b * b % mod;
    }
}

void solve1()
{
    string s;
    cin >> s;
    m[0] = 1;
    s = '#' + s;
    ll ans = 0;
    for( int i = 1; i < (int)s.size(); i++ ){
        d[i] = (d[i - 1] * 10 + s[i] - '0') % mod;
        ll y = bnp( 10 , (int)s.size() - i - 1 ) * d[i - 1] % mod;
        //m[y] += 1;
        //cout << y << " ";
        y = bnp( 10 , (int)s.size() - i ) * d[i] % mod;
        ans += m[y];
        m[y] += 1;
        //cout << y << " " << m[y] << "\n";
    }
    cout << ans;
}

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

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}


Measured memory_bytes: 5264
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef pair<int,int> pii;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);v++)
#define FOR(v,a,n) for(int v=a;v<(int)(n);v++)
#define FORE(x,arr) for(auto &x:arr)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=(int)(n);v>=0;v--)
#define ALL(c) begin(c),end(c)
const int DX[4]={0,1,0,-1}, DY[4]={-1,0,1,0};
const int INF = 1e9;
const ll INFLL = 1e18;
template<class T,class U>ostream&operator<<(ostream &os,const pair<T,U> &p){
    os<<"("<<p.first<<","<<p.second<<")";return os;}
template<class T>ostream&operator<<(ostream &os,const vector<T> &v){
    ITR(i,v)os<<*i<<(i==end(v)-1?"":" ");return os;}
//------------------------------------------------------------------------------

signed main() {
    int N;
    cin>>N;
    vector<int> g1(N),g2(N),g3(N),ans(N);
    REP(i,N) {
        cin>>g1[i]>>g2[i]>>g3[i];
    }
    REP(i,N) if(count(ALL(g1),g1[i])==1) ans[i]+=g1[i];
    REP(i,N) if(count(ALL(g2),g2[i])==1) ans[i]+=g2[i];
    REP(i,N) if(count(ALL(g3),g3[i])==1) ans[i]+=g3[i];
    REP(i,N) {
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3140
S = list(input())

def func(S):
    if S[0] != 'A':
        return 'WA'

    if S[2:-1].count('C') != 1:
        return 'WA'

    for s in [s for s in S if s != 'A' and s!= 'C']:
        if s.isupper():
            return 'WA'
    
    return 'AC'

print(func(S))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rep2(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rev(i, n) for (int (i) = (n)-1; (i) >= 0; (i)--)
#define rev2(i, a, b) for (int (i) = (a)-1; (i) >= (b); (i)--)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Pll = pair<long long, long long>;
template<class T> using Vec = vector<T>;
template<class T> using VVec = vector<vector<T>>;
long long TEN(int i) {return !i ? 1 : TEN(i-1)*10LL;}
template<class T, class U> 
bool chmin(T& a, const U& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T, class U> 
bool chmax(T& a, const U& b) {if (a < b) {a = b; return 1;} return 0;}
 
struct IoSetup {
  	IoSetup() {
    	cin.tie(nullptr);
    	ios::sync_with_stdio(false);
    	cout << fixed << setprecision(10);
  	}
} iosetup;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

int N, K;
int t[100005], d[100005];

int main() {
	cin >> N >> K;
	rep (i, N) cin >> t[i] >> d[i];

	set<int> st;
	int syu = 0;
	rep (i, N) st.insert(t[i]);
	syu = st.size();

	rep (i, N) t[i]--;
	VVec<P> ho(N);
	rep (i, N) ho[t[i]].eb(d[i], 0);
	rep (i, N) sort(rrng(ho[i]));
	rep (i, N) if (ho[i].size()) ho[i][0].se = 1;
	priority_queue<P> Q;
	rep (i, N) rep (j, ho[i].size()) Q.push({ho[i][j].fi, ho[i][j].se});
	
	/*
	while (!Q.empty()) {
		auto [oi, mask] = Q.top();
		Q.pop();
		cout << oi << "  " << mask << endl;
	}
	*/

	ll ans = 0;
	int cnt = 0;
	Vec<int> ko0;
	rep (i, K) {
		auto [oi, mask] = Q.top();
		Q.pop ();
		cnt += mask;
		if (!mask) ko0.pb(oi);
		ans += oi;
	}
	ans += (ll)cnt * cnt;
	
	sort(rrng(ko0));
	ll before_ans = ans;
	rep2 (i, cnt + 1, syu + 1) {
		ll tans = before_ans;
		if (ko0.size() == 0) break;
		tans -= ko0[ko0.size() - 1];
		ko0.pop_back();
		int oi, mask = 0;
		while (!mask) {
			tie(oi, mask) = Q.top();
			Q.pop ();
		}
		tans += oi;
		tans -= (ll)(i - 1) * (i - 1);
		tans += (ll) i * i;
		chmax(ans, tans);
		before_ans = tans;
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 15132
from collections import defaultdict

import heapq
import sys

input = sys.stdin.readline

def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    d = [[float("inf")]*N for i in range(N)]
    for i in range(N-1):
        d[i][i+1] = 1
        d[i+1][i] = 1

    d[X][Y] = 1
    d[Y][X] = 1
    e = defaultdict(int)
    for i in range(N):
        for j in range(i,N):
            if i == j:
                continue
            tmp = min(j - i, abs(X-i) + 1 + abs(Y-j))
            e[tmp] += 1
    for i in range(1,N):
        print(e[i])






if __name__ == "__main__":
    main()

Measured memory_bytes: 162652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll ,P> P3;
typedef pair<P ,P> PP;
const ll MOD = ll(1e9+7);
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()



int main() {
    int n, q, cum[2][MAX_N]{};
    string s;
    cin >> n >> q >> s;
    s.push_back('#');
    REP(i,n){
        if(s[i]=='A' && s[i+1] == 'C'){
            cum[0][i+2]++;
            cum[1][i+1]++;
        }
        cum[0][i+2] += cum[0][i+1];
        cum[1][i+1] += cum[1][i];
    }

    REP(i,q){
        int l,r;
        cin >> l >> r;
        cout << cum[0][r] - cum[1][l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 1792