akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;

void solve() {
  ll n;
  cin >> n;
  cout << fixed << setprecision(12) << n*n*n/27. << "\n";
}

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


Measured memory_bytes: 256
/*
  Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define mkpr make_pair
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define fbo find_by_order
#define ook order_of_key
#define init0(x) memset(x,0,sizeof(x));

using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const int maxlimit=2e5+2;
const ll inf=1e18;
//TTBDC

vector<ll> ht(maxlimit),score(maxlimit);
vector<ll> sg(4*maxlimit);

ll query(int ql,int qr,int id,int start,int end){
  if(qr<start || end<ql)return 0;
  else if(ql<=start && end<=qr)return sg[id];
  int mid = (start+end)/2;
  return max(query(ql,qr,(id<<1),start,mid),query(ql,qr,(id<<1)+1,mid+1,end));
}

void update(int id,int start,int end,int idx,ll val){
  if(idx<start || end<idx)return;
  else if(idx==start && start==end)sg[id]=val;
  else {
    int mid=(start+end)/2;
    update((id<<1),start,mid,idx,val);
    update((id<<1)+1,mid+1,end,idx,val);
    sg[id]=max(sg[(id<<1)],sg[(id<<1)+1]);
  }
}

int main()
{
  fatafat
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)cin>>ht[i];
  for(int i=1;i<=n;i++)cin>>score[i];
  ll res=-1,curr;
  for(int i=1;i<=n;i++){
    curr = score[i]+query(1,ht[i],1,1,n);
    res=max(res,curr);
    update(1,1,n,ht[i],curr);
  }
  cout<<res;

  return 0;
}

Measured memory_bytes: 12620
#include <bits/stdc++.h>
 using namespace std;
 #define rep(i,N) for(int i=0;i<int(N);++i)
 using ll = long long;
 const int INF = 2147483647;
 const ll MOD = 1000000007;
 // const ll INF = 1000000000000000000LL;
 
 int main(){
   ll n;
   cin >> n;
   vector<ll> ans(n);
   for(int i=1;i<=n;i++){
    ll cnt=0;
    for(int x=1;x<=100;x++){
      for(int y=1;y<=100;y++){
        for(int z=1;z<=100;z++){
          if(x*x+y*y+z*z+x*y+y*z+z*x==i)
            cnt++;
          if(x*x+y*y+z*z+x*y+y*z+z*x>i)
            break;
        }
      }
    }
    ans[i-1] = cnt;
   }
  rep(i,n)
    cout << ans[i] << endl;
   return 0;
 }

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

int main(){
    int a[100100], b[100100];
    int N, H; cin >> N >> H;
    for(int i=0; i<N ;i++){ cin >> a[i] >> b[i];}
    //a[i]は何回でも使える
    //b[i]は一回だけ
    sort(a,a+N,greater<int>());
    sort(b,b+N,greater<int>());

    int now=0;
    int ans=0;
    while( now<N && a[0]<b[now]){
        H -=b[now];
        ans++;
        if(H<=0) {cout << ans << endl; return 0;}
        now++;
    }
    cout << ans + (H+a[0]-1)/a[0] << endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 1000000007;
constexpr ll modsize = 100010;
vector<ll> fac(modsize);
vector<ll> inv(modsize);
vector<ll> facinv(modsize);

void modcalc() {
	if (modsize == 0) abort();
	fac[0] = 1; fac[1] = 1; inv[1] = 1;
	facinv[0] = 1; facinv[1] = 1;
	for (ll i = 2; i < modsize; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		facinv[i] = facinv[i - 1] * inv[i] % mod;
	}
}

ll modinv(ll a) {
	if (a == 0) abort();
	ll b = mod, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;
	return u;
}

ll modpow(ll a, ll b) {
	ll ans = 1;
	a %= mod;
	while (b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

ll modcomb(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[k] % mod * facinv[n - k] % mod;
}

ll modperm(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[n - k] % mod;
}

ll modhom(ll n, ll k) {
	if (n < 0 || k < 0 || n == 0 && k > 0) return 0;
	if (n == 0 && k == 0) return 1;
	return fac[n + k - 1] * facinv[k] % mod * facinv[n - 1] % mod;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	modcalc();
	
	ll n, m;
	cin >> n >> m;
	if (n == m) cout << fac[n] * fac[n] * 2 % mod << '\n';
	else if (n == m + 1 || n == m - 1) cout << fac[n] * fac[m] % mod << '\n';
	else cout << 0 << '\n';
}

Measured memory_bytes: 2560
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

int main() {
	int n;
	cin >> n;
	int ret = 0;
	int count = 1;
	int cur = n % 10;
	n /= 10;
	for (int i = 0; i < 3; i++) {
		if (n % 10 == cur) {
			count++;
		} else {
			ret = max(ret, count);
			cur = n % 10;
			count = 1;
		}
		n /= 10;
	}
	ret = max(ret, count);
	if (ret >= 3) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
Ss = input()

Ns = []
prev = Ss[0]
num = 0
for S in Ss:
    if S != prev:
        Ns += [num]
        num = 1
    else:
        num += 1
    prev = S

Ns += [num]

sumN = 0
restN = sum(Ns)
ans = float('inf')
for N in Ns:
    sumN += N
    restN -= N
    ans = min(ans, max(sumN, restN))

print(ans)


Measured memory_bytes: 3572
n = gets.to_i

a = gets.split.map(&:to_i)
a1 = a.count(1)
a2 = a.count(2)
a3 = a.count(3)

m = a2 + a3
d = Array.new(m+1) {Array.new(n+1, 0.0)}
u = Array.new(m+1) {Array.new(n+1, 0.0)}

(a3+1).times do |c3|
    (m-c3+1).times do |c2|
        (n-c2-c3+1).times do |c1|
            t = c1 + c2 + c3
            next if t == 0
            s = n.to_f
            s += u[c2][c1-1] * c1 if c1 > 0
            s += u[c2-1][c1+1] * c2 if c2 > 0
            s += d[c2+1][c1] * c3 if c3 > 0
            u[c2][c1] = s / t
        end
    end
    d, u = u, d
end

p d[a2][a1]

Measured memory_bytes: 15628
#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9 + 7;
const int maxN = (int)1e5 + 10;
const int inv3 = (mod + 1) / 3;
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int sub(int a, int b) {
    int s = a - b;
    if (s < 0) s += mod;
    return s;
}
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int c[maxN];
int bc[maxN];
int abc[maxN];
int pw3[maxN];
int prefc[maxN];
int prefbc[maxN];
string s;
int main() {
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin >> s;
    pw3[0] = 1;
    for (int i = 1; i <= s.size(); i++) pw3[i] = mult(pw3[i - 1], 3);
    int quest = 0;
    for (int i = 0; i < s.size(); i++) if (s[i] == '?') quest++;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'C') c[i] = pw3[quest];
        else if (s[i] == '?') c[i] = pw3[quest - 1];
    }
    // summa c[i] = 'C'
    for (int i = s.size() - 1; i >= 0; i--) {
        prefc[i] = sum(prefc[i + 1], c[i]);
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'B') bc[i] = prefc[i + 1];
        else if (s[i] == '?') bc[i] = mult(prefc[i + 1], inv3);
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        prefbc[i] = sum(prefbc[i + 1], bc[i]);
    }
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'A') ans = sum(ans, prefbc[i + 1]);
        else if (s[i] == '?') ans = sum(ans, mult(prefbc[i + 1], inv3));
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 2384
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int n=0;
    cin>>n;
    map<long long int,long long int> count;
    long long int A[200005];
    for(int i=0;i<n;i++){
        cin>>A[i];
        count[A[i]]++;
    }
    long long int total=0;
    for(auto x:count){
        total+=x.second*(x.second-1)/2;
    }
    for(int i=0;i<n;i++){
        cout<<total-count[A[i]]+1<<endl;
    }    
    return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pii std::pair<int,int>
#define pli std::pair<ll,int>
#define pil std::pair<int,ll>
#define psi std::pair<string,int>
#define pll std::pair<ll,ll>
#define pci std::pair<char,int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define pb push_back
#define vll std::vector<ll>
#define vpi std::vector<std::pair<int,int>>
#define vi std::vector<int>
#define vvi std::vector<std::vector<int>>
#define vvpil std::vector<std::vector<std::pair<int,ll>>>
#define vlpii std::vector<std::list<pii>>
#define vlpil std::vector<std::list<pil>>
#define li std::list<int>
#define lpil std::list<pil>
#define Endl printf("\n")
#define vli vector<list<int>>
#define vvll vector<vector<ll>>
#define mp make_pair
#define x first
#define y second
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod = 1000000007;
using namespace std;
void add(ll& x , ll y){
	x += y;
	if(x >= mod) x -= mod;
}
ll mul(ll x , ll y){
	return (x * y) % mod;
}
ll Pow(ll x , ll y){
	if(y == 0) return 1 ;
	ll z = Pow(x , y / 2) ;
	if(y % 2) return (((z * z) % mod) * x) % mod ;
	return (z * z) % mod  ;
}
bool f(string x , string y){
	string c = x + y ;
	string d = y + x ;
	vll h(c.size() , 0) ;
	h[0] = (c[0] == 'h') ;
	for(int i = 1 ; i < (int)c.size() ; i++){
		h[i] = h[i - 1] + (c[i] == 'h') ;
	}
	vll h1(c.size() , 0) ;
	h1[0] = (d[0] == 'h') ;
	for(int i = 1 ; i < (int)c.size() ; i++){
		h1[i] = h1[i - 1] + (d[i] == 'h') ;
	}
	ll ans1 = 0 ;
	for(int i = 0 ; i < (int)c.size() ; i++){
		if(c[i] == 's')
			ans1 += h[(int)c.size() - 1] - h[i] ;
	}
	ll ans2 = 0 ;
	for(int i = 0 ; i < (int)c.size() ; i++){
		if(d[i] == 's')
			ans2 += h1[(int)c.size() - 1] - h1[i] ;
	}
	return ans1 >  ans2 ;
}
//Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1
///    *check mod
///    *check input file  
int main(){
	IOS;
	int n ; cin >> n ;
	vi a(n + 1) ; for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
	vi ans(n + 1, 0) ;
	vi res ;
	for(int i = n ; i >= 1 ;i--){
		int nb = 0 ; 
		for(int j = 2 * i ; j <= n ;j += i) nb += ans[j] ;
		if(nb % 2 != a[i]) {ans[i] = 1 ;res.pb(i) ;}
		
	}
	
	for(int i = 1 ; i <= n ;i++){
		int nb = 0 ;
		for(int j = i ; j <= n ; j += i) nb += ans[j] ;
		if(nb % 2 != a[i]) return cout << -1 << "\n" , 0 ;
	}
	cout << res.size() << endl; 
	for(int i = 0 ; i < (int) res.size() ; i++) cout << res[i] <<"\n" ;
	
			
	
	return 0;
}



Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N;
  cin >> N;
  map<ll, int> A;
  rep(i, N)
  {
    ll tmp;
    cin >> tmp;
    A[tmp]++;
  }
  ll count = 0;
  for (auto a : A)
  {
    if (a.second % 2 != 0)
    {
      count++;
    }
  }
  cout << count << endl;

  return 0;
}

Measured memory_bytes: 6528
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, t;
	cin >> n >> t;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	int minV = 1000000000;
	int maxSa = -1;
	int ans = 0;
	for(int i = 0; i < n; i++){
		if(minV > a[i]){
			minV = a[i];
		}else{
			if(a[i] - minV > maxSa){
				maxSa = a[i] - minV;
				ans = 1;
			}else if(a[i] - minV == maxSa){
				ans++;
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

frag, loop, lcnt = set(), [], []
for i in range(n):
    if i in frag:
        continue
    now, tmp, tmpc = i, [], 0
    while True:
        frag.add(now), tmp.append(now)
        now = p[now] - 1
        tmpc += c[now]
        if now in frag:
            loop.append(tmp * 2)
            lcnt.append(tmpc)
            break

lacc = []
for l in loop:
    tmp = [0]
    for li in l[1:]: 
        tmp.append(tmp[-1] + c[li])
    lacc.append(tmp)

ans = min(c)
for l, la, lc in zip(loop, lacc, lcnt):
    llen = len(l) // 2
    num = k % llen
    for cnt in range(1, min(llen + 1, k + 1)):
        for i in range(len(l) - cnt - 1):
            tmp = la[i + cnt] - la[i]
            tmp2 = tmp + lc * (k // llen - (cnt > num))
            ans = max(ans, tmp, tmp2)
print(ans)


Measured memory_bytes: 69272
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	LL n; cin >> n;
	vector<LL> a(5);

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

	LL mi = INF2;
	LL idx = 0;
	for (int i = 0; i < 5; i++) {
		if (a[i] < mi) {
			mi = a[i];
			idx = i;
		}
	}

	LL cnt = (n + mi - 1) / mi;
	LL ans = 4 + cnt;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
template<typename T> ll min(ll a, const T&& b) { return a < b ? a : b; }
template<typename T> ll min(const T&& a, ll b) { return a < b ? a : b; }
template<typename T> ll max(ll a, const T&& b) { return a > b ? a : b; }
template<typename T> ll max(const T&& a, ll b) { return a > b ? a : b; }
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

void solve() {
  ll n; cin >> n;
  vector<ll> a(n); cin >> a;
  sort(all(a));
  vector<bool> is_neg(n, false);
  is_neg[0] = true;
  rep(i, 1, n-1) {
    if (a[i] < 0) is_neg[i] = true;
  }
  queue<ll> pos, neg;
  rep(i, n) {
    if (is_neg[i]) neg.push(a[i]);
    else pos.push(a[i]);
  }
  assert(!pos.empty() && !neg.empty());
  ll Pos = pos.front(); pos.pop();
  ll Neg = neg.front(); neg.pop();
  vector<P> op;
  while (!pos.empty()) {
    ll x = Neg;
    ll y = pos.front(); pos.pop();
    op.eb(x, y);
    Neg = x - y;
  }
  neg.push(Neg);
  while (!neg.empty()) {
    ll x = Pos;
    ll y = neg.front(); neg.pop();
    op.eb(x, y);
    Pos = x - y;
  }
  ll ans = Pos;
  cout << ans << endl;
  each(p, op) {
    cout << p.first << " " << p.second << endl;
  }
}


Measured memory_bytes: 5236
#include<iostream>
#include<bits/stdc++.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    long long n,m,x,y,z,j;
    cin>>n;
    long long a[n+1];
    long long b[n];
    long long sum=0;
    for(int i=0;i<n+1;i++)
    {
        cin>>a[i];
        sum=sum+a[i];

    }
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    j=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<=b[i])
        {
            b[i]=b[i]-a[i];
            a[i]=0;
            if(a[i+1]<=b[i])
            {
                a[i+1]=0;
            }
            else
            {
                a[i+1]=a[i+1]-b[i];
            }
        }
        else
        {
            a[i]=a[i]-b[i];
        }
    }
    long long sum2=0;
    for(int i=0;i<n+1;i++)
    {
        //cout<<a[i]<<" ";
        sum2=sum2+a[i];
    }
    cout<<sum-sum2<<endl;
}



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

#define PI 3.14159265359
#define INF 1000000009
#define LINF 1000000000000000009
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

int dx[4] = {1, 0, -1, 0};
int dy[5] = {0, 1, 0, -1};
using namespace std; 

int main(void)
{
    ll n, a, b;
    cin >> n >> a >> b;
    
    if(n == 1) {
        if(a == b) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        } 
    } else {
        if(b >= a) {
            ll c = (n-1) * a + b;
            ll d = (n-1) * b + a;
            cout << d-c+1 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}
/** tcoder **/


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
    int n,i,a,min,max;
    long sum;
    scanf("%d",&n);
    scanf("%d",&a);
    min=a;
    max=a;
    sum=a;
    for(i=1;i<n;i++)
    {
        scanf("%d",&a);
        if(min>a)
        {
            min=a;
        }
        if(max<a)
        {
            max=a;
        }
        sum+=a;
    }
    printf("%d %d %ld\n",min,max,sum);
    return 0;
}


Measured memory_bytes: 2100
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  int N; cin >> N;
  LL L = 1, R = 1;
  for (int i = 0; i < N; ++i) {
    LL x, y; cin >> x >> y;
    long double X = (long double)L / x;
    long double Y = (long double)R / y;
    LL k = (LL)max(ceil(X), ceil(Y));
    L = k * x, R = k * y;
  }
  cout << L + R << endl;
}


Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
  int n;
  int data;
  int min,max;
  long long int sum=0;
  cin>>n;
  cin>>data;
  min=data;
  max=data;
  sum+=data;
  for(int i=1;i<n;i++){
    cin>>data;
    if(data>max){
      max=data;
    }else if(data<min){
      min=data;
    }
    sum+=data;
  }
  cout<<min<<' '<<max<<' '<<sum<<endl;
  return (0);
}

Measured memory_bytes: 3100
fn main(){
	let mut s = String::new();
	std::io::stdin().read_line(&mut s).unwrap();
	let vec: Vec<&str> = s.trim().split(' ').collect();
	let mut n = String::new();
	for v in &vec {
		n += &format!("{}", v);
	}
	let p = n.parse::<i32>().unwrap();
	for i in 0..10000 {
		let s = i * i;
		if s == p {
			println!("Yes");
			return;
		}
	}
	println!("No");
}



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

int tab[110];

int main()
{
//	freopen("input.txt","r",stdin);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	 cin>>tab[i];
	int ans=0;
	for (int i=1;i<n;i++)
	 for (int j=1;j<=n;j++)
	  ans=max(ans,abs(tab[i]-tab[j]));
	cout<<ans<<"\n";
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    ll M = 1000;
    for (int i = 0; i < N-1; ++i) {
        ll stocks = 0;
        if (A[i] < A[i+1]) stocks = M / A[i];
        M += (A[i+1] - A[i]) * stocks;
    }
    cout << M << endl;
    return 0;
}

Measured memory_bytes: 3628
#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 n;
  cin >> n;
  if(n%2==1){
    cout << 0 << "\n";
    return 0;
  }
  ll ans=0;
  while(n>=10){
    ans+=n/10;
    n/=5;
  }
  cout << ans << "\n";  
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int main(){
	char s[100000];
	int count = 0;
	cin >> s;

	for(int i=0; s[i]!='\0'; i++){
		if(s[i]!=s[i+1]){
			count += 1;
		}
	}

	cout << count-1 << endl;
	return 0;
}

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

int main(){
    ll n ;
    cin >> n ;
    vector<pair<ll,ll>> G ;
    for(ll i = 0 ; pow(i,5) <= 1e18 ; i++ ){
        G.push_back(make_pair(pow(i,5),i));
    }
    for(ll i = -1 ; pow(i,5) >= -1e18 ; i-- ){
        G.push_back(make_pair(pow(i,5),i));
    }
    for(auto p : G){
        for(auto q : G ){
            if( p.first - q.first == n){
                cout << p.second << endl;
                cout << q.second << endl;
                return 0 ;
            }
        }
    }
}

Measured memory_bytes: 4360
x, y = map(int, input().split())
if (x+y)%3 != 0:
    print(0)
    exit()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
 
# a = (2*x-y)//3
# b = (2*y-x)//3
a = y - (x+y)//3
b = x - (x+y)//3
n = a+b
r = a
res = cmb((x+y)//3,r,mod)
print(res)

Measured memory_bytes: 127556
n,m,k = map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
def size(x):
    return -par[find(x)]
g = [[] for _ in range(n+1)]
b = [[] for _ in range(n+1)]
for _ in range(m):
    s,t = map(int,input().split())
    unite(s,t)
    g[s].append(t)
    g[t].append(s)
for _ in range(k):
    s,t = map(int,input().split())
    b[s].append(t)
    b[t].append(s)
for i in range(1,n+1):
    ans = size(i)-1-len(g[i])
    for e in b[i]:
        if same(i,e):
            ans -= 1
    print(ans,end=" ")

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

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007

ll freq[1000005];

int main(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
	ll N;
	cin>>N;
	ll ar[N];
	for(ll i=0;i<N;i++) cin>>ar[i];
	ll gc=ar[0];
	ll flag=1;
	for(ll i=0;i<N;i++){
		gc=__gcd(gc,ar[i]);
		if(ar[i]%2==0){
			if(freq[2])
				flag=0;
			freq[2]=1;
		}
		while(ar[i]%2==0){
			ar[i]/=2;
		}
		for(ll j=3;j*j<=ar[i];j+=2){
			if(ar[i]%j==0){
				if(freq[j])
					flag=0;
				freq[j]=1;
			}
			while(ar[i]%j==0)
				ar[i]/=j;
		}
		if(ar[i]>2){
			if(freq[ar[i]])
				flag=0;
			freq[ar[i]]=1;
		}
	}
	if(flag){
		cout<<"pairwise coprime"<<endl;
	}
	else if(gc==1)
		cout<<"setwise coprime"<<endl;
	else
		cout<<"not coprime"<<endl;
}

Measured memory_bytes: 19184
N = int(input())
l=[]
cnt=a_cnt=b_cnt=ab_cnt=0
for n in range(N):
	s = input()
	if s[0] == 'B':
		b_cnt += 1
	if s[-1] == 'A':
		a_cnt += 1
	if s[0] == 'B' and s[-1] == 'A':
		ab_cnt += 1
	for i in range(len(s)-1):
		if s[i:i+2] == 'AB':
			cnt += 1
	l.append(s)

if ab_cnt == a_cnt and ab_cnt == b_cnt:
	if ab_cnt == 0:
		print(cnt)
	else:
		print(ab_cnt-1+cnt)
else:
	m = min(a_cnt,b_cnt)
	print(m+cnt)


Measured memory_bytes: 3700
#include <bits/stdc++.h>
    #include <iostream>
    #include <unordered_map>
    #include <unordered_set>
    #define pb push_back
    #define mpr make_pair
    #define pii pair<int, int>
    #define pll pair<ll, ll>
    #define ll long long
    #define ld long double
    #define fi first
    #define se second
    #define all(arr) arr.begin(), arr.end()
    #define rep(i, n) for (int i = 0; i < (int)(n); i++)
    #define fo(i, l, r) for (int i = l; i <= r; i++)
    #define INF 1000000001
    #define inf1 1000000000000000001
    #define MOD 1000000007
    #define mod 1000000007
    #define pie 3.14159265358979323846264338327950L
    #define N 200009
    #define M 1e6 + 9
    #define mid(l, r) l + (r - l) / 2
    #define vec vector<int>
    #define vecl vector<ll>
    #define umap unordered_map<ll, ll>
    #define yes cout << "Yes" << endl;
    #define no cout << "No" << endl;
    #define endl "\n"
    #define int long long
    using namespace std;
    
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};  
    int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
    ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
    ll lcm(ll a, ll b) { return (a*b)/ gcd(a,b);}
    

    
    void test_case()
    {
        
        
        int a,b;
        cin>>a>>b;

        int ans = lcm(a,b);

        cout<<ans<<endl;


        



    
        
    }
    
    signed main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout << fixed << setprecision(20);
    
        // freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    
        int t = 1;
        // cin >> t;
        while (t--)
        {
            test_case();
        }
    }

Measured memory_bytes: 3616
n = int(input())
v = list(map(int, input().split()))

v_even = [0]*100000
v_odd = [0]*100000

for i in range(n):
  if i%2==0:
    v_even[v[i]-1] += 1 
  else:
    v_odd[v[i]-1] += 1
    
res1 = max(v_even)
res2 = max(v_odd)
if v_even.index(res1) == v_odd.index(res2):
  if res1 > res2:
    v_odd[v_odd.index(res2)] = 0
    res2 = max(v_odd)
  elif res2 > res1:
    v_even[v_even.index(res1)] = 0
    res1 = max(v_even)
  elif res1 == res2:
    v_odd[v_odd.index(res2)] = 0
    v_even[v_even.index(res1)] = 0
    res3 = max(v_even)
    res4 = max(v_odd)
    if res3 > res4:
      res1 = res3
    else:
      res2 = res4
      
print(n//2-res1 + n//2-res2)

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

unsigned int dp[2001][2001];

int main() {
	unsigned int n, m;
	cin >> n >> m;
	unsigned int s[2001], t[2001];

	dp[0][0] = 1;

	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		dp[i][0] = 1;
	}
	for (int i = 1; i <= m; i++) {
		cin >> t[i];
		dp[0][i] = 1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			if (s[i] != t[j])dp[i][j] += 1000000007-dp[i - 1][j - 1];
			dp[i][j] %= 1000000007;
		}
	}

	cout << dp[n][m] << endl;

	return 0;
}


Measured memory_bytes: 15872
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)


#include <complex>

using std::complex;
typedef complex<double> P;
const double eps = 1e-10;
const double EPS = eps;



static inline bool eq(const P &a, const P &b){
  return std::abs<double>(a-b) < EPS;
}

static inline double inp(const P &a, const P &b){
  return (conj(a)*b).real();
}

static inline double outp(const P &a, const P &b){
  return (conj(a)*b).imag();
}

class Line{
public:
  P p;
  P d;
  Line(){}
  Line(P pos, P dir){
    p=pos; d=dir/abs(dir);
  }
};

Line LineDirect(P pos, P dir){
  return Line(pos, dir);
}

Line LinePos(P p1, P p2){
  return Line(p1, p2-p1);
}

P crossPoint(const Line &l1, const Line &l2){
  if(std::abs<double>((l1.d / l2.d).imag()) < eps){
    throw 0;
  }

  double num = outp(l2.d, l2.p-l1.p);
  double denom = outp(l2.d, l1.d);

  return P(l1.p + l1.d * num/denom);
}

double dist(const Line &l, const P &p){
  return std::abs(outp(l.d, p-l.p) / std::abs(l.d));
}

using namespace std;

double in(P p){
  bool ret = true;
  ret &= p.real() >= -100 - eps;
  ret &= p.real() <=  100 + eps;
  ret &= p.imag() >= -100 - eps;
  ret &= p.imag() <=  100 + eps;
  return ret;
}

double on(P p){
  if(!in(p)) return false;
  if(p.real() < -100.0 + eps) return true;
  if(p.imag() < -100.0 + eps) return true;
  if(p.real() >  100.0 - eps) return true;
  if(p.imag() >  100.0 - eps) return true;
  return false;
}

int main(){
  int n;
  while(scanf("%d",&n), n){
    vector<Line> ln(n);

    REP(i,n){
      P p1, p2;
      scanf("%lf%lf%lf%lf", &p1.real(), &p1.imag(), &p2.real(), &p2.imag());
      ln[i] = LinePos(p1, p2);
    }

    int ans = 1;

    REP(i,n){
      vector<P> cross;
      ans += 1;
      REP(j,i){
	try{
	  P c = crossPoint(ln[i], ln[j]);
	  
	  if(!in(c) || on(c)) continue;
	  
	  bool ok = true;
	  
	  REP(k, cross.size()){
	    if(std::abs<double>(c - cross[k]) < eps){
	      ok = false;
	      break;
	    }
	  }
	  
	  cross.push_back(c);
	  if(ok){
	    ans += 1;
	  }
	}catch(int n){

	}
      }
    }
      
    printf("%d\n", ans);
  }
  return 0;
}

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

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

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m1,m2 = LI()
    r = [[inf]*401 for _ in range(401)]
    r[0][0] = 0
    for a,b,c in [LI() for _ in range(n)]:
        for i in range(400-a,-1,-1):
            for j in range(400-b,-1,-1):
                if r[i][j] == inf:
                    continue
                if r[i+a][j+b] > r[i][j] + c:
                    r[i+a][j+b] = r[i][j] + c

    t = inf
    for k in range(1,401):
        k1,k2 = m1*k,m2*k
        if k1 > 400 or k2 > 400:
            break
        if r[k1][k2] < t:
            t = r[k1][k2]

    if t == inf:
        return -1
    return t


print(main())


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

int main() {
  int A1, A2, A3;
  cin >> A1 >> A2 >> A3;

  if (A1 + A2 + A3 >= 22)
    cout << "bust" << endl;
  else
    cout << "win" << endl;
  return 0;
}

Measured memory_bytes: 3608
/* AtCoder Beginner Contest abc137
 * Problem E
 * Au: SJoshua
 */
#include <queue>
#include <cstdio>
#include <climits>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge {
	int u, v, w;
};

struct node {
	int pos;
	long long int val;	
};

int main(void) {
	int n, m, p;
	cin >> n >> m >> p;
	vector <edge> edges(m);
	vector <vector <int>> graph(n + 1);
	vector <long long int> rec(n + 1);
	for (int i = 1; i <= n; i++) {
		rec[i] = INT_MIN;
	}

	for (int i = 0; i < m; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
		edges[i].w -= p;
		graph[edges[i].u].push_back(i);
	}
	long long int ans = 0;
	queue <node> q;
	q.push({1, 0});
	int ops = 0, upd = 0;
	while (!q.empty()) {
		if (++ops > 50000000) {
			break;
			return 0;
		}
		auto t = q.front();
		q.pop();
		if (t.val <= rec[t.pos]) {
			continue;
		} else {
			if (t.pos == n) {
				upd++;
			}
			rec[t.pos] = t.val;
		}
		for (auto id: graph[t.pos]) {
			q.push({edges[id].v, t.val + edges[id].w});
		}
	}
	if (upd > 5000) {
		cout << -1 << endl;
	} else {
		cout << max(0LL, rec[n]) << endl;
	}
	return 0;
}



Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
	int s;
	cin >> s;
	s--;
	a[i] = s;
  }
  int cnt = 0, temp, index = 0;
  if (a[0] == 0) {
	cout << -1 << endl;
	return 0;
  }
  while (true) {
	temp = a[index];
	index = temp;
	cnt++;
	if (cnt > n) {
	  cout << -1 << endl;
	  return 0;
	}
	if (temp == 1) {
	  cout << cnt << endl;
	  return 0;
	}
  }

  return 0;
}



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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll X, N; cin >> X >> N;
    vector<ll> p(N);
    rep(i, N){cin >> p.at(i);}
    sort(p.begin(), p.end());
    if (!binary_search(p.begin(), p.end(), X)){cout << X << endl; exit(0);}
    rep2(i, 1, 101){
        // マイナスする方から
        if (!binary_search(p.begin(), p.end(), X - i)){cout << X - i << endl; exit(0);}
        if (!binary_search(p.begin(), p.end(), X + i)){cout << X + i << endl; exit(0);}
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3620
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#define rep(i, n) for(int64_t i=0;i<(n);++i)
#define for(i, a, b) for(int64_t i=(a);i<(b);++i)
#define all(obj) (obj).begin(), (obj).end()
#define in(x) cin >> (x)
#define out(y) cout << (y) << "\n"
#define i64 int64_t
#define str string
using namespace std;
void Main() {
	/*----------------------------------------------------------------------------------------------------*/
	i64 r; in(r);
	out(r * r);
	/*----------------------------------------------------------------------------------------------------*/
}
int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	Main();
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from operator import or_


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


class SegmentTree():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value for i in range(treesize)]
        self.st = st

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        offset = len(self.st) // 2
        k = offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        offset = len(self.st) // 2
        a += offset
        b += offset - 1
        s = self.init_value
        while a < b:
            if a & 1 == 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if b & 1 == 0:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k, l, r):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        # return self._query_topdown(a, b, k=1, l=0, r=len(self.st)//2)
        return self._query_bottomup(a, b)


def solve_online(N, S, Q):
    tree = SegmentTree(N, op=or_, init_value=0)
    C = [ord(s) - ord("a") for s in S]
    for i in range(N):
        c = ord(S[i]) - ord("a")
        tree.update(i, 1 << c)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c = int(a)-1, ord(b) - ord("a")
            tree.update(i, 1 << c)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            b = tree.query(l, r+1)
            s = 0
            while b > 0:
                if b & 1 == 1:
                    s += 1
                b >>= 1
            print(s)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 116044
import collections
N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
C = collections.Counter(A)

#print(A, B, C)
def n2(n):
  if n == 0:
    return 0
  elif n == 1:
    return 0
  else:
    return int(n * (n - 1) / 2)

all_ans = 0
x = -1
count = 0
for i in range(N):
  if B[i] == x:
    count += 1
  else:
    all_ans += n2(count)
    x = B[i]
    count = 1
  #print(count, x, all_ans) 
  
all_ans += n2(count)    
#print(all_ans)
    
for i in range(N):
  y = C[A[i]]
  print(all_ans - y + 1)
  

Measured memory_bytes: 26780
#include "iostream"
#include "algorithm"
#include "vector"

using namespace std;

int main() {
	vector<int> v;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	std::sort(v.rbegin(), v.rend());
	int a=0, b=0, t=0;
	for (int i = 0; i < n; i++) {
		if (t % 2 == 0) a += v[i];
		else b += v[i];
		t++;
	}
	cout << a - b << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		int[] ans = new int[n];
		
		for(int i=0;i<n;i++){
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();			
			c[i] = sc.nextInt();			
		}
		
		boolean x;
		for(int i=0;i<n;i++){
			x = true;
			for(int j=0;j<n;j++){
				if(i!=j){
					if(a[j]==a[i])x=false;
				}
			}
			if(x==true)ans[i]+=a[i];
		}
		for(int i=0;i<n;i++){
			x = true;
			for(int j=0;j<n;j++){
				if(i!=j){
					if(b[j]==b[i])x=false;
				}
			}
			if(x==true)ans[i]+=b[i];
		}
		for(int i=0;i<n;i++){
			x = true;
			for(int j=0;j<n;j++){
				if(i!=j){
					if(c[j]==c[i])x=false;
				}
			}
			if(x==true)ans[i]+=c[i];
		}
		for(int i=0;i<n;i++){
			System.out.println(ans[i]);
		}
	
	}
}

Measured memory_bytes: 21092
S = input()
cnt = [0]
now = '0'
for i in S:
    if now == i:
        cnt[-1] += 1
    else:
        cnt.append(1)
        now = i

ans = len(S)
sum = 0
for i in cnt:
    sum += i
    ans = min(ans, max(sum, len(S) - sum))
print(ans)

Measured memory_bytes: 9372
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
typedef long long ll;
using namespace std;

const int MAXN = 1e5+5;
const int MOD = 1e9+7;

int main()
{
    int a, b;
    cin >> a >> b;
    string str1(a, b+'0');
    string str2(b, a+'0');
    cout << min(str1, str2) << endl;

    return 0;
}


Measured memory_bytes: 256
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main():
    s, t = input().split()
    print(t+s)
    
            
                

        




    


if __name__ == '__main__':
    main()


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

#define ln '\n'
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    VPL vpl;
    REP(i, n) {
        ll a, b;
        cin >> a >> b;
        vpl.push_back(make_pair(a, b));
    }

    sort(ALL(vpl), [](PL a, PL b) {
        if (a.second == b.second) {
            return a.first < b.first;
        } else {
            return a.second < b.second;
        }
    });
    ll t = 0;

    REP(i, n) {
        t += vpl[i].first;
        if(t > vpl[i].second) {
            cout << "No" << ln;
            return 0;
        }
    }

    cout << "Yes" << ln;
    return 0;
}


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

using namespace std;

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

    bool ans = false;
    int d = 0;
    int c = 0;
    while(4*d <= N){
        while(4*d+7*c <= N){
            if(4*d+7*c == N){
                ans = true;
                break;
            }
            c++;
        }
        if(ans) break;
        c=0;
        d++;
    }
    string answer = "";
    if(ans){
        answer = "Yes";
    } else{
        answer = "No";
    }
    
    cout << answer << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
const int MaxN=100010;
int N,L,T,X[MaxN],W[MaxN],mem[MaxN],*list[2],cnt[2],end[MaxN];
bool cmp(int i,int j){
	return end[i]<end[j]||end[i]==end[j]&&W[i]>W[j];
}
void csort(int*l,int*r){
	int*i=l+1;
	while(i<r&&end[i[-1]]<end[*i])i++;
	if(i<r)std::inplace_merge(l,i,r,cmp);
}
long long dis(int w,int i,int d){
	long long t1=d/cnt[w]*1ll*L,t2;
	d%=cnt[w];
	int j=w?(i+d)%cnt[w]:(i-d+cnt[w])%cnt[w];
	t2=X[list[w][i]]-X[list[w][j]];
	if(w)t2=-t2;
	if(t2<0)t2+=L;
	return t1+t2;
}
int main(){
	scanf("%d%d%d",&N,&L,&T);
	list[0]=list[1]=mem;
	for(int i=0;i<N;i++){
		scanf("%d%d",X+i,W+i);
		if(!--W[i])list[1]++;
	}
	for(int i=0;i<N;i++){
		int w=W[i];
		list[w][cnt[w]++]=i;
		end[i]=w?((X[i]-T)%L+L)%L:(X[i]+T)%L;
	}
	for(int w=0;w<2;w++)if(!cnt[w]){
		for(int i=0;i<N;i++)printf("%d\n",end[i]);
		return 0;
	}
	int st=**list,pos=-1,md=L;
	for(int i=0;i<cnt[1];i++){
		int x=X[list[1][i]],d=(x-X[st])%L;
		if(d<0)d+=L;
		if(d<md)pos=i,md=d;
	}
	long long left=0,right=T*2ll+1,mid;
	while(right-left>1){
		mid=left+right>>1;
		int c0=mid/2,c1=(mid+1)/2-1;
		long long t=dis(0,0,c0)+md+dis(1,pos,c1);
		if(t<=T*2ll)left=mid;
		else right=mid;
	}
	int ty=left%2,cur=list[ty][ty?(pos+left/2)%cnt[1]:(cnt[0]-left/2%cnt[0])%cnt[0]],i=0;
	csort(mem,list[1]);
	csort(list[1],mem+N);
	std::inplace_merge(mem,list[1],mem+N,cmp);
	while(i<N&&mem[i]!=cur)i++;
	i=(i-st+N)%N;
	for(int j=0;j<N;j++)printf("%d\n",end[mem[(i+j)%N]]);
}

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

string s;

int main(){
	cin >> s;
	int m = s.size() - 1;
	long long int A = 0;
	for (int i = 0; i < (1 << m); i++){
		long long int sum = 0;
		long long int pr = 0;
		for (int j = 0; j < s.size(); j++){
			pr *= 10LL;
			pr += s[j] - '0';
			if (j == s.size() - 1){
				sum += pr;
				break;
			}
			if ((i >> j) & 1){
				sum += pr;
				pr = 0;
			}
		}
		A += sum;
	}
	printf("%lld\n", A);
	return 0;
}

Measured memory_bytes: 256