akhauriyash/Code-Regression huggingface dataset:
N = int(input())
L = input().split()

L_i = [int(s) for s in L]

Length = 0
sum = 0
num = 0

for i in range(N):
    sum += L_i[i]

    if L_i[i] > Length:
        Length = L_i[i]
        num = i


if Length * 2 < sum:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 typedef long long ll;
 
int main() {
ll a,b;
cin>>a>>b;
ll ans;
if(a==1&&b==1)ans=1;
else if(a==1||b==1)ans=max(a,b)-2;
else {
ans=(a-2)*(b-2);
}
cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
     
#define endl '\n'
     
using namespace std;
     
int main(){
     
  cin.tie(0); // cout と cin の同期を切る
  ios::sync_with_stdio(false); /* cの stdioストリーム (printfとか)と*/
     
     
  long long N;
     
  long long X;
     
  cin>>N>>X;
     
  int a[100001];
     
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
     
  long long ans=0;
  for(int i=0;i<N-1;i++){
     
    if(a[i]+a[i+1]>X){

      if(a[i+1]>=(a[i]+a[i+1])-X){
	ans+=(a[i]+a[i+1]-X);
	a[i+1]-=((a[i]+a[i+1])-X);
      }else{
	ans+=(a[i]+a[i+1]-X);

	a[i]-=a[i]-X;
	a[i+1]=0;

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


Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using ll = long long int;
using P = std::pair<ll, ll>;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll gcd(ll a, ll b){
	return ((b)?gcd(b,a%b):a);
}

std::vector<P> v[2];
int t[225816];
P vc[225816];
std::map<P, ll> mp[2];

ll rwpw(ll a, ll p){
	ll ret = 1ll;
	while(p){
		if(p%2){
			mul_mod(ret,a);
		}
		mul_mod(a,a);
		p /= 2;
	}
	return ret;
}

int main(void){
	int n,i,z=0;
	ll a,b,g,ans=1ll,tmp=0ll;
	std::cin >> n;
	for(i=0; i<n; ++i){
		std::cin >> a >> b;
		if(a==0 && b==0){
			t[i] = 2;
			++z;
			continue;
		}
		g = gcd(std::abs(a),std::abs(b));
		a /= g; b /= g;
		if(a>=0 && b>0){
			vc[i] = P(a,b);
			t[i] = 0;
		}else if(a>0 && b<=0){
			vc[i] = P(-b,a);
			t[i] = 1;
		}else if(a<=0 && b<0){
			vc[i] = P(-a,-b);
			t[i] = 0;
		}else{
			vc[i] = P(b,-a);
			t[i] = 1;
		}
		++mp[t[i]][vc[i]];
	}
	for(i=0; i<n; ++i){
		if(t[i]>1){
			continue;
		}
		tmp = rwpw(2ll,mp[0][vc[i]]);
		add_mod(tmp,rwpw(2ll,mp[1][vc[i]]));
		add_mod(tmp,MOD-1);
		mul_mod(ans,tmp);
		mp[0][vc[i]] = 0ll; mp[1][vc[i]] = 0ll;
	}
	add_mod(ans,MOD-1);
	if(z){
		add_mod(ans,z);
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 32320
#include <stdio.h>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main(){

	bool frontflag;
	int n, odd, i=0;
	cin >> n;
	int a[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	deque<int> b;
	b.clear();
	odd = n % 2;

	if(odd == 1) frontflag = true;
	if(odd == 0) frontflag = false;

	while(i<n){
		if(frontflag == false){
			b.push_back(a[i]);
			i++;
			frontflag = true;
		}else{
			b.push_front(a[i]);
			i++;
			frontflag = false;
		}
	}

	// for(int i=0;i<n;i++){
	// 	b.push_back(a[i]);

	// 	reverse(b.begin(), b.end());
	// }
	for(int i=0;i<n;i++) cout << b[i] << " ";
	cout << endl;

	return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll result(ll n){
  if(n==1){
    return 1;
  }
  else{
    return result(n/2)*2+1;
  }
}
int main(){
  ll a;
  cin>>a;
  cout<<result(a);
  
}

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

int main() {
  string n;

  while (cin >> n) {

    n += ".";

    int num[] = {1, 5, 10, 50, 100, 500, 1000};
    char ch[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

    int cnt = 0;
    vector<int> a;
    for (int i = 0; i < n.size(); ++i) {
      int x = 0;
      for (int j = 0; j < 7; ++j) {
        if (n[i] == ch[j]) x = num[j];
      }
      cnt += x;
      if (n[i] == n[i + 1]) continue;
      a.push_back(cnt);
      cnt = 0;
    }

    int ans = 0;
    for (int i = 0; i < a.size(); ++i) {
      if (a[i] < a[i + 1]) a[i + 1] -= a[i];
      else ans += a[i];
    }

    cout << ans << endl;
  }
}

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

int main() {
  int d;
  int c[26];
  int last[26];
  scanf("%d", &d);
  for ( int i = 0; i < 26; i++ ) {
    scanf("%d", &c[i]);
    last[i] = 0;
  }
  int s[d][26];
  for ( int i = 0; i < d; i++ ) {
    for ( int j = 0; j < 26; j++ ) {
      scanf("%d", &s[i][j]);
    }
  }

  int now = 0;
  int val = 0;
  while ( now < d ) {
    int mx = - (1e9 + 7);
    int select;
    for ( int k = 0; k < 26; k++ ) {
      int val_tmp = val;
      int now_tmp = now;
      int contest = k;
      val_tmp += s[now_tmp][contest];
      now_tmp++;
      for ( int i = 0; i < 26; i++ ) {
        if ( contest == i ) { continue; }
        val_tmp -= c[i]*(now_tmp-last[i]);
      }
      if ( val_tmp > mx ) {
        mx = val_tmp;
        select = contest;
      }
    }
    now++;
    last[select] = now;
    val = mx;
    printf("%d\n", select+1);
  }

  return 0;
}


Measured memory_bytes: 3860
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());

        long sum = n*(n+1)/2;

        long n3 = n/3;
        long sum3 = 3*(n3*(n3+1)/2);
        long n5 = n/5;

        long sum5 = 5*(n5*(n5+1)/2);

        long n15 = n/15;
        long sum15 = 15*(n15*(n15+1)/2);

        System.out.println(sum-sum3-sum5+sum15);
        System.out.flush();
    }
}

Measured memory_bytes: 26928
parseInt(x) = parse(Int,x)

function next(d,i)
  if d[i] == 1
    tmp = 0
    while tmp + i <= length(d) && d[i+tmp] == 1 
      tmp += 1
    end
    else
    tmp = 0
    while tmp+i <= length(d) && d[i+tmp] == -1 
      tmp += 1
    end
  end
  return(tmp)
end

function main()
  S = chomp(readline())
  N = length(S)
  c = zeros(Int,N)
  d = zeros(Int,N)
  for j = 1:N
    S[j] == 'R' ? d[j] = 1 : d[j] = -1
  end
  i = 1
  while i <= N 
    t = next(d,i)
    s = div(t,2)
    d[i] == 1 ? c[i+t] += s :c[i-1] += s 
    d[i] == 1 ? c[i+t-1] += t-s :c[i] += t-s
    i += t
  end
  for i = 1:(N-1)
    print(c[i]," ")
  end
  print(c[N])
end

main()

Measured memory_bytes: 140780
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define endl '\n'

const int max4 = 10004;
const int maxx = 100005;
const int max6 = 1000006;
const int lg5 = 17;

const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;

/***************/

int powmod (int a, int b, int mod) {
    int res = 1; a %= mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
    }
    return res;
}
#define ll long long
ll gcd (ll a, ll b) {
    while (b > 0) {
        ll t = a % b;
        a = b, b = t;
    }
    return a;
}

int lcm (int a, int b) {
    return (a / gcd (a, b)) * b;
}

int is_prime (int n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/******Don't forget to use long long when needed!!******/

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    long long n;
    cin >> n;
    vector <int> d;
    while (n > 0) {
        d.pb(n % 10);
        n /= 10;
    }
    int ok = 1;
    for (int i = 0; i < d.size() - 1; i++) {
        if (d[i] != 9) {
            ok = 0; break;
        }
    }
    if (ok == 1) {
        cout << d.back() + 9 * (d.size() - 1) << endl;
    } else {
        cout << d.back() + 9 * (d.size() - 1) - 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;

const int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};
int w,h;
string c[22];
int dis[22][22];
int t[20][1<<11];

int main(){
  while(cin >> w >> h, w){
    for(int i=0;i<h;i++)cin >> c[i];

    vector<pii> gomi;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(c[i][j] == 'o')gomi.push_back(pii(i,j));
      }
    }
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	if(c[i][j] == '*')gomi.push_back(pii(i,j));
      }
    }
    int num = gomi.size();
    vector<pii> g[22];

    for(int i=0;i<num;i++){
      queue<pii> q;
      q.push(gomi[i]);
      memset(dis,-1,sizeof(dis));
      dis[gomi[i].first][gomi[i].second] = 0;

      while(q.size()){
	pii p = q.front(); q.pop();
	int y = p.first, x = p.second;

	for(int d=0;d<4;d++){
	  int ny = y+dy[d], nx = x+dx[d];
	  if(ny<0 || nx<0 || ny>=h || nx>=w || c[ny][nx] == 'x')continue;
	  if(dis[ny][nx]<0){
	    dis[ny][nx] = dis[y][x] + 1;
	    q.push(pii(ny,nx));
	  }
	}
      }

      for(int j=0;j<num;j++){
	if(i==j)continue;
	if(dis[gomi[j].first][gomi[j].second]<0)continue;
	g[i].push_back(pii(dis[gomi[j].first][gomi[j].second],j));
      }
    }

    memset(t,-1,sizeof(t));
    t[0][1] = 0;

    for(int bit=0;bit<(1<<num);bit++){
      for(int v=0;v<num;v++){
	if(t[v][bit]<0)continue;
	for(int i=0;i<(int)g[v].size();i++){
	  int u = g[v][i].second, cost = t[v][bit] + g[v][i].first;
	  if( (bit>>u) & 1)continue;
	  int nb = bit|(1<<u);
	  if(t[u][nb]<0 || t[u][nb]>cost)t[u][nb] = cost;
	}
      }
    }

    int ans = 1e8;
    for(int i=0;i<num;i++){
      if(t[i][(1<<num)-1]<0)continue;
      ans = min(ans, t[i][(1<<num)-1]);
    }
    if(ans==1e8)cout << -1 << endl;
    else cout << ans << endl;
  }
}

Measured memory_bytes: 1396
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<vector>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<sstream>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

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

#define MAX 100010
int N;
ll A[MAX],B[MAX];

void compute() {
  ll cost = 0;
  for(int i=N-1;i>=0;--i) {
    A[i] += cost;
    if( A[i] % B[i] == 0 ) continue;
    ll v = A[i] / B[i];
    ++v;
    cost += ( v * B[i] - A[i] );
  }
  cout << cost << endl;
}

int main() {
  cin >> N;
  rep(i,N) cin >> A[i] >> B[i];
  compute();
  return 0;
}


Measured memory_bytes: 1920
N=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))

import  bisect
from collections import  Counter
D.sort()
T.sort()
tmpa=Counter(D)
tmpt=Counter(T)
cnt=0
for i in range(M):
    hnt=T[i]
    v=True
    if tmpt[hnt]<=tmpa[hnt]:
        continue
    else:
        v=False
        print("NO")
        exit()

if v:
    print("YES")

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

std::vector<int> take_cycle(int position, const std::vector<int>& initial, const std::vector<int>& permutation) {
	std::vector<int> result;
	int value = initial[position];
	do {
		result.push_back(value);
		value = permutation[value];
	} while (result.front() != value);
	return result;
}
std::pair<__int128_t, __int128_t> gcd_pair(const __int128_t a, const __int128_t b, const __int128_t ar = 1, const __int128_t br = 0, const __int128_t as = 0, const __int128_t bs = 1) {
	auto aa = ar * a + br * b;
	auto bb = as * a + bs * b;
	auto q = aa / bb;
	auto r = aa % bb;
	auto rr = (ar - as * q) % b * a + (br - bs * q) % a * b;
	if (r != rr) throw "???";
	if (r == 0) return std::make_pair((as % b + b) % b, (bs % a + a) % a);
	else return gcd_pair(a, b, as, bs, (ar - as * q) % b, (br - bs * q) % a);
}
__int128_t gcd(const __int128_t a, const __int128_t b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
__int128_t lcm(const __int128_t a, const __int128_t b) {
	return a / gcd(a, b) * b;
}
__int128_t solve(const std::vector<int>& initial, const std::vector<int>& permutation) {
	std::vector<bool> taken(initial.size(), false);
	__int128_t first = -1;
	__int128_t loop_length = 0;
	for (auto pos = 0; pos < initial.size(); ++pos) if (!taken[pos]) {
		auto cycle = take_cycle(pos, initial, permutation);
		auto shift = std::distance(cycle.begin(), std::find(cycle.begin(), cycle.end(), pos));
		if (shift == cycle.size()) {
			return -1;
		}
		for (auto i = 0; i < cycle.size(); ++i) {
			taken[cycle[i]] = true;
			if (initial[cycle[(i + shift) % cycle.size()]] != cycle[i]) {
				return -1;
			}
		}
		if (first < 0) {
			first = shift;
			loop_length = cycle.size();
		}
		else {
			auto g = gcd(loop_length, cycle.size());
			if (first % g != shift % g) {
				return -1;
			}
			auto pair = gcd_pair(loop_length, cycle.size());
			auto l = lcm(loop_length, cycle.size());
			auto next = ((pair.first % cycle.size() * (shift / g) % cycle.size() * loop_length % l + pair.second % loop_length * (first / g) % loop_length * cycle.size() % l + first % g) % l + l) % l;
			if (next % cycle.size() != shift || next % loop_length != first)
				throw "???";
			first = next;
			loop_length = lcm(loop_length, cycle.size());
		}
	}
	return first;
}

std::ostream& operator<<(std::ostream& os, __int128_t value) {
	if (value == -1) return os << -1;
	if (value == 0) return os << 0;
	std::vector<int> digits;
	while (value != 0) {
		digits.push_back(value % 10);
		value /= 10;
	}
	std::reverse(digits.begin(), digits.end());
	for (auto d : digits) os << d;
	return os;
}
int main() {
	int n; std::cin >> n;
	std::vector<int> initial(n), permutation(n); for (auto& p : initial) { std::cin >> p; --p; }; for (auto& p : permutation) { std::cin >> p; --p; };
	std::cout << solve(initial, permutation) << std::endl;
}


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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  string z;
  cin >> z;
  z.resize(4,'#');
  if(z == "YAKI"){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }
}


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

const long long MOD = 1000000007;

#define MAX 20000050
long long cache_f[MAX],cache_invf[MAX];
void init_cache_egced(){
    long long maxn=MAX;
    cache_f[0]=1; for (long long i=1;i<maxn;i++) cache_f[i]=cache_f[i-1]*i%MOD;
    cache_invf[0]=cache_invf[1]=1; for (long long i=2;i<maxn;i++) cache_invf[i]=MOD-(MOD/i)*cache_invf[MOD%i]%MOD;
    for (long long i=2;i<maxn;i++) cache_invf[i]=cache_invf[i-1]*cache_invf[i]%MOD;
}

long long C(long long x,long long y){
    if (y<0||y>x) return 0;
    return cache_f[x]*cache_invf[y]%MOD*cache_invf[x-y]%MOD;
}

void solve(long long H, long long W, long long K){
    init_cache_egced();
    long long ans=0;
    for(long long k = 1; k <= K; k++)
    {
        long long ret=(H*W%MOD*C(H+W-2,k-2)%MOD+(H+W)*C(H+W-1,k-1)%MOD+C(H+W,k))%MOD;
        ans=(ans+ret*cache_f[H+W-k]%MOD*cache_f[k]%MOD*cache_invf[H+W-K]%MOD)%MOD;
    }
    cout<<ans<<endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    long long K;
    scanf("%lld",&K);
    solve(H, W, K);
    return 0;
}


Measured memory_bytes: 312704
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int a[3][3];
	int n=3;
	REP(i,n){
		REP(j,n){
			cin>>a[i][j];
		}
	}
	int N;
	cin>>N;
	int b[N];
	REP(i,N){
		cin>>b[i];
	}
	for(int x:b){
		REP(i,n){
			REP(j,n){
				if(x==a[i][j]){
					a[i][j]=0;
					break;
				}
			}
		}
	}
	bool found=false;
	REP(i,n){
		if(a[i][0]+a[i][1]+a[i][2]==0){
			found=true;
		}
		else if(a[0][0]+a[1][1]+a[2][2]==0){
			found=true;
		}
		else if(a[0][i]+a[1][i]+a[2][i]==0){
			found=true;
		}
		else if(a[0][2]+a[1][1]+a[2][0]==0){
			found=true;
		}
	}
	if(found){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
d=list(input().split())
ans=n
p=0
for i in range(10*n+1):
    s=str(ans)
    for j in range(len(str(s))):
        if s[j] in d:
            break
    else:
        break
    ans+=1
print(ans)

Measured memory_bytes: 3060
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def main():
    sx,sy,ex,ey = list(map(int, input().split()))
    n = int(input())
    f = [False] * n
    a = [list(map(int, input().split())) for _ in range(n)]
    aa = [[inf]*n for _ in range(n)]
    k = [0] * n
    for i in range(n):
        ai = a[i]
        t = math.sqrt((sx-ai[0])**2 + (sy-ai[1])**2) - ai[2]
        if t <= 0:
            t = 0
        k[i] = t

    for i in range(n-1):
        ai = a[i]
        for j in range(i+1, n):
            aj = a[j]
            t = math.sqrt((aj[0]-ai[0])**2 + (aj[1]-ai[1])**2) - ai[2] - aj[2]
            if t < 0:
                t = 0
            aa[i][j] = t
            aa[j][i] = t

    while True:
        mi = -1
        mk = inf
        for i in range(n):
            if f[i]:
                continue
            if k[i] < mk:
                mk = k[i]
                mi = i
        if mi < 0:
            break

        aai = aa[mi]
        f[mi] = True
        #print('aai',mi,aai)
        #print('aaik',k)
        for j in range(n):
            if aai[j] + k[mi] < k[j]:
                k[j] = aai[j] + k[mi]

    r = math.sqrt((sx-ex)**2 + (sy-ey)**2)
    for i in range(n):
        ai = a[i]
        t = math.sqrt((ex-ai[0])**2 + (ey-ai[1])**2) - ai[2]
        if t < 0:
            t = 0
        #print('it',i,t)
        if r > k[i] + t:
            r = k[i] + t

    #print('aa',aa)
    #print('k',k)
    return r


print(main())


Measured memory_bytes: 25560
N, M = map(int, input().split())
AB = [0 for _ in range(N)]
for i in range(M):
	a, b = map(int, input().split())
	AB[a-1] += 1
	AB[b-1] += 1
for i in range(N):
	if AB[i]%2 or AB[i]%2:
		print("NO")
		exit()
print("YES")

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

const int mxN = 50;
int vis[mxN][mxN], ans[mxN];

void solve() {
    int m, n;
    read(n, m);
    
    FOR(m) {
        int a, b;
        read(a, b);
        a--;
        b--;
        ans[a]++;
        ans[b]++;
    }
    
    FOR(n) {
        print(ans[i]);
    }
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    //read(tt);
    FOR(tt) {
        
        solve();
        
    }
    
}



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

int main() {
  ll n,k;
  cin >> n >> k;
  
  n %= k;
  
  if(n * 2 > k)
    n = k - n;
  
  cout << n << endl;
}

Measured memory_bytes: 3636
import scala.io.StdIn

object Main {
	def main(args: Array[String]): Unit ={
		val S = StdIn.readLine

		val S_sub = S.substring(2, S.length - 1)
		val S_sub_WithoutC = S_sub.replace("C", "")

		val b1 = S.startsWith("A")
		val b2 = S.charAt(1).isLower
		val b3 = S_sub.contains("C") && S_sub_WithoutC.length == S_sub.length - 1
		val b4 = S_sub_WithoutC == S_sub_WithoutC.toLowerCase
		val b5 = S.charAt(S.length - 1).isLower
		
		val result = b1&& b2 && b3 && b4 && b5

		println(if(result) "AC" else "WA")
	}
}

Measured memory_bytes: 25556
N,M,C = map(int,input().split(" "))
B = input().split(" ")
B = [int(i) for i in B]
#print(B)
count = 0
for i in range(N):
    A = input().split(" ")
    A = [int(i) for i in A]
    #print(A)
    total = C
    for j in range(M):
        total += A[j] * B[j]
        #print(total)
    if total > 0:
        count += 1
print(count)

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

using namespace std;

signed main()
{
    int x,y,z,i;
    std::vector<int> Size(3);
    cin >>Size[0]>>Size[1]>>Size[2];
    rep(i,2){
    if(Size[i]>Size[i+1]) std::swap(Size[i],Size[i+1]);
    }
     cout<<Size[0]+Size[1]<<endl;
    return 0;
}


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

int main() {
    int r, d, x[11];

    cin >> r >> d >> x[0];
    for(int i = 1; i <= 10; i++) {
        x[i] = r * x[i - 1] - d;
        cout << x[i] << endl;
    }
}

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

int main() {
	int N = 0;
    cin >> N;
    
    if((N + 7)%10 == 0){
    cout << "bon";
    }
    else if((N+10)%10 == 0 || (N+9)%10 == 0 || (N+4)%10 == 0 || (N+2)%10 == 0){
    cout << "pon";
    }
    else
    cout << "hon";
}


Measured memory_bytes: 3592
#include<iostream>
#include<string>
using namespace std;
struct Dice{
  int s[6];
  void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
  }
  int top() {
    return s[0];
  }
};
int main(){
  Dice d;
  for(int i=0;i<6;i++) cin >> d.s[i];
  string s;cin >> s;
  for(int i=0;i<s.size();i++) d.roll(s[i]);
  cout << d.top() << endl;
  return 0;
}


Measured memory_bytes: 3176
n = int(input())
listP = []
i=0
while i < n:
    a, b = map(int, input().split())
    listP.append([a+b, a, b])
    i+=1
listP.sort()
listP.reverse()

takaP=0
aokiP=0
index=0
while index < len(listP):
    if index%2==0:
        takaP+=listP[index][1]
    else:
        aokiP+=listP[index][2]
    index+=1
print(takaP-aokiP)

Measured memory_bytes: 23260
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

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

typedef pair<int, int> pii;

int n, m;
vector<pii> g[10000]; // work -> syokunin , kaisuu
int b[2][10000];
int ans[10000];

int main() {
	cin >> n >> m;
	
	int s, t, e;
	while (scanf("%d %d %d", &s, &t, &e), s || t || e) {
		s--; t--;
		g[t].push_back(pii(s, e));
	}
	int l;
	cin >> l;
	REP(i, m) scanf("%d", &b[0][i]);
	REP(i, m) REP(j, g[i].size()) ans[g[i][j].first] += g[i][j].second * b[0][i];
	REP(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
	l--;
	
	while (l--) {
		REP(i, m) scanf("%d", &b[1][i]);
		REP(i, m) {
			int diff = b[1][i] - b[0][i];
			if (diff == 0) continue;
			REP(j, g[i].size()) ans[g[i][j].first] += g[i][j].second * diff;
		}
		
		REP(i, m) b[0][i] = b[1][i];
		REP(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
	}
	
	return 0;
}

Measured memory_bytes: 4264
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, m;
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n;
	if(n%2 == 1){
		print(0)
	}
	else{
		ll ans = 0;
		n /= 2;
		while(n > 0){
			ans += n/5;
			n /= 5;
		}
		print(ans)
	}
	
	return 0;
}

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

int main()
{
  ll N;
  scanf("%lld",&N);
  ll W;
  scanf("%lld",&W);
  vector<ll> w(N);
  vector<ll> v(N);
  for(int i=0; i<N; i++){
    scanf("%lld",&w[i]);
    scanf("%lld",&v[i]);
  }

  vector<vector<ll>> dp(N+1, vector<ll>(N*1000+10, 1e18));
  dp[0][0] = 0;
  for (int i=0; i<N; i++) {
    for (int j=0; j<=N*1000; j++) {
      if (j>=v[i] && dp[i][j-v[i]]!=1e18) {
        dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);
      } else {
        dp[i+1][j] = dp[i][j];
      }
    }
  }
  ll ans = 0;
  for (int i=0; i<=N*1000; i++) {
    if (dp[N][i]<=W) {
      ans = i;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> G[n*n];
    rep(i, 2*n*(n-1)){
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int ans[n][n];
    int s;
    rep(i, n*n)if(G[i].size() == 2){s = i; break;}
    ans[0][0] = s;
    bool used[n*n];
    memset(used, false, sizeof(used));
    used[s] = true;
    for(int t=G[s][0], j=1; j<n; ++j){
        ans[0][j] = t;
        used[t] = true;
        for(int nt: G[t])if(G[nt].size() <= 3 && !used[nt]) t = nt;
    }
    for(int t=G[s][1], j=1; j<n; ++j){
        ans[j][0] = t;
        used[t] = true;
        for(int nt: G[t])if(G[nt].size() <= 3 && !used[nt]) t = nt;
    }

    For(i, 1, n)For(j, 1, n){
        for(int a: G[ans[i-1][j]])for(int b: G[ans[i][j-1]])if(a == b && !used[a]){
            ans[i][j] = a;
            used[a] = true;
        }
    }

    rep(i, n){
        rep(j, n) printf("%d ", ans[i][j] + 1);
        printf("\n");
    }
}


Measured memory_bytes: 3892
#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(){
    ll a, b, n;
    ll x, y;
    cin >> a >> b >> n;
    if (n >= b){
        x = ll(double(a) * double(b-1) / double(b));
        y = a * ll(double(b - 1) / double(b));
        cout << x - y << endl;
        return 0;
    }else{
        x = ll(double(a) * double(n) / double(b));
        y = a * ll(double(n) / double(b));
        cout << x - y << endl;
        return 0;
    }
}

Measured memory_bytes: 3608
read N

[ $N -eq 1 ] &&  { echo 0; exit; }

nums=`echo $N | factor | cut -d\  -f2- | tr " " "\n" | uniq -c | awk '{for(i=1;i<=$1;i++) print $2^i}' | sort -n | tr "\n" " "  | sed "s; $;;g" `


[ ${#nums} = ${#N} ] && { echo 1; exit; }

cnt=0
for z in `echo $nums`; do
#       echo $N,$z
        [ $(($N%$z)) -eq 0 ] || continue;
        N=$(($N/$z));
        cnt=$((cnt+1))
        [ $N -lt $z ] && break;
done
echo $cnt

Measured memory_bytes: 4704
while True:
    h, w = map(int, input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):
        for j in range(w):
            if (i + j) % 2 == 0: 
                print("#", end = "")
            else:
                print(".", end = "")
        print()
    print()


Measured memory_bytes: 7004
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans=0,sum=0,n,i,a[100005],b[100005];
int main()
{
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(i=1;i<=n;i++)scanf("%lld",&b[i]),a[i]-=b[i];
	sort(a+1,a+n+1);
	for(i=1;a[i]<0&&i<=n;i++)sum-=a[i],ans++;
	for(i=n;a[i]>0&&i>0&&sum>0;i--)sum-=a[i],ans++;
	if(sum>0)printf("-1\n");
	else printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
 
  cin >> n;
 
  vector<long> h(n), ans(n);
 
  for (int i = 0; i < n; i++) cin >> h[i];
 
  ans[1] = abs(h[0] - h[1]);
  for (int i = 2; i < n; i++) {
    ans[i] = 1e9;
    for (int j = 1; j < 2 + 1; j++) {
      ans[i] = min(ans[i], abs(h[i] - h[i - j]) + ans[i - j]);
    }
  }
 
  cout << ans[n - 1];
 
  return 0;
}

Measured memory_bytes: 1792
use std::io::BufRead;
fn main() {
    let stdin = std::io::stdin();
    let mut lines: Vec<Vec<i64>> = stdin
        .lock()
        .lines()
        .map(|l| {
            l.unwrap()
                .split_whitespace()
                .map(|w| w.parse().unwrap())
                .collect()
        })
        .collect();
    let (_n, k, mut al, mut fl) = (lines[0][0], lines[0][1], lines.remove(1), lines.remove(1));
    if al.iter().sum::<i64>() <= k {
        println!("0");
        return;
    } else {
        al.sort();
        al.reverse();
        fl.sort();
        let list: Vec<_> = al.iter().zip(fl.iter()).collect();
        let mut lp: i64 = 1;
        let mut rp: i64 = 1 << 60;
        let mut mp: i64;
        while rp - lp > 1 {
            mp = (lp + rp) / 2;
            let sum: i64 = list
                .iter()
                .filter(|x| (x.0 * x.1) > mp)
                .map(|x| x.0 - (mp / x.1))
                .sum();
            if sum <= k {
                rp = mp;
            } else {
                lp = mp;
            }
        }
        println!("{}", rp);
    }
}


Measured memory_bytes: 13420
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  if(s=="Sunny")
    cout<<"Cloudy\n";
  else if(s=="Cloudy")
    cout<<"Rainy\n";
  else
    cout<<"Sunny\n";
     //is Sunny, Cloudy, or Rainy.
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653

#define N 55
#define M 25

vector<ll> restl(M);
vector<vector<ll>> conn(N, vector<ll>(N,0));
vector<vector<ll>> whitel(N, vector<ll>(N,0ll));


ll cntone(ll x){
	ll cnt = 0;
	REP(i,N) if ((x>>i)&1ll) cnt++;
	return cnt;
}

void dfs(ll nowat, ll prim, ll tot){
	//cout << nowat << " " << prim << "dfs開始" << tot << endl;
	ll ind;
	REP(i,N) if (conn[nowat][i]!=0){
		ind = conn[nowat][i];
		if (i==prim||whitel[prim][i]>0) continue;
		whitel[prim][i] = tot+ind;
		dfs(i, prim, tot+ind);
	}
}

int main(){
	ll n, a, b; cin >> n;
	REP(i,n-1){
		cin >> a >> b;
		conn[a-1][b-1] = (1ll<<i);
		conn[b-1][a-1] = (1ll<<i);
	}
	REP(j,n) dfs(j,j,0);
	ll m, u, v; cin >> m;
	REP(i,m){
		cin >> u >> v;
		restl[i] = whitel[u-1][v-1];
	}
	ll ans = (1ll<<n-1);
	FOR(i,1,(1ll<<m)-1){
		ll whitepath = 0;
		REP(j,m) if ((i>>j)%2==1) {
			//cout << i << " " << j << " " << restl[j] << endl;
			whitepath = whitepath|restl[j];
		}
		ll vari = (n-1ll-cntone(whitepath));
		//cout << "vari" << vari << endl;
		if (cntone(i)%2==1) ans-= (1ll<<vari);
		else ans += (1ll<<vari);
	}
	cout << ans << endl;
}

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

stack<int> V[1000];

int main() {
 UL N,Q;scanf("%u%u",&N,&Q);
 rep(q,Q){
  UL c; scanf("%u",&c);
  if(c==0){
   UL t; int x; scanf("%u%d",&t,&x);
   V[t].push(x);
  } else if(c==1){
   UL t; scanf("%u",&t);
   if(V[t].size()) printf("%d\n",V[t].top());
  } else if(c==2){
   UL t; scanf("%u",&t);
   if(V[t].size()) V[t].pop();
  }
 }
 return 0;
}




Measured memory_bytes: 4252
#include<bits/stdc++.h>
using namespace std;
/**
********************************************************************
******************* Author:Bisnu sarkar ****************************
********************************************************************
**/
#define ull            unsigned long long
#define ll             long long
#define pii            pair<int,int>
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second
#define endl           '\n';

int set_1(int n,int pos){return n = (n | (1<<pos));}
int reset_0(int n,int pos){return n= n & ~(1<<pos);}
bool check_bit(int n,int pos){return n = n & (1<<pos);}

int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};
const int N = (int) 1e6 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);
const double eps=1e-9;


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

    int t=1,te=0;
    // cin>>t;
    while(t--){
        int n,k,x,res=0;
        cin>>n>>k;

        for(int i=1;i<=n;++i){
            cin>>x;
            if(x>=k){
                ++res;
            }
        }
        printf("%d\n", res);


        //printf("Case %d: ",++te);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000000+7;

struct Query {
  int a,b,c,d;
};

int main() {
  long long a,b,n;
  cin >> a >> b >> n;

  long long num = min(b-1,n);

  cout << (a*num)/b - a * (num/b) << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>

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

using namespace std;
int mod = 1000000007;

string s;

int main() {
  cin >> s;
  auto N = s.size();

  vector<ll> a(N);
  vector<ll> c(N);

  ll numa = 0;
  ll comb = 1;
  a.at(0) = 0;
  for(auto i=0; i<N-1; i++) {
    if (s.at(i) == 'A') {
      numa = (numa+comb)%mod;
    }
    if (s.at(i) == '?') {
      numa = (numa*3+comb)%mod;
      comb = (comb*3)%mod;
    }
    a.at(i+1) = numa;
  }

  ll numc = 0;
  comb = 1;
  c.at(N-1) = 0;
  for(auto i=N-1; i>0; i--) {
    if (s.at(i) == 'C') {
      numc = (numc+comb)%mod;
    }
    if (s.at(i) == '?') {
      numc = (numc*3+comb)%mod;
      comb = (comb*3)%mod;
    }
    c.at(i-1) = numc;
  }

  ll ans = 0;
  rep(i, N) {
    if (s.at(i) == 'B' || s.at(i) == '?') {
      ans = (ans + a.at(i)*c.at(i))%mod;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 2048
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
    
n = int(input())
a = list(map(int, input().split()))

pre = [0]
for i in range(n - 1):
    pre.append(gcd(pre[-1], a[i]))

post = [0]
for i in range(n - 1):
    post.append(gcd(post[-1], a[n - 1 - i]))

res = 0
for i in range(n):
    res = max(gcd(pre[i], post[n - 1 - i]), res)

print(res)


Measured memory_bytes: 65380
<?php
[$N] = fscanf(STDIN, "%d");
$A = fscanf(STDIN, str_repeat("%d",$N));

$list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];
$rev = array_flip($list);

$all = array_fill(1,1000000,[]);
for($i=1;$i<=1000000;$i++){
    if(isset($rev[$i])){
       $all[$i] = [$i => 1];
    }else{
        $end = 0;
        foreach($list as $prime) {
//            $start = $i;
            if ($i % $prime === 0) {
                $value = $i / $prime;
                $all[$i] = $all[$value];
                if (isset($all[$i][$prime])) {
                    $all[$i][$prime]++;
                } else {
                    $all[$i][$prime] = 1;
                }
                $end = 1;
                break;
            }
        }
        if($end === 0){
            $all[$i][$i] = 1;
        }

    }

}
$ans = [];
$pp = 0;
$ok = -1;
foreach($A as $no => $value){
    if($no !== 0){
        $ok = 0;
    }
    if($value === 1){
        continue;
    }
    foreach($all[$value] as $key => $data){
        if(isset($ans[$key])){
//            echo $key;
            $pp = 1;
            $ans[$key]++;
            if($ans[$key] === $no+1){
                $ok = 1;
            }
        }else{
            $ans[$key] = 1;
        }
    }
    if($ok === 0 && $pp == 1){
        echo "setwise coprime";
        exit;
    }
}
if($ok === 1){
    echo "not coprime";
}elseif($pp===1){
    echo "setwise coprime";
}else{
    echo "pairwise coprime";
}

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

int main() {

    int n, m;
    cin >> n >> m;
    vector< int > one;
    vector< bool > via(n + 1, false);
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if(a == n) via[b] = true;
        if(b == n) via[a] = true;
        if(a == 1) one.push_back(b);
        if(b == 1) one.push_back(a);
    }

    for(int i = 0; i < one.size(); i++) {
        if(via[one[i]]) {
            cout << "POSSIBLE" << endl;
            exit(0);
        }
    }
    cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 896
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int main(){
  ll N, a;
  cin >> N;
  vector<ll> A;
  for(int i=0; i<3*N; ++i) {
    cin >> a;
    A.emplace_back(a);
  }

  multiset<ll> min(A.begin(), A.begin()+N), max(A.end()-N, A.end());

  //min.sort();
  //max.sort();

  vector<ll> S_l{0}, S_r{0};
  for(int i=0; i<N; ++i){
    S_l[0]+=A[i];
    S_r[0]+=A[2*N+i];
  }

  ll s_l, s_r;
  auto ptr_min = min.begin();
  auto ptr_max = --max.end();
  for(int i=0; i<N; ++i) {
    a = A[N+i];
    if (a <= *ptr_min){
      s_l = a;
    }else{
      s_l = *ptr_min;
      //auto ptr_insert = min.lower_bound(a);
      min.insert(a);
      ++ptr_min;
    }
    S_l.emplace_back(S_l[i] + a - s_l);

    a = A[2*N-i-1];
    if (a >= *ptr_max){
      s_r = a;
    }else{
      s_r = *ptr_max;
      //auto ptr_insert = max.upper_bound(a);
      max.insert(a);
      --ptr_max;
    }
    S_r.emplace_back(S_r[i] + a - s_r);
  }

  ll ans = S_l[0]-S_r[N];
  for(int i=1; i<N+1; ++i) {
    if(S_l[i]-S_r[N-i] > ans) ans = S_l[i]-S_r[N-i];
  }

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

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

int main(void){
    int d[4];
    string s;
    cin>>s;
    rep(i,4) d[i] = s[i] - '0';
    char op[2] = {'+','-'};
    int sign[2] = {+1,-1};
    rep(i,2)rep(j,2)rep(k,2){
        if(d[0] + sign[i]*d[1] + sign[j]*d[2] + sign[k]*d[3] == 7) {
            printf("%d%c%d%c%d%c%d=7\n",d[0],op[i],d[1],op[j],d[2],op[k],d[3] );
            return 0;
        }
    }
}


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

int main()
{
  int64_t a, b, k;
  cin >> a >> b >> k;
  
  if (a >= k)
    cout << a - k << " " << b << endl;
  else if (a + b >= k)
    cout << 0 << " " << a + b - k << endl;
  else
    cout << 0 << " " << 0 << endl;

  return 0;
}

Measured memory_bytes: 256
/*
 * AtCode Beginner Contest 132 : C.Divide the Problems
 * Author : anaksoleh
 * 25 August 2019
 *
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N;

int main()
{
	vector<int> d;

	cin >> N;

	int num;
	for(int i = 1 ; i <= N ; i++){
		cin >> num;
		d.push_back(num);
	}

	sort(d.begin(),d.end());

	int left = d[(N/2) - 1];
	int right = d[(N/2) ];

	cout << right - left << '\n';

	return 0;
}

Measured memory_bytes: 892
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.math.*;


public class Main {
    static class sol{
        public static void solve(InputReader in,PrintWriter out) {
            int n=in.nextInt();
            String s1=in.next();
            String s2=in.next();
            String res="";
            for(int i=0;i<n;i++){
                res+=s1.charAt(i);
                res+=s2.charAt(i);
            }
            out.print(res);
        }
    }
    public static void main(String[] args) throws FileNotFoundException {
          InputStream input=System.in;
//        InputStream input=new FileInputStream(new File("src//input.in"));
        InputReader in=new InputReader(input);
        OutputStream output=System.out;
        PrintWriter out=new PrintWriter(output);
        sol a=new sol();
        a.solve(in,out);
        out.close();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public boolean hasNext() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    return false;
                }
            }
            return true;
        }

        public String next() {
            if (hasNext())
                return tokenizer.nextToken();
            return null;
        }

        public String nextLine() {
            if (hasNext())
                return tokenizer.nextToken("");
            else
                return null;
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }

        public BigDecimal nextBigDecimal() {
            return new BigDecimal(next());
        }
    }
}


Measured memory_bytes: 21716