akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

ll INF = (1ll << 32);
double EPS = 1e-4;

ll MOD = 1000000007;

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

  K -= 1;

  vi v;
  for (ll i = 0; i < (1ll << (W - 1)); i++) {
    bool ok = true;
    for (ll j = 0; j < W - 2; j++) {
      if ((i & (1ll << j)) && (i & (1ll << (j + 1)))) {
        ok = false;
      }
    }
    if (ok) {
      v.push_back(i);
    }
  }

  vvi dp(H + 1, vi(W));
  dp[0][0] = 1;
  for (ll i = 1; i <= H; i++) {
    for (ll j: v) {
      for (ll k = 0; k < W - 1; k++) {
        if (j & (1ll << k)) {
          dp[i][k] += dp[i - 1][k + 1];
          dp[i][k + 1] += dp[i - 1][k];
        }
      }
      for (ll k = 0; k < W; k++) {
        if (k == 0) {
          if (!(j & (1ll << k))) {
            dp[i][k] += dp[i - 1][k];
          }
        } else if (k == W - 1) {
          if (!(j & (1ll << (k - 1)))) {
            dp[i][k] += dp[i - 1][k];
          }
        } else {
          if (!(j & (1ll << k)) && !(j & (1ll << (k - 1)))) {
            dp[i][k] += dp[i - 1][k];
          }
        }
      }
      for (ll k = 0; k < W; k++) {
        dp[i][k] %= MOD;
      }
    }
  }

  cout << dp[H][K] << endl;
}


Measured memory_bytes: 256
H,W,A,B= map(int, input().split())
mod = 10**9+7
N=W-B

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range( 2, H+W-2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

ANS=0

for i in range(N):
    ANS=(ANS+com(H-A-1+B,B+i, mod)*com(W+A-1-B,A+i, mod))%mod
print(ANS)


Measured memory_bytes: 27024
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n,k;
int res[200005],vis[200005];
vector<int>e[200005],dis[200005];
void add(int f, int t) { e[f].push_back(t), e[t].push_back(f); }
bool check(int x, int y) { return x - y == 1 || y - x == 1; }
int main() {
	scanf("%d",&n);
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}scanf("%d",&k);
	int mn=100000000;
	for(int i=1,u;i<=k;++i){
		scanf("%d",&u);
		scanf("%d",res+u);
		mn=min(res[u],mn),vis[u]=1;
	}for(int i=1;i<=n;++i)
		if(vis[i])dis[res[i]-mn].push_back(i);
	for(int i=0;i<n;++i)
		for(int j=dis[i].size()-1,u;j>=0;--j)
			for(int t=e[u=dis[i][j]].size()-1,v;t>=0;--t)
				if(!vis[v=e[u][t]])
					res[v]=res[u]+1,dis[i+1].push_back(v),vis[v]=1;
	for(int u=1;u<=n;++u)
		for(int i=e[u].size()-1,v;i>=0;--i)
			if(!check(res[u],res[e[u][i]]))return puts("No"),0;
	puts("Yes");
	for(int u=1;u<=n;++u)printf("%d\n",res[u]);
	return 0;
}

Measured memory_bytes: 19800
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
   
    char x;
    cin >> x ;
    if((int)x >90)
    cout << "a" << endl;
    else cout << "A" << endl;
    //cout << (int)x << endl;

 return 0;
}

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

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

  vector<int> A(N);
  rep(i, N) cin >> A[i];

  sort(A.begin(), A.end());

  int ans = 0;
  int last = A[0];
  int count = 0;
  rep(i, N) {
    if (A[i] != last) {
      if (count % 2 != 0)
        ans++;
      last = A[i];
      count = 1;
    } else {
      count++;
    }
  }
  if (count % 2 != 0)
    ans++;

  cout << ans << endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;

namespace cswork
{
    class Program
    {
        class Scanner
        {
            string[] s;
            int i;

            char[] cs = new char[] { ' ' };

            public Scanner()
            {
                s = new string[0];
                i = 0;
            }

            public string next()
            {
                if (i < s.Length) return s[i++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();

                s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
                i = 0;
                return next();
            }

            public int nextInt()
            {
                return int.Parse(next());
            }

            public long nextLong()
            {
                return long.Parse(next());
            }

            public double nextDouble()
            {
                return double.Parse(next());
            }
        }

        public Program() { }

        static void Main(string[] args)
        {
            new Program().Omame();
        }

        Scanner cin;
        const int MAXIN = 1024;
        bool[] used = new bool[MAXIN];
        int[] perm = new int[MAXIN];

        List<int[]> permList = new List<int[]>();

        public void Permutation(int pos, int n, int length)
        {
            if (pos == n)
            {
                permList.Add((int[])perm.Clone());
            }

            for (int i = 0; i < n; i++)
            {
                if (!used[i])
                {
                    perm[pos] = i;
                    used[i] = true;
                    Permutation(pos + 1, n, length);
                    used[i] = false;
                }
            }
        }

        void Omame()
        {
            cin = new Scanner();
            int N = cin.nextInt();

            long ans = 0;
            for (int i = 1; i < N+1; i++)
            {
                if(i%3!= 0 && i%5 != 0)
                {
                    ans += i;
                }
            }

            Console.WriteLine(ans);
        }

    }
}


Measured memory_bytes: 27740
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))

    amount = 1000
    kabu = 0
    for i in range(N):
        if i >= N-1:
            amount += kabu * A[i]
            kabu = 0
        else:
            if A[i] < A[i+1]:
                kabu += amount//A[i]
                amount %= A[i]
            elif A[i] > A[i+1]:
                amount += kabu * A[i]
                kabu = 0

    print(amount)
main()


Measured memory_bytes: 9192
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define MP make_pair
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((L + R) >> 1)
#define eps (1e-5)
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
typedef pair<int, int> PII;
int n, k, l;
int f[200010], g[200010], h[200010], ans[200010];
int findfa(int *w, int o) {
    if (w[o] == o)
        return o;
    return w[o] = findfa(w, w[o]);
}
bool cmp(const int &o, const int &p) {
    int fa = findfa(f, o);
    int fb = findfa(f, p);
    if (fa != fb)
        return fa < fb;
    fa = findfa(h, o);
    fb = findfa(h, p);
    return fa < fb;
}
int main() {
    scanf("%d%d%d", &n, &k, &l);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        g[i] = i;
        h[i] = i;
    }
    for (int i = 0; i < k; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int fa = findfa(f, u);
        int fb = findfa(f, v);
        f[fa] = fb;
    }
    for (int i = 0; i < l; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int fa = findfa(h, u);
        int fb = findfa(h, v);
        h[fa] = fb;
    }
    sort(g + 1, g + n + 1, cmp);
    for (int i = 1; i <= n;) {
        int j = i;
        while (j <= n && findfa(f, g[i]) == findfa(f, g[j]) &&
               findfa(h, g[i]) == findfa(h, g[j])) {
            j++;
        }
        for (int k = i; k < j; ++k) {
            ans[g[k]] = j - i;
        }
        i = j;
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}

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

signed main() {
	int n, d;
	cin >> n >> d;
	int a = n / (2 * d + 1);
	int r = n % (2 * d + 1);
	cout << (r ? a + 1 : a) << endl;
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll k;
    cin >> k;
    vector<ll> a(k);
    for(i = 0;i < k;++i){
        cin >> a.at(i);
    }
    if(a.back() != 2){
        cout << -1 << endl;
        return 0;
    }
    ll mi = 2, ma = 2;
    for(i = 1;i < k;++i){
        ll tmpmi = mi;
        ll tmpma = ma + a.at(k-1-i+1) - 1;
        if(tmpmi%a.at(k-1-i) && tmpma%a.at(k-1-i)){
            if(tmpmi/a.at(k-1-i) == tmpma/a.at(k-1-i)){
                cout << -1 << endl;
                return 0;
            }
        }
        if(tmpmi%a.at(k-1-i) == 0){
            mi = tmpmi;
        }else{
            mi = (tmpmi + a.at(k-1-i))/a.at(k-1-i)*a.at(k-1-i);
        }
        ma = tmpma/a.at(k-1-i)*a.at(k-1-i);
    }
    ma = ma + a.at(0)-1;
    cout << mi << endl;
    cout << ma << endl;

    return 0;
}

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

int main(void){
    int N,i,max,count=0;
    int mount[21]={0};
    cin >> N;
    for(i=1;i<=N;i++){
        cin >> mount[i];
    }

    for(i=1;i<=N;i++){
        if(i==1){
            count++;
            max = mount[1];
        }else if(mount[i]>=max){
            count++;
            max = mount[i];
        }
    }

    cout << count;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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 long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s,t;
char maze[60][60];
int dis[101][101]; int graph[52][52]; bool vis[52];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

int main() {
	cin >> n;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	ll cnt = 0;
	rep(i, n) {
		ll j;
		for (j = 0;; j++) {
			if (a[i] % 2 == 0) {
				a[i] /= 2;
			}
			else break;
		}
		cnt += j;
	}
	cout << cnt << endl;
}



Measured memory_bytes: 384
s = list(input())

if len(s) % 2 == 1:
    print("No")
    exit()

for i in range(len(s)):
    if i % 2 == 0:
        if s[i] == "h":
            continue
        else:
            print("No")
            exit()
    else:
        if s[i] == "i":
            continue
        else:
            print("No")
            exit()
else:
    print("Yes")



Measured memory_bytes: 3060
n = int(input())
P = sorted(list(map(int,input().split())))
flag = True
if n % 2 == 0:
    for i in range(0, n-1, 2):
        if P[i] != P[i+1]:
            flag = False
            break
else:
    for i in range(1, n-1, 2):
        if P[i] != P[i+1]:
            flag = False
            break
if flag:
    ans = 2 ** (n//2) % (10 ** 9 + 7)
else:
    ans = 0
print(ans)

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


int main(){
string a,b,c;
cin >>a >> b>>c;
 char w ='A' -'a';
 char d,e,f;
 d = a.at(0)-32;
 e = b.at(0)-32;
 f=c.at(0)-32;
  cout <<d << e << f << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

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(a>b){a=b;return 1;}return 0;}

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

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

  int H, W, A, B;

  cin >> H >> W >> A >> B;

  COMinit();

  ll ans = 0LL;

  FOR(i, 0, H-A){
    ans += COM(B-1+i, B-1) * COM(W-B-1 + H-1-i, W-B-1)%MOD;
    ans %= MOD;
  }  
  
  cout << ans << endl;
  
  return 0;
}


  /*  
  FOR(j, W-B-1, W){
    ans += COM(H-A+j,W-j);
    cout << "n:" <<  H-A+j << " c:" << W-j << endl;
    ans %= MOD;
    ans += COM(H-A+j,j);
    cout << "n:" <<  H-A+1+j << " c:" << j << endl;    
    ans %= MOD;
  }
  */

Measured memory_bytes: 12160
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Rmq
{
    int n;
    vector<int> data;
    int query(int a, int b, int k, int l, int r){
        if(r < a || b < l)
            return INT_MAX;
        if(a <= l && r <= b)
            return data[k];
        int x = query(a, b, k*2+1, l, (l+r)/2);
        int y = query(a, b, k*2+2, (l+r+1)/2, r);
        return min(x, y);
    }
public:
    Rmq(int n0){
        n = 1;
        while(n < n0)
            n *= 2;
        data.assign(2*n-1, INT_MAX);
    }
    Rmq(vector<int> vi){
        int n0 = vi.size();
        n = 1;
        while(n < n0)
            n *= 2;
        data.assign(2*n-1, INT_MAX);
        for(int i=0; i<n0; ++i)
            data[i+n-1] = vi[i];
        for(int i=n-2; i>=0; --i)
            data[i] = min(data[i*2+1], data[i*2+2]);
    }
    void update(int k, int a){
        k += n - 1;
        data[k] = a;
        while(k > 0){
            k = (k - 1) / 2;
            data[k] = min(data[k*2+1], data[k*2+2]);
        }
    }
    int query(int a, int b){
        return query(a, b, 0, 0, n-1);
    }
};

int main(){
    for(;;){
        int r, c, q;
        cin >> r >> c >> q;
        if(r == 0)
            return 0;

        if(r < c){
            vector<vector<int> > grid(r, vector<int>(c));
            for(int i=0; i<r; ++i){
                for(int j=0; j<c; ++j){
                    cin >> grid[i][j];
                }
            }
            vector<Rmq> rmq;
            for(int i=0; i<r; ++i)
                rmq.push_back(Rmq(grid[i]));

            for(int i=0; i<q; ++i){
                int r1, c1, r2, c2;
                cin >> r1 >> c1 >> r2 >> c2;
                int ret = INT_MAX;
                for(int i=r1; i<=r2; ++i)
                    ret = min(ret, rmq[i].query(c1, c2));
                cout << ret << endl;
            }
        }else{
            vector<vector<int> > grid(c, vector<int>(r));
            for(int i=0; i<r; ++i){
                for(int j=0; j<c; ++j){
                    cin >> grid[j][i];
                }
            }
            vector<Rmq> rmq;
            for(int i=0; i<c; ++i)
                rmq.push_back(Rmq(grid[i]));

            for(int i=0; i<q; ++i){
                int r1, c1, r2, c2;
                cin >> r1 >> c1 >> r2 >> c2;
                int ret = INT_MAX;
                for(int i=c1; i<=c2; ++i)
                    ret = min(ret, rmq[i].query(r1, r2));
                cout << ret << endl;
            }
        }
    }
}

Measured memory_bytes: 23000
def comb(n,m):
    ans = 1
    if n==0 or m == 0:
        return 0
    else:
        for i in range(m):
            j = n-i
            ans *= j
        for i in range(1,m+1):
            ans //= i
        return ans
    
def main():
    import sys
    input = sys.stdin.readline
    N,A,B = map(int,input().split())
    V = list(map(int,input().split()))
    #N,A,B = 50,1,50
    #V = [1]*50
    V = sorted(V)[::-1]
    maxAv = sum(V[:A])/A
    maxB = A
    for i in range(A+1,B+1):
        tmp = sum(V[:i])/i
        if maxAv == tmp:
            maxB = i
    count = 0
    
    C = []
    now = V[0]
    c = 0
    for i in V:
        if now == i:
            c += 1
        else:
            C.append([now,c])
            now = i
            c = 1
    if c != 0:
      C.append([now,c])
    C = sorted(C,key=lambda a: a[0])[::-1]
    for i in range(A,maxB+1):
        pretmp = 0
        tmp = 0
        now = 0
        for j in C:
            if tmp >= i:
                break
            now = j[1]
            pretmp = tmp
            tmp += now
        count += comb(now, i-pretmp)
    #print(C)
    print(maxAv)    
    print(count)
            
    
main()

Measured memory_bytes: 39280
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {//221
	int n;
	cin>>n;
	unordered_map<string,int> a,b;
	while(n--) {
		string val;
		cin>>val;
		a[val]++;
	}
	int m;
	cin>>m;
	while(m--) {
		string val;
		cin>>val;
		b[val]++;
	}
	int ans = 0;
	for(auto i:a) {
		ans=max(ans, i.S-b[i.F]);
	}
	cout<<ans;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3656
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (array[i] < array[j]) {
                    int m = array[i];
                    array[i] = array[j];
                    array[j] = m;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < k; i++) {
            ans += array[i];
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 23124
from itertools import accumulate
N,W = [int(i) for i in input().split()]

dp = [[0 for _ in range(W+1)] for _ in range(N)]

li = [[int(i) for i in input().split()] for _ in range(N)]
dp[0][li[0][0]] = li[0][1]
dp[0] = list(accumulate(dp[0]))
for i in range(1,N):
    for j in range(W+1):
        if j < li[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j-li[i][0]]+li[i][1],dp[i][j-1],dp[i-1][j])

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


Measured memory_bytes: 171784
def submit():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    modp = 10 ** 9 + 7
    dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(n):
        for j in range(1, k + 1):
            if j - 1 - a[i] >= 0:
                dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a[i]]
            else:
                dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1]
            dp[i + 1][j] %= modp
    print(dp[n][k])


submit()
    


Measured memory_bytes: 171656
s=input()
d='dream'
e='erase'
i=0
while i<=len(s)-1:
    if len(s)-1-i<4:
        i=float('inf')
        break
    elif s[i]=='d':
        for j in range(5):
            if s[i+j]!=d[j]:
                i=float('inf')
                break
        else:    
            if i+6<=len(s)-1 and s[i+5]=='e' and s[i+6]=='r':
                if i+7<=len(s)-1 and s[i+7]=='a':
                    i+=5
                else:
                    i+=7
            else:
                i+=5
    elif s[i]=='e':
        for j in range(5):
            if s[i+j]!=e[j]:
                i=float('inf')
                break
        else:
            if i+5<=len(s)-1 and s[i+5]=='r':
                i+=6
            else:
                i+=5
    else:
        i=float('inf')
        break
if i==float('inf'):
    print('NO')
else:
    print('YES')

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

// 2で割れる回数
int div2(int n){
    // 回数を入れる変数
    int cnt = 0;

    // n = 0でないとき、いつか必ず奇数になり、2で割り切れなくなってループを抜ける
    while(n % 2 == 0){
        n /= 2;
        cnt++;
    }

    return cnt;
}

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

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

    int ans = 0;

    // ある整数を3倍しても、2で割れる回数は変わらない(素因数分解を考えればわかる)
    // できるだけ多く操作をするには、ある2で割れる整数を2で割り、それ以外は3倍するのがよい
    // こうしたときに行う操作の回数は、各要素の2で割れる回数の合計である
    for(int i = 0 ; i < n ; i++){
        ans += div2(a[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<unordered_map>
#include<string>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=2e5+5;
LL n,k,a[maxn];
int main()
{
	n=read();
	k=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=k+1;i<=n;++i){
		if(a[i]>a[i-k])
			printf("Yes\n");
		else
			printf("No\n");
	} 
	return 0;
}


Measured memory_bytes: 5192
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
class E { static void Main() { new K(); } }
class K
{
	int F() { return int.Parse(Console.ReadLine()); }
	int[] G() { return Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); }
	public K()
	{
		Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
		var S = Console.ReadLine();
		var a = "";
		foreach (var c in S)
		{
			if (c == 'B' && a.Length > 0) a = a.Substring(0, a.Length - 1);
			else if (c != 'B') a += c;
		}
		Console.WriteLine(a);
		Console.Out.Flush();
	}
}

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

int main() {
  string s;
  cin>>s;
  int n=s.size();
  vector<int>a(n+1,0);
  for(int i=0;i<n;i++){
    if(s[i]=='<'){
      a[i+1]=a[i]+1;
    }
  }
  for(int i=n-1;i>=0;i--){
    if(s[i]=='>'){
      a[i]=max(a[i],a[i+1]+1);
    }
  }
  long long sum=0;
  for(int i=0;i<n+1;i++){
    //cout<<a[i]<<" ";
    sum+=a[i];
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 5784
import bisect

N = int(input())
L = sorted(map(int, input().split()))

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = max(0, (index - 1) - j)
        res += n

print(res)


Measured memory_bytes: 43500
import math
import sys
sys.setrecursionlimit(1000010)

SN = input()
N = int(SN)
K = int(input())
# print(N,K)

m = [[0,0,0,0]]
s = [ 1, 9, 0, 0 ]
m.append(s)
#print(m) 


for i in range(2,101):
    t = [s[0], s[0]*9 + s[1], s[1]*9 + s[2], s[2]*9 + s[3] ]
    s = t
    m.append(s)

# print(m)


def count(n,k):
    if n ==0:
        if k == 0:
            return 1
        else:
            return 0
    if n < 10:
        if k == 0:
            return 1
        elif k == 1:
            return n
        else:
            return 0
    if k == 0:
        return 1

    if n < 10 ** (k-1):
        return 0
        
    t = n 
    p = 1 
    q = 0
    while t >= 10:
        t = t //10
        p = p * 10
        q = q + 1 
    # Saijoui 0 : 00000-09999
    #print("t,q", t,q)
        
    ans = m[q][k]
    #print(n,k, "#1", ans)
    # Saijoun 1-(t-1): x0000-x9999
    #print(n,k,"#2",(t-1)* m[q][k-1])
    ans = ans + (t-1)* m[q][k-1]

    # Saijoui t: t0000-tbcdrf
    remain = n - p * t 
    x = count(remain,k-1)
    #print(n,k, "#3", x)
    ans = ans + x
    # print(n,k,"#4",ans)
    return ans

print(count(N,K))




Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    map<int, int> mp;
    rep(i, n)
    {
        int t;
        cin >> t;
        mp[t]++;
    }
    int ans = 0;
    for (auto x : mp)
    {
        if (x.first > x.second)
            ans += x.second;
        else
            ans += x.second - x.first;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4736
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	N := getStdinInt()

	switch {
	case (N%10 == 2) ||
		(N%10 == 4) ||
		(N%10 == 5) ||
		(N%10 == 7) ||
		(N%10 == 9):
		fmt.Print("hon")
	case (N%10 == 0) ||
		(N%10 == 1) ||
		(N%10 == 6) ||
		(N%10 == 8):
		fmt.Print("pon")
	case (N%10 == 3):
		fmt.Print("bon")
	}

	fmt.Printf("\n")
}

func getStdin() string {
	sc.Scan()
	return sc.Text()
}
func getStdinInt() int {
	str := getStdin()
	rtn, _ := strconv.Atoi(str)
	return rtn
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}


Measured memory_bytes: 1752
#include<stdio.h>
int main(void){
int r,c,i,j;
int sheet[101][101];
scanf("%d %d\n",&r ,&c);
for(i=0;i <= r;i++){
for(j=0;j <= c;j++){
sheet[i][j]=0;
}
}
for(i=0;i < r;i++){
for(j=0;j < c;j++){
if (j == c-1){
scanf("%d\n",&sheet[i][j]);
}else{
scanf("%d ",&sheet[i][j]);
}
}
}
for(i=0;i < r;i++){
for(j=0;j < c;j++){
sheet[i][c] += sheet[i][j];
}
}
for(j=0;j < c;j++){
for(i=0;i < r;i++){
sheet[r][j] += sheet[i][j];
}
}
for(i=0;i < r;i++){
for(j=0;j < c;j++){
sheet[r][c] += sheet[i][j];
}
}
for(i=0;i <= r;i++){
for(j=0;j <= c;j++){
if (j == c){
printf("%d\n",sheet[i][j]);
}else{
printf("%d ",sheet[i][j]);
}
}
}
return 0;
}

Measured memory_bytes: 640
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

ll dp[6010][12010];

int main() {
    ll N, M; scanf("%lld%lld", &N, &M);
    
    int ofs = 6000;
    dp[0][ofs] = 1;
    for(int i=0; i<3*N; i++) {
        for(int j=0; j<=2*ofs; j++) {
            if(i+1 <= 3*N and j+1 <= 2*ofs) {
                (dp[i+1][j+1] += dp[i][j]) %= M;
            }
            if(i+2 <= 3*N and j-1 >= 0) {
                (dp[i+2][j-1] += dp[i][j] * (3*N-i-1)) %= M;
            }
            if(i+3 <= 3*N) {
                ll m = (3*N-i-1) * (3*N-i-2);
                (dp[i+3][j] += dp[i][j] * m) %= M;
            }
        }
    }

    ll ans = 0;
    for(int i=ofs; i<=ofs+3*N; i++) (ans += dp[3*N][i]) %= M;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 563328
#include<bits/stdc++.h>
#define int long long int
#define MP make_pair
#define PB push_back
#define F first
#define S second
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef vector<PII> VP;

const int INF = 3e18;

int h, w;
char field[1010][1010];

queue<PII> qu, qu_new;
int ans = 0;

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

signed main()
{
  cin >> h >> w;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> field[i][j];
    }
  }

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(field[i][j] == '.'){
	qu.push(MP(i, j));
      }
    }
  }

  while(!qu.empty()){

    while(!qu_new.empty()){
      PII now = qu_new.front();
      qu_new.pop();

      field[now.F][now.S] = '.';
    }

    int sz = qu.size();
    for(int i = 0; i < sz; i++){

      PII now = qu.front();
      qu.pop();
      
      if(field[now.F][now.S] == '.'){
	field[now.F][now.S] = ':';
	
	for(int j = 0; j < 8; j++){
	  PII next = MP(now.F + dx[j], now.S + dy[j]);

	  if(1 <= next.F && next.F < h - 1 && 1 <= next.S && next.S < w - 1 && '0' <= field[next.F][next.S] && field[next.F][next.S] <= '9'){
	    int ct = 0;
	    for(int k = 0; k < 8; k++){
	      if(!('0' <= field[next.F + dx[k]][next.S + dy[k]] && field[next.F + dx[k]][next.S + dy[k]] <= '9')){
		ct++;
	      }
	    }

	    if(ct >= field[next.F][next.S] - '0'){
	      qu_new.push(next);
	      qu.push(next);
	    }
	  }
	  
	}
      }
    }
    if(!qu.empty()){
      ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4312
#include <iostream>
#include <deque>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#define llint long long
#define mod 998244353
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;
typedef pair<llint, P> E;

llint n;
llint a[3], b[3];

int main(void)
{
	cin >> n;
	for(int i = 0; i < 3; i++) cin >> a[i];
	for(int i = 0; i < 3; i++) cin >> b[i];
	
	llint cnt = 0;
	for(int i = 0; i < 3; i++){
		if(a[i] <= b[i]) cnt++;
	}
	llint ans = n;
	if(cnt == 3){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				llint k = n-(i+j);
				if(k < 0) continue;
				llint tmp = i/a[0]*b[0] + j/a[1]*b[1] + k/a[2]*b[2];
				tmp += i%a[0] + j%a[1] + k%a[2];
				ans = max(ans, tmp);
			}
		}
	}
	if(cnt == 0){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				llint k = n-(i+j);
				if(k < 0) continue;
				llint tmp = i/b[0]*a[0] + j/b[1]*a[1] + k/b[2]*a[2];
				tmp += i%b[0] + j%b[1] + k%b[2];
				ans = max(ans, tmp);
			}
		}
	}
	if(cnt == 1){
		llint x, y, z;
		if(a[0] <= b[0]) x = 0, y = 1, z = 2;
		if(a[1] <= b[1]) x = 1, y = 2, z = 0;
		if(a[2] <= b[2]) x = 2, y = 0, z = 1;
		
		llint m = n/a[x]*b[x] + n%a[x];
		for(int i = 0; i <= m; i++){
			llint j = m-i;
			llint tmp = i/b[y]*a[y] + j/b[z]*a[z];
			tmp += i%b[y] + j%b[z];
			ans = max(ans, tmp);
		}
	}
	if(cnt == 2){
		llint x, y, z;
		if(a[0] > b[0]) x = 0, y = 1, z = 2;
		if(a[1] > b[1]) x = 1, y = 2, z = 0;
		if(a[2] > b[2]) x = 2, y = 0, z = 1;
		
		llint m = 0;
		for(int i = 0; i <= n; i++){
			llint j = n-i;
			llint tmp = i/a[y]*b[y] + j/a[z]*b[z];
			tmp += i%a[y] + j%a[z];
			m = max(m, tmp);
		}
		ans = m/b[x]*a[x] + m%b[x];
	}
	
	cout << ans << endl;
	
	return 0;
}


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


class Graph {
    int V;
    vector<list<int>> edges;
    public:
    Graph(int nodes){
        V = nodes;
        edges.resize(nodes + 1);
    }
    void addEdge(int from, int to){
        edges[from].push_back(to);
    }
    int min_dist(int &fin, int i, map<int ,bool> &special, vector<bool> &check){
        check[i] = true; 
        multiset<int> ms;     
        int k;
        for(auto it = edges[i].begin(); it != edges[i].end(); it++){
            if(check[*it] == true)
                continue;
            k = min_dist(fin, *it, special, check);
            if(k != 0)
                ms.insert(k);
        }
        for(auto it = ms.begin(); it != ms.end(); it++){
            fin += (*it);
            //cout << *it << " ";
        }
        //cout << endl;
        if(ms.size() % 2 == 0){
            if(special[i])    
                return 1;
            return 0;
        }
        else{
            if(special[i])
                return 0;
            auto it = ms.begin();
            fin -= (*it);
            return (*it) + 1;
        }
    }
};


int main(){
    int t = 1;
    //cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<ll> arr(n);
        for(int i = 0; i < n; i++){
            cin >> arr[i];
        }
        ll sum = 0;
        ll temp = arr[n - 1];
        for(int i = n - 2; i >= 0; i--){
            sum = (sum + (arr[i] % INF)*(temp % INF)) % INF;
            temp =  (temp + arr[i])  % INF;
        }
        
        
        cout << sum % INF << endl;
    }
    return 0;
}







Measured memory_bytes: 4812
/*
      author  : nishi5451
      created : 14.08.2020 19:51:57
*/

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


int main(){
    int n;
    cin >> n;
    for(int i=0; i<=100; i++){
        for(int j=0; j<=100; j++){
            if(7*i+4*j==n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3636
from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

N,K,L = map(int,input().split())
u1 = UnionFind(N)
u2 = UnionFind(N)
for _ in range(K):
    p,q = map(int,input().split())
    u1.union(p-1,q-1)
for _ in range(L):
    r,s = map(int,input().split())
    u2.union(r-1,s-1)

d = defaultdict(lambda:0)
for i in range(N):
    d[(u1.find(i),u2.find(i))] += 1

ans = []
for i in range(N):
    ans.append(str(d[(u1.find(i),u2.find(i))]))

ans = ' '.join(ans)
print(ans)

Measured memory_bytes: 48644
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N ;
  vector<int> l(N);
  vector<int> r(N);
  for ( int i=0 ; i < N ; i++ ) {
    cin >> l.at(i) >> r.at(i) ;
  }
  int l_sum = accumulate(l.begin(), l.end(), 0);
  int r_sum = accumulate(r.begin(), r.end(), 0);
  cout << r_sum-l_sum+N << endl;
}

Measured memory_bytes: 3604
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = int(lines[0])

    return (n, )


def solve(n):


    x = n / 1.08

    a = int(math.floor(math.floor(x) * 1.08))
    b = int(math.floor(math.ceil(x) * 1.08))

    result = ':('
    if a == n:
        result = str(int(math.floor(x)))

    if b == n:
        result = str(int(math.ceil(x)))


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

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

char s[205];

bool check(int len){
	
	int i = 0, j = len / 2;
	for( ;i < len/2; i ++, j ++){
		if(s[i] != s[j])return false;
	} 
	return true;
}
int main(){
	cin>>s;
	int len = strlen(s);
	for(int i = len - 1; i >= 2; i --){
		if(i % 2 == 0 &&check(i)){
			printf("%d", i);
			return 0;
		}
	}
	printf("-1");
	return 0;
}

Measured memory_bytes: 256
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<int> A(N);
    REP(i, N) cin >> A[i];

    int tmp = 0;
    REV(k, 50, 0) {
        int test = tmp + (1LL << k);
        if (tmp + (1LL << k) > K) continue;

        int cnt = 0;
        REP(i, A.size()) {
            if ((A[i] >> k) & 1LL) cnt++;
        }

        if (cnt * 2LL < A.size()) {
            tmp += (1LL << k);
        }
    }

    int ans = 0;
    REP(i, A.size()) {
        ans += (tmp ^ A[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		//スキャナ宣言
		Scanner sc = new Scanner(System.in);

		//子供の人数Nを入力
		int N = sc.nextInt();

		//N人の子供に対して合計何個のキャンディーがいるかを算出する。
		int candySum = 0;
		for (int i = 1; i <= N; i++) {
			candySum = candySum + i;
		}

		//結果の出力
		System.out.println(candySum);
	}

}

Measured memory_bytes: 23636
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string S;
  cin >> S;
  int a = 0, b = 0;
  F0R(i, S.size()) {
    if (S[i] == '0' + (i & 1)) {
      a++;
    }
    else b++;
  }
  cout << min(a, b);
}
#endif


Measured memory_bytes: 3756
from itertools import accumulate

n, x = [int(z) for z in input().split()]
a = [int(z) for z in input().split()]

a.sort()
cnt = 0
for suma in accumulate(a):
    if suma > x:
        break
    cnt += 1
else:
    if suma != x:
        cnt -= 1

print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define fo(i,n) for(int i=0;i<n;i++)
int main(){
   int n,ans = 0;cin >>n;
   string s,t;cin >> s >>t;
   if(s==t){
       cout << n;return 0;
   }
   fo(i,n){
       if((s.substr(n-1-i,i+1)==t.substr(0,i+1))&&(i+1 > ans)){
           ans = i+1;
       }
   }
   cout << 2*n -ans;
}



Measured memory_bytes: 3580
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    G[x-1].append(y-1)

memo = [-1]*N
def dfs(v):
    if memo[v] != -1:
        return memo[v]
    memo[v] = r = max(dfs(w) for w in G[v]) + 1 if G[v] else 0
    return r
print(max(dfs(v) for v in range(N)))

Measured memory_bytes: 106648
#include <stdio.h>
#include <vector>
using namespace std;

#define ll long long
#define MAX_N 100000

ll max_(ll a, ll b){
    if(a < b){
        return b;
    }
    return a;
}

int main(void){
    ll N, C;
    scanf("%lld", &N);
    scanf("%lld", &C);

    vector<pair<ll, ll>> vec;
    ll x_, v_;
    for(int i = 0; i < N; i++){
        scanf("%lld", &x_);
        scanf("%lld", &v_);
        vec.push_back(make_pair(x_, v_));
    }

    ll Cr1[MAX_N + 1];
    ll Cr2[MAX_N + 1];
    Cr1[0] = 0;
    Cr2[0] = 0;
    ll sum_v = 0;
    for(int i = 1; i <= N; i++){
        sum_v += vec[i - 1].second;
        Cr1[i] = max(sum_v - vec[i - 1].first, Cr1[i - 1]);
        Cr2[i] = max(sum_v - vec[i - 1].first * 2, Cr2[i - 1]);
    }
    
    ll Cl1[MAX_N + 1];
    ll Cl2[MAX_N + 1];
    Cl1[0] = 0;
    Cl2[0] = 0;
    sum_v = 0;
    for(int i = 1; i <= N; i++){
        sum_v += vec[N - i].second;
        Cl1[i] = max(sum_v - (C - vec[N - i].first), Cl1[i - 1]);
        Cl2[i] = max(sum_v - (C - vec[N - i].first) * 2, Cl2[i - 1]);
    }

    ll max_right_c = 0;
    for (int i = 0; i <= N; i++){
        max_right_c = max_(max_(Cr1[i] + Cl2[N - i], Cr2[i] + Cl1[N - i]), max_right_c);
        //printf("%lld\n", max_right_c);
    }

    /*
    for(int i = 0; i <= N; i++){
        printf("Cr1[%d] %lld\n", i, Cr1[i]);
    }
    for(int i = 0; i <= N; i++){
        printf("Cr2[%d] %lld\n", i, Cr2[i]);
    }
    for(int i = 0; i <= N; i++){
        printf("Cl1[%d] %lld\n", i, Cl1[i]);
    }
    for(int i = 0; i <= N; i++){
        printf("Cl2[%d] %lld\n", i, Cl2[i]);
    }
    */


    printf("%lld\n", max_right_c);

    return 0;
}


Measured memory_bytes: 5104
import sys
from bisect import bisect
F = sys.stdin
A, B, Q = map(int, F.readline().strip("\n").split(" "))
S, T =[None] * (A+2), [None] * (B+2)
S[0], T[0] = -10**20, -10**20
for i in range(A):
    S[i+1] = int(F.readline().strip("\n"))
for i in range(B):
    T[i+1] = int(F.readline().strip("\n"))
S[A+1] = 10**20
T[B+1] = 10**20

lenS, lenT = len(S), len(T)
Out = ""
for _ in range(Q):
    x = int(F.readline().strip("\n"))
    si, ti = bisect(S, x, 0, lenS), bisect(T, x, 0, lenT)
    sLength0, sLength1 = x - S[si-1], S[si] - x
    tLength0, tLength1 = x - T[ti-1], T[ti] - x
    Ans = min(max(sLength0, tLength0), max(sLength1, tLength1), sLength0 + tLength1 + min(sLength0, tLength1), sLength1 + tLength0 + min(sLength1, tLength0))
    Out += str(Ans) + "\n"
print(Out)

Measured memory_bytes: 14400
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;



int main()
{
	string str;
	cin>>str;
	if(str[0] == str[1] && str[1] == str[2]){
		cout<<"No"<<endl;
	}else{
		cout<<"Yes"<<endl;
	}
	return 0;
}



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

using namespace std;

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl

int main(){
    char c;
    string b="aeiou";
    cin>>c;
    
    cout<<((b.find(c)!=string::npos)?"vowel":"consonant")<<endl;
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
s=list(input())
if s[k-1]=='A':
  s[k-1]='a'
else:
  if s[k-1]=='B':
    s[k-1]='b'
  else:
    s[k-1]='c'

s = ''.join(s)
print(s)

Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int main() {
	ll a, b;
	ll n;
	cin >> n >> a >> b;
	if (a > b) swap(a, b);
	ll len = b - a;
	if (len % 2 == 0) {
		cout << (b - a) / 2 << endl;
	}
	else {
		ll ans = min(a - 1, n - b) + 1;
		ll aaa = b - a - 1;
		cout << aaa / 2 + ans << endl;
	}

	return 0;
}

Measured memory_bytes: 256