akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.lang.Math;
public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        if( Character.isUpperCase( str.charAt( 0 ) ) ) {
            System.out.println( "A" );
        }
        else {
            System.out.println( "a" );
        }
    }
}


Measured memory_bytes: 35632
#include <stdio.h>
int n,i,A[2000];
int solve(int,int);
int main(){
  int m[2000],q;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)
    scanf("%d",&m[i]);
  for(i=0;i<q;i++){
    if(solve(0,m[i])==1)
      printf("yes\n");
    else printf("no\n");
  }
  return 0;
}
int solve(int i,int m){
  int res;
  if(m==0)
    return 1;//真                                                               
  if(i>=n)
    return 0;//負                                                               
  res=solve(i+1,m)||solve(i+1,m-A[i]);
  return res;
}




Measured memory_bytes: 2104
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
bool is_contains(const std::string& word, const std::string& target) {
	for (auto i = 0; i + target.size() <= word.size(); ++i) {
		bool contains = true;
		for (auto j = 0; j < target.size(); ++j) {
			if (word[i + j] != target[j]) {
				contains = false;
				break;
			}
		}
		if (contains) return true;
	}
	return false;
}
int max_common_suffix(const std::string& prev, const std::string& last) {
	for (int i = std::max(0, (int)prev.size() - (int)last.size()); i < prev.size(); ++i) {
		bool is_match = true;
		for (auto j = i; j < prev.size(); ++j) {
			if (prev[j] != last[j - i]) {
				is_match = false;
				break;
			}
		}
		if (is_match) return prev.size() - i;
	}
	return 0;
}
int main() {
	std::cin.tie(0); std::cin.sync_with_stdio(false);
	while (true) {
		int n; std::cin >> n; if (n == 0) break;
		std::vector<std::string> raw_words(n); for (auto& w : raw_words) std::cin >> w;
		std::vector<std::string> words;
		for (auto i = 0; i < raw_words.size(); ++i) {
			bool contains = false;
			for (auto j = 0; j < raw_words.size(); ++j) if (i != j) {
				if (is_contains(raw_words[j], raw_words[i])) {
					contains = true;
					break;
				}
			}
			if (!contains) {
				words.push_back(raw_words[i]);
			}
			else {
				--n;
			}
		}
		std::vector<std::vector<int>> additional_suffix(n, std::vector<int>(n, 0));
		for (auto i = 0; i < n; ++i) for (auto j = 0; j < n; ++j) if (i != j) {
			additional_suffix[i][j] = words[j].size() - max_common_suffix(words[i], words[j]);
		}
		std::vector<std::vector<int>> min_length(1 << n, std::vector<int>(n, INT_MAX));
		for (auto i = 0; i < n; ++i) {
			min_length[1 << i][i] = words[i].size();
		}
		for (auto pattern = 1; pattern < min_length.size(); ++pattern) for (auto from = 0; from < n; ++from) if ((pattern & (1 << from)) != 0) {
			for (auto to = 0; to < n; ++to) if (from != to && (pattern & (1 << to)) == 0) {
				min_length[pattern | (1 << to)][to] = std::min(min_length[pattern | (1 << to)][to], min_length[pattern][from] + additional_suffix[from][to]);
			}
		}
		std::cout << *std::min_element(min_length.back().begin(), min_length.back().end()) << '\n';
	}
}


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

int main() {
  int n;
  cin >> n;
  int c = 0;
  for(int i = 1; i <= n; i++){
    int a = 0;
    for(int j = 1; j <= i; j++){
      if(i % j == 0)
        a++;
    }
    if(a == 8 && i % 2 == 1)
      c++;
  }
  cout << c << endl;
}

Measured memory_bytes: 256
/*@author hussein zayed ;
    ___  ___
   |\  \|\  \
   \ \  \_\  \
    \ \   ___ \USSEIN
     \ \  \\ \ \
      \ \__\\ \_\
       \|__| \|__|
****************************************
*/

#include <bits/stdc++.h>
using namespace std;
#define fr for(int i=0;i<n;++i)
#define fr1 for(int i=1;i<=n;++i)
#define cinA for(int i=0;i<n;++i){cin>>arr[i];}
#define cinA1 for(int i=1;i<=n;++i){cin>>arr[i];}
#define coutA for(int i=0;i<n;++i){cout<<arr[i]<<" ";}
#define ll long long
#define lnarray sizeof(arr)/sizeof(*arr)
#define vi vector<int>
#define vs vector<string>
void Fast()
{
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}
inline int RD()
{
    int i ;
    cin>>i;
    return i;
}

inline float RF()
{
    float i ;
    cin>>i;
    return i;
}

inline double RDO()
{
    double i ;
    cin>>i;
    return i;
}

inline string RS()
{
    string i ;
    cin>>i;
    return i;
}

inline ll RLL()
{
    ll i ;
    cin>>i;
    return i;
}

int cm[200000];

ll sumSet(ll n)
{
    return (1ll*n*(n+1))/2;
}
string s;


bool isPrime(int n)
{
    if(n==1)
        return false;
    for(int i=2; i*i<=n; ++i)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int sumDigit(int n){
int sum =0;
  while (n != 0)
    {
        sum+= + n % 10;
        n = n / 10;
    }
    return sum;
}

ll power2(int n){
  ll ans=(1<<n);
  return ans;
}

ll sumpow2(ll n){
 ll sum=(n*(n+1)*(2*n-1))/6;
 return sum;
}
map<int ,int> mp;
vi vr;
int main(){
    Fast();
//freopen("output.txt" , "w" , stdout);
//freopen("wall.in" , "r" , stdin);
int A=RD(), B=RD(), C=RD(), D=RD();
	
	int cont = 0;
	for (int i = 0; i <= 100; i++){
	if (A < i && B >= i && C < i && D >= i) {
			cont++;
		}}
	cout<<cont;
}


Measured memory_bytes: 256
S = input()
maxLength = 0
start, flag = -1, False
for i in range(len(S)):
    if S[i] in {"A", "G", "C", "T"}:
        if not flag:
            flag = True
            start = i
    else:
        if flag:
            maxLength = max(maxLength, i - start)
            flag = False
if flag: maxLength = max(maxLength, len(S) - start)
print(maxLength)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ff(i,n) for(i=0;i<n;i++)
#define ll long long int
#define pb push_back
#define mp make_pair
ll bg=998244353;
ll power(ll x,ll y)
{
	ll ss=1;
	if(y==0)
	return ss;
	ll h=(power(x,y/2))%bg;
	h=(h*h)%bg;
	ll gg=(x*h)%bg;
	if(y%2==1)
	 return gg;
	else
	 return h;
}
ll modinv(ll k)
{
	return (power(k,bg-2))%bg;
}
ll dp[500001];
int main()
{
    ll a[3]={0},b,c,i;
    string f;
	cin>>f;
	for(i=0;i<3;i++)
	{
		a[f[i]-'A']++;
	}	   	  	  	
	if(a[0]>0 && a[1]>0)
	   cout<<"Yes";
	else
	   cout<<"No";   
    return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  if(a % 2 == 0 || b % 2 == 0){
    cout << "Even" << endl;
    return 0;
  }
  cout << "Odd" << endl;
}

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

const ll MAXN = 200000;
const ll INF = 1001001001;

ll H, W, D, Q, ans=0, tmp=0;
vector<vector<ll>> A,S;
vector<pair<ll,ll>> P;

signed main(){
    cin >> H >> W >> D;
    P.resize(H*W);
    S.resize(D);
    for(int i=0;i<D;i++) {
        S[i].resize(H*W/D+1,0);
    }
    for(int i=0;i<H;i++) {
        for(int j=0;j<W;j++) {
            ll a;
            cin >> a;
            a--;
            P[a] = make_pair(i,j);
        }
    }
    for(int i=0;i<D;i++) {
        for(int j=i+D;j<H*W;j+=D) {
            S[i][(j-i)/D] += S[i][(j-i-D)/D] + abs(P[j].first-P[j-D].first) + abs(P[j].second-P[j-D].second);
        }
    }
    cin >> Q;
    for(int i=0;i<Q;i++) {
        ll l, r;
        cin >> l >> r;
        l--;
        r--;
        cout << S[l%D][(r-r%D)/D]-S[l%D][(l-l%D)/D] << endl;
    }
    return 0;
}

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

int main() {
  int W, H;
  cin >> W >> H;
  vector<ll> P(W), Q(H);
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
  rep(i, W) { cin >> P[i]; que.push(make_pair(P[i], 0)); }
  rep(i, H) { cin >> Q[i]; que.push(make_pair(Q[i], 1)); }
  ll ans = 0;
  int cntP=H+1, cntQ=W+1;
  while(!que.empty()) {
    auto top = que.top();
    que.pop();
    if(top.second == 0) {
      ans += top.first * cntP;
      cntQ--;
    } else {
      ans += top.first * cntQ;
      cntP--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8048
//>>>>>>>>>>>>>>>>>>>>>>>>>>JAI BAJRANG BALI<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<//
//😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😇😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😝😝😝😝😝😝😝😝😝😝😝😝😝😂😂😂😂😂😂😂😜😜😜😜😜😜😜😜😜😜😜
#define HARSH_JUDGE
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define db(x)                   cout<<#x<<"="<<x<<'\n'
#define db2(x,y)                 cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ull unsigned long long
#define setbits(x)      __builtin_popcountll(x)
#define str string
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fo(i,a,n) for(ll i=a;i<n;i++)
#define forr(i,n,a) for(ll i=n;i>=a;i--)
#define cases   long long t;cin>>t;while(t--)
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define ff first
#define ss second
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))
#define sp(x,y)         fixed<<setprecision(y)<<x
#define nl '\n'
#define sz(x) ((int)(x).size())
const int mod = (int) 1e9 + 7 ;
const int MOD = (int) 998244353 ;
const int INF = (int) 1e18 ;
const ll N = 1e5 + 5;
#define printall(a) fo(i,0,a.size()) cout<<a[i]<<" "; cout<<endl;



typedef vector<int> vi;
typedef map<ll, ll> mll;
typedef set<int> si;
typedef unordered_set<int> usi;
typedef map<ll, int> mli;
typedef map<char, int> mci;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef vector<vector<int> > vv;

bool cmp(const pair<ll, ll>& a, const pair<ll, ll>& b)
{

	return a.ss < b.ss;
}

// >>>>>>>>>>>>>>>>>>>>>>>>>>TOR DE DUSHMAN KI NALI<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<//

void solve()
{

	ll n, cnt = 0;
	cin >> n;
	ll a[n];
	fo(i, 0, n)
	cin >> a[i];
	fo(i, 0, n - 1)
	{
		if (a[i] > a[i + 1])cnt += a[i] - a[i + 1], a[i + 1] = a[i];
	}
	cout << cnt;


	return;
}

int main()
{	fio
#ifndef HARSH_JUDGE
	freopen("inputf.in", "r", stdin);
	freopen("outputf.in", "w", stdout);
#endif
	ll t = 1;
	// cin >> t;
	// clock_t timest = clock();
	// cerr << "[Executes in " << (double)(clock() - timest) / CLOCKS_PER_SEC << "s]" << endl;
	while (t--)
	{
		solve();

	}
}

Measured memory_bytes: 5152
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

int n, q;
string s;
int k;
LL cntd, cntm, durm[1010101], l, r, cnt;

int main(){
	cin >> n;
	cin >> s;
	cin >> q;
	REP(qqq, q){
		cntd = 0;
		cntm = 0;
		l = r = 0;
		cnt = 0;
		LL ans = 0;
		REP(i, 1010101)durm[i] = 0;
		cin >> k;
		REP(i, n){
			if(s[i] == 'D'){
				cntd++;
				r++;
			}
			if(s[i] == 'M'){
				cnt += cntd;
				cntm++;
				durm[r]++;
			}
			if(s[i] == 'C'){
				ans += cnt;
			}
			if(i - k + 1 >= 0){
				if(s[i - k + 1] == 'D'){
					cntd--;
					cntm -= durm[l];
					l++;
					cnt -= cntm;
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 9220
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll n,m,a[101],dp[101][100001];
const ll MOD=1e9+7;

int main()
{Tie
	cin>>n>>m,dp[0][0]=1;
	for(int i=1;i<=n;i++)
		cin>>a[i],dp[i][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=(dp[i][j-1]+dp[i-1][j])%MOD;
			if(j-a[i]>0)
				dp[i][j]=((dp[i][j]-dp[i-1][j-a[i]-1])%MOD+MOD)%MOD;
		}
	}
	cout << dp[n][m]<<'\n';
}

Measured memory_bytes: 78336
import sys
sys.setrecursionlimit(200002)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, input().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))
X = [None] * N


def dfs(u):
    global X, G
    for w, d in G[u]:
        if X[w] is None:
            X[w] = X[u] + d
            if not dfs(w):
                return False
        else:
            if X[w] != X[u] + d:
                return False

    return True


flag = True
for i in range(N):
    if X[i] is None:
        X[i] = 0
        flag &= dfs(i)

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

Measured memory_bytes: 128900
def istriangle(a,b,c):
    if(a==b or b==c or c==a):
        return False
    
    elif(max(a,b,c)>= a+b+c - max(a,b,c)):
        return False
    
    else:return True
        

n = int(input())

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

count=0

for i in range(len(l)-2):
    for j in range(i+1,len(l)-1):
        for z in range(j+1,len(l)):
            if(istriangle(l[i],l[j],l[z])==True):
                count+=1
                #print(i+1,j+1,z+1)
                
print(count)
            
        


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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> v_s(n + 1);
    vector<int> v_wa(n + 1);
    int cnt_wa = 0;
    int cnt_ac = 0;
    rep(i, m)
    {
        int p;
        string s;
        cin >> p >> s;
        if (v_s[p] == -1)
            continue;
        if (s == "WA")
        {
            v_wa[p] += 1;
            v_s[p] = 1;
        }
        else
        {
            cnt_ac += 1;
            cnt_wa += v_wa[p];
            v_s[p] = -1;
        }
    }

    cout << cnt_ac << " " << cnt_wa << endl;
    return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))
bfr_A = sum(A)
B = list(map(int, input().split()))

for i in range(N):
    if A[i] <= B[i]:
        tmp = A[i]
        A[i] = 0
        if A[i + 1] < B[i] - tmp:
            A[i + 1] = 0
        else:
            A[i + 1] -= B[i] - tmp
    else:
        A[i] -= B[i]
print(bfr_A - sum(A))

Measured memory_bytes: 18624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char i,ans;
  cin>>i;
  if(i=='A'){
    ans='T';
  }
  if(i=='T'){
    ans='A';
  }
  if(i=='G'){
    ans='C';
  }
  if(i=='C'){
    ans='G';
  }
  cout<<ans;
}

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

void test_case(){
    
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    ll n, a, b;
    cin >> n >> a >> b;
    
    ll res = (n/(a+b))*a;
    
    res += min(a, n%(a+b));
    cout<<res<<endl;
    
	return 0;
}






Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,k;
  cin>>n>>k;
  int x[n];
  for(int i=0;i<n;i++) cin>>x[i];
  int ans=0;
  for(int i=0;i<n;i++)
    ans+=min(x[i],k-x[i])*2;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int n, m;
    scan(n, m);
    auto c = readln.split.to!(int[]);
    auto dp = new int[](n + 1);
    dp[] = inf;
    dp[0] = 0;
    foreach (i ; 1 .. n + 1) {
        foreach (j ; 0 .. m) {
            if (i - c[j] >= 0) chmin(dp[i], dp[i - c[j]] + 1);
        }
    }
    auto ans = dp[n];
    writeln(ans);
}



















void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}



Measured memory_bytes: 2492
from collections import Counter

S = list(input())
T = [int(S[len(S)-1])]
k = int(S[len(S)-1])
for i in range(len(S)-2,-1,-1):
    k = (int(S[i])*pow(10,len(S)-i-1,2019) + k ) % 2019
    T.append(k)

A = Counter(T)
ans = 0
ans += A.get(0,0)
for i in A.values():
    ans += i*(i-1)//2
print(ans)

Measured memory_bytes: 96828
a, b, c, k = map(int, input().split())
ans = min(k, a)
k = max(k-ans, 0)

if k!=0:
	x = min(k, b)
	k = max(k-x, 0)

if k!=0:
	x = min(k, c)
	ans += (-1*x)

print(ans)

Measured memory_bytes: 61568
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
string S, T;
const int Qmax = 1e5;
int Q;

int main(){
	cin >> S >> T >> Q;
	vector<int> ns(S.size()+1), nt(T.size()+1);
	for(int i=0; i<S.size(); i++) ns[i+1] = ns[i]+(S[i]=='A'?1:0);
	for(int i=0; i<T.size(); i++) nt[i+1] = nt[i]+(T[i]=='A'?1:0);

	for(int i=0; i<Q; i++){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int x = b-a+1 - 2*(ns[b]-ns[a-1]);
		int y = d-c+1 - 2*(nt[d]-nt[c-1]);
		if((x+300000)%3==(y+300000)%3) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}


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

#define W_MAX 50
#define H_MAX 50


using namespace std;

int map[H_MAX][W_MAX];
int zyo[H_MAX][W_MAX];
int w,h;
int flag;

void solve(int H,int W){
	int dx[4]={-1,1,0, 0};
	int dy[4]={ 0,0,1,-1};
	/*cout<<H<<","<<W<<","<<map[H][W]<<","<<zyo[H][W]<<","<<flag<<endl;*/
	for(int a=0;a<4;a++){
			if(H+dx[a]<0||H+dx[a]>=h) continue;
			if(W+dy[a]<0||W+dy[a]>=w) continue;
			if(zyo[H+dx[a]][W+dy[a]]==-1&&map[H+dx[a]][W+dy[a]]==0){
				zyo[H+dx[a]][W+dy[a]]=3;
				solve(H+dx[a],W+dy[a]);
			}
			else if(map[H+dx[a]][W+dy[a]]==1){
				if(flag==-1) flag=1;
				if(flag==2) flag=0;
			}
			else if(map[H+dx[a]][W+dy[a]]==2){
				if(flag==-1) flag=2;
				if(flag==1) flag=0;
		}
	}
	return;
}

int main(void){

	char tmp;
	int bc,wc;

	while(1){
			memset(map,-1,sizeof(map));
			memset(zyo,-1,sizeof(zyo));
			bc=0,wc=0;

			cin>>w>>h;
			if(w==0&&h==0) break;
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					cin>>tmp;
					switch(tmp){
					case '.':
						map[i][j]=0;
						zyo[i][j]=-1;
						break;
					case 'B':
						map[i][j]=1;
						zyo[i][j]=0;
						break;
					case 'W':
						map[i][j]=2;
						zyo[i][j]=0;
						break;
					}
				}
			}

		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(zyo[i][j]==-1){
					zyo[i][j]=3;
					flag=-1;
					solve(i,j);
					for(int k=0;k<h;k++){
						for(int l=0;l<w;l++){
							if(zyo[k][l]==3) zyo[k][l]=flag;
						}
					}
				}
			}
		}

		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				//cout<<zyo[i][j];
				if(zyo[i][j]==1) bc++;
				else if(zyo[i][j]==2) wc++;
			}
			//cout<<endl;
		}
		cout<<bc<<" "<<wc<<endl;
	}
	return 0;
}

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

int main(){
    int X,Y;
    cin >> X >> Y;
    if(2*X<=Y && Y<=4*X && Y%2==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 3704
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

// ceil of a/b
inline int ceil(int a, int b) { return (a+b-1)/b; }


signed main() {
	int n;
	std::cin >> n;
	print(ceil(n,2));
	return 0;
}


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

int main() {
  int H, W;
  
  cin >> H >> W;

  vector<string> S(H);
  vector<vector<int>> dp(H, vector<int> (W));


  rep(i,H){
    cin >> S.at(i);
  }

  rep(i,H){
    vector<int> done(W);
    rep(j,W){
      if(S.at(i).at(j) == '#') continue;
      if(done.at(j) == 1) continue;

      int p = 0;
      while(j+p < W){
        if(S.at(i).at(j+p) == '#') break;
        p++;
      }
      rep(k,p){
        dp.at(i).at(j+k) += p;
        done.at(j+k) = 1;
      }
    }
  }

  rep(j,W){
    vector<int> done(H);
    rep(i,H){
      if(S.at(i).at(j) == '#') continue;
      if(done.at(i) == 1) continue;

      int p = 0;
      while(i+p < H){
        if(S.at(i+p).at(j) == '#') break;
        p++;
      }
      rep(k,p){
        dp.at(i+k).at(j) += p;
        done.at(i+k) = 1;
      }
    }
  }

  int res = 0;
  rep(i,H){
    rep(j,W){
      res = max(res, dp.at(i).at(j)-1);
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 22016
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K,p[1000];
  cin >> N >> K;
  for(int i=0;i<N;i++){
    cin >> p[i];
  }
  sort(p,p + N);
  int ans = 0;
  for(int i=0;i<K;i++){
    ans += p[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 3640
s = input()

def fun(s):
    n = len(s)
    ans = 0
    for bit in range(1 << (n-1)):
        f = s[0]
        for i in range(n-1):
            if bit & (1 << i):
                f += "+"
            f += s[i+1]
        ans += sum(map(int, f.split('+')))

    return ans

print(fun(s))

Measured memory_bytes: 41324
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
#define MOD9 998244353
#define intMAX 51000;
#define PI 3.14159265359
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int main(){
	int N, M, X, Y;
	cin >> N >> M >> X >> Y;
	int maxx = -101;
	int miny = 101;
	for(int i=0; i<N; ++i){
		int x;
		cin >> x;
		maxx = max(maxx, x);
	}
	for(int i=0; i<M; ++i){
		int y;
		cin >> y;
		miny = min(miny, y);
	}
	maxx = max(maxx, X);
	miny = min(miny, Y);
	if(maxx<miny) cout << "No War" << endl;
	else cout << "War" << endl;
}

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

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

int calc(int x, int[] a) {
    a.sort();
    int ans = 0;
    for (int i = 0; i < a.length; i++) {
        if (x >= a[i]) {
            ans++;
            x -= a[i];

            if (i == a.length - 1) {
                if (x > 0) ans--;
            }
        }
        else break;
    }
    return ans;
}

void main() {
    auto nx = readints;
    int x = nx[1];
    auto a = readints;

    writeln(calc(x, a));
}


Measured memory_bytes: 256
import numpy as np
N, D = map(int, input().split())
L = [list(map(int,input().split())) for i in range(N)]
L = np.array(L)
count = 0
for j in range(N):
    dis = np.linalg.norm(L[j])
    if dis <= D:
        count+=1
print(count)

Measured memory_bytes: 66584
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<61;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

map<int,int> Prime_Factor(int n){
	map<int,int> m;
	for(int i=2;i*i<=n;i++){
		while(n%i==0){
			m[i]++;
			n/=i;
		}
	}
	if(n!=1) m[n]++;
	return m;
}

const int N=7;

int n,S;
vi x,a;
map<int,int> m[300],pm;

int dfs(int I,vi& b){
	if(b.size()==N){
		vi c(S);
		int res=0;
		for(int i=0;i<n;i++){
			bool B=1;
			int ind=-1;
			for(auto j=m[i].begin();j!=m[i].end();j++){
				int key=j->first,num=j->second,J=pm[key];
				if(J<N){
					if(b[J]<num) B=0;
				}
				else ind=J;
			}
			if(B){
				if(ind==-1) res+=x[i];
				else c[ind]+=x[i];
			}
		}
		for(int i=N;i<S;i++) if(c[i]>0) res+=c[i];
		return res;
	}
	int res=-inf,t=1,num=0;
	do{
		b.push_back(num);
		res=max(res,dfs(I+1,b));
		b.pop_back();
		t*=a[I];
		num++;
	}while(t<=300);
	return res;
}

int main(){
	cin>>n;
	x=vi(n);
	for(int i=0;i<n;i++){
		int M;
		cin>>M>>x[i];
		m[i]=Prime_Factor(M);
	}
	for(int i=2;i<=300;i++){
		bool B=1;
		for(int j=2;j*j<=i;j++) if(i%j==0) B=0;
		if(B){
			pm[i]=a.size();
			a.push_back(i);
		}
	}
	S=a.size();
	vi t;
	cout<<dfs(0,t)<<endl;
}

Measured memory_bytes: 384
#include<iostream>
#define INF 2000000000
typedef struct{
  char c;
  int n;
}data;
int partition(data*,int,int);
void quickSort(data*,int,int);
void merge(int*,int,int,int);
void mergeSort(data*,int,int);
int main(){
  int n;
  std::cin>>n;
  data A[n],B[n];
  for(int i=0;i<n;i++){
    std::cin>>A[i].c>>A[i].n;
    B[i]=A[i];
  }
  quickSort(A,0,n-1);
  mergeSort(B,0,n);
  bool stable=true;
  for(int i=0;i<n;i++){
    if(A[i].c!=B[i].c){
      stable=false;
      break;
    }
  }
  std::cout<<(stable?"Stable\n":"Not stable\n");
  for(int i=0;i<n;i++) std::cout<<A[i].c<<" "<<A[i].n<<"\n";
  return 0;
}
int partition(data *A,int p,int r){
  int i=p-1;
  data tmp,x=A[r];
  for(int j=p;j<=r-1;j++){
    if(A[j].n<=x.n){
      i++;
      tmp=A[i];
      A[i]=A[j];
      A[j]=tmp;
    }
  }
  tmp=A[i+1];
  A[i+1]=A[r];
  A[r]=tmp;
  return i+1;
}
void quickSort(data *A, int p, int r){
  int q;
  if(p < r){
    q = partition(A, p, r);
    quickSort(A, p, q-1);
    quickSort(A, q+1, r);
  }
}
void merge(data *A,int l,int m,int r){
  int n1=m-l,n2=r-m, i, j;
  data L[n1+1],R[n2+1];
  for(i=0;i<n1;i++) L[i]=A[l+i];
  for(i=0;i<n2;i++) R[i]=A[m+i];
  L[n1].n=R[n2].n=INF;
  i=j=0;
  for(int k=l;k<r;k++){
    if(L[i].n<=R[j].n){
      A[k]=L[i];
      i++;
    }
    else{
      A[k]=R[j];
      j++;
    }
  }
}
void mergeSort(data *A,int l,int r){
  int m;
  if(l+1<r){
    m=(l+r)/2;
    mergeSort(A,l,m);
    mergeSort(A,m,r);
    merge(A,l,m,r);
  }
}

Measured memory_bytes: 5436
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)


num_balls, final_int = map(int,input().split())
balls = list(map(int,input().split()))
ball = balls[0]
for i in balls:
    ball = gcd(ball,i)

if final_int % ball==0 and final_int <= max(balls):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

const int N=100009;
int n,fa[N],deg[N],stk[N],mdep[N],dep[N],top;
int to[N<<1],nxt[N<<1],beg[N],ans[N],ans2[N],tot;

inline void add(int u,int v)
{
	to[++tot]=v;
	nxt[tot]=beg[u];
	beg[u]=tot;
	deg[v]++;
}

inline void dfs(int u)
{
	mdep[u]=dep[u];
	for(int i=beg[u];i;i=nxt[i])
		if(to[i]!=fa[u])
		{
			dep[to[i]]=dep[u]+1;
			fa[to[i]]=u;
			dfs(to[i]);
			mdep[u]=max(mdep[u],mdep[to[i]]);
		}
}

int main()
{
	if(fopen("vj.in","r"))
	{
		freopen("vj.in","r",stdin);
		freopen("vj.out","w",stdout);
	}
	
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}

	dfs(dep[1]=1);
	int maxv=0;top=0;
	for(int i=1;i<=n;i++)
		if(dep[i]>maxv)
			stk[top=1]=i,maxv=dep[i];
		else if(dep[i]==maxv)
			stk[++top]=i;
	
	int lp=stk[1];
	for(int i=1;i<=n;i++)
		dep[i]=fa[i]=0;
	
	dep[lp]=1;
	dfs(lp);

	maxv=top=0;
	for(int i=1;i<=n;i++)
		if(dep[i]>maxv)
			stk[top=1]=i,maxv=dep[i];
		else if(dep[i]==maxv)
			stk[++top]=i;
	int rp=stk[1];

	for(int u=1;u<=n;u++)
		if(deg[u]>=3)
		{
			int cnt=0;
			for(int i=beg[u];i;i=nxt[i])
				if(to[i]!=fa[u] && mdep[to[i]]>dep[u]+1)
					cnt++;
			if(cnt==2)
				return puts("-1"),0;
		}

	top=0;
	for(int i=rp;i!=lp;i=fa[i])
		stk[++top]=deg[i];
	stk[++top]=deg[lp];

	if(1<top)
	{
		stk[1]--;
		stk[top]--;
	}
	for(int i=2;i<top;i++)
		stk[i]-=2;

	int atop=0;
	for(int i=1;i<=top;i++)
	{
		if(stk[i]==0)
		{
			atop++;
			ans[atop]=atop;
		}
		else
		{
			int cur=atop+1;
			for(int j=1;j<=stk[i];j++)
			{
				atop++;
				ans[atop]=atop+1;
			}
			atop++;ans[atop]=cur;
		}
	}

	reverse(stk+1,stk+top+1);
	atop=0;
	for(int i=1;i<=top;i++)
	{
		if(stk[i]==0)
		{
			atop++;
			ans2[atop]=atop;
		}
		else
		{
			int cur=atop+1;
			for(int j=1;j<=stk[i];j++)
			{
				atop++;
				ans2[atop]=atop+1;
			}
			atop++;ans2[atop]=cur;
		}
	}

	for(int i=1;i<=n;i++)
	{
		if(ans[i]<ans2[i])
		{
			for(int i=1;i<=n;i++)
				printf("%d ",ans[i]);
			puts("");
			return 0;
		}
		else if(ans2[i]<ans[i])
		{
			for(int i=1;i<=n;i++)
				printf("%d ",ans2[i]);
			puts("");
			return 0;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]);
	puts("");
	return 0;
}


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

int main(void){
    long long n,k,ans=0 ;
    cin >> n >> k ;
    vector<long long> h ;
    for (int i=0; i<n; i++){
        long long x ;
        cin >> x ;
        h.push_back(x) ;
    }
    sort(h.begin(),h.end()) ;
    for (int i=0; i<n-k; i++){
        ans+=h[i] ;
    }
    cout << ans << endl ;
}

Measured memory_bytes: 2420
#include <iostream>
#include <assert.h>
#include <string>
#include <algorithm>

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

  int32_t N;
  std::cin >> N;
  std::string S;
  std::cin >> S;

  for(int32_t i = 0; i < (int32_t)S.size(); i++){
    char s = S[i] + N;
    if (s > 'Z') s = s - 26;
    std::cout << s;
  }
  std::cout << std::endl;

  return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

st = []
for n in range(N):
  st.append(list(map(int, input().split())))

cs = []
for m in range(M):
  cs.append(list(map(int, input().split())))
  
for n in range(N):
  min_d = 100000000000000
  min_i = -1
  for m in range(M):
    d = abs(st[n][0]-cs[m][0]) + abs(st[n][1]-cs[m][1])
    if d < min_d:
      min_d = d
      min_i = m
  print(min_i+1)


Measured memory_bytes: 39280
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os, const map<T,U>& mp){ os << "{"; for(auto& p : mp){ os << p << ","; } os << "}"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

int main(){
    int N,Q; cin >> N >> Q;
    vector<int> ans(Q,-1);

    using T = tuple<ll,ll,ll>;
    vector<T> stx(N);
    rep(i,N){
        ll s,t,x;
        cin >> s >> t >> x;
        stx[i] = make_tuple(x,s,t);
    }

    using P = pair<ll,int>;
    set<P> ca;
    rep(i,Q){
        int d; cin >> d;
        ca.insert(make_pair(d,i));
    }

    sort(all(stx)); // xが小さい順
    for(int i=0;i<N;i++){
        ll s,t,x;
        tie(x,s,t) = stx[i];

        ll a = s-x;
        ll b = t-x;

        auto is = ca.lower_bound(make_pair(a,0));
        auto ie = ca.lower_bound(make_pair(b,0));
        vector<P> del;
        for(auto itr = is; itr != ie; itr++){
            int idx = itr->second;
            ans[idx] = x;
            del.push_back(*itr);
        }
        for(auto d : del){
            ca.erase(d);
        }
    }

    for(int i=0;i<Q;i++){
        cout << ans[i]<< endl;
    }
}


Measured memory_bytes: 23964
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int SIZE=100050;
//int arr[SIZE]={};
//ここまでテンプレ
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	int sum=a+b+c;
	cout<<sum-max({a,b,c})<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  string s;
  cin >> s;
  cout << s.substr(0,5) << ' ' << s.substr(6,7) << ' ' << s.substr(14,5) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

template<typename value_type>
class extended_euclidean
{
public:
	value_type gcd;
	value_type lcm;
	value_type x0;
	value_type y0;

public:
	extended_euclidean(value_type a, value_type b)
		: gcd(0), lcm(0), x0(0), y0(0)
	{
		tie(gcd, x0, y0) = process(a, b);
		lcm = a * b / gcd;
	}

public:
	tuple<value_type, value_type, value_type> process(value_type a, value_type b)
	{
		if (a == 0) return make_tuple(b, 0, 1);

		value_type g, x, y;
		tie(g, x, y) = process(b % a, a);

		return make_tuple(g, y - (b / a) * x, x);
	}
};

//extended_euclidean<long long> ee(a, b);
//long long gcd = ee.gcd;
//long long lcm = ee.lcm;

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

	int N;
	cin >> N;

	int curr;
	cin >> curr;

	for (int i = 1; i < N; i++)
	{
		int next;
		cin >> next;

		extended_euclidean<int> ee(curr, next);
		curr = ee.gcd;
	}

	cout << curr;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll dp[101][200003]={};//dp[i][j]:i番目まで読んだとき合計がjになるような場合の数
int main(){
	int N,K;
	ll MOD=1e+9+7;
	ll a[100001];
	scan(N);scan(K);
	dp[0][0]=1;
	rep(i,N){
		scan(a[i]);
		rep(j,K+1){
			dp[i+1][j]+=dp[i][j];
			dp[i+1][j]%=MOD;
			dp[i+1][j+a[i]+1]-=dp[i][j];
			if(dp[i+1][j+a[i]+1]<0) dp[i+1][j+a[i]+1]+=MOD;
		}
		rep(j,K){
			dp[i+1][j+1]+=dp[i+1][j];
			dp[i+1][j+1]%=MOD;
		}
	}
	prin(dp[N][K]);
	return 0;
}


Measured memory_bytes: 156544
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
#define _name3(_1,_2,_3,name,...) name
#define _rep1(n) for(ll i=0;i<(n);++i)
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _name3(__VA_ARGS__,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define rrep(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define each(i,a) for(auto &i:a)
#define sum(a) accumulate(range(a),0LL)
#define range(i) (i).begin(),(i).end()
template<class T> inline constexpr bool chmin(T &mn,const T &cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;}
template<class T> inline constexpr bool chmax(T &mx,const T &cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;}


int n,k;
vector<vector<int>>f,g;
vector<bool>used;
struct pq{
    const vector<int>e;
    vector<int>waiting;
    priority_queue<int,vector<int>,function<bool(int,int)>>q;
    pq(const vector<int>&e,const vector<int>&waiting):e(e),waiting(waiting),q([&e](int a,int b)->bool{for(auto&i:e){if(f[a].at(i)!=f[b].at(i))return f[a][i]<f[b][i];}return 0;}){
        rep(n)if(!waiting[i])q.push(i);
    }
    int pop(){
        int ans;
        do{
            ans=q.top();
            q.pop();
        }while(used.at(ans));
        used.at(ans)=1;
        return ans;
    }
    void push(int x){
        q.push(x);
    }
};
int main() {
    cin>>n>>k;
    f.assign(n,vector<int>(k));
    for(auto&i:f)for(auto&j:i)cin>>j;
    int d;
    cin>>d;
    g.resize(n);
    vector<int>waiting(n);
    rep(d){
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].push_back(b);
        waiting[b]++;
    }
    unordered_map<vector<int>,int,function<unsigned(const vector<int>&)>>m(100,[](const vector<int>&e)->unsigned{unsigned ans=0;each(i,e){ans<<=3;ans|=i;}return ans;});
    vector<int>e(k);
    iota(range(e),0);
    vector<pq>q;
    int cnt=0;
    do{
        m[e]=cnt++;
        q.push_back({m.find(e)->first,waiting});
    }while(next_permutation(range(e)));
    vector<int>ans;
    each(i,e){
        cin>>i;
        i--;
    }
    int E=m[e];
    cnt=0;
    int r;
    cin>>r;
    vector<pll>es(r);
    each(i,es){
        cin>>i.first;
        each(j,e){
            cin>>j;
            j--;
        }
        i.second=m[e];
    }
    reverse(range(es));
    used.resize(n);
    each(i,q)each(j,i.e)assert(0<=j&&j<k);
    while(cnt<n){
        if(es.size()&&cnt==es.back().first){
            E=es.back().second;
            es.pop_back();
        }
        while(true){
            int a=q[E].pop();
            each(i,g[a])if(!--waiting[i]){
                each(j,q){
                    j.push(i);
                }
            }
            ans.push_back(a+1);
            break;
        }
        cnt++;
    }
    each(i,ans)cout<<i<<endl;
}



Measured memory_bytes: 20956
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
 
using namespace std;

int main() {
    int A,B;

    cin >> A >> B;

    int sum = 1;
    int k = 0;

    while(sum < B){
        sum += A-1;
        k++;
    }

    cout << k << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    priority_queue<int> que;
    for(int i = 0; i < N; ++i){
        cin >> A[i];
        que.push(A[i]);
    }
    
    for(int i = 0; i < N; ++i){
        int temp = que.top();
        if(temp != A[i]){
            cout << temp << '\n';
        }
        else{
            que.pop();
            cout << que.top() << '\n';
            que.push(temp);
        }
    }
   
}


Measured memory_bytes: 3316
n,k=map(int,input().split())
a=list()
for i in range(1,n+1):
    a.append(i)

for i in range(k):
    d=int(input())
    b=list(map(int, input().split()))
    for j in range(d):
        try:
            a.remove(b[j])
        except ValueError:
            pass

print(len(a))


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

typedef long long LL;

const int N=100000;

int n,a[N+9],b[N+9],x[N+9],y[N+9];

void into(){
  scanf("%d",&n);
  for (int i=1;i<=n;++i){
    scanf("%d",&a[i]);
	x[i]=a[i];
  }
  for (int i=1;i<=n;++i){
	scanf("%d",&b[i]);
	y[i]=b[i];
  }
}

int cnt[N+9],p[N+9],vis[N+9],ans;

void Get_ans(){
  sort(x+1,x+n+1);
  sort(y+1,y+n+1);
  for (int i=1;i<=n;++i)
	if (x[i]>y[i]) return;
  ans=1;
  for (int i=1;i<=n;++i){
	if (++cnt[a[i]=lower_bound(y+1,y+n+1,a[i])-y]==2) return;
	p[b[i]=lower_bound(y+1,y+n+1,b[i])-y]=i;
  }
  for (int i=1;i<=n;++i) a[i]=p[a[i]];
  for (int i=1;!vis[i];i=a[i]) vis[i]=1;
  for (int i=1;i<=n;++i)
	if (!vis[i]) return;
  ans=0;
}

void work(){
  Get_ans();
}

void outo(){
  puts(ans?"Yes":"No");
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 6328
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int count = func(i);
            System.out.println(count);
        }
    }

    private static int func(int n) {
        int count = 0;
        for (int x = 1; x * x < n; x++) {
            for (int y = x;  y * y < n; y++) {
                for (int z = y;  z * z < n; z++) {
                    if (calc(x,y,z) == n) {
                        if (x != y && x != z && y != z) count+=6;
                        if (x == y && y == z) count++;
                        if ((x == y && y != z) || (x != y && y == z)) count += 3;
                    }
                }
            }
        }
        return count;
    }

    private static int calc(int x, int y, int z) {
        return x * x + y * y + z * z + x *y + x* z + y*z;
    }
}

Measured memory_bytes: 40848
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] line1 = sc.nextLine().split(" ");
        String[] line2 = sc.nextLine().split(" ");
        long H = Long.parseLong(line1[0]);
        long N = Long.parseLong(line1[1]);
        sc.close();

        long sum = 0;
        for (String string : line2) {
            sum += Long.parseLong(string);
        }

        String res = "No";

        if (sum >= H) {
            res = "Yes";
        }

        System.out.println(res);
    }

}

Measured memory_bytes: 49168
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define EPS 1e-9
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;
typedef pair<pii,pii> ppp;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}

#define in(a,b,c,d) ppp(pii(a,b),pii(c,d))

signed main(void) {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n)cin >> a[i];
    vvi p(n);
    rep(i,n)p[a[i]].push_back(i);
/*
    rep(i,n)if(p[i].size()){
        cout << i << ": ";
        rep(j,p[i].size())cout << p[i][j] << " ";
        cout << endl;
    }
    */
    rep(i,n)if(p[i].size() > 3){
        cout << 0 << endl;
        return 0;
    }
    rep(i,n-1)if(p[i].size() < p[i+1].size()){
        cout << 0 << endl;
        return 0;
    }
    map<ppp,int> ma;
    ma[in(0,-1,-1,-1)] = 1;
    set<ppp> st;
    st.insert(in(0,-1,-1,-1));
    int ans = 0;
    while(st.size()){
        ppp p = *st.begin();
        st.erase(p);
        int i = p.first.first;
        int x = p.first.second;
        int y = p.second.first;
        int z = p.second.second;
        int now = ma[in(i,x,y,z)];
        now %= MOD;
        if(i == n){
            ans += now;
            ans %= MOD;
            continue;
        }
        if(a[i] == x + 1){
            ma[in(i+1,x+1,y,z)] += now;
            ma[in(i+1,x+1,y,z)] %= MOD;
            st.insert(in(i+1,x+1,y,z));
        }
        if(a[i] == y + 1){
            ma[in(i+1,x,y+1,z)] += now;
            ma[in(i+1,x,y+1,z)] %= MOD;
            st.insert(in(i+1,x,y+1,z));
        }
        if(a[i] == z + 1){
            ma[in(i+1,x,y,z+1)] += now;
            ma[in(i+1,x,y,z+1)] %= MOD;
            st.insert(in(i+1,x,y,z+1));
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 51712