akhauriyash/Code-Regression huggingface dataset:
def main():
    import copy
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    D = [[float("inf")]*(N+1) for i in range(N+1)]
    ID = [[float("inf")]*(N+1) for i in range(N+1)]
    NEX = [[set() for j in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        a,b,c = map(int,input().split())
        D[a][b] = c
        D[b][a] = c
        ID[a][b] = i
        ID[b][a] = i
        NEX[a][b].add(b)
        NEX[b][a].add(a)
        
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    NEX[i][j].clear()
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
                elif D[i][j] == D[i][k]+D[k][j] and i!=j and j!=k and k!=i and D[i][j]<float("inf"):
                    for l in NEX[i][k]:
                        NEX[i][j].add(l)
    S = set()
    for i in range(1,N+1):
        for j in range(1,N+1):
            if i != j:
                for l in NEX[i][j]:
                    S.add(ID[i][l])
                #print(i,j,D[i][j],NEX[i][j])
    #print(S)            
    print(M-len(S))
            
    
    
main()

Measured memory_bytes: 51696
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long int ll;

#define C(I) cout<<(I)<<endl
int n;

int dsm(int target){
    int sum=0;
    while(target){
        sum+=target%10;
        target/=10;
    }
    return sum;
}


int main(){
    cin>>n;
    cout<<(n%dsm(n)==0 ? "Yes":"No")<<endl;
}

Measured memory_bytes: 384
from itertools import permutations
n = int(input())
x = ''.join([str(i) for i in range(1,  n + 1)])
p = tuple(input().split())
q = tuple(input().split())
pers = list(permutations(x, n))
pers.sort()
print(abs(pers.index(p) - pers.index(q)))

Measured memory_bytes: 8052
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 20021225
#define N 160
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
int f[2][N][N],n,K,mdn;
void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}
void solve1()
{
	f[0][0][0]=1; int cur=0,lst=1;
	for(int i=1;i<=n;i++)
	{
		cur^=1,lst^=1; memset(f[cur],0,sizeof(f[cur]));
		for(int j=0;j<K/2+1;j++)	for(int k=0;k<K/2+1;k++)
		{
			if((i&1))
			{
				upd(f[cur][0][k],f[lst][j][k]);
				if(j<K/2)	upd(f[cur][j+1][k],f[lst][j][k]);
			}
			else
			{
				upd(f[cur][j][0],f[lst][j][k]);
				if(k<K/2)	upd(f[cur][j][k+1],f[lst][j][k]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<K/2+1;i++)	for(int j=0;j<K/2+1;j++)
		upd(ans,f[cur][i][j]);
	printf("%d\n",ans);
}
int g[N*2][N][N];
void solve2()
{
	g[0][0][0]=1; int cur=0,ans=0;
	for(int i=2;i-K<=n;i+=2)
	{
		for(int j=0;j<=n;j++)	for(int k=0;k<=K+1;k++)
			upd(g[i][0][0],g[i-2][j][k]);
		if(i<=n)
		{
			for(int j=0;j<=n;j++)	for(int k=0;k<=K+1;k++)
				upd(g[i][j+1][0],g[i-2][j][k]);
		}
		if(i-K>=1)
		{
			for(int j=0;j<=n;j++)
			{
				for(int k=1;k<=K;k++)
					upd(g[i][0][k+1],g[i-2][j][k]);
				upd(g[i][0][0],g[i-2][j][0]);
			}
		}
		if(i<=n && i-K>=1)
		{
			for(int j=0;j<=n;j++)	for(int k=0;max(j+2,k+1)<=K+1;k++)
				upd(g[i][j+1][max(j+2,k+1)],g[i-2][j][k]);
		}
		cur=i;
	}
	for(int i=0;i<=n;i++)	for(int j=0;j<=K+1;j++)
		upd(ans,g[cur][i][j]);
	printf("%d\n",ans);
}
int main()
{
	n=read(),K=read(),mdn=read();
	if(K&1)	solve2();
	else	solve1();
	return 0;
}


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

int main()
{
   ll n;
   cin>>n;
   vector<ll> arr(n+1);
   for(ll i=1;i<=n;i++)
      cin>>arr[i];
   vector<ll> left(n+2);
   vector<ll> right(n+2);
   left[0] = right[n+1] = 0;

   for(ll i=1;i<=n;i++)
      left[i] = __gcd(left[i-1],arr[i]);
   for(ll i = n;i>=1;i--)
      right[i] = __gcd(right[i+1],arr[i]);

   ll ans = 1;
   for(int i=0;i<=(n+1);i++)
      ans = max(ans, __gcd(left[i-1],right[i+1]));
   
   cout<<ans;
   return 0;
}


Measured memory_bytes: 5636
#include <bits/stdc++.h>
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, f[3005][3005]; char s[3005];
int main() {
	read(n), scanf("%s", s+2), f[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			if (s[i] == '>') f[i][j] = f[i-1][j-1];
			else f[i][j] = (f[i-1][i-1]-f[i-1][j-1]+P)%P;
		for (int j = 1; j <= i; j++)
			(f[i][j] += f[i][j-1]) %= P;
	}
	return printf("%d\n", f[n][n]), 0;
}


Measured memory_bytes: 34176
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;
int n, ans = 0, h[22];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> h[i];
		bool ok = true;
		for (int j = 0; j < i; ++j)
			if (h[j] > h[i]) {
				ok = false;
				break;
			}

		if (ok)
			++ans;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define adj_list vector<vi>
#define endl "\n"
#define INF_INT 2e9
#define INF_LL 2e18
#define matmax 25
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pair<int, int> >
#define pl pair<ll, ll>
#define pll pair<ll, pair<ll, ll> >
#define vi vector<int>
#define vl vector<ll>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long int ll;

int lsone(int n)
{
	return (n&-n);
}

ll pow1(ll a, ll b)
{
	if (b == 0)
		return 1ll;
	else if (b == 1)
		return a;
	else
	{
		ll x = pow1(a, b/2);
		x *= x;
		x %= mod;
		if (b%2)
		{
			x *= a;
			x %= mod;
		}
		return x;
	}
}

ll n, h[110000], dp[110000], k;

int main()
{
	fastio;		
	cin>>n>>k;

	for (int i = 1; i <= n; i++)
		cin>>h[i];

	dp[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		dp[i] = 1e18;
		for (int j = i-1; j >= max(1ll, i-k); j--)
		{
			dp[i] = min(dp[i], dp[j]+abs(h[i]-h[j]));
		}
	}

	cout<<dp[n]<<endl;

	return 0;
}


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

#ifdef _PRINTDEBUG
  #include "lib/printdebug.hpp"
#else
  #define printdebug(...) 1
#endif
#define MOD_1_000_000_007 (1000000007)
#define IINF (1<<28)
#define LINF (1LL<<60)
#define rep(i, n)      REP(i, 0, (n))
#define repc(i, n)     REPC(i, 0, (n))
#define REP(i, n, m)   for (int i = (int)(n); i <  (int)(m); i++)
#define REPC(i, n, m)  for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
#define yesno(cond)       YESNO((cond), "Yes", "No")
#define YESNO(cond, a, b) cout << ((cond) ? (a) : (b)) << "\n"

namespace solver {
  using namespace std;
  typedef long long ll;

  static const int MAX = 3030;
  int N, as[MAX];
  ll dp[MAX][MAX];

  void init() {
    cin >> N;
    rep(i, N) {
      cin >> as[i];
    }
    repc(l, N) REPC(r, l, N) {
      if((N-r+l)%2) dp[l][r] = LINF;
      else dp[l][r] = -LINF;
    }
  }

  ll rec(int l, int r, bool turn) {
    if(abs(dp[l][r]) != LINF) return dp[l][r];
    if(l==r) return dp[l][r] = 0;
    if(turn) {
      dp[l][r] = max(dp[l][r], rec(l+1, r, !turn) + as[l]);
      dp[l][r] = max(dp[l][r], rec(l, r-1, !turn) + as[r-1]);
    } else {
      dp[l][r] = min(dp[l][r], rec(l+1, r, !turn) - as[l]);
      dp[l][r] = min(dp[l][r], rec(l, r-1, !turn) - as[r-1]);
    }
    return dp[l][r];
  }

  void solve() {
    cout << rec(0, N, true) << "\n";
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  solver::init();
  solver::solve();
  return 0;
}

Measured memory_bytes: 72064
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

int main() {
  int H, W;
  cin >> H >> W;
  string s;
  rep(i, H) rep(j, W) {
    cin >> s;
    if (s == "snuke") {
      cout << char('A'+j) << i+1 << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
# include <bits/stdc++.h> 
# define imax(a,b) ((a)>(b))?(a):(b)
# define imin(a,b) ((a)<(b))?(a):(b)
# define LL long long 
# define is(a) (a>='0'&&a<='9')
using namespace std;
int n;
string st;
inline void read(int &x)
{
	x=0;
	int f=0;
	char ch=getchar();
	for (; !is(ch); ch=getchar()) f|=(ch=='-');
	for (; is(ch); ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	x=(f)?-x:x;
}
int main()
{
	read(n);
	getline(cin,st);
	if (n<3200) printf("red");
	else cout<<st;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include<algorithm>
#include<cstdio>
#define inf 0x7fffffff
using namespace std;
#define N 1005
map<string, int>fy;
int n, m;

struct node
{
    int s, t;
} p[N], q[N];

void change(int i)
{
    if (p[i].t >= 2400)
    {
        p[i].s += 1;
        p[i].t -= 2400;
    }
    p[i].s = p[i].s * 24 * 60 + (p[i].t / 100)*60 + p[i].t % 100;
    p[i].t = p[i].s + 30;
}

bool cmp(const node a, const node b)
{
    if (a.s != b.s)
        return a.s < b.s;
    else
        return a.t < b.t;
}

int main()
{
    string fuck;
    while (scanf("%d", &n))
    {
        if (n == 0)
            break;
        fy.clear();
        for (int i = 1; i <= n; i++)
        {
            cin >> fuck >> p[i].s >> p[i].t;
            if (!fy[fuck])
                fy[fuck] = i;

            change(i);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            cin >> fuck;
            q[i].s = p[fy[fuck]].s;
            q[i].t = p[fy[fuck]].t;
        }
        sort(q, q + m, cmp);
        bool flag=1;
        for (int i = 1; i < m; i++)
        {
            if (q[i].s < q[i - 1].t)
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
        printf("-1\n");
        continue;
        }
        sort(&p[1], &p[n + 1], cmp);
        int ans = m;
        if (m == 0)
        {
            int cur = -inf;
            for (int gg = 1; gg <= n; gg++)
            {
                if (p[gg].s >= cur)
                {
                    ans++;
                    cur = p[gg].t;
                }
                else if (p[gg].t < cur)
                {
                    cur = p[gg].t;
                }
            }
            printf("%d\n", ans);
            continue;
        }
        int cnt = 0;
        q[m].s = inf;
        for (int i = 1; i <= n;)
        {
            int j = i;
            for (; j <= n && p[j].t <= q[cnt].s;)
                j++;
            int cur = -inf;
            for (int gg = i; gg <= j - 1; gg++)
            {
                if (p[gg].s >= cur)
                {
                    ans++;
                    cur = p[gg].t;
                }
                else if (p[gg].t < cur)
                {
                    cur = p[gg].t;
                }
            }
            for (; j <= n && p[j].s < q[cnt].t;)
                j++;
            cnt++;
            i = j;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 1036
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;

const int N = (int) 1e6 + 6, mod = (int) 0;
int cnt = 1, par[N];
vector<int> adj[N];
int find(int v) { return v == par[v]? v: par[v] = find(par[v]); }
void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    cnt++;
    par[u] = v;
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) par[i] = i;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int x;
            cin >> x;
            --x;
            adj[x].push_back(i);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < (int) adj[i].size() - 1; ++j)
            unite(adj[i][j], adj[i][j + 1]);
    }
    if (cnt == n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}


Measured memory_bytes: 25728
n, m = gets.chomp.split(" ").map(&:to_i);

s = gets.strip()
t = gets.strip()

l = n * m /  m.gcd(n)



result = true

for i in 0...n do
    if i * m % n == 0
        k = i * m / n
        if k < t.size() and t[k] != s[i]
            result = false
        end
    end
end

if result
    print(l)
else
    print(-1)
end


Measured memory_bytes: 2044
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
inf=float("inf")
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy]==".":
            data=[[inf]*W for i in range(H)]
            que=[[sx,sy]]
            data[sx][sy]=0
            count=1
            while que:
                h=[]
                for x,y in que:
                    for dx,dy in d:
                        nx,ny=x+dx,y+dy
                        if 0<=nx<H and 0<=ny<W and S[nx][ny]=="." and data[nx][ny]==inf:
                            h.append([nx,ny])
                            data[nx][ny]=count
                que=h
                count+=1
            for i in range(H):
                for j in range(W):
                    if data[i][j]!=inf:
                        ans=max(ans,data[i][j])
print(ans)

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


int main(void) {
  string s;
  cin >> s;

  string ans((s.length() + 1) / 2, 'a');
  for (int i = 0; i < s.length(); i += 2) {
    ans[i / 2] = s[i];
  }

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

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <class T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

void usaco(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(name.size())
    {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

signed main()
{
    usaco();
    int n, ans = 0;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i)
    {
        for (int j = i+1; j < n; ++j)
        {
            for (int k = j+1; k < n; ++k)
            {
                if (a[i] != a[j] && a[j] != a[k] && a[k] != a[i] && a[i]+a[j] > a[k] && a[i]+a[k] > a[j] && a[j]+a[k] > a[i]) ++ans;
            }
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    int n;
    cin >> n;
    vector<vector<char>> board(n, vector<char>(n));
    rep(y, n) rep(x, n) cin >> board[y][x];

    auto mapping = [&](int y, int x) {
        vector<vector<char>> next(n, vector<char>(n));
        rep(yi, n) rep(xi, n) {
                next[yi][xi] = board[(yi + y) % n][(xi + x) % n];
            }
        return next;
    };

    auto check = [&](vector<vector<char>> &next) -> bool {
        rep(y, n) rep(x, n) {
                if (next[y][x] != next[x][y]) return false;
            }
        return true;
    };

    int ans = 0;
    rep(y, n) {
//        rep(x, n) {
        vector<vector<char>> next = mapping(y, 0);
        bool ok = check(next);
        if (ok) ans += n;
//        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3832
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int main(){
	int A,B,C;
	cin>>A>>B>>C;
	if(B/A>=C)cout<<C;
	else cout<<B/A;
	return 0;
	}

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

int main(){
  string C;
  cin >> C ;
  if(C=="a"){
    cout << "b" << endl;
  }
    if(C=="b"){
    cout << "c" << endl;
  }
    if(C=="c"){
    cout << "d" << endl;
  }
    if(C=="d"){
    cout << "e" << endl;
  }
    if(C=="e"){
    cout << "f" << endl;
  }
    if(C=="f"){
    cout << "g" << endl;
  }
    if(C=="g"){
    cout << "h" << endl;
  }  if(C=="h"){
    cout<< "i" << endl;
  }  if(C=="i"){
    cout << "j" << endl;
  }  if(C=="j"){
    cout<< "k" << endl;
  }  if(C=="k"){
    cout << "l" << endl;
  }  if(C=="l"){
    cout << "m" << endl;
  }  if(C=="m"){
    cout << "n" << endl;
  }  if(C=="n"){
    cout << "o" << endl;
  }  if(C=="o"){
    cout << "p" << endl;
  }  if(C=="p"){
    cout << "q" << endl;
  }  if(C=="q"){
    cout << "r" << endl;
  }  if(C=="r"){
    cout << "s" << endl;
  }  if(C=="s"){
    cout << "t" << endl;
  }  if(C=="t"){
    cout << "u" << endl;
  }  if(C=="u"){
    cout << "v" << endl;
  }  if(C=="v"){
    cout << "w" << endl;
  }  if(C=="w"){
    cout << "x" << endl;
  }  if(C=="x"){
    cout << "y" << endl;
  }  if(C=="y"){
    cout << "z" << endl;
  }  
}


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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    map<string, int> mp;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        mp[s]++;
    }
    int best = -1;
    vector<string> an;
    for (auto &kv: mp) {
        if (kv.second > best) {
            best = kv.second;
            an.clear();
            an.push_back(kv.first);
        } else if (kv.second == best) {
            an.push_back(kv.first);
        }
    }
    sort(an.begin(), an.end());
    for (auto &s: an) {
        cout << s << '\n';
    }
    return 0;
}


Measured memory_bytes: 25584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int maxn = 100005;
ll pre[maxn];
ll inv[maxn];
ll prei[maxn];
void build(int n){
    pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % mod;
        inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
        prei[i] = prei[i-1] * inv[i] % mod;
    }
}
ll C(int n, int k){
   return pre[n] * prei[k] % mod * prei[n-k] % mod;
}
void go() {
    int n;
    cin >> n;
    ll ans = 0;
    build(n*2 + 5);
    for (int i = 1 ; i*3 <= n;i++) {
        ans += C(n-3*i+i-1,i-1);
        ans %= mod;
    }
    cout << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }
    
}

Measured memory_bytes: 3700
#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 ull uint64_t
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod =  1e9 + 7;
const int MAX = 300005;
using namespace std;
void add(ll& a , ll b){
	a += b;
	if(a >= mod) a -= mod;
}
ll mul(ll a , ll b){
	return (a * b) % mod;
}
ll Pow(ll a , ll b){
	if(b == 0) return 1 ;
	ll c = Pow(a , b / 2) ;
	if(b % 2) return (a * ((c * c)% mod )) % mod ;
	return (c * c) % mod ;
}

//check modulo
int main(){
	IOS;
	cout.precision(50) ;
	int n ; cin >> n ;
	ll maax = 0 ;
	map<ll , int> maap ;
	ll x;for(int i = 0 ; i < (1 << n) ; i++){ cin >> x ; maax = max(x , maax) ; maap[x]++ ;}
	if(maap[maax] > 1) return cout << "No" << endl , 0 ;
	map<ll , int> curr  ;
	curr[maax] = 1 ;
	maap.erase(maax);
	while(maap.size()){
		map<ll , int> tmp =curr ;
		for(auto x:curr){
			ll u = x.x ;
			for(int i = 0 ; i < (int)x.y ; i++){
				auto up = maap.lower_bound(u) ;
				if(up == maap.begin()) return cout << "No" << endl , 0 ;
				up-- ;
				maap[up->x]-- ;
				if(maap[up->x] == 0) maap.erase(up) ;
				tmp[up->x]++ ;
			}
		}
		curr = tmp ;
	}
	cout << "Yes" << endl; 
	
	
	
	return 0;
}


Measured memory_bytes: 33024
#include<stdio.h>
int main(void)
{
	int a[3],temp,i,j;
		for(i=0;i<3;i++){
			scanf("%d",&a[i]);
		}
		for(i=0;i<3;i++){
			for(j=i+1;j<3;j++){
				if(a[i]>a[j]){
					temp=a[i];
					a[i]=a[j];
					a[j]=temp;
				}
			}
		}
	printf("%d %d %d\n",a[0],a[1],a[2]);
	return 0;
}

Measured memory_bytes: 1028
fn main() {
    proconio::input! {
        n: usize,
        a_s: [usize; n],
    }
    let mut sum = 0usize;
    let mut current = a_s[0];
    for a in a_s.into_iter().skip(1) {
        if current > a {
            sum += current - a;
        } else {
            current = a;
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 5540
#include "bits/stdc++.h"

using namespace std;

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

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#ifdef Debug
#define dump(x)  cerr << #x << " = " << (x) << endl
#else
#define dump(x)
#endif

int main(){
	string s;
	while(cin>>s){
		if(s=="#")break;
		vector<string> data;
		rep(i,s.size()){
			if(s[i]=='w'){
				data.pb( s.substr(i,4) );
				i+=3;
			}else if(s[i]=='n'){
				data.pb( s.substr(i,5) );
				i+=4;
			}else return 0;
		}

		int up,down=1;
		if( data[data.size()-1]=="north" )up=0;
		else up=90;

		for(int i=data.size()-2,c=1;i>=0;i--,c++){

			if(data[i]=="north"){
				up=up*((1<<c)/down)-90;
				down=1<<c;
			}
			else{
				up=up*((1<<c)/down)+90;
				down=1<<c;
			}
		}
		while( up%2==0 && down%2==0 ){
			up/=2;down/=2;
		}
		cout<<up;
		if(down!=1){
			cout<<"/"<<down<<endl;
		}
		else cout<<endl;

	}
	return 0;
}

Measured memory_bytes: 1200
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication12
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var abc = Console.ReadLine().Split();
                int a = int.Parse(abc[0]);
                string b = abc[1];
                int c = int.Parse(abc[2]);

                if (b == "?")
                    break;
                if (b == "+")
                {
                    Console.WriteLine(a + c);
                }
                if (b == "-")
                {
                    Console.WriteLine(a - c);
                }
                if (b == "*")
                {
                    Console.WriteLine(a * c);
                }
                if (b == "/")
                {
                    Console.WriteLine("{0:F0}", a / c);
                }






            }
        }
    }
}

Measured memory_bytes: 9184
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,ans=0;
int n,num[15];
inline void dfs(int pos,ll sum){
	if(pos==n+1){ans+=sum;return;}
	ll tmp=0;
	for(int i=pos;i<=n;++i)tmp=tmp*10+num[i],dfs(i+1,sum+tmp);
}
int main(){
	cin>>x;
	while(x)num[++n]=x%10,x/=10;
	reverse(num+1,num+n+1);
	dfs(1,0);
	cout<<ans;
	return 0;
}


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

int main() {
  int a,b,cnt;
  cnt=0;
  cin >> a >> b;
  vector <int> c(a);
  for (int i=0;i<a;i++){
    cin >> c.at(i);
    if(c.at(i)>=b)
      cnt++;
  
  }
  cout << cnt << endl;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
#define re return
#define mp make_pair
#define makeunique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define endl '\n'

typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<string> vs;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }

const double pi = acos(-1.);
const ll inf = 1e18 + 7;
const int N = 3e5 + 17;

int n, m;
int a[N], b[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll x;
	cin >> n >> x;
	for (int i = 0; i < n; i++) cin >> a[i], b[i] = a[i];
	ll ans = 0;
	for (int i = 0; i < n; i++) ans += a[i];
	auto cur = ans;
	for (int j = 1; j < n; j++) {
		for (int i = 0; i < n; i++) {
			int pr = (i + n - 1) % n;
			if (a[i] > b[pr]) {
				cur += b[pr] - a[i];
				a[i] = b[pr];
			}
		}
		for (int i = 0; i < n; i++) b[i] = a[i];
		ans = min(ans, cur + j * x);
	}
	cout << ans;	
}


Measured memory_bytes: 3636
import copy

n, m, = map(int, input().split())
h = list(map(int, input().split()))
p = []
for i in range(m):
    a, b, = map(int, input().split())
    p.append([a-1, b-1])

#print("p = {}".format(p))

height = copy.copy(h)
for i in p:
    index0 = i[0]
    index1 = i[1]
    if h[index0] < h[index1]:
        height[index0] = -1
    elif h[index0] > h[index1]:
        height[index1] = -1
    elif h[index0] == h[index1]:
        height[index0] = -1
        height[index1] = -1

#print("height = {}".format(height))

ret = 0
for i in range(n):
    if height[i] == h[i]:
        ret += 1

print("{}".format(ret))

Measured memory_bytes: 29176
#include <iostream>

int main()
{
    size_t cnt = 0;

    while( true )
    {
        int x;

        std::cin >> x;
        if( x == 0 )
        {
            break;
        }

        ++cnt;
        std::cout << "Case " << cnt << ": " << x << std::endl;
    }

    return 0;
}

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

#define int long long
#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
template <class T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

/*
 */

using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;

signed main() {
  int n;
  cin >> n;

  vi a(n);
  rep(i, 0, n) cin >> a[i];

  sort(all(a));

  bool ok = true;
  rep(i, 1, n) if(a[i-1] == a[i]) ok = false;

  cout << (ok ? "YES" : "NO") << endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std; 
int main(void) {
 int N,X,m[101],ans=0,sum=0,mini=100000;
  cin >> N >> X;
  for(int i=0;i<N;i++){
    cin >> m[i];
    sum +=m[i];
    mini=min(mini,m[i]);
  }
  ans=N+(X-sum)/mini;
  cout << ans;

  }
  

Measured memory_bytes: 256
import heapq

# 優先度付きキューは「最も値が小さいもの」を出すことに注意

prio = []

n, m =list(map(int, input().split()))
nums =list(map(int, input().split()))

for num in nums:
    heapq.heappush(prio, -num)

for i in range(m):
    temp = heapq.heappop(prio)
    heapq.heappush(prio, -((-temp) // 2))

print(-sum(prio))


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

int main()
{
		int n, m, l, i, j, k;
		cin >> n >> m >> l;
		long int A[n][m], B[m][l], C[n][l];
		for (i=0; i<n; i++) for (j=0; j<m; j++) cin >> A[i][j];
		for (i=0; i<m; i++) for (j=0; j<l; j++) cin >> B[i][j];
		for (i=0; i<n; i++) for (j=0; j<l; j++) C[i][j] = 0;

		for (i=0; i<n; i++) {
				for (j=0; j<l; j++) {
						for (k=0; k<m; k++) {
								C[i][j] += A[i][k]*B[k][j];
						}
				}
		}

		for (i=0; i<n; i++) {
				for (j=0; j<l; j++) {
						if (j==l-1) cout << C[i][j] << "\n";
						else cout << C[i][j] << " ";
				}
		}
}

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

using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
    vector<vector<int>> A(h), B(h);
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            int a;
            cin >> a;
            A[i].push_back(a);
        }
    }

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            int b;
            cin >> b;
            B[i].push_back(b);
        }
    }

    vector<vector<array<bool, 100000>>> M(h + 1);
    for (int i = 0; i <= h; i++){
        for (int j = 0; j <= w; j++){
            array<bool, 100000> a = {};
            M[i].push_back(a);
        }
    }
    M[0][0][50000] = true;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            for (int k = 0; k <= 100000; k++){
                if (!M[i][j][k])
                    continue;
                M[i + 1][j][k + A[i][j] - B[i][j]] = true;
                M[i + 1][j][k - A[i][j] + B[i][j]] = true;
                M[i][j + 1][k + A[i][j] - B[i][j]] = true;
                M[i][j + 1][k - A[i][j] + B[i][j]] = true;
            }
        }
    }

    int ans = 1e9;
    for (int k = 0; k <= 100000; k++){
        if (M[h - 1][w][k])
            ans = min(ans, abs(k - 50000));
    }

    cout << ans << endl;
}

Measured memory_bytes: 739044
#include <stdio.h>

int main(void) {
    int a, b, n, i, s;

    while (scanf("%d%d%d", &a, &b, &n) == 3) {
        for (i = 0, s = 0; i < n; i++) {
            a = (a % b) * 10;
            s += a / b;
        }
        printf("%d\n", s);
    }
    return 0;
}

Measured memory_bytes: 596
#!/usr/bin/env python3
#ABC141 E
#Z-algorithm

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0 #L:=LCPの左端,R:=LCPの右端
    for i in range(1, n):
        if i > R: #比較結果を再利用できない
            L = R = i
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
            R -= 1
        elif Z[i-L] < R-i+1:#比較結果を再利用できる
            Z[i] = Z[i - L]
        else:#比較結果を一部再利用できる
            L = i
            R += 1
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
            R -= 1
    return Z

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)

Measured memory_bytes: 50396
from itertools import product
N=int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]
store_str=list(product('01', repeat=10))
store=[[int(i) for i in j] for j in store_str]
store.pop(0)
all_sum=[]
for s in store:
    value_list=[]
    for i,j in zip(F,P): 
        l=len([1 for a,b in zip(s,i) if a==1 and b==1])
        value_list.append(j[l])
    value_sum=sum(value_list)
    all_sum.append(value_sum)
print(max(all_sum))

Measured memory_bytes: 3572
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            String S = in.next();
            for (int i = 1; i < S.length(); i++) {
                if (S.charAt(i - 1) == S.charAt(i)) {
                    System.out.println("Bad");
                    return;
                }
            }
            System.out.println("Good");
        }
    }
}


Measured memory_bytes: 26792
#include <stdio.h>
#include <string.h>

int main(void)
{
	char num[1001] = {'0'};

	int sum = 0;

	int i;

	while (1) {
		scanf("%s", num);

		if(num[0] == '0')
		break;

		for(i = 0; i < strlen(num); i++){
			sum += num[i] - '0';
		}

		printf("%d\n", sum);

		sum = 0;
	}

	return 0;
}

Measured memory_bytes: 536
#include<stdio.h>
void Swap(int*,int*);

int main(){
  int A[100],i,N,s;
  int flag=1,scount=0,j;
  
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
 
  while(flag){
    flag = 0;
    for(j=N-1;j>s;j--){
      if(A[j] < A[j-1]){
	Swap(&A[j],&A[j-1]);

	/*
	for(i=0;i<N;i++){
	  if(i) printf(" ");
	  printf("%d",A[i]);
	}
	printf("\n");
	*/
	scount++;		
      }
      
      flag = 1;
     
    }
    s++;
  }
  for(i=0;i<N;i++){
    if(i) printf(" ");
    printf("%d",A[i]);
  }
  
  printf("\n");
  printf("%d\n",scount);

    return 0;
    }

void Swap(int *x,int *y){
  int work;

  work = *x;
  *x = *y;
  *y = work;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
            #include <chrono>
          
            using namespace std;
            using namespace std::chrono; 
         
            typedef long long int ll;
         
            #define MOD (ll)(1e9+7)
            #define endl "\n"
            #define pb push_back
            #define TEST_CASES  ll t;cin>>t;while(t--)
            #define forn(i,a,n) for (int i = a; i < n; ++i)
            #define f first
            #define s second
            #define all(x) x.begin(), x.end()


            
            ll powD(ll x,ll y){
              ll res = 1;
              while(y > 0){
                if(y & 1)
                  res = (res*x);
                x = (x*x);
                y = y>>1;
              }
              return res;
            }
            int MAX = 1e7;
            vector<int> SPF(MAX+1);
            void seive(int n){
              vector<bool> visited(n+1,0);
              for(ll i = 2;i <= n;i++){
                if(!visited[i]){
                  SPF[i] = i;
                  for (ll j = i*i ; j <= n; j += i)
                  {
                    if(!visited[j]){
                      SPF[j] = i;
                      visited[j] = true;
                    }
                  }
                }
              }
            }

            int main()
            {
              ios_base::sync_with_stdio(false);
              cin.tie(NULL);
              seive(MAX);
              vector<ll> dp(MAX+1);
              dp[0] = 0;
              dp[1] = 1;
              int n;
              cin>>n;
              forn(i,2,MAX+1){
                ll mult = 1;
                int temp = i;
                while(temp > 1){
                  int factor = SPF[temp];
                  ll cnt = 1;
                  while(factor == SPF[temp]){
                    cnt++;
                    temp /= factor;
                  }
                  mult *= cnt;
                }
                dp[i] = dp[i-1] + i*mult;
              }
              cout<<dp[n]<<endl;  
            }

            
          


Measured memory_bytes: 120244
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<iostream>
#define int long long
const int maxn=1e5+5;
typedef long long ll; 
using namespace std;
signed main(){
	int x,y;
	cin>>x>>y;
	int ans=(x*(x-1)/2+y*(y-1)/2);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 888
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int x[10], y[10], k[10];
int main()
{
    int n; scanf("%d", &n);
    for(int i=0; i<n; ++i) {
        scanf("%d%d", x+i, y+i);
        k[i]=i;
    }

    long double sum=0;
    int fn=0;
    do {
        long double d=0;
        for(int i=1; i<n; ++i)
            d+=hypotl(x[k[i]]-x[k[i-1]], y[k[i]]-y[k[i-1]]);
        sum+=d;
        ++fn;
    } while (next_permutation(k, k+n));

    printf("%.9Lf\n", sum/fn);
}


Measured memory_bytes: 384
using System;

namespace ConsoleApp1
{
    class ABC117C
    {
        // https://atcoder.jp/contests/abc177/tasks/abc177_c
        static void Main(string[] args)
        {
            const UInt64 m = 1000000007;

            uint N = uint.Parse(Console.ReadLine());
            var items = Console.ReadLine().Split();

            UInt64[] A = Array.ConvertAll(items, UInt64.Parse);

            UInt64 p = 0;
            UInt64 sum = 0;

            for (var i = N - 1; i > 0; i--)
            {
                p = (p + A[i]) % m;
                sum = (sum + p * A[i - 1]) % m;
            }

            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 46712
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int N;
  cin>>N;
  vector<int>A(N),B(N);
  vector<tuple<int,int,int>>p(N);
  for(int i=0;i<N;i++){
    cin>>A[i]>>B[i];
    p[i]=make_tuple(A[i]+B[i],A[i],B[i]);
  }
  sort(p.rbegin(),p.rend());
  int64_t sumt=0,suma=0;
  for(int i=0;i<N;i++){
    int s,t,a;
    tie(s,t,a)=p[i];
    if(i%2==0){
      sumt+=t;
    }
    else{
      suma+=a;
    }
  }
  cout<<sumt-suma<<endl;
  return 0;
}

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

int main() {
  string s;
  cin >> s;
  int count = 0;
  if (s[0] == 'o') count += 1;
  if (s[1] == 'o') count += 1;
  if (s[2] == 'o') count += 1;
  cout << 700 + 100*count << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>


using namespace std;

int main() {
        //freopen("testcase", "r", stdin);

            char str1[20], str2[20], str3[20];
                scanf("%s %s %s", str1, str2, str3);

                    int l1 = strlen(str1);
                        int l2 = strlen(str2);
                            if (str1[l1 - 1] == str2[0] && str2[l2 - 1] == str3[0]) {
                                        printf("YES\n");
                                            }
                                else printf("NO\n");

                                    return 0;
}

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

#define ris   return *this
#define tmplt template<class T
#define dbgo  debug& operator<<
tmplt > struct rge { T b, e; };
tmplt > rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
~debug(){cerr<<endl;}
tmplt > dbgo(T x){cerr<<boolalpha<<x;ris;}
tmplt, class C > dbgo(pair<T, C> x){ris<<"("<<x.first<<", "<<x.second<<")";}
tmplt > dbgo(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}ris<<"]";}
tmplt > dbgo(vector<T> x){ris<<range(x.begin(),x.end());}
#else
tmplt > dbgo(const T&){ris;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define ford(i, n) for(int i = n-1; i >= 0; i--) 

template<typename T> 
void min_self(T& a, T b) { 
    a = min(a, b); 
}
template<typename T>
void max_self(T& a, T b) { 
    a = max(a, b); 
}

void no() {
    cout << "-1\n";
    exit(0);
}

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

    int n;
    cin >> n;
    ++n;
    vector<ll> a(n);
    forn(i, n) cin >> a[i];
    if(n == 1) {
        cout << (a[0] == 1 ? 1 : -1) << '\n';
        exit(0);
    }
    if(a[0] == 1) {
        no();
    }
    vector<ll> suf(n);
    suf[n-1] = a[n-1];
    for(int i = n-2; i >= 0; i--) {
        suf[i] = suf[i+1] + a[i];
    }
    ll ans = 1;
    ll prev = 1;
    for(int i = 1; i < n; i++) {
        ll can_have = 2*prev;
        ll maybe = suf[i];
        min_self(can_have, maybe);
        debug() nav(i) nav(can_have);
        if(can_have < a[i]) {
            no();
        }
        else {
            ans += can_have;
        }
        prev = can_have - a[i]; // can you have children
    }
    
    cout << ans << endl;
}













// Spend more time thinking, it won't hurt

// Read statement carefully
// Solve on paper first!
// Make your infinity big enough
// Overflows (long long)

// Author: blondie


Measured memory_bytes: 5048
#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;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 1000000000;
    bool ok = true;
    rep(i, N) {
        ll cnt = 0;
        while (A[i] > 0) {
            if (A[i] % 2 == 0) {
                ++cnt;
                A[i] /= 2;
            } else break;
        }
        ans = min(ans, cnt);
    }
    if (ok) cout << ans << endl;
    else cout << 0 << endl;
}

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

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

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

  for(int j=n-1;j>=0;j--){
    cout << a[j];
    if(j>0) cout << " ";
  }
  cout << endl;

 return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll dp[606][606][303];
int main()
{
	int n;
	cin>>n;
	int a[606];
	for(int i=0; i<2*n; i++){
		cin>>a[i];
	}
	int b[606], c[606]={};
	fill(b+1, b+2*n+1, 1);
	int m=0;
	for(int i=0; i<n; i++){
		if(a[2*i]>=0 && a[2*i+1]>=0){
			b[a[2*i]]=b[a[2*i+1]]=0;
		}
	}
	for(int i=1; i<=2*n; i++){
		if(b[i]>0){
			m++;
			b[i]=m;
		}
	}
	if(m==0){
		cout<<1<<endl;
		return 0;
	}
	int cnt=0;
	for(int i=0; i<n; i++){
		if(a[2*i]>=0 && a[2*i+1]>=0) continue;
		if(a[2*i]>=0) c[b[a[2*i]]]=1, cnt++;
		if(a[2*i+1]>=0) c[b[a[2*i+1]]]=1, cnt++;
	}
	dp[m+1][0][0]=1;
	for(int i=m+1; i>=2; i--){
		for(int j=0; j<=m+1-i; j++){
			for(int l=0; l<=min(m/2, m+1-i-j); l++){
				if(c[i-1]){
					(dp[i-1][j][l+1]+=dp[i][j][l])%=MOD;
					if(j) (dp[i-1][j-1][l]+=dp[i][j][l])%=MOD;
				}else{
					dp[i-1][j+1][l]+=dp[i][j][l];
					if(l) (dp[i-1][j][l-1]+=l*dp[i][j][l])%=MOD;
					if(j) (dp[i-1][j-1][l]+=dp[i][j][l])%=MOD;
				}
			}
		}
	}
	ll ans=dp[1][0][0];
	for(int i=1; i<=m/2-cnt; i++) (ans*=i)%=MOD;
	cout<<ans<<endl;
	return 0;
}

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

#define int long long

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

int H, W;
bool s[50][50];

struct node {
    int y, x, t;
};

signed main() {
    cin >> H >> W;
    int white = 0;
    for (int i = 0; i < H; i++) {
        string x;
        cin >> x;
        for (int j = 0; j < W; j++) {
            s[i][j] = x[j] == '.';
            if (s[i][j]) {
                white++;
            }
        }
    }
    queue<node> bfs;
    bfs.push({0, 0, 1});
    s[0][0] = false;
    while (!bfs.empty()) {
        int y = bfs.front().y, x = bfs.front().x, t = bfs.front().t;
        if (y == H - 1 && x == W - 1) {
            cout << white - t << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny >= 0 && ny < H && nx >= 0 && nx < W && s[ny][nx]) {
                bfs.push({ny, nx, t + 1});
                s[ny][nx] = false;
            }
        }
        bfs.pop();
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
p="abcdefghijklmnopqrstuvwxyz"
def f(s,a):
  for i in range(len(s)):
    if s[i] in a: a[s[i]]+=1
    else: a[s[i]]=1

n=int(input())
S=input().rstrip()
A={}
f(S,A)
for i in range(1,n):
  S=input().rstrip()
  B={}
  f(S,B)
  for j in range(26):
    if not p[j] in A: continue
    if p[j] in A and p[j] in B:
      A[p[j]]=min(A[p[j]],B[p[j]])
    elif p[j] in A and not p[j] in B:
      del(A[p[j]])
ans=""
for i in range(26):
  if p[i] in A:
    ans=ans+p[i]*A[p[i]]
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<utility>
#include<tuple>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<algorithm>

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FUNCTION__ << endl;
#define int long long

const long long MAXN = 1e6;
const long long MOD = 1e9+7;
const long long INF = __LONG_LONG_MAX__ / 2;

using namespace std;

int hoge[MAXN];

bool isGuusuu(string s, int l){
  if(l % 2 != 0) return false;
  int hl = l/2;
  for(int i = 0; i < hl; i++){
   if(s[i]!=s[hl+i]) return false;
  }
  return true;
}

signed main(){
    string s;
    cin >> s;
    int n = s.length() - 1;
    while(true){
      if(isGuusuu(s,n)){
        cout << n;
        return 0;
      }
      n--;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int sec,hou,min,sec2;
    scanf("%d",&sec);
    hou = sec / 3600;
    min = (sec % 3600) / 60;
    sec2 = sec % 60;
    printf("%d:%d:%d\n",hou,min,sec2);
    return 0;
}   
    

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,N,r;
  cin >> N >> A;
  
  r = N % 500;
  if (r <= A) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

int main(){
  
  string a, b;
  cin >> a >> b;
  int n = stoi(a+b);
  int nr = sqrt(n);

  string ans = "No";
  if(nr*nr == n) ans = "Yes";
  cout << ans << endl;

}

Measured memory_bytes: 256