akhauriyash/Code-Regression huggingface dataset:
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  field = [[i=='#' for i in input()] for _ in range(H)]
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      if x > 0 and not field[y][x-1]:
        field[y][x-1] = True
        nq.append((y,x-1))
      if y > 0 and not field[y-1][x]:
        field[y-1][x] = True
        nq.append((y-1,x))
      if x<W-1 and not field[y][x+1]:
        field[y][x+1] = True
        nq.append((y,x+1))
      if y<H-1 and not field[y+1][x]:
        field[y+1][x] = True
        nq.append((y+1, x))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
if __name__ == "__main__":
  main()

Measured memory_bytes: 111084
from heapq import heappush, heappop
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
ls = []
ans = [0]*N
for i in range(N):
  heappush(ls, (-a[i], i))
for i in range(M):
  x, j = heappop(ls)
  x = -1*x
  heappush(ls, (-x/2,j))
  ans[j] += 1

total = 0
for i in range(N):
  total += a[i]//(2**ans[i])
print(total)

Measured memory_bytes: 96792
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい
// https://github.com/atcoder/live_library
// cppdbg: test.exeのterminalに標準入力を打てる

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq; //逆順priority_queue
typedef priority_queue<ll> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

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

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

using namespace std;

const long long P=1e9+7;

long long ans=0;
int n,k;
long long ans1,ans2;
int a[2010];

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]>a[i])
				ans1++;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[j]>a[i])
				ans2++;
	ans = ans1 * k %P;
	ans += ans2 * (((long long)k*(long long)(k-1)/2LL)%P)%P;
	ans%=P;

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)


# dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (a, p) in enumerate(A):
    for j in range(i + 1):
        # 左に詰める場合
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)

        # 右に詰める場合
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)

print(max(dp[-1]))


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

int main() {
  string S;
  cin >> S;

  int N = S.size();
  int replaced = 0;
  for (int i = 0; i < N/2; i++) {
    if (S[i] != S[N-1-i]) {
      S[i] = S[N-1];
      replaced++;
    }
  }
  cout << replaced << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <fstream>
#include <array>
#include <map>
#include <queue>
#include <time.h>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <assert.h>
#include <unordered_set>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) (min(a,b) <= (x) && (x) <= max(a,b)) //hei
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 998244353LL 
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
 
 
#define izryt bool
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
	std::fill((T*)array, (T*)(array + N), val);
}
 
//[a, b)
#define Getsum(ar, a,b) (ar[b] - ar[a])
#define INF 10000000000000000LL
#define chmax(a,b) a = max(a,b)
#define chmin(a,b) a = min(a,b)
 
struct Edge {
	int from, to;
	ll w;
	bool operator<(const Edge& rhs) const {
		return MP(w, MP(from, to)) < MP(rhs.w, MP(rhs.from, rhs.to));
	}
 
};
typedef vector<vector<Edge>> Graph;
typedef unsigned long long ull;
 
pii updtp2(pii p, int nw){
  if(p.first == -1) p.first = nw;
  else if(p.second == -1) p.second = nw;
  else if(p.first >= nw) {
    p.second = p.first;
    p.first = nw;
  }
  else if(p.second >= nw) p.second = nw;
  return p;
}
 
#define isValid(y,x) (y >=0 && y < n && x >= 0 && x < m)

const pii Dir[4] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

int main(){
  int t;
  cin >> t;
  REP(_,t){
    ll n,a,b,c,d;
    cin >> n >> a >> b >> c >> d;

    map<ll,ll> memo;
    
    memo[0] = 0;
    memo[1] = d;
    
    function<ll(ll)> func = [&](ll x){
      if(memo.count(x)) return memo[x];

      memo[x] = min({func(x/2) + x%2*d + a,func((x+1)/2) + (2-x%2)*d + a, func(x/3) + x%3*d + b,func((x+2)/3) + (3-x%3)*d + b,func(x/5) + x%5*d + c,func((x+4)/5) + (5-x%5)*d + c});
      __int128 buf = ((__int128)x) * d;
      if(buf < (__int128)LLONG_MAX)
        memo[x] = min(memo[x], d * x);
      return memo[x];
    };
    
    cout << func(n) << endl;
  }
	return 0;
} 

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

int main()
{
    int d;
    cin>>d;
    if (d==25) cout<<"Christmas";
    else if(d==24) cout<<"Christmas Eve";
    else if(d==23) cout<<"Christmas Eve Eve ";
    else if(d==22) cout<<"Christmas Eve Eve Eve";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a,b,c,x,ans,i,j,k;
int main(){
	scanf("%d%d%d%d",&a,&b,&c,&x);
	for(i=0;i<=a&&i*500<=x;i++)
		for(j=0;j<=b&&i*500+j*100<=x;j++)
			for(k=0;k<=c&&i*500+j*100+k*50<=x;k++)
				if(i*500+j*100+k*50==x) ans++;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  vector<int> ans(N+1, 0);
  for(int x = 1; x <= 110; x++){
    for(int y = 1; y <= 110; y++){
      for(int z = 1; z <= 110; z++){
        int res = x*x + y*y + z*z + x*y + y*z + z*x;
        if(res > N) continue;
        ans[res]++;
      }
    }
  }
  for(int i = 1; i <= N; i++){
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define init ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL);
using namespace std;

//  =========     /\       /|    |====/|
//      |        /  \       |    |   / |
//      |       /____\      |    |  /  |
//      |      /      \     |    | /   |
//  ========= /        \  =====  |/====|  
//  code

int main(){
    init;
    int n,k,i,j,l;
    cin>>n>>k;
    int dp[n],h[n];
    
    for(i=0;i<n;i++){
        cin>>h[i];
        dp[i] = 1e9 + 5;
    }
    dp[0] = 0;
    for(i=1;i<n;i++){
        for(j=i-1;j>=max(i-k , 0);j--){
            dp[i] = min(dp[i],abs(h[j]-h[i]) + dp[j]);
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

ll countDiv(ll n) {
	if (n == 1)
		return 0;

	ll cnt = 1;	// n is a divisor. We have to count all divisors not 1
	for (ll i = 2; i*i <= n; i++) {

		if (i*i == n)
			cnt ++;
		else if (n%i == 0)
			cnt += 2;
	}

	return cnt;
}

bool reduced(ll n, ll i) {
	while (n%i == 0)
		n /= i;

	return n % i == 1;
}

int main() {

	IOS

	ll n;
	cin >> n;

	ll m = n-1;

	ll cnt = 1;
	cnt += countDiv(m);

	for (ll i = 2; i*i <= n; i++) {
		if (i*i == n)
			cnt++;

		else if (n%i == 0) {
			if (reduced(n, i))
				cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n, m;

struct unionfind {
  int parent;
  int node;
  int edge;
};
unionfind g[100001];

void init() {
  for (int i = 0; i <= n; i++) {
    g[i].parent = i;
    g[i].node = 1;
    g[i].edge = 0;
  }
}

int find(int x) {
  if (x == g[x].parent) {
    return x;
  }
  int res = find(g[x].parent);
  g[x].node = g[res].node;
  g[x].edge = g[res].edge;
  g[x].parent = res;
  return res;
}

void merge(int x, int y) {
  if (x > y) {
    x ^= y;
    y ^= x;
    x ^= y;
  }
  g[x].node += g[y].node;
  g[x].edge += g[y].edge + 1;
  g[y].parent = x;
}

ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }
    x = x * x % mod;
    n /= 2;
  }
  return res;
}

ll dp[5001][5001];

int main() {
  int p[5001];
  ll cnt = 0LL, ans, k = 0LL, mi = 0LL, m;
  vector<ll> v;
  cin >> n;
  m = n;
  init();
  for (int i = 0; i < n; i++) {
    cin >> p[i + 1];
    if (p[i + 1] == -1) {
      k++;
    } else {
      find(i + 1);
      find(p[i + 1]);
      if (g[i + 1].parent != g[p[i + 1]].parent) {
        merge(g[i + 1].parent, g[p[i + 1]].parent);
        cnt++;
      }
    }
  }
  ans = (cnt)*mod_pow((ll)n - 1, k, MOD) % MOD;
  for (int i = 1; i <= n; i++) {
    find(i);
    if (p[i] == -1) {
      v.push_back(g[i].node);
      m -= g[i].node;
    }
  }
  dp[0][0] = 1;
  for (ll i = 0; i < v.size(); i++) {
    ans += (n - v[i]) * mod_pow(n - 1, v.size() - 1, MOD) % MOD;
    ans %= MOD;
    for (ll j = 0; j <= i + 1; j++) {
      dp[i + 1][j] = dp[i][j];
      if (j == 1) {
        dp[i + 1][j] += dp[i][j - 1] * v[i] % MOD;
      } else if (j) {
        dp[i + 1][j] += dp[i][j - 1] * (ll)(j - 1) * v[i] % MOD;
      }
      dp[i + 1][j] %= MOD;
    }
  }
  for (ll i = 2; i <= n; i++) {
    ans +=
        MOD - dp[v.size()][i] % MOD * mod_pow(n - 1, v.size() - i, MOD) % MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 120352
Scanf.scanf "%d" (fun n ->
    let a = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in

    let rec loop i dis balance stock =
        if i = n then balance + stock * a.(n - 1) else
            if dis < 0 && a.(i) > a.(i - 1) then loop (i + 1)   1  (balance - balance / a.(i - 1) * a.(i - 1)) (balance / a.(i - 1)) else
            if dis > 0 && a.(i) < a.(i - 1) then loop (i + 1) (-1) (balance + stock * a.(i - 1)) 0 else
                loop (i + 1) dis balance stock
    in
    Printf.printf "%d\n" @@ 
    if a.(0) < a.(1) then loop 1 1    (1000 - 1000 / a.(0) * a.(0)) (1000 / a.(0))
                     else loop 1 (-1) 1000 0
)


Measured memory_bytes: 3848
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e17;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int N=100005;

void solve()
{
    int a[3];
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    if(a[0]==a[1]&&a[1]!=a[2])
    {
        cout<<"Yes"<<endl;
    }
    else if(a[1]==a[2]&&a[1]!=a[0])
    {
        cout<<"Yes"<<endl;
        
    }
    else
        cout<<"No"<<endl;
}
int32_t main()
{
    IOS;
    
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
n = int(input())
H = [int(el) for el in input().split(' ')]

d = max_d = 0
for i in range(1, n):
    if H[i] <= H[i-1]:
        d += 1
        max_d = max(d, max_d)
    else:
        d = 0
print(max_d)


Measured memory_bytes: 14252
a, b, k = gets.chomp.split(" ").map(&:to_i);

if (a > k)
  a -= k
  k = 0
else
  k -= a
  a = 0
end

if (b > k)
  b -= k
  k = 0
else
  k -= b
  b = 0
end

puts "#{a} #{b}"

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

int main()
{
  int a, b;
  cin >> a >> b;
  if(a % 3 == 0 || b % 3 == 0 || (a + b)%3 == 0)
  {
    cout << "Possible" << endl;
  }
  else
  {
    cout << "Impossible" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const ll INF = 1e17;
ll N, M, L, Q;
ll fuel[305][305];
ll dist[305][305];
ll s[105000], t[105000];
ll A[100000], B[100000], C[100000];

void input() {
    cin >> N >> M >> L;
    for(int i = 1; i <= M; i++) cin >> A[i] >> B[i] >> C[i];
    cin >> Q;
    for(int i = 1; i <= Q; i++) cin >> s[i] >> t[i];
}

void solve() {
    input();
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            fuel[i][j] = INF;
            dist[i][j] = INF;
        }
        fuel[i][i] = 0;
        dist[i][i] = 0;
    }
    for(int i = 1; i <= M; i++) {
        chmin(fuel[A[i]][B[i]], C[i]);
        chmin(fuel[B[i]][A[i]], C[i]);
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            for(int k = 1; k <= N; k++) {
                chmin(fuel[j][k], fuel[j][i] + fuel[i][k]);
            }
        }
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(i == j) continue;
            if(fuel[i][j] <= L) chmin(dist[i][j], 1LL);
        }
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            for(int k = 1; k <= N; k++) {
                chmin(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
    for(int i = 1; i <= Q; i++) {
        if(dist[t[i]][s[i]] < INF) cout << dist[t[i]][s[i]] - 1 << "\n";
        else cout << -1 << "\n";
    }
    return;
}

int main() {
//    freopen("std.in","r",stdin);
//    freopen("std.out","w",stdout);
    solve();
    return 0;
}


Measured memory_bytes: 4864
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

int main(){
  int n;
  cin>>n;
  
  vector<int> A(n),B(n),C(n);
  rep(i,n) cin>>A[i];
  rep(i,n) cin>>B[i];
  rep(i,n) cin>>C[i];
  sort(ALL(A));
  sort(ALL(C));
  
  ll a,c;
  ll ans=0;
  rep(i,n){
    a=lower_bound(ALL(A),B[i])-A.begin();
    c=C.end()-upper_bound(ALL(C),B[i]);
    ans+=a*c;
  }
  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 4556
#include<iostream>
#include<stack>
#include<string>
using namespace std;

bool solve(string str) {
  stack<char> stk;
  for (char c : str) {
    if (c == '[') {
      stk.push(c);
    } else if (c == '(') {
      stk.push(c);
    } else if (c == ']') {
      if (stk.empty() or stk.top() != '[') {
        return false;
      }
      stk.pop();
    } else if (c == ')') {
      if (stk.empty() or stk.top() != '(') {
        return false;
      }
      stk.pop();
    }
  }
  return stk.empty();
}

int main() {
  string query;
  while (getline(cin, query) and query != ".") {
    cout << (solve(query) ? "yes" : "no" ) << endl;
  }
}

Measured memory_bytes: 1184
#include <cstdint>
#include <algorithm>
#include <iostream>

// mondai_b
int main()
{
    int32_t h, n;

    std::cin >> h >> n;

    for ( int _i = 0; _i < n ; _i++ ) {
        int32_t a;
        std::cin >> a;
        h -= a;
    }

    if ( h > 0 ) {
        std::cout << "No" << std::endl;
    } else {
        std::cout << "Yes" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int a[200011];

bool check(long long x, long long y,long long z){
    
    long long sum = x+z;
    
    long long tmp = y^z;
    
    if(sum==tmp) return true;
    return false;

    
    
    
}
int main(int argc, const char * argv[]) {
    
    int n;
    
    scanf("%d",&n);
    
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    
    
    int l = 0;
    int r = 0;
    long long tmp = a[l];
    long long xo = a[l];
    long long ans = 0;
    while(l<=r && r<n){
        if(l==r){
            tmp = a[l];
            xo = a[l];
            r++;
          
        }
        else if(check(tmp,xo,a[r])){//가능하면 더해주고..
            ans+= r-l;
            tmp += a[r];
            xo ^= a[r];
            r++;
            
        }else{
            tmp-=a[l];
            xo = tmp;
            l++;
        }
        
    }
    
    printf("%lld\n",ans+n);
    
    return 0;
}


Measured memory_bytes: 1024
from collections import deque

class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}

    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def next_vertices(self, v):
        """ 隣接したノードを返す """
        return self.adjacency_dict[v]

def bfs(start):
    visited[start] = True
    q = deque()
    q.append(start)

    group_size = 1
    while q:
        v_now = q.popleft()
        for v_next in graph.next_vertices(v_now):
            if visited[v_next] == False:
                visited[v_next] = True
                q.append(v_next)
                group_size += 1

    return group_size
    

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

graph = Graph()
for i in range(1, N+1):
    graph.add_vertex(i)
for v1, v2 in AB:
    graph.add_edge(v1, v2)

visited = [False] * (N+1)

max_group_size = 1
for i in range(1, N+1):
    if visited[i] == False:
        group_size = bfs(i)
        max_group_size = max(max_group_size, group_size)
    
print(max_group_size)

Measured memory_bytes: 140172
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)

inline int gn(){
    int s=0,f=1; 
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=s*10+ch-'0';ch = getchar();}
    return s*f;
}

inline ll gl(){
    ll s=0,f=1; 
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=s*10+ch-'0';ch = getchar();}
    return s*f;
}

const int N=2e5+100;
ll num[3],n;
string s[N];
char ans[N];

bool dfs(int cnt,ll num[]){
    if(cnt==n){
        puts("Yes");
        rep(i,n){
            cout<<ans[i]<<endl;
        }
        return true;
    }
    if(num[s[cnt][0]-'A']==0&&num[s[cnt][1]-'A']==0){
        return false;
    }
    if(num[s[cnt][0]-'A']==1&&num[s[cnt][1]-'A']==1){
        rep(i,2){
            ans[cnt]=s[cnt][1-i];
            --num[s[cnt][i]-'A'];
            ++num[s[cnt][1-i]-'A'];
            if(dfs(cnt+1,num))return true;
            ++num[s[cnt][i]-'A'];
            --num[s[cnt][1-i]-'A'];
        }
    }
    else{
        if(num[s[cnt][0]-'A']>num[s[cnt][1]-'A']){
            ans[cnt]=s[cnt][1];
            --num[s[cnt][0]-'A'];
            ++num[s[cnt][1]-'A'];
            if(dfs(cnt+1,num))return true;
        }
        else{
            ans[cnt]=s[cnt][0];
            --num[s[cnt][1]-'A'];
            ++num[s[cnt][0]-'A'];
            if(dfs(cnt+1,num))return true;
        }
    }
    return false;
}

void solve(){
    n=gn();
    rep(i,3)num[i]=gl();
    rep(i,n)cin>>s[i];
    if(!dfs(0,num)){
        puts("No");
    }
}

int main(){
    // int t;
    // t=gn();
    // while(t--)
        solve();
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/


Measured memory_bytes: 19344
N, M = map(int, input().split())
X, Y = [], []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
mx = max(X)
Y.sort()
r = 0
for y in Y[::-1]:
    if y < mx: break
    r+=1
    M -= y
    if M <= 0: break
if M > 0: r += -(-M//mx)
print(r)


Measured memory_bytes: 62296
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int A[200005];
int K;
int V[200005];
int nb = 0;
void Read()
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i];
        V[A[i]]++;
        if(V[A[i]] == 1)
            ++nb;
    }
}

void Solve()
{
    sort(V + 1, V + N + 1);
    int ans = 0;
    for(int i = 1; i <= N && nb > K; i++)
    {
        if(V[i] == 0)
            continue;
        --nb;
        ans += V[i];
    }
    cout << ans << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>
#include<string.h>

int main(){
	int a[3], b[3], i, len, j;
	char str[100];
	while(1){
		scanf("%s", &str);
		if(str[0] == '0') break;
		for(i = 0; i < 3; i++){
			a[i] = 0;
			b[i] = 0;
		}
		len = strlen(str);
		for(i = 1; i < len; i++){
			if(str[i] == 'A') a[0]++;
			if(str[i] == 'B') b[0]++;
		}
		if(a[0] > b[0]) a[0]++;
		if(b[0] > a[0]) b[0]++;
		for(i = 1; i < 3; i++){
			scanf("%s", &str);
			len = strlen(str);
			for(j = 1; j < len; j++){
				if(str[j] == 'A') a[i]++;
				if(str[j] == 'B') b[i]++;
			}
			if(a[i] > b[i]) a[i]++;
			if(b[i] > a[i]) b[i]++;
		}
		for(i = 0; i < 3; i++) printf("%d %d\n", a[i], b[i]);
	}
	return 0;
}

Measured memory_bytes: 536
#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() {
    string S;
    cin >> S;
    if (S[2] == S[3] && S[4] == S[5]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

struct Node {
  int key;
  Node *p, *l, *r;
};

Node *null, *root;

void Print_P(Node *u) {
  if (u == null)
    return;

  printf(" %d", u->key);
  Print_P(u->l);
  Print_P(u->r);
}

void Print_M(Node *u) {
  if (u == null)
    return;

  Print_M(u->l);
  printf(" %d", u->key);
  Print_M(u->r);
}

Node *Minimum(Node *x) {
  while (x->l != null)
    x = x->l;

  return x;
}

Node *Successor(Node *x) {
  if (x->r != null)
    return Minimum(x->r);

  Node *y = x->p;
  while (y != null && x == y->r)
    x = y, y = y->p;

  return y;
}

void Delete(Node *z) {
  Node *y;
  if (z->l == null || z->r == null)
    y = z;
  else
    y = Successor(z);

  Node *x;
  if (y->l != null)
    x = y->l;
  else
    x = y->r;

  if (x != null)
    x->p = y->p;

  if (y->p == null) {
    root = x;
  } else {
    if (y == y->p->l)
      y->p->l = x;
    else
      y->p->r = x;
  }

  if (y != z)
    z->key = y->key;

  free(y);
}

Node *Find(Node *u, int k) {
  while (u != null && k != u->key) {
    if (k < u->key)
      u = u->l;
    else
      u = u->r;
  }

  return u;
}

void Insert(int k) {
  Node *b = null, *a = root, *c = (Node *)malloc(sizeof(Node));
  c->key = k, c->l = null, c->r = null;
  while (a != null) {
    b = a;
    if (c->key < a->key)
      a = a->l;
    else
      a = a->r;
  }
  c->p = b;

  if (b == null)
    root = c;
  else if (c->key < b->key)
    b->l = c;
  else
    b->r = c;
}

int main() {
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    char o[7];
    scanf("%s", o);
    if (strcmp(o, "insert") == 0) {
      int k;
      scanf("%d", &k);
      Insert(k);
    } else if (strcmp(o, "find") == 0) {
      int k;
      scanf("%d", &k);
      if (Find(root, k) != null)
        printf("yes\n");
      else
        printf("no\n");
    } else if (strcmp(o, "delete") == 0) {
      int k;
      scanf("%d", &k);
      Delete(Find(root, k));
    } else {
      Print_M(root);
      printf("\n");
      Print_P(root);
      printf("\n");
    }
  }
}



Measured memory_bytes: 21988
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+23;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=k;i<n;i++){
		if(a[i]>a[i-k]) puts("Yes");
		else puts("No");
	}
}

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

int N,M;
vector<int> a;

int main() {
    cin>>N>>M;
    a.resize(N);
    for (int i=0; i<M; i++) cin>>a[i];
    int cnt=0;
    for (int i=0; i<M; i++) cnt+=a[i];
    int ans=N-cnt;
    if (ans>=0) cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}


Measured memory_bytes: 7192
//嘘っぽいのに通ってたやつでいこう

#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

char cn[100000], *ci = cn, c;
const char* owa = cn + 100000;
inline char getcha() {
	if (ci == owa) {
		fread(cn, 1, 100000, stdin);
		ci = cn;
	}
	return *ci++;
}

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


	fread(cn, 1, 100000, stdin);
	int N = 0;
	while ((c = getcha()) >= '0') N = N * 10 + c - '0';
	int sL[1001] = {}, sR[1001] = {};
	pair<int, int> RR[500], LL[500];
	int rr = 0, ll = 0;
	int tot = 0;
	rep(i, N) {
		int l = 0, r = 0;
		while ((c = getcha()) >= '(') {
			if (c == '(') r++;
			else {
				if (r > 0) r--;
				else l++;
			}
		}
		tot += r - l;
		if (l < r) {
			if (l <= 1000) sR[l] += r;
			else RR[rr++] = { l,r };
		}
		else {
			if (r <= 1000) sL[r] += l;
			else LL[ll++] = { r,l };
		}
	}

	if (tot != 0) {
		printf("No");
		return 0;
	}

	sort(RR, RR + rr);
	sort(LL, LL + ll);

	int OK = 1;
	int k = 0;
	rep(i, 1001) {
		if (sR[i]) {
			if (k < i) OK = 0;
			k += sR[i];
		}
	}
	rep(i, rr) {
		if (k < RR[i].first) OK = 0;
		k += RR[i].second - RR[i].first;
	}
	k = 0;
	rep(i, 1001) {
		if (sL[i]) {
			if (k < i) OK = 0;
			k += sL[i];
		}
	}
	rep(i, ll) {
		if (k < LL[i].first) {
			OK = 0;
		}
		k += LL[i].second - LL[i].first;
	}

	if (OK) printf("Yes");
	else printf("No");

	Would you please return 0;
}

Measured memory_bytes: 3312
a = input()
mae = int(a[:2])
usiro = int(a[2:])

if(1 <= mae <= 12):
    if(1 <= usiro <= 12):
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if(1 <= usiro <= 12):
        print('YYMM')
    else:
        print('NA')


Measured memory_bytes: 2940
n = int(input())
 
def dfs(s):

    if int(s) > n:
        return 0
    if s.count('3') > 0 and s.count('5') > 0 and s.count('7') > 0:
        cnt = 1
    else:
        cnt = 0
    cnt += dfs(s + '3')
    cnt += dfs(s + '5')
    cnt += dfs(s + '7')
    return cnt
 
 
print(dfs('0'))

Measured memory_bytes: 3060
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int D, N;
    cin >> D >> N;
    if (N == 100) {
        N = 101;
    }
    cout << N;
    REP(i, D) {
        cout << "00";
    }
    cout << endl;
    return 0;
}


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

#define INF_LL 1e18
#define INF 1e9

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()

using namespace std;

using ll = long long;
using PII = pair<int, int>;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int H, W;
	string a[501], r[501], b[501];
	cin >> H >> W;
	REP(i, H){
		cin >> a[i];
		r[i] = string(W, '.');
		b[i] = string(W, '.');
	}
	REP(i, H){
		r[i][0] = '#';
		b[i][W-1] = '#';
		if(i%2 == 0){
			REP(j, W-1){
				r[i][j] = '#';
			}
		}else{
			FOR(j, 1, W){
				b[i][j] = '#';
			}
		}
	}
	REP(i, H){
		REP(j, W){
			if(a[i][j] == '#'){
				b[i][j] = r[i][j] = '#';
			}
		}
	}
	REP(i, H){
		cout << b[i] << endl;
	}
	cout << endl;
	REP(i, H){
		cout << r[i] << endl;
	}
}


Measured memory_bytes: 1536
import collections
import sys
import bisect
input = sys.stdin.readline
N = int(input())
queue = collections.deque()
queue.append(int(input()))
for i in range(N-1):
    a = int(input())
    index = bisect.bisect_left(queue, a)
    if index == 0:
        queue.appendleft(a)
    else:
        queue[index-1] = a

print(len(queue))


Measured memory_bytes: 44592
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, a, b, c, d, e);
  	int s = a*60+b;
  	int t = c*60+d;
    Cout(t-s-e);
}

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

const ll INF = ll(1e18)+1;

int main() {

  ll n, ans = INF;
  cin >> n;
  for(ll i = 1; i * i <= n; ++i){
    if(n % i == 0){
      ll j = n / i;
      ans = min(ans, i + j -2);
    }
  }
  cout << ans << endl;
}


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

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define MP make_pair
#define PB push_back
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int INF = 1e9 + 7;
const int maxn = 2005;

int ans = INF;
int ab[maxn][maxn], ac[maxn][maxn], bc[maxn][maxn];
string a, b, c;

inline bool match(int mat[][maxn], int xl, int xr, int yl, int yr){
	int zl = max(xl, yl), zr = min(xr, yr);
	if(zl > zr)
		return true;
	return mat[zl - xl][zl - yl] >= (zr - zl + 1);
}

int main(){
	cin >> a >> b >> c;
	for(int i = a.size() - 1; i >= 0; --i) for(int j = b.size() - 1; j >= 0; --j)
		ab[i][j] = (a[i] != b[j] && a[i] != '?' && b[j] != '?' ? 0 : ab[i + 1][j + 1] + 1);
	for(int i = a.size() - 1; i >= 0; --i) for(int j = c.size() - 1; j >= 0; --j)
		ac[i][j] = (a[i] != c[j] && a[i] != '?' && c[j] != '?' ? 0 : ac[i + 1][j + 1] + 1);
	for(int i = b.size() - 1; i >= 0; --i) for(int j = c.size() - 1; j >= 0; --j)
		bc[i][j] = (b[i] != c[j] && b[i] != '?' && c[j] != '?' ? 0 : bc[i + 1][j + 1] + 1);
	int tot = a.size() + b.size() + c.size();
	FOR(i, 0, tot) FOR(j, 0, tot){
		int al = i, ar = i + a.size() - 1,
			bl = j, br = j + b.size() - 1,
			cl = 0, cr = 0 + c.size() - 1;
		if(!match(ab, al, ar, bl, br))
			continue;
		if(!match(ac, al, ar, cl, cr))
			continue;
		if(!match(bc, bl, br, cl, cr))
			continue;
		ans = min(ans, max(ar, max(br, cr)) + 1);
	}
	FOR(i, 0, tot) FOR(j, 0, tot){
		int al = i, ar = i + a.size() - 1,
			bl = 0, br = 0 + b.size() - 1,
			cl = j, cr = j + c.size() - 1;
		if(!match(ab, al, ar, bl, br))
			continue;
		if(!match(ac, al, ar, cl, cr))
			continue;
		if(!match(bc, bl, br, cl, cr))
			continue;
		ans = min(ans, max(ar, max(br, cr)) + 1);
	}
	FOR(i, 0, tot) FOR(j, 0, tot){
		int al = 0, ar = 0 + a.size() - 1,
			bl = i, br = i + b.size() - 1,
			cl = j, cr = j + c.size() - 1;
		if(!match(ab, al, ar, bl, br))
			continue;
		if(!match(ac, al, ar, cl, cr))
			continue;
		if(!match(bc, bl, br, cl, cr))
			continue;
		ans = min(ans, max(ar, max(br, cr)) + 1);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 47488
//ABC089A
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	int x;
	cin >> x;
	cout << x/3 << endl;
	return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    int R, G;
    cin >> R >> G;
    cout << G * 2 - R << endl;
    return 0;
}

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

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif

const LL INF = 1e9;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    int N;
    cin >> N;
    vector<LL> A(N+1);
    for (int i = 0; i <= N; i++) cin >> A[i];
    vector<LL> L(N+1), R(N+1);
    L[N] = R[N] = A[N];
    for (int i = N-1; i >= 0; i--) {
        L[i] = (L[i+1]+1)/2 + A[i];
        R[i] = R[i+1] + A[i];
        
    }
    //~ for (int i = 0; i <= N; i++) {
        //~ cout << i << " "<< L[i] << " " << R[i] << endl;
    //~ }
    if (L[0] > 1) {
        cout << -1 << "\n";
        return 0;
    }
    vector<LL> Q(N+1);
    Q[0] = 1;
    LL res = 1;
    for (int i = 1; i <= N; i++) {
        //~ cout << i << ": [" << L[i] << " " << R[i] << "], [" << 2*(Q[i-1]-A[i-1]) << ", " << Q[i-1] - A[i-1] << "]\n";
        if (2*(Q[i-1]-A[i-1]) < L[i] or R[i] < Q[i-1]-A[i-1]) {
            cout << -1 << "\n";
            return 0;
        }
        Q[i] = min(2*(Q[i-1]-A[i-1]), R[i]);
        res += Q[i];
        //~ cout << i << " " << Q[i] << endl;
    }
    cout << res << "\n";
    
}


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

int main()
{
	int N, x;
	int a[101];

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

	sort(a, a + N);

	for (int i = 0; i < N; i++) {
		x = x - a[i];
		if (x < 0) {
			cout << i << endl;
			return 0;
		}
	}
	
	if (x == 0) {
		cout << N << endl;
	}
	else {
		cout << N - 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
s = []
for i in range(n):
    s.append(list(map(int,input().split())))
s.sort()
ans = 0
for i in s:
    if i[1]<m:
        ans += i[0]*i[1]
        m -= i[1]
    else:
        ans += i[0]*m
        break
print(ans)
        

Measured memory_bytes: 27528
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
//deque/functional/iterator/list/map/memory/numeric/queue/set/stack/utility/vector
//#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
    string a,b;
    cin>>a>>b;
    int c=a.size();
    int d=b.size();
    int x;
    if(c>d){
		x=d;
		for(int i=0;i<x;i++){
		cout<<a[i]<<b[i];
		}
		for(int i=x;i<c;i++){
			cout<<a[i];
		}
    }else{
		x=c;
		for(int i=0;i<x;i++){
		cout<<a[i]<<b[i];
		}
		for(int i=x;i<d;i++){
			cout<<b[i];
		}
    }
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int main(void){
    ll a,b,k; cin >> a >> b >> k;
    ll tmpk = k;
    k = k - a;
    a = a - tmpk;
    if(a<0) a = 0;
    if(k<0) k = 0;
    b = b - k;
    if(b<0) b = 0;
    cout << a << " " << b << endl;
}



Measured memory_bytes: 256
#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 k; cin >> k;
	queue<ll> q;
	REP(i, 9) q.push(i + 1);
	REP(i, k - 1) {
		ll num = q.front();
		q.pop();
		ll rem = num % 10;
		if (rem != 0)
			q.push(10 * num + rem - 1);
		q.push(10 * num + rem);
		if (rem != 9)
			q.push(10 * num + rem + 1);
	}
	cout << q.front() << '\n';
    return 0;
}


Measured memory_bytes: 5028
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

typedef long long ll;
vector<ll> A;
vector<ll> nxt;
ll sum[1005];
ll tmp;
int main() {
  int n,k;
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    sum[i+1] = sum[i] + a;
  }
  for(int i = 0; i < n; i++) {
    for(int j = i + 1; j <= n; j++) {
      A.push_back(sum[j] - sum[i]);
      tmp = max(tmp,sum[j] - sum[i]);
    }
  }

  // sort(A.begin(),A.end(),greater<ll> ());
  
  /*  for(int i = 0; i < A.size(); i++) {
   
    }*/
  

  int K = 0;
  while(tmp > 0) {
    tmp /=2;
    K++;
  }


 
  ll ans = 0;
  for(int i = K - 1; i >= 0; i--) {
    ll s = (1ll << i);
    int kk = 0;
    for(int j = 0; j < A.size(); j++) {
    
      if(A[j] & s) {
	kk++;
	nxt.push_back(A[j]);
      }
    }
    // cout << s <<"   "<<kk <<"  "<<nxt.size()<<"  "<<A.size()<< endl;
     if(kk >= k) {
       ans += s;
      swap(nxt,A);
      nxt.clear();
     }
     else nxt.clear();
  }

  cout << ans << endl;
}


Measured memory_bytes: 6512
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int len = s.length();
    for (int i = 0;i < len;i++)
    {
        if (s[i] == 'C')
        {
            for (int j = i + 1;j < len;j++)
            {
                if (s[j] == 'F')
                {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int> pii;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
//bridge:it is an edge,without which the graph will be unconnected.
int n,m;
const int Maxn=5e5+5;
vector<int>G[Maxn];
int depth[Maxn],pare[Maxn],low[Maxn];
void dfs(int u,int par,int d){
	depth[u]=d;
	pare[u]=par;
	rep(i,SZ(G[u])){
		int to=G[u][i];
		if(to!=par){
			if(depth[to]==-1){
				dfs(to,u,d+1);
				chkmin(low[u],low[to]); 
			}else{
				chkmin(low[u],depth[to]);
			}
		}
	}
	chkmin(low[u],depth[u]);
}
int main(){
	cin>>n>>m;
	rep(i,m){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	memset(depth,-1,sizeof(depth));
	rep(i,Maxn)low[i]=INF;
	low[1]=0;
	dfs(1,-1,0);
	vector<pii>bridge;
	for(int i=2;i<=n;i++){
		if(low[i]==depth[i]){
			bridge.push_back(make_pair(pare[i],i));
		}
	}
	cout<<SZ(bridge)<<endl;
	return 0;
}

Measured memory_bytes: 19280
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) throws IOException{ 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			String line = br.readLine();
			String[] str = line.split("");
			int sum = 0;
			if ("0".equals(str[0])){break;}
			for (int i = 0 ; i < str.length ; i++ ) {
				sum += Integer.parseInt(str[i]);
			}
		System.out.println(sum);
		}
	}
}

Measured memory_bytes: 25404
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			int n = sc.nextInt();
			sc.nextLine();
			for(int i=0;i<n;i++){
				String s = sc.nextLine();
				System.out.println(s.replace("Hoshino", "Hoshina"));
			}
		}
	}	
}

Measured memory_bytes: 17304
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
const int MOD = 1e9+7;
char a[N][N];
int dp[N][N];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)   scanf(" %s",a[i]+1);
    dp[0][1] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j] == '#')  dp[i][j] = 0;
            else                dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    string s; cin>>s;
    map<char,int> mp;
    rep(i,3) mp[s[i]]++;
    bool ok=false;
    if(mp['a']*mp['b']*mp['c']==1) ok=true;
    cout<<(ok?"Yes":"No")<<endl;
}

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

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int,int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int,int>;
using vMii = vector<Mii>;

#define fi first
#define se second
#define INF INT_MAX
#define mod(a,m) (a%m+m)%m
#define PB push_back
#define MP make_pair

int n;
vi a;
vvll memo;

ll dp(int i, int j) {
	ll& ans = memo[i][j];
	if(ans != -1) return ans;
	if(i == j) return ans = a[i];
	return ans = max(a[i] - dp(i+1, j), a[j] - dp(i, j-1));
}

int main(){
//	cout.setf(ios::fixed);
//	cout.precision(4);
	while (cin >> n) {
		a = vi(n);
		for (int i = 0; i < n; ++i) cin >> a[i];
		memo = vvll(n, vll(n, -1));
		cout << dp(0, n-1) << '\n';
	}
}



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

int main() {
int N;
  cin >> N;
int Nc = N;
int sum = 0;
  for(int i = 0; i < 9; i++){
    sum += N % 10;
    N = N / 10;
  }
  if(Nc % sum == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3552