akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using ll = long long;
using namespace std;

ll get(ll h) {
   if(h == 1) return 1;
   return 2 * get(h / 2) + 1;
}
void solve() {
   ll h;
   cin >> h;
   cout << get(h) << endl;
}

int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   int testcase = 1;
   // cin >> testcase;

   for(int i = 0; i < testcase; i++) {
      solve();
   } 
   return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<cmath>
#include <iomanip>
#include<stack>


#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
int gcd(int a,int b){return b?gcd(b,a%b):a;}


using namespace std;

struct P
{
    string f;
    ll s;
    ll idx;
};

bool mp0(const P &a, const P &b)
{
    return a.f < b.f;
}

bool mp1(const P &a, const P &b)
{
    return a.s > b.s;
}

bool mp2(const P &a, const P &b)
{
    return a.idx > b.idx;
}


int main()
{
    ll n;
    cin >> n;
    vector<P> vp(n);
    rep(i, n){
        P tmp;
        cin >> tmp.f >> tmp.s;
        tmp.idx = i+1;
        vp[i] = tmp;
    }
    sort(all(vp), mp0);

    rep(i, n){
        for(ll j=i+1; j<n; j++){
            if(vp[i].f == vp[j].f){
                sort(vp.begin()+i, vp.begin()+j+1, mp1);
            }
        }
    }

    rep(i, n){
        cout << vp[i].idx << endl; 
    }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int s;
  cin >> s;
  set<int> aaa;
  aaa.insert(s);
  int b = s;
  int c = 1;
  
  bool jad = true;
  while(jad){
    c++;
    if(b%2 == 0){
      b /= 2;
    }
    else{
      b = 3*b+1;
    }
    
    if(aaa.count(b)){
      jad = false;
      break;
    }
    
    aaa.insert(b);
  }
  
  cout << c << endl;
}

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

const int MOD=1000000007;

int n,a,b;

ll sq(int i){return (ll)i*i;}

long long qexp(long long b,long long p,int m){
    long long res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}

ll combi (int i,int j){
	ll res=1;
	for (int x=1;x<=j;x++) res=(res*inv(x))%MOD;
	for (int x=i-j+1;x<=i;x++) res=(res*x)%MOD;
	
	return res;
}

int main(){

	cin>>n>>a>>b;
	
	ll ans=qexp(2,n,MOD)-1;
	
	ans-=combi(n,a);
	ans-=combi(n,b);
	
	cout<<(ans+2*MOD)%MOD;
}

Measured memory_bytes: 256
#include<cmath>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
using namespace std;
using i64=long long;
using ld=long double;
const ld pi=acos(-1),eps=1e-12;
int read(){int x=0,c=getchar(),f=1;while(isspace(c))c=getchar();if(c=='-')f=-1,c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return f*x;}
int main()
{
    ld a,b,h,m;cin>>a>>b>>h>>m;
    h+=m/60;
    ld c1=h/12+eps,c2=h+eps;
    c1-=floor(c1),c2-=floor(c2);
    ld d=fabs(c1-c2);
    d=min(d,1-d);
    cout<<fixed<<setprecision(12)<<sqrt(a*a+b*b-2*a*b*cos(d*2*pi));
}


Measured memory_bytes: 4172
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

n, m = map(int, input().split())
costs = [int(item) for item in input().split()]
costs_sorted = sorted([(item, i) for i, item in enumerate(costs)], reverse=True)

edge = [[] for _ in range(n)]
edge_dict = dict()
for i in range(m):
    u, v = map(int, input().split())
    u -= 1; v -= 1
    edge[u].append(v)
    edge[v].append(u)
    if u > v:
        u, v = v, u
    edge_dict[(u, v)] = i

visited = [0] * n
color = [-1] * n
costs_on_edge = [INF] * m

while costs_sorted:
    c, v = costs_sorted.pop()
    if visited[v]:
        continue
    visited[v] = True
    ok = False
    for nv in edge[v]:
        if costs[nv] <= c:
            if color[nv] == -1 and color[v] == -1:
                color[nv] = True
                color[v] = False
                visited[nv] = True
            else:
                color[v] = not color[nv]
            if nv < v:
                costs_on_edge[edge_dict[nv, v]] = c
            else:
                costs_on_edge[edge_dict[v, nv]] = c
            ok = True
            break
    # Construction Failed
    if not ok:
        print(-1)
        exit()
color_str = ""
for item in color:
    if item == 1:
        color_str += "W"
    else:
        color_str += "B"
print(color_str)
for item in costs_on_edge:
    print(item)

Measured memory_bytes: 79560
N,A,B=map(int,input().split())
c=10**100
if N<c:
    if N%(A+B)<=A:
        print((N//(A+B))*A+(N%(A+B)))
    elif N%(A+B)>A:
        print((N//(A+B))*A+A)
elif N>=c:
    if c%(A+B)<=A:
        print((c//(A+B))*A+(c%(A+B)))
    elif c%(A+B)<=A:
        print((c//(A+B))*A+A)

Measured memory_bytes: 9124
//بسم الله الرحمن الرحيم
///   ***   ---   |||		 In the name of ALLAH		|||   ---   ***   ///
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el << endl
#define PI 3.141592653589793238
#define _test_ int t; cin >> t; while(t--)
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define file() freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
ll gcd ( ll  a, ll b ) { return __gcd ( a, b ); }
ll lcm ( ll a, ll b ) { return a * ( b / gcd ( a, b ) ); }
int dx[]={0,0,+1,-1,+1,-1,-1,+1};
int dy[]={+1,-1,0,0,+1,-1,+1,-1};
///*......................*//* LET'S BEGIN (-_^) *//*............................///
const int mx= 1e5+123;
string n;
int a,b;


void _case_()
{
    cin >> a >> b;
    if(a<=0 or a>=10) cout << -1 ;
    else if(b<=0 or b>=10) cout << -1 ;
    else cout << a*b ;
}



int main()
{
    optimize();
    //_test_
    _case_();
}

///////////*  N A Y E M  *///////////

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

int main(){
    int n, cep = 0, wrong = 0, limit = 0, runt = 0;
    scanf("%d", &n);
    char ved[4];
    
    for (int i = 0; i < n; ++i){
        scanf("%s", ved);
        
        if (strcmp(ved, "AC") == 0)
            cep += 1;
        else if (strcmp(ved, "WA") == 0)
            wrong += 1;
        else if (strcmp(ved, "TLE") == 0)
            limit += 1;
        else
            runt += 1;
    }
    printf("AC x %d\n", cep);
    printf("WA x %d\n", wrong);
    printf("TLE x %d\n", limit);
    printf("RE x %d\n", runt);


    return 0;
}


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

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

  int n, q; cin >> n >> q;
  VI c(n); rep(i, n) cin >> c[i];
  vector<pair<int, int>> lr(q); rep(i, q) cin >> lr[i].first >> lr[i].second;
  rep(i, q) lr[i].first--;

  const int sq = 700;
  vector<tuple<int, int, int>> lri(q);
  rep(i, q) lri[i] = make_tuple(lr[i].first / sq, lr[i].second, i);
  sort(lri.begin(), lri.end());

  VI ans(q);

  VI cnt(n+1);
  int prev = -1;
  int lx, rx; lx = rx = get<0>(lri[0]);
  int sum = 0;
  VI changed;
  for (auto [ls, r, i] : lri) {



    // ここのコメントを外すとhandmade03-05, random06がWAになる

    if (ls != prev) {
      for (auto cx : changed) cnt[cx] = 0;
      changed.clear();
      lx = rx = r;
      prev = ls;
      sum = 0;
    }



    int l = lr[i].first;
    assert(r == lr[i].second); assert(rx <= r);
    int cx;
    while (rx < r) if (cnt[cx=c[rx++]]++ == 0) sum += 1, changed.push_back(cx);
    while (lx > l) if (cnt[cx=c[--lx]]++ == 0) sum += 1, changed.push_back(cx);
    while (lx < l) if (--cnt[c[lx++]] == 0) sum -= 1;
    ans[i] = sum;
  }
  rep(i, q) cout << ans[i] << "\n";
}


Measured memory_bytes: 22920
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define int long long int
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define endl '\n'
#define boost                    \
	ios::sync_with_stdio(false); \
	cin.tie(0);                  \
	cout.tie(0);
#define mod 1000000007
#define inf 1e18
#define pf push_front
#define pob pop_back
#define pof pop_front
#define deb(x) cout << #x << " " << x << endl;
#define deb2(x, y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define deb3(x, y, z) cout << #x << " " << x << " " << #y << " " << y << " " << #z << " " << z << endl;
#define file                          \
	freopen("input.txt", "r", stdin); \
	freopen("output.txt", "w", stdout);

typedef pair<int, int> pi;
typedef pair<int, pair<int, int>> piii;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;

int32_t main()
{
	// boost
	int t = 1;
	//cin>>t;
	while (t--)
	{
		int n;
		cin >> n;

		int a[n];
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
			//sum += a[i];
		}
		sort(a, a + n, greater<int>());
		int ans = a[0];
		int ctr = 1;
		for (int i = 1; i < n; i++)
		{
			if (ctr >= n - 1)
				break;
			ans += a[i];
			ctr++;
			if (ctr >= n - 1)
				break;
			ans += a[i];
			ctr++;
		}

		cout<<ans<<endl;
	}
}

Measured memory_bytes: 5204
n = gets.to_i
h = gets.split.map(&:to_i)
ans = 0
while h.any?{|i|i != 0}
    i = 0
    while h[i] == 0
        i += 1
    end
    for j in i..n-1
        if h[j] != 0
            h[j] -= 1
        else
            break
        end
    end
    ans += 1
end
puts ans

Measured memory_bytes: 3836
#include<stdio.h>
#include<string.h>
int main()
{
	int n;
	char s[200];
	scanf("%d", &n);
	int i;
	for ( i = 0; i < 2*n-1; i++)
	{
		scanf("%c", &s[i]);
		if (s[i] == 'Y')
		{
			printf("Four");
			return 0;
		}
	}
	printf("Three");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
int main(void){
    int n, k;
    cin >> n >> k;

    vector <int > p;
    
    for(int i=0; i<n; i ++){
        int t;
        cin >> t;
        p.push_back(t);
    }
    sort(p.begin(), p.end());
    int ans = 0;
   for (int i=0; i<k; i++){
        ans += p[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>

using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

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

    vector<int> a(n);
    rep(i, n)cin >> a[i];

    sort(ALL(a));
    cout << a.back() - a.front();
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

Int mod_pow(Int x, Int a, Int m = MOD){
  if(a == 0)return 1;
  Int res = mod_pow(x, a / 2, m);
  res = res * res % m;
  if(a % 2)res *= x;
  return res % m;
}

Int inv(Int x, Int m = MOD){
  return mod_pow(x, m-2, m);
}

Int fact[10800000];
Int revfact[10800000];
Int rev[10800000];

void init(){
  Int m = MOD;
  fact[0] = 1;
  revfact[0] = 1;
  rev[0] = 0;
  rev[1] = 1;
  for(int i = 1;i < 10800000;i++){
    fact[i] = fact[i-1] * i % m;
    if(i>1)rev[i] = MOD / i * (MOD-rev[MOD % i]) % MOD;
    revfact[i] = revfact[i-1] * rev[i] % MOD;
  }
}

Int nCk(Int n, Int k){
  if(n < k)return 0;
  return fact[n] * revfact[n-k] % MOD * revfact[k] % MOD;
}



int main(){
  init();
  Int h, w, k, res = 0;
  cin >> h >> w >> k;
  for(int i = 0;i <= h;i++){
    int j = k - i;
    if(j < 0 || j > w)continue;
    Int tmp = 0;
    tmp += (k+1)*rev[3]%MOD*i%MOD*j%MOD;tmp %= MOD;
    tmp += (k+1)*rev[2]%MOD*(k)%MOD;tmp %= MOD;
    tmp += k;tmp %= MOD;
    tmp *= nCk(h, i) * nCk(w, j) % MOD;tmp %= MOD;
    res = (res + tmp) % MOD;
  }
  for(int i = 1;i <= k;i++)(res *= i) %= MOD;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 253440
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

vector<int> a(100050,100050);

int BinarySearch(int pnt,int n){
    int low = -1;
    int high = n;
    while(high - low > 1){
        int mid = (high + low) / 2;
        if(a[mid] >= pnt) high = mid;
        else low = mid;
    }
    return high;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    int maxv = -100,minv = INF;
    cin >> n;
    rep(i,n){
        cin >> a[i];
        maxv = max(a[i],maxv);
        minv = min(a[i],minv);
    }
    sort(all(a));
    int cnt = 0,pnt = 0;
    int maxv2 = -1 * INF;
    for(int i = minv;i <= maxv;i++){
        pnt = BinarySearch(i-1,n);
        cnt = 0;
        for(int j = pnt;a[j] >= i - 1 && a[j] <= i + 1;++j){
            ++cnt;
        }
        maxv2 = max(cnt,maxv2);
    }
    cout << maxv2 << '\n';
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

int main(){
    int P, Q, R;
    cin >> P >> Q >> R;

    int A = P+Q;
    int B = Q+R;
    int C = R+P;
    int ans = 0;
    if (A<=B)
    {
        ans = A;
    }else
    {
        ans = B;
    }
    
    if (C<=ans)
    {
        ans = C;
    }
    
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    string n; cin >> n;
    string nr = n;
    reverse(all(n));

    if(n == nr) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
vector<int> g[100005];
bool rev[100005], vis[100005], ok[100005];
int deg[100005];
void dfs(int u, int p){
    vis[u] = 1;
    for(int i=0;i<g[u].size();i++){
        int j = g[u][i];
        int v = b[j];
        if(v == u) v = a[j];
        if(vis[v]) continue;
        dfs(v, u);
    }

    int idx = -1;
    for(int i=0;i<g[u].size();i++){
        int j = g[u][i];
        if(ok[j]) continue;
        int v = b[j], r = 0;
        if(v == u) v = a[j], r = 1;
        if(v == p){
            idx = j;
            continue;
        }
        ok[j] = 1;
        deg[u]++;
        rev[j] = r;
    }
    if(idx != -1){
        int j = idx;
        int v = b[j], r = 0;
        if(v == u) v = a[j], r = 1;

        ok[j] = 1;
        if(deg[u]%2 == 1){
            deg[u]++;
            rev[j] = r;
        }
        else{
            r = 1-r;
            deg[p]++;
            rev[j] = r;
        }
    }
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        scanf("%d%d", &a[i], &b[i]);
        g[a[i]].push_back(i);
        g[b[i]].push_back(i);
    }
    if(m%2 == 1){
        printf("-1\n");
        return 0;
    }
    dfs(1, 0);

    for(int i=1;i<=m;i++){
        if(rev[i]) printf("%d %d\n", b[i], a[i]);
        else printf("%d %d\n", a[i], b[i]);
    }
}

Measured memory_bytes: 16128
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


int main(){
  int a, b, q;
  cin>>a>>b>>q;

  LL s[a], t[b], answer[q];
  LL query, sl, sr, tl, tr, ans;
  int s_itr, t_itr;
  REP(i, a) cin>>s[i];
  REP(i, b) cin>>t[i];
  LL out = 1000000000000;

  REP(i, q){
    cin>>query;
    s_itr = lower_bound(s, s+a, query) - s;
    t_itr = lower_bound(t, t+b, query) - t;
    if(s_itr==0) sl=out;
    else sl = abs(s[s_itr-1]-query);
    if(t_itr==0) tl=out;
    else tl = abs(t[t_itr-1]-query);
    if(s_itr==a) sr=out;
    else sr = abs(s[s_itr]-query);
    if(t_itr==b) tr=out;
    else tr = abs(t[t_itr]-query);

    answer[i] = min(max(sl, tl), max(sr, tr));
    answer[i] = min({answer[i], 2*sl+tr, sl+2*tr, 2*sr+tl, sr+2*tl});
  }

  REP(i, q) cout<<answer[i]<<endl;

  return 0;
}


Measured memory_bytes: 3712
N,Q = map(int,input().split())
s =input()
td = []
lend = 0
rend = N-1

for i in range(Q):
    t,d = map(str,input().split())
    td.append([t,d])
td = td[::-1]
for i,j in td:
    if j == "L" and i == s[lend]:#左端を1つずらす
        lend += 1
    if j == "R" and i == s[rend]:#右端を1つずらす
        rend -= 1  
    if rend < (N-1) and j == "L" and i == s[rend+1]:#1つ前の位置を参照して右に戻す
        rend += 1
    if lend > 0 and j == "R" and i == s[lend-1]:#1つ前の位置を参照して左に戻す
        lend -= 1
    if lend > rend:
        break

print(rend - lend + 1)

Measured memory_bytes: 25268
#include <stdio.h>
#define INF 2000000000;

int min(int, int);
int matrixChainOrder(int);

int A[100];
int M[100][100];

int main()
{
  int i;
  int n;

  scanf("%d", &n);
  for(i = 0; i < n; i++)
    {
      scanf("%d %d", &A[i], &A[i + 1]);
    }

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

  return 0;
}

int min(int u, int v)
{
  if(u < v) return u;
  return v;
}

int matrixChainOrder(int n)
{
  int i, l, j, k;
  int tmp;

  for(i = 1; i <= n; i++)
    {
      M[i][i] = 0;
    }

  for(l = 2; l <= n; l++)
    {
      for(i = 1; i <= n - l + 1; i++)
	{
	  j = i + l - 1;

	  M[i][j] = INF;

	  for(k = i; k < j; k++)
	    {
	      tmp = M[i][k] + M[k + 1][j] + A[i - 1] * A[k] * A[j];
	      M[i][j] = min(M[i][j], tmp);
	    }
	}
    }

  return M[1][n];
}

Measured memory_bytes: 636
N,K = map(int,input().split())
V = list(map(int,input().split()))

take_count = min(N,K)
# とる個数
ans = -1 * 10**8
for i in range(1,take_count+1):
    drop_num = K-i # 捨てれる個数
    # 左からとる個数
    for li in range(i+1):
        take_left = V[:li]
        #　右からとる個数
        for ri in range(i+1-li):
            take = take_left
            take_right = []
            if ri>0:
                take_right =  V[-ri:]
            take = take_left + take_right
            take = sorted(take)
            # 捨てる
            for di in range(min(drop_num, len(take))):
                if take[di] < 0:
                    take[di] = 0
            ans = max(ans, sum(take))
            # print(i,li,ri,drop_num,ans,take_left,take_right,take,sum(take))
print(ans)

Measured memory_bytes: 43996
d = {
    'S': [i for i in range(13)],
    'H': [i for i in range(13)],
    'C': [i for i in range(13)],
    'D': [i for i in range(13)],
}
n = int(input())
for i in range(n):
    a, b = input().split()
    b = int(b)
    d[a][b - 1] = -1
for i in d.keys():
    for j in d[i]:
        if j != -1:
            print(i, str(j + 1))



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  lint n, m; cin >> n >> m;
  VV<> g(n);
  for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v, u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  V<> vis(n);
  lint a = 0, b = 0, c = 0;
  for (int i = 0; i < n; i++) if (!vis[i]) {
    if (g[i].empty()) {
      vis[i] = 1;
      a++;
    } else {
      bool bi = true;
      queue<int> q;
      vis[i] = 1; q.push(i);
      while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto&& i : g[v]) {
          if (vis[i]) {
            if (vis[i] == vis[v]) bi = false;
            continue;
          }
          vis[i] = -vis[v]; q.push(i);
        }
      }
      (bi ? b : c)++;
    }
  }
  lint res = (b + c) * (b + c) + b * b + 2 * n * a - a * a;
  cout << res << '\n';
}

Measured memory_bytes: 7296
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = 0
for i in range(len(ab)):
    max_a = max(max_a, ab[i][0])

# usual
dp2 = [[0] * (t + 1 + max_a) for _ in range(n + 1)]
for i in range(n):
    for j in range(t + 1 + max_a):
        a = ab[i][0]
        b = ab[i][1]
        if j < a:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i][j - a] + b)

# use as the last
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(t + 1):
        a = ab[i][0]
        b = ab[i][1]
        if j < a:
            if j >= 1:
                dp[i+1][j] = max(dp[i][j], dp2[i][j-1] + b)
            else:
                dp[i+1][j] = dp[i][j]
        else:
            if j >= 1:
                dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b, dp2[i][j-1] + b)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b)

print(dp[-1][-1])


Measured memory_bytes: 249604
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)

	s := getString()
	if s == "ABC" {
		out("ARC")
	} else {
		out("ABC")
	}
}


Measured memory_bytes: 1756
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<P,int>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    int ans=0;
    REP(i,3){
        int a;
        scanf("%1d",&a);
        ans+=a;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define endl        "\n"
#define si(a)       scanf("%d",&a)
#define si2(a,b)    scanf("%d%d",&a,&b)
#define sl(a)       scanf("%lld",&a)
#define sl2(a,b)    scanf("%lld%lld",&a,&b)
#define pb          push_back
#define mk          make_pair
#define loop(n)     for(int i=0; i<n; i++)
#define FOR(a,b)    for(int i=a; i<=b; i++)
#define sz          size()
#define ff          first
#define ss          second
#define mem(a,val)  memset(a, val, sizeof(a))
#define md          1000000007
#define pi          acos(-1.0)

ll a[200010];
int main()
{
    ll t,n,i,j,k,l,mn=0, mx=0;

    sl(n);
    for(int i=0; i<n; i++)
    {
        sl(a[i]);
    }
    sort(a, a+n, greater<int>());

    ll ans=0;
    if(n>1)
    {
        ans+=a[0];
        n-=2;
        int p=n/2;
        i=1;
        while(p--)
        {
            ans+=a[i]*2;
            i++;
        }
        if(n%2)
            ans+=a[i];
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 5384
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <set>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int> ;
using vl = vector<ll>;

int main(){
    int n;
    cin >> n;
    int tmp;
    map<int,int> mp;
    rep(i,n){
        cin >> tmp;
        mp[tmp]++;
    }

    vi v(3,0),v2(3,0);
    int i = 0;
    int size = mp.size();
    if(size == 3){
        for(auto e : mp){
            v[i] = e.first;
            v2[i] = e.second;
            i++;
        }
    }

    if(mp[0] == n){
        cout << "Yes" << endl;
        return 0;
    }else if(mp[0] * 3 == n && size == 2){
        cout << "Yes" << endl;
        return 0;
    }else if(size == 3){
        if((v2[0] == v2[1] && v2[1] == v2[2]) && ((v[0] ^ v[1]) ^ v[2]) == 0)  {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 7020
#include<bits/stdc++.h>
#define rep(i,n) for(ll i = 0; i < n; i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF 1e9
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(b<a) { a=b; return 1; } return 0; }

int main(){
  int n; cin >> n;
  vector<ll> cnt(5);
  rep(i,n){
    string s; cin >> s;
    if(s[0]=='M') cnt[0]++;
    if(s[0]=='A') cnt[1]++;
    if(s[0]=='R') cnt[2]++;
    if(s[0]=='C') cnt[3]++;
    if(s[0]=='H') cnt[4]++;
  }

  ll ans = 0;
  for(int i = 0; i < 3; i++){
    for(int j = i+1; j < 4; j++){
      for(int k = j+1; k < 5; k++){
        ans += cnt[i]*cnt[j]*cnt[k];
      }
    }
  }
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3588
// AOJ  0503: Cup
// 2017.10.29 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

int c[16];

int main()
{
	int n, m, i, j, k, ans;
	int p3[16];

	for (p3[0] = 1, i = 1; i < 16; i++) p3[i] = 3*p3[i-1];
	while (scanf("%d%d", &n, &m) && n > 0) {
		for (i = 0; i < 3; i++) {
			scanf("%d", &j);
			while (j-- > 0) scanf("%d", &k), c[k-1] = i;
		}
		ans = k = 0;
		for (i = 0; i < n; i++) {
			j = c[i] - k;
			if (j < 0) j = -j;
			ans += j * p3[n-i-1];
			if (j == 1) k = 2 - k;
		}
		k = p3[n] - ans - 1;
		if (ans > k) ans = k;
		if (ans > m) ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1796
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

using namespace std;

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF (int)(1e9+10)
#define LLINF (lint)(1e18+10)

int main(){
    string s;
    cin >> s;
    int cnt = 0, ans = 0;
    rep(i, s.size()){
        if(s[i] == 'g'){
            if(cnt > 0){
                cnt--;
                ans++;
            }else{
                cnt++;
            }
        }else{
            if(cnt > 0){
                cnt--;
            }else{
                cnt++;
                ans--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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


int main(){
    vector< vector<int> > a;
    while(true){
        int i,j;
        cin >> i >> j;
        if(i ==0 && j ==0) break;
        vector<int> b;
        b.push_back(i);b.push_back(j);
        a.push_back(b);
    }
    for(int i = 0; i <= a.size() -1; i++){
        cout << min(a[i][0],a[i][1]) << " " << max(a[i][0],a[i][1]) << endl;
    }
    return 0;
}


Measured memory_bytes: 3276
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();
		if(a.charAt(a.length()-1)==b.charAt(0)&&b.charAt(b.length()-1)==c.charAt(0)){
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

}

Measured memory_bytes: 23764
n,m = map(int, input().split())
a = [-1] + [int(input()) for _ in range(m)] + [n + 1]
MOD = 10 ** 9 + 7

fib = [0, 1]
for i in range(100100):
	fib.append((fib[i] + fib[i + 1] % MOD))

res = 1
for i in range(m + 1):
	p, q = a[i], a[i + 1]
	res = (res * fib[q - p - 1]) % MOD

print(res)

Measured memory_bytes: 11656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1e6+5;
int main() {
	int n;cin>>n;
	vector<int> pre(n+1);
	for(int i=1;i<=n;i++) cin>>pre[i];
    int ans=1e9;
    for(int i=-1000;i<=1000;i++) {
    	int sum=0;
    	for (int j=1;j<=n;j++) {
    		sum+=(i-pre[j])*(i-pre[j]);
    	}
    	ans=min(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

int gcd(int a, int b);
int r;

int main(void)
{
	int x, y;
	int ans;
	
	scanf("%d %d", &x, &y);
	
	printf("%d\n", gcd(x, y));
	
	return (0);
}

int gcd(int a, int b)
{
	if (a % b != 0 && b % a != 0) {
		if (a > b) {
			if (a % b != 0) {
				a = a % b;
				gcd(a, b);
			}
		}
		else {
			if (b % a != 0) {
				b = b % a;
				gcd(a, b);
			}
		}
	}
	else {
		if (a < b) {
			return (a);
		}
		else  {
			return (b);
		}
	}
}

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

int main()
{
	int gakuseki;
	double sin, tai;

	while (scanf("%d, %lf, %lf", &gakuseki, &tai, &sin) != EOF){
		if (tai / (sin * sin) >= 25) cout << gakuseki << endl;
	}
	
	return (0);
}

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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
#define mins(x, y) (x = min(x, y))
#define maxs(x, y) (x = max(x, y))
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using P = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

// usage:
// vector<T> v; v.push_back(T(1, 2, 3)); v.emplace_back(1, 2, 3);
// queue<T> q; q.push(T(1, 2, 3));
// int x, y, z; tie(x, y, z) = q.front(); q.pop();
typedef tuple<int, int, int> T;

void solve() {
  int n, m;
  cin >> n >> m;
  vvi to(n);
  rep(i, m) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    to[u].push_back(v);
    to[v].push_back(u);
  }
  deque<T> q;
  vi dist(n, INF);
  vi used(n, 0);
  vi from(n, 0);
  q.push_back(T(0, -1, 0));
  while (!q.empty()) {
    int u, p, c;
    tie(u, p, c) = q.front();
    q.pop_front();
    if (used[u] && dist[u] <= c) continue;
    used[u] = 1;
    dist[u] = c;
    from[u] = p;
    for (auto& v : to[u]) {
      q.push_back(T(v, u, c + 1));
    }
  }
  cout << "Yes" << endl;
  rep(i, n) {
    if (i == 0) continue;
    cout << from[i] + 1 << endl;
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 13964
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <functional>

using namespace std;

int main(void)
{
	int N;
	vector<long long> A;

	cin >> N;
	int minus_num = 0;
	for (int i = 0; i < N; i++) {
		long long tmp;
		cin >> tmp;

		if (tmp >= 0) {
			A.push_back(tmp);
		}
		else {
			A.push_back(-tmp);
			minus_num++;
		}
	}
		
	// 降順ソート
	sort(A.begin(), A.end(), std::greater<int>());

	long long sum = 0;
	for (int i = 0; i < A.size(); i++) {
		sum += A[i];
	}
	
	if (minus_num % 2 == 1) {
		sum -= A[A.size() - 1] * 2;
	}
	
	cout << sum << endl;

	return 0;
}

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

Z = []
for i in range(N):
  a, b = map(int, input().split())
  Z.append((a, b))

Z.sort(key=lambda x:x[0])

count = 0
cost = 0
shop = 0
while count < M:
  buy = min(Z[shop][1], M - count)
  count += buy
  cost +=  buy * Z[shop][0]
  if count < M:
    shop += 1
  
print(cost)

Measured memory_bytes: 23684
#include <iostream>
#include <string.h>
using namespace std;

int main(){
    string s;
    getline(cin, s);

    for(int i = 0; i < s.size(); i++ ){
        char c = s[i];
        if( c >= 'A' && c <= 'Z' ) c = c + 32;
        else if( c >= 'a' && c <= 'z' ) c = c - 32;

        cout << c;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3208
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

int main() {
    int N;
    vector<int> a;
    cin >> N ;
    a.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    int sum = 0;
    for (int j = 0; j < N; ++j) {
        while (a[j] % 2 == 0) {
            a[j] /= 2;
            sum++;
        }
    }
    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
template<class T> inline istream& operator >> (istream & c, vector<T> & A) {rep(i, A.size()) c >> A[i];return c;}
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cntR = 0, cntW = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'R') cntR++;
	}
	int ans = cntR;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'W') cntW++;
		else cntR--;
		int tmp = max(cntR, cntW);
		mins(ans, tmp);
	}
	mins(ans, cntW);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3752
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;  
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b){
    if (a < b){ a = b;return 1;}
    return 0;
}
template <class T, class U> //chmin(min,a)
bool chmin(T &a, U b){
    if (a > b){ a = b; return 1;}
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
   
// g++ -std=c++11 prac.cpp
template<typename T>
T gcd(T a, T b){
	return b != 0 ? gcd(b, a % b) : a;
}    
template<typename T>
T lcm(T a, T b){
    return a/gcd(a,b)*b;
}    
        
int main(){
    ll x,y,z,n,m=0,k,h,w,sum=0,ans=0,Max=-1e9,count=0,Min=1e9+1;
    string s,t,u1,u2;
    bool ok=true;
    cin >> h >> w;
    VCC o(h+2, vector<char> (w+2));
    rep(i,h+2){
        rep(j,w+2){
            o[i][j]='.';
        }
    }
    for(int i=1; i<h+1;i++){
        for(int j=1; j<w+1; j++){
            cin >> o[i][j];
        }
    }
    x=0; y=0;
    for(int i=1; i<h+1;i++){
        for(int j=1; j<w+1; j++){
            if(o[i][j]=='#'){
                if(i>=y && j>=x){
                    x = j; y = i;
                    continue;
                }
                else{
                    cout << "Impossible" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Possible" << endl;
    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    vector<int> a(27);
    for (auto i : s) {
        a[i - 96]++;
    }
    for (auto i : a) {
        if (i % 2 != 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3580
import collections 
n = int(input())
v = list(map(int,input().split()))
if len(set(v)) == 1:
    print(n//2)
    exit()
cnt = 0
e = []
o = []
for i in range(n):
    if (i+1) % 2 == 0:
        e.append(v[i])
    else:
        o.append(v[i])
E = collections.Counter(e)
O = collections.Counter(o)
list_e = []
list_o = []
set_e = set(e)
set_o = set(o)
E_1 = E.most_common()[0][0]
if len(set_e) != 1:
    E_2 = E.most_common()[1][0]
    E_2_kosu = E.most_common()[1][1]
else:
    E_2 = E.most_common()[0][0]
    E_2_kosu = E.most_common()[0][1]

O_1 = O.most_common()[0][0]
if len(set_o) != 1:
    O_2 = O.most_common()[1][0]
    O_2_kosu = O.most_common()[1][1]
else:
    O_2 = O.most_common()[0][0]
    O_2_kosu = O.most_common()[0][1]

if E_1 != O_1:
    ans = n - E.most_common()[0][1] - O.most_common()[0][1]
else:
    ans = min(n-E_2_kosu-O.most_common()[0][1],n-E.most_common()[0][1]-O_2_kosu)
print(ans)

Measured memory_bytes: 24416
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;
 
int main() {
  ll s;
  cin >> s;
  ll s2 = sqrt(s);
  ll x1=1, y1, x2=e9, y2;
  y2 = s/e9;
  if(y2!=e9)y2++;
  y1 = x2*y2-s;
  
  cout << 0 << " " << 0 << " " <<  x1 << " " << y2 << " " << x2 << " " << y1 << endl;
}

Measured memory_bytes: 256
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

struct TrieNode {
    TrieNode *children[2];
    bool isEndOfWord;
}; 

TrieNode *getNode() {
    TrieNode *pNode =  new TrieNode;
    pNode->isEndOfWord = false;
    FOR(i,0,1) pNode->children[i] = nullptr; 
    return pNode; 
}

void insert(TrieNode *root, string &key) {
    TrieNode *pCrawl = root; 
    FOR(i,0,SZ(key)-1) { 
        int index = key[i] - '0'; 
        if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); 
        pCrawl = pCrawl->children[index]; 
    }
    pCrawl->isEndOfWord = true;
}

string s;
int n;
ll L;

ll getGrundyNumber(TrieNode *root, int depth) {
    if (root->isEndOfWord) return 0;
    ll res = 0;
    FOR(i,0,1) {
        if (!root->children[i]) {
            ll h = L - depth;
            ll grundy = (-h) & (h);
            res ^= grundy;
        }
        else {
            res ^= getGrundyNumber(root->children[i], depth+1);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> L;
    TrieNode *root = getNode();
    FOR(i,1,n) {
        cin >> s;
        insert(root, s);
    }

    ll res = getGrundyNumber(root, 0);
    if (res) cout << "Alice";
    else cout << "Bob";
    return 0;
}


Measured memory_bytes: 8144
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)
 
int main() {

long N;
cin>>N;
vector<long> r(20);
vector<long> A(20);
int R;

r.at(0)=26;

for(int i=1;i<20;i++){
    r.at(i)=(r.at(i-1)+1)*26;
}

for(int i=0;i<20;i++){
    if(r.at(i)>=N){
    R=i;
    break;
    }
}

if(R>0){
    N=N-r.at(R-1);
}
N=N-1;
  
for(int i=0;i<R+1;i++){
    A.at(i)=N%26;
    N=(N-A.at(i))/26;
}
for(int i=R;i>=0;i--){
    A.at(i)=A.at(i)+97;
    printf("%c",A.at(i));
}
cout<<endl;


}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)



int main(){
    int x;
    cin>>x;
    int ans=0;
    ans+=(x/500)*1000;
    x%=500;
    ans+=(x/5)*5;
    cout<<ans<<endl;
}

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

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
  int n, k;
  cin >> n >> k;
  k = min(k, n - 1); //全部ゼロで埋まることは無い
  combination c(n);
  mint ans;
  // i :: ゼロの個数
  for (int i = 0; i <= k; i++) {
    ans += c(n, i) * c((n - i - 1) + i, i);
  }
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
const int MOD=1e9+7;


int main() {
    int n;
    cin >> n;
    int k=0,ans=100000;
    vector<int> nine_ele;
    nine_ele.push_back(1);
    rep(i,5) nine_ele.push_back(nine_ele[i]*9);
    while (1) {
        int m=n,l=k,six_ele=6,tans=0;
        while (l>0) {
            m-=l%6*six_ele;
            tans+=l%6;
            l/=6;
            six_ele*=6;
        }
        if (m<0) break;
        else {
            while (m>0) {
                invrep(i,6) {
                    int r=m/nine_ele[i];
                    tans+=r;
                    m-=r*nine_ele[i];
                }
            }
        }
        ++k;
        ans=min(ans,tans);
    }
    cout << ans << endl;
}

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

int n;
int fie[11][11];
int dx[13]={0,1,0,-1,0,-1,1,-1,1,2,0,-2,0};
int dy[13]={0,0,1,0,-1,-1,-1,1,1,0,-2,0,2};
int res[15],resx[15],resy[15];
int now[15],nowx[15],nowy[15];
int cnt;

void dfs(int x,int y,int v){
	if(y==9 || v==n){
		if(cnt==0){
			for(int i=0;i<n;i++){
				res[i]=now[i];
				resx[i]=nowx[i];
				resy[i]=nowy[i];
			}
		}
		return;
	}
	if(fie[x][y]>=1){
		if(y>=2 && fie[x][y-2]>=1){
			for(int i=0;i<13;i++){
				int nx=x+dx[i],ny=y+dy[i];
				if(nx>=0 && nx<10 && ny>=0 && ny<10){
					if(fie[nx][ny]==0)return;
				}else return;
			}
			for(int i=0;i<13;i++){
				cnt--;
				fie[x+dx[i]][y+dy[i]]--;
			}
			now[v]=3;
			nowx[v]=x;
			nowy[v]=y;
			dfs(x,y,v+1);
			for(int i=0;i<13;i++){
				cnt++;
				fie[x+dx[i]][y+dy[i]]++;	
			}
		}else{
			int i;
			for(i=0;i<9;i++){
				int nx=x+dx[i],ny=y+dy[i];
				if(nx>=0 && nx<10 && ny>=0 && ny<10){
					if(fie[nx][ny]==0)break;
				}else break;
			}
			if(i==9){
				for(int j=0;j<9;j++){
					cnt--;
					fie[x+dx[j]][y+dy[j]]--;
				}
				now[v]=2;
				nowx[v]=x;
				nowy[v]=y;
				dfs(x,y,v+1);
				for(int j=0;j<9;j++){
					cnt++;
					fie[x+dx[j]][y+dy[j]]++;	
				}
			}
			for(i=0;i<5;i++){
				int nx=x+dx[i],ny=y+dy[i];
				if(nx>=0 && nx<10 && ny>=0 && ny<10){
					if(fie[nx][ny]==0)break;
				}else break;
			}
			if(i==5){
				for(int j=0;j<5;j++){
					cnt--;
					fie[x+dx[j]][y+dy[j]]--;
				}
				now[v]=1;
				nowx[v]=x;
				nowy[v]=y;
				dfs(x,y,v+1);
				for(int j=0;j<5;j++){
					cnt++;
					fie[x+dx[j]][y+dy[j]]++;	
				}
			}
		}
	}
	if(x==8)dfs(0,y+1,v);
	else dfs(x+1,y,v);
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			scanf("%d",&fie[j][i]);
			cnt+=fie[j][i];
		}
	}
	dfs(1,1,0);
	for(int i=0;i<n;i++){
		printf("%d %d %d\n",resx[i],resy[i],res[i]);
	}
	return 0;
}

Measured memory_bytes: 1032
# ITP1_11_B: Dice3

class Dice
  Side = Struct.new :sides, :back

  TOP    = 0
  FRONT  = 1
  RIGHT  = 2
  LEFT   = 3
  BACK   = 4
  BOTTOM = 5

  def initialize(labels)
    @labels = labels
    @sides  = layout_map
  end

  def pip_of(side)
    @labels[side]
  end

  def sides_of(side)
    @sides[side].sides
  end

  def back_of(side)
    @sides[side].back
  end
 
  def rotate(p1, p2, p3, p4)
    l = @labels
    l[p1], l[p2], l[p3], l[p4] = l[p4], l[p1], l[p2], l[p3]
  end
 
  def roll_to(direction)
    rotate *case direction
    when 'N'
      [TOP, FRONT, BOTTOM, BACK]
    when 'E'
      [TOP, LEFT, BOTTOM, RIGHT]
    when 'S'
      [TOP, BACK, BOTTOM, FRONT]
    when 'W'
      [TOP, RIGHT, BOTTOM, LEFT]
    end
  end

  def each_side
    @labels.each_with_index
  end

  def same_as?(other)
    mytop   = self.pip_of TOP
    mysides = self.sides_of TOP
    myback  = self.back_of TOP

    other.each_side.any? do |label, id|
      next unless mytop == label && myback == other.back_of(id)
      other_sides = other.sides_of(id)
      mysides.size.times.any? do
        mysides == other_sides.rotate!(1)
      end
    end
  end

  private

    def layout_map()
      Hash.new.tap do |sides|
        sides[TOP]    = make_sides [FRONT, RIGHT, BACK, LEFT], BOTTOM
        sides[FRONT]  = make_sides [BOTTOM, RIGHT, TOP, LEFT], BACK
        sides[RIGHT]  = make_sides [BOTTOM, BACK, TOP, FRONT], LEFT
        sides[LEFT]   = make_sides [BOTTOM, FRONT, TOP, BACK], RIGHT
        sides[BACK]   = make_sides [TOP, RIGHT, BOTTOM, LEFT], FRONT
        sides[BOTTOM] = make_sides [BACK, RIGHT, FRONT, LEFT], TOP
      end
    end

    def make_sides(sides, back)
      Side.new sides.map{ |id| @labels[id] }, @labels[back]
    end
end

labels1 = gets.chomp.split.map &:to_i
labels2 = gets.chomp.split.map &:to_i

dice1 = Dice.new labels1
dice2 = Dice.new labels2
puts dice1.same_as?(dice2) ? 'Yes' : 'No'

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

signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int h, w, n; cin >> h >> w >> n;
  vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> res;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < a[i]; j++) {
      res.push_back(i + 1);
    }
  }
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << (i % 2 ? res[i * w + j] : res[i * w + w - 1 - j]) << ' ';
    }
    cout << '\n';
  }
  return 0;
}

Measured memory_bytes: 512