akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>

#define int long long

using namespace std;

class Solver {
};

tuple<string,char> dfs(string s, int remain) {
	string now = "";
	for (int i = 0; i < s.size(); i++) {
		if ('0' <= s[i] && s[i] <= '9') {
			int loop = 0;
			while ('0' <= s[i] && s[i] <= '9') {
				loop *= 10;
				loop += (s[i] - '0');
				i++;
			}
			i++;
			string tmp = "";
			int nest = 1;
			for (; i < s.size(); i++) {
				if (s[i] == '(')nest++;
				if (s[i] == ')') {
					nest--;
					if (nest == 0) {
						break;
					}
				}
				tmp += s[i];
			}

			tuple<string, char> tpl = dfs(tmp, remain);
			if (get<1>(tpl) != '0')return make_tuple(now, get<1>(tpl));
			tmp = get<0>(tpl);
			for (int j = 0; j < loop; j++) {
				remain -= tmp.size();
				now += tmp;
				if (remain < 0)return make_tuple(now, now[now.size() + remain]);
			}
		}
		else {
			now += s[i];
			remain--;
			if (remain < 0)return make_tuple(now, now[now.size() + remain]);
		}
	}
	return make_tuple(now, '0');
}

signed main() {
	while (true) {
		string s;
		int n;
		cin >> s >> n;
		if (s[0] == '0')break;

		string formated = "";
		for (int i = 0; i < s.size(); i++) {
			if (i > 0 && 'A' <= s[i] && s[i] <= 'Z'
				&& '0' <= s[i - 1] && s[i - 1] <= '9') {
				formated += '(';
				formated += s[i];
				formated += ')';
			}
			else {
				formated += s[i];
			}
		}
		cout << get<1>(dfs(formated, n)) << endl;
	}
}


Measured memory_bytes: 8152
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long


signed main() {
  while (true) {
    int n, m, a;
    cin >> n >> m >> a;
    if (!n && !m && !a) return 0;
    int h[m], p[m], q[m];
    for (int i = 0; i < m; i++) {
      cin >> h[i] >> p[i] >> q[i];
    }
    int ans = a;
    for (int i = 1000; i >= 0; i--) {
      for (int j = 0; j < m; j++) {
        if (h[j] == i) {
          if (ans == p[j]) ans = q[j];
          else if (ans == q[j]) ans = p[j];
        }
      }
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 3080
import bisect
def is_ok(mid):
  ind=bisect.bisect_right(h,mid*b)
  cnt=0
  for i in range(ind,n):
    cnt+=(h[i]-mid*b+a-b-1)//(a-b)
  if cnt<=mid:return True
  else:return False
n,a,b=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
ng=-1
ok=(h[-1]+b-1)//b
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if is_ok(mid):ok=mid
  else:ng=mid
print(ok)

Measured memory_bytes: 81796
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,y,z;
    int k,s;
    cin>>k>>s;
    long long count1=0;
    for(int i=0;i<=k;i++){
        for(int j=0;j<=k;j++){
            if(s-j-i<=k && s-j-i>=0){
                count1++;
            }
        }
    }
    cout<<count1<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int x,a,b;
  cin>>x>>a>>b;
  if(abs(x - a) > abs(x - b)) {
    cout << "B" << endl;
  } else {
    cout << "A" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sat Feb  9 20:33:11 2019

@author: Yamazaki Kenichi
"""

A = [list(map(int,input().split())) for i in range(3)]

a=[]
for j in range(3):
    for i in range(2):
        a.append(A[j][i])
        
ans = 'YES'
for i in range(1,5):
    if a.count(i) >=3 :
        ans ='NO'
        
print(ans)

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

int main()
{
	
	long long a,x;
	cin >> x >> a;
	if(x<a){
		cout << 0 << endl;
	}
	else {
		cout << 10 << endl;
	}
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;


int main(void)
{
	int n, m;
	while(scanf("%d%d", &n, &m)==2)
	{
		vi a(m);
		for(auto&ma:a) scanf("%d", &ma);

		int ans=n;
		for(int ma:a) ans-=ma;
		if(ans<0) ans=-1;
		printf("%d\n", ans);
	}
	return 0;
}


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

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1 + (key % (M-1)); }

int find(char str[]){
  long long key, i, h;
  key = getKey(str);
  for ( i = 0;; i++){
    h = (h1(key)+i*h2(key))%M;
    if( strcmp(H[h],str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ) return 0;
  }
  return 0;
}

int insert(char str[]){
  long long key, i, h;
  key = getKey(str);
  for ( i = 0; ; i++ ){
    h = (h1(key)+i*h2(key))%M;
    if( strcmp(H[h],str) == 0 ) return 1;
    else if ( strlen(H[h]) == 0 ){
      strcpy(H[h], str);
      return 0;
    }
  }
  return 0;
}

main(){
  int i, n, h;
  char str[L], com[9],a=0;
  a=kansu(a);
  if(a == 0){
  for ( i = 0; i < M; i++ ) H[i][0] = '\0';
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s %s", com, str);

    if ( com[0] == 'i' ){
      if (insert(str)){

      }
    } else {
      if (find(str) ){
	printf("yes\n");
      } else {
	printf("no\n");
      }
    }
  }
  return 0;
}
}
void kansu(int a){
 int b=0,c=1;
 if(b == 0);
  if(c == 1);
   return a;
}


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

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)

static const int maxN = 333;
static const int base = 1e9 + 7;

int n, m;
int dp[maxN][maxN][maxN];
vector < pair <int, int> > L[maxN];

void Enter() {
    scanf("%d%d", &n, &m);
    FOR(i, 1, m) {
        int l, r, x; scanf("%d%d%d", &l, &r, &x);
        L[r].push_back(make_pair(l, x));
    }
}

bool ok (int i, int j, int k) {
    int r = max(i, max(j, k));
    for (auto v : L[r])
        if ((i >= v.first) + (j >= v.first) + (k >= v.first) != v.second) return 0;
    return 1;
}

void Process() {
    for (auto v : L[1]) if (v.second != 1) {
        puts("0");
        return;
    }
    dp[1][0][0] = dp[0][1][0] = dp[0][0][1] = 1;
    FOR(k, 1, n) {
        //k is res; i is blue; j is green
        REP(i, k) REP(j, k) if (i != j || !j) {
            if (ok(k + 1, i, j)) dp[k + 1][i][j] = (dp[k + 1][i][j] + dp[k][i][j]) % base;
            if (ok(k, k + 1, j)) dp[k][k + 1][j] = (dp[k][k + 1][j] + dp[k][i][j]) % base;
            if (ok(k, i, k + 1)) dp[k][i][k + 1] = (dp[k][i][k + 1] + dp[k][i][j]) % base;
        }
        //i is red; k is blue; j is green
        REP(i, k) REP(j, k) if (i != j || !j) {
            if (ok(i, k + 1, j)) dp[i][k + 1][j] = (dp[i][k + 1][j] + dp[i][k][j]) % base;
            if (ok(k + 1, k, j)) dp[k + 1][k][j] = (dp[k + 1][k][j] + dp[i][k][j]) % base;
            if (ok(i, k, k + 1)) dp[i][k][k + 1] = (dp[i][k][k + 1] + dp[i][k][j]) % base;
        }
        //i is red; j is blue; k is green
        REP(i, k) REP(j, k) if (i != j || !j) {
            if (ok(i, j, k + 1)) dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % base;
            if (ok(i, k + 1, k)) dp[i][k + 1][k] = (dp[i][k + 1][k] + dp[i][j][k]) % base;
            if (ok(k + 1, j, k)) dp[k + 1][j][k] = (dp[k + 1][j][k] + dp[i][j][k]) % base;
        }
    }
    int res = 0;
    REP(i, n + 1) REP(j, n + 1) REP(k, n + 1)
        if (i == n || j == n || k == n)
            res = (res + dp[i][j][k]) % base;
    printf("%d\n", res);
}

int main() {
  //  freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);

    Enter();
    Process();

    return 0;
}


Measured memory_bytes: 131200
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

int K, dist[(int)1e5 + 5];
deque<int> BFS;

int main(){
  FAST_IO
  cin >> K;

  for(int rep = 0; rep < K; ++rep) dist[rep] = INF;
  dist[1] = 1;
  BFS.push_back(1);

  while(!BFS.empty()){
    int cur = BFS.front();
    if(cur == 0){
      cout << dist[cur] << '\n';
      return 0;
    }

    BFS.pop_front();

    int nxt = (cur + 1) % K;
    if(dist[nxt] > dist[cur] + 1){
      dist[nxt] = dist[cur] + 1;
      BFS.push_back(nxt);
    }

    nxt = (cur * 10) % K;
    if(dist[nxt] > dist[cur]){
      dist[nxt] = dist[cur];
      BFS.push_front(nxt);
    }
  }

  return 0;
}


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

using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	char s[n];
	char t[n];
	scanf("%s %s",s,t);
	for (int i = 0; i < n; ++i){
		printf("%c", s[i]);
		printf("%c", t[i]);
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int N,Y; cin>>N>>Y;
  int a10000=0,a5000=0,a1000=0;
  Y /= 1000;

  bool flag = false;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      if(10*i + 5*j + N-i-j == Y && N-i-j >= 0){
        a10000 = i;
        a5000 = j;
        a1000 = N-i-j;
        flag = true;
      }
    }
  }

  if(flag){
    cout<<a10000<<" "<<a5000<<" "<<a1000<<endl;
  }else{
    cout<<"-1 -1 -1"<<endl;
  }
}


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

struct UnionFind {
    vector<int> data; int group;
    UnionFind(int N) : data(N, -1), group(N) {}
    void init(int N) {
        data.assign(N, -1);
        group = N;
    }
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(data[x] > data[y])  swap(x, y);        
        if(x != y){
            data[x] += data[y];
            data[y] = x;
            --group;
        }
    }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]);}
    bool same(int a, int b) { return root(a) == root(b);}
};

class in{struct It{int it;const bool rev;explicit constexpr It(int it_, bool rev=false):it(it_),rev(rev){}int operator*(){return it;}bool operator!=(It& r){return it!=r.it;}void operator++(){rev?--it:++it;}};const It i,n;public:explicit constexpr in(int n):i(0),n(n<0?0:n){}explicit constexpr in(int i,int n):i(i,n<i),n(n){}const It& begin(){return i;}const It& end(){return n;}};

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

    int n, q;
    cin >> n >> q;
    UnionFind uf(n);

    for(int _ : in(q)) {
        int k, u, v;
        cin >> k >> u >> v;
        if(k)
            cout << uf.same(u, v) << '\n';
        else
            uf.unite(u, v);
    }
    return 0;
}

Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> A,B,C;
  A=B=C=vector<int>(N);
  for(int i=0;i<N;i++)cin>>A[i];
  for(int i=0;i<N;i++)cin>>B[i];
  for(int i=0;i<N-1;i++)cin>>C[i];
  int ans=0;
  int log=A[0]-1;
  for(int i=0;i<N;i++){
    int tmp=A[i];
    tmp--;
    if(log+1==tmp){
      ans+=C[tmp-1];
    }
    log=tmp;
    ans+=B[tmp];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
msb = 1
ret = sum(a)
acc = sum(a)
while msb <= k:
    d = sum(msb if ai & msb == 0 else -msb for ai in a)
    ret = max(d + ret, acc) if msb & k != 0 else ret
    acc = max(d + acc, acc)
    msb *= 2
print(ret)


Measured memory_bytes: 14596
n,k = gets.chomp.split(" ")
s = gets.chomp.split("")

if s[k.to_i-1] == "A"
  s[k.to_i-1] = "a"
elsif s[k.to_i-1] == "B"
  s[k.to_i-1] = "b"
elsif s[k.to_i-1] == "C"
  s[k.to_i-1] = "c"
end

puts s.join 

Measured memory_bytes: 1788
import fractions as f
n,m=map(int,input().split())
a=list(map(int,input().split()))
g=1
def check(n):
  cnt=0
  while n%2==0:
    n//=2
    cnt+=1
  return cnt
chk=check(a[0])
for i in a:
  if chk!=check(i):
    print(0)
    exit()
  else:
    chk=check(i)
for i in range(n):
  g=g*(a[i]//2)//(f.gcd(g,a[i]//2))
  if g>m:print(0);exit()
print(m//g-m//(2*g))


Measured memory_bytes: 89580
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1200;
const int k = 33;
//const int offset = 0;
const int offset = 1000000000;
typedef long long ll;
int X[N], Y[N],bits[k][2];

char s[40];
int sn;

vector<ll> vec;

void test(int a, int b) {
    ll x = 0, y = 0;
    assert(sn == m);
    for (int i = 0; i < sn; i++) {
        ll v = vec[i];
        if (s[i] == 'L') x -= v;
        else if (s[i] == 'R') x += v;
        else if (s[i] == 'D') y -= v;
        else y += v;
    }
    assert(a == x && b == y);
}

void add(int j, int sign) {
    if (j == 0) {
        if (sign == -1) s[sn++] = 'L'; else s[sn++] = 'R';   
    }
    else {
        if (sign == -1) s[sn++] = 'D'; else s[sn++] = 'U'; 
    } 
}

void solve1(int i) {
    int *x = bits[i], *nx = bits[i+1];
    //printf("i=%d, x=(%d,%d),nx=(%d,%d),bits[i+1]=(%d,%d)\n",i,x[0],x[1],nx[0],nx[1],bits[i+1][0],bits[i+1][1]);
    for (int j = 0; j < 2; j++) {
        if (x[j] == 2) nx[j] += 1, x[j] = 0;
    }
    int j = x[1] == 1;
    
    bool op = (nx[0]^nx[1])&1;
    //printf("i=%d, j=%d,op=%d,x=(%d,%d),nx=(%d,%d)\n",i,j,op,x[0],x[1],nx[0],nx[1]);
    if (i + 1 == k - 1) op ^= 1;
    //printf("i=%d, j=%d,op=%d,x=(%d,%d),nx=(%d,%d)\n",i,j,op,x[0],x[1],nx[0],nx[1]);
    if (op) add(j, 1);
    else {
        add(j, -1);
        nx[j] += 1;
    }
}
void solve2(int i) {
    int *x = bits[i];
    if (x[0] == 0) add(0, 1), add(0, -1);
    else add(0, 1), add(1, 1);
}

void solve0(ll x, ll y) {
    sn = 0;
    memset(s,0,sizeof s);
    add(0, -1);
    add(1, -1);
    x += offset;
    y += offset;
    for (int i = 0; i < k; i++) {
        bits[i][0] = x >> i & 1;
        bits[i][1] = y >> i & 1;
        //printf("HaHa: %d, %d, %d, %d\n",x, i,bits[i][0], bits[i][1]);
    }
    
    int num = bits[0][0] * 2 + bits[0][1];
    if (num == 0) {
        add(0, -1);
        bits[0][0] = 1;
    }
    else if (num == 3) {
        add(0, 1);
        bits[0][0] = 0;
    }
    for (int i = 0; i < k - 1; i++) solve1(i);
    solve2(k - 1);
    printf("%s\n", s);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", X + i, Y + i);
    }
    bool isodd;
    
    isodd = (X[0] + Y[0]) & 1;
    for (int i = 1; i < n; i++) {
        if (((X[i] + Y[i]) & 1) != isodd) {
            puts("-1");
            return 0;
        }
    }

    vec.push_back(offset);
    vec.push_back(offset);

    if (!isodd) {
        vec.push_back(1);
    }
    for (int i = 0; i < k; i++) {
        vec.push_back(1LL<<i);
    }
    vec.push_back(1LL<<(k-1));
    m = vec.size();
    printf("%d\n",m);
    for (int i = 0; i < m; i++) {
        printf("%lld%c", vec[i], " \n"[i == m - 1]);
    }
    for (int i = 0; i < n; i++) {
        solve0(X[i], Y[i]);
        test(X[i], Y[i]);
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class ilds1_4_a{
  public static void Main(){
    int n = int.Parse(Console.ReadLine());
    int[] numn = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    int q = int.Parse(Console.ReadLine());
    int[] numq = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    int ans = 0;
    for(int i=0; i<q; i++){
      for(int j=0; j<n; j++){
        if(numn[j] == numq[i]){
          ans++;
          break;
        }
      }
    }
    Console.WriteLine(ans);
  }
}



Measured memory_bytes: 18340
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<utility>
#include<cstdio>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<deque>
using namespace std;
#define rep(i,x,n) for(int i=x;i<n;i++)
#define WHITE 0
#define BLACK 1
typedef long long ll;
typedef pair<ll,ll> pl;
typedef pair<int,int> pi;
int INFi=1000000000;
ll INFl=1000000000000000;

struct UnionFind{
    vector<int> par;//初期化
    vector<int> rank;//高さ
    UnionFind(int n=0):par(n),rank(n,0){
        for(int i=0;i<n;i++) par[i]=i;
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);//経路圧縮
    }
    void unite(int x,int y){
        int rx=root(x);
        int ry=root(y);
        if(rx==ry) return;
        if(rank[rx]<rank[ry]) rank[rx]=ry;
        else rank[ry]=rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
        }
    bool same(int x,int y){
        return root(x)==root(y);
    }
};

int main(){
    int q,f;cin>>q;
    deque<int> que;
    for(int i=0;i<q;i++){
        cin>>f;
        switch(f){
            case 0:int d,x;cin>>d>>x;
            if(d==0) que.push_front(x);
            else que.push_back(x);
            break;
            case 1:int p;cin>>p;
            cout<<que[p]<<endl;
            break;
            case 2:int d2;cin>>d2;
            if(d2==0) que.pop_front();
            else que.pop_back();
            break;
        }
    }
}


Measured memory_bytes: 4612
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
signed main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		int r = 0;
		a %= b;
		for (int i = 0; i < c; i++) {
			a *= 10;
			r += a / b;
			a %= b;
		}
		cout << r << endl;
	}
}


Measured memory_bytes: 3060
N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse = True)

s = []
i = 0
while i < N - 1:
    if len(s) == 2:
        break
    if A[i] == A[i + 1]:
        s.append(A[i])
        i += 2
    else:
        i += 1

if len(s) == 2:
    print(s[0] * s[1])
else:
    print(0)

Measured memory_bytes: 20012
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#include<cassert>
using namespace std;

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

#define INF INT_MAX/3
#define REP(i,n) for(int i=0;i<n;i++)

int N, M, Q;
vector<int>a_array;
vector<int>b_array;
vector<int>c_array;
vector<int>d_array;
vector<int> n_arr;
int answer = 0;

int value_check(){
	int cost = 0;

	for(int i = 0; i < Q; i++){
		if(n_arr[b_array[i]] - n_arr[a_array[i]] == c_array[i]){
			cout<<"d ["<<i<<"] "<<d_array[i]<<endl;
			cost += d_array[i];
		}
	}
	return cost;
}

//vector<int> arr;
void rec(int length,int before,vector<int> arr){
	//cout<<length<<" "<<before<<endl;
	if(length == N){
//		for(auto& s: arr){
//			cout<<s<<" ";
//		}
//		cout<<endl;
//		cout<<"as : "<<arr.size()<<endl;
		int cost = 0;
		for(int i = 0; i < Q; i++){
			if(arr[b_array[i]-1] - arr[a_array[i]-1] == c_array[i]){
//				cout<<"d ["<<i<<"] "<<d_array[i]<<endl;
				cost += d_array[i];
			}
		}
		answer = max(cost,answer);
		return;
	}

	for(int i = before; i <= M; i++){
		arr.push_back(i);
		rec(length + 1, i,arr);
		arr.pop_back();
	}

}

ll conv_calc(ll n,ll m){

	ll ans = 1;
	ll n_mem = n;
	for(ll i = 0; i < m; i++){
		ans *= n_mem;
		n_mem--;
	}

	for(ll i = 1; i <= m; i++){
		ans /= i;
	}
	return ans;
}
int main(){

	cin>>N>>M>>Q;
	a_array.resize(Q);
	b_array.resize(Q);
	c_array.resize(Q);
	d_array.resize(Q);
	
	for(int i = 0; i < Q; i++){
		cin>>a_array[i]>>b_array[i]>>c_array[i]>>d_array[i];
	}
	rec(0,1,vector<int>());
	cout<<answer<<endl;
	return 0;

}



Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<string>
#include<numeric>
#include<set>
using namespace std;

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

  double ans = 0.0;
  double tmp = 0.0;
  for(int i = 0; i < n; i++){
    cin >> tmp;

    ans += 1.0 / tmp;
  }

  cout << (1.0 / ans) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> G[1111];
bool used[1111];
void dfs(int v){
  used[v]=1;
  for(int i=0;i<(int)G[v].size();i++) dfs(G[v][i]);
}
int main(){
  int n,m;
  while(cin>>n>>m,n||m){
    cin.ignore();
    for(int i=0;i<1111;i++) G[i].clear();
    string per[n];
    int depth[n],rG[n];
    rG[0]=-1;
    depth[0]=0;
    map<string,int> ms;
    for(int i=0;i<n;i++) getline(cin,per[i]);
    for(int i=0;i<n;i++){
      int k=0;
      while(per[i][k]==' ') k++;
      depth[i]=k;
      per[i]=per[i].substr(k,per[i].size()-k);
      ms[per[i]]=i;
    }
    int p=0;
    stack<int> st;
    for(int i=1;i<n;i++){
      G[p].push_back(i);
      rG[i]=p;
      //cout<<per[p]<<" "<<per[i]<<endl;
      if(i+1<n&&depth[i]<depth[i+1]){
	st.push(p);
	p=i;
      }
      if(i+1<n){
	while(depth[i+1]<=(int)st.size()){
	  p=st.top();st.pop();
	}	
      }
    }
    for(int i=0;i<m;i++){
      string st[6];
      for(int j=0;j<6;j++) cin>>st[j];
      st[5]=st[5].substr(0,st[5].size()-1);
      //cout<<st[0]<<" "<<st[3]<<" "<<st[5]<<endl;
      bool f=0;
      if(st[3]=="child"){
	int v=ms[st[5]];
	for(int j=0;j<(int)G[v].size();j++) f|=ms[st[0]]==G[v][j];
      }
      if(st[3]=="parent"){
	int v=ms[st[0]];
	if(~v) for(int j=0;j<(int)G[v].size();j++) f|=ms[st[5]]==G[v][j];
      }
      if(st[3]=="sibling"){
	int v=rG[ms[st[0]]];
	for(int j=0;j<(int)G[v].size();j++) f|=ms[st[5]]==G[v][j];
      }
      if(st[3]=="descendant"){
	memset(used,0,sizeof(used));
	dfs(ms[st[5]]);
	f=used[ms[st[0]]];
      }
      if(st[3]=="ancestor"){
	memset(used,0,sizeof(used));
	dfs(ms[st[0]]);
	f=used[ms[st[5]]];
      }
      cout<<(f?"True":"False")<<endl;
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
#define ALL(a)  (a).begin(),(a).end()
typedef long long ll;
using namespace std;

int main(){
    ll n, ans = 0;
    string s;
    cin >> n;
    unordered_map<string, int> mp; 

    for(int i = 0; i < n; i++){
        cin >> s;
        sort(ALL(s));

        ans += mp[s]++;
        
    }
    cout << ans << endl;
}



Measured memory_bytes: 10660
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(){
  int k; cin >> k;
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << a[k-1] << "\n";
}


Measured memory_bytes: 256
// Package main provides
//
// File:  b.go
// Author: ymiyamoto
//
// Created on Mon Aug  6 00:34:38 2018
//
package main

import (
	"fmt"
	"unicode"
)

var S string

func main() {
	fmt.Scan(&S)

	if S[0] == 'A' {
		for i := 1; i < len(S); i++ {
			if S[i] != 'C' && unicode.IsUpper([]rune(S)[i]) {
				fmt.Println("WA")
				return
			}
		}

		num := 0
		for i := 2; i < len(S)-1; i++ {
			if S[i] == 'C' {
				num++
			}
		}
		if num != 1 {
			fmt.Println("WA")
			return
		}

		fmt.Println("AC")
		return
	}

	fmt.Println("WA")
}


Measured memory_bytes: 640
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double pi = acos(-1);
const ll SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[200005], finv[200005], inv[200005];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
	for (auto &e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

//↑template↑





int main() {

	int a, b, k[105], now = 0, ans = 0;
	cin >> a >> b;
	for (int i = 0; i < a; ++i) {
		if (now <= b) { ++ans; }
		cin >> k[i];
		now += k[i];
	}
	if (now <= b) { ++ans; }

	cout << ans << endl;



}

Measured memory_bytes: 256
/*
英小文字からなる文字列 
s
 が与えられます。前から数えて奇数文字目だけ抜き出して作った文字列を出力してください。 
 ただし、文字列の先頭の文字を1文字目とします。
*/

#include <iostream>
#include <string>
using namespace std;



int main() {
    string s;
    cin >> s;
    //cout <<" s len " << s.length();
    string n;
    n = "";
    for (int i = 0; i < (s.length()+1)/2; ++i){
    	n += s[i*2];
    	// cout << i;
    }
    cout <<n;

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
vector<ll> tate;
vector<ll> yoko;
bool flag[50005];
ll len[50005];
ll rect[50005];

int main(void){
	for(ll i=1;i<=50000;i++){
		len[i]=len[i-1]+i;
	}
	for(ll i=1;i<=50000;i++){
		rect[i]=rect[i-1]+i*i;
	}
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		ll q,k;
		scanf("%lld%lld",&q,&k);
		k--;
		if(q==2){
			if(k<n)flag[k]=true;
		}
		if(q==0){
			if(k<len[n])tate.push_back(k);
		}
		if(q==1){
			if(k<n)yoko.push_back(k);
		}
	}
	sort(tate.begin(),tate.end());
	sort(yoko.begin(),yoko.end());
	ll dec=0;
	ll ans=0;
	ll cnt_ty=(ll)0;
	for(int i=0;i<tate.size();i++){
		int lv=upper_bound(len,len+n,tate[i])-len;
		int l2=lower_bound(yoko.begin(),yoko.end(),lv)-yoko.begin();
		dec+=lv;
		cnt_ty+=l2;
	}
	for(int i=0;i<yoko.size();i++){
		dec+=len[n]-len[yoko[i]];
	}
	ll po=0;
	int i_t=0,i_y=0;
	for(int i=0;i<n;i++){
		while(i_t<tate.size() && tate[i_t]<len[i]){
			int lv=upper_bound(len,len+n,tate[i_t])-len;
			int l2=lower_bound(yoko.begin(),yoko.end(),lv)-yoko.begin();
			dec-=lv;
			cnt_ty-=l2;
			i_t++;
		}
		while(i_y<yoko.size() && yoko[i_y]<i){
			i_y++;
		}
		dec-=(ll)(i)*i_y;
		if(flag[i])continue;
		ll val=rect[n]-rect[i];
		val-=dec;
		val+=cnt_ty;
		ans+=val;
		//printf("%lld %lld %lld\n",rect[n]-rect[i],dec,(ll)cnt_ty);
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 4332
program atcoder_contest_scheduling
  implicit none
  integer :: d, c(26) = 0, s(26, 365) = 0, t(365) = 0, u(365), m, n, p, i
  real(8) :: t1, t2
  call cpu_time(t1)
  call random_seed_clock()
  read(*,*) d
  read(*,*) c
  read(*,*) (s(:, i), i = 1, d)
  t = [(maxloc(s(:, i), 1), i = 1, d)]
  m = score()
  u = t
  do
    p = next_int(365)
    do i = 1, 26
      t(p) = i
      n = score()
      if (m < n) then
        m = n
        u(p) = i
      else
        t(p) = u(p)
      end if
      call cpu_time(t2)
      if (t2 - t1 > 1.975d0) goto 100
    end do
  end do
  100 write(*,'(i0)') (u(i), i = 1, d)
contains
  integer function score() result(res)
    integer :: last(26), i
    last = 0
    res = 0
    do i = 1, d
      last(t(i)) = i
      res = res + s(t(i), i) - sum(c * (i - last))
    end do
  end
  subroutine random_seed_clock()
    integer :: nseed, clock
    integer, allocatable :: seed(:)
    call system_clock(clock)
    call random_seed(size = nseed)
    allocate(seed(nseed))
    seed = clock
    call random_seed(put = seed)
    deallocate(seed)
  end
  integer function next_int(m) result(res)
    integer, intent(in)  :: m
    real(8) :: r
    call random_number(r)
    res = int(m * r) + 1
  end
end program atcoder_contest_scheduling

Measured memory_bytes: 3032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll p = 1e9 + 7;
#define DEBUG(x) cout << (x) << '\n'
#define fi first
#define se second

ll n, _2[MAXN], _8[MAXN], F[MAXN], Finv[MAXN], inv[MAXN];
void init(int n){
    F[0] = Finv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p%i] % p;
    for(int i = 1; i <= n; i++){
        F[i] = F[i-1] * i % p;
        Finv[i] = Finv[i-1] * inv[i] % p;
    }
}
ll C(int n, int m){
    return F[n] * Finv[n-m] % p * Finv[m] % p;
}
void run(){
    cin >> n, init(n);
    _2[0] = _8[0] = 1;
    for(int i = 1; i <= n; i++){
        _2[i] = _2[i-1] * 2 % p;
        _8[i] = _8[i-1] * 8 % p;
    }
    if(n == 1) DEBUG(0);
    else if(n == 2) DEBUG(2);
    else{
        ll ans = 0;
        for(int i = 2; i <= n; i++){
            ll k = (_2[i] + p - 2) % p * C(n, i) % p * _8[n-i] % p;
            ans = (ans + k) % p;
        }
        DEBUG(ans);
    }
}
int main(){
#ifdef Irene
    freopen("in.txt", "r", stdin);
#endif // Irene
    ios_base::sync_with_stdio(false);

    run(); return 0;
}


Measured memory_bytes: 42600
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back()
#define INF 1000000000

using namespace std;

const int mod = 1e9+7;

int main(){
	
	int vec[5];
	int res;
	for(int i = 0; i< 5;i++){
		cin>>vec[i];
		if(vec[i] == 0) res = i+1;
	}
	cout<< res<<endl;

	return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define N 140000
#define lg2(x) (31 - __builtin_clz(x))
using std::reverse;

typedef long long ll;
const ll mod = 998244353, root = 31;

int A, B, n;
char scx[2][N], *p, *q;
int z[N], y[N], buf1[N], buf2[N];
int fact[N], finv[N];

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init(){
	int i;
	for(*fact = i = 1; i < N; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
	--i; finv[i] = PowerMod(fact[i], mod - 2);
	for(; i; --i) finv[i - 1] = (ll)finv[i] * i % mod;
}

namespace Poly {
	int l, n; ll iv;
	int x[N], y[N], buf[N];
	int rev[N];

	void NTT_init(int length) {
		n = 1 << (l = length); iv = PowerMod(n, mod - 2);
		ll g = PowerMod(root, 1 << 23 - l);
		x[0] = 1; rev[0] = 0;
		for (int i = 1; i < n; ++i) {
			x[i] = (ll)x[i - 1] * g % mod;
			rev[i] = (i & 1 ? rev[i - 1] | 1 << (l - 1) : rev[i >> 1] >> 1);
		}
	}

	void DNTT(int *d, int *t){
		int i, *j, *k, len = 1, delta = n, R;
		for (i = 0; i < n; ++i) t[rev[i]] = d[i];
		for (i = 0; i < l; ++i) {
			delta >>= 1;
			for (k = x, j = y; j < y + len; k += delta, ++j) *j = *k;
			for (j = t; j < t + n; j += len << 1)
				for (k = j; k < j + len; ++k){
					R = (ll)y[k - j] * k[len] % mod;
					k[len] = (*k - R < 0 ? *k - R + mod : *k - R);
					*k = (*k + R >= mod ? *k + R - mod : *k + R);
				}
			len <<= 1;
		}
	}
}

using Poly::DNTT;

void PolyPowerMod(int n, int k) {
	Poly::NTT_init(lg2(k) + 2); int n0 = Poly::n, i;
	for (; n; n >>= 1) {
		if (n & 1) {
			DNTT(y, buf1); DNTT(z, buf2);
			for (i = 0; i < n0; ++i) buf1[i] = (ll)buf1[i] * buf2[i] % mod;
			DNTT(buf1, y); reverse(y + 1, y + n0);
			for (i = 0; i <= k; ++i) y[i] = y[i] * Poly::iv % mod;
			for (; i < n0; ++i) y[i] = 0;
		}
		DNTT(z, buf1);
		for (i = 0; i < n0; ++i) buf1[i] = (ll)buf1[i] * buf1[i] % mod;
		DNTT(buf1, z); reverse(z + 1, z + n0);
		for (i = 0; i <= k; ++i) z[i] = z[i] * Poly::iv % mod;
		for (; i < n0; ++i) z[i] = 0;
	}
}

int main() {
	int i; ll ans = 0;
	scanf("%s%s", scx[0], scx[1]);
	for (p = scx[0], q = scx[1]; *p; ++p, ++q) A += *p & *q & 1, B += *p & ~*q & 1;
	n = A + B; init();
	for (i = 0; i <= A; ++i) z[i] = finv[i + 1];
	*y = 1; PolyPowerMod(B, A);
	for (i = 0; i <= A; ++i) ans += y[i];
	ans = ans % mod * fact[A] % mod * fact[B] % mod * fact[A + B] % mod;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2944
#include<stdio.h>
int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


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

using namespace std;

typedef long long int li;
typedef vector<li> vi;
typedef pair<li,li> pi;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define f(i,l,r) for(li i=l;i<=r;++i)
#define fr(i,l,r) for(li i=l;i>=r;--i)
#define u_map unordered_map

li fastpow(li base,li exp,li M) 
{
    li res=1;
    while(exp>0) {
        if(exp&1)
            res=(res*base)%M;

        base=(base*base)%M;
        exp>>=1;
    }
    return res;
}
    
int main()
{    
    ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        li n;

        cin>>n;

        li a[n];

        for(li i=0;i<n;i++)
            cin>>a[i];

        sort(a,a+n);

        li cnt=0;

        f(i,0,n-1)
        {
            li k=i+2;

            f(j,i+1,n-1)
            {
                while(k<n && a[i]+a[j]>a[k])
                    k++;

                if(k>j)
                    cnt+=(k-j-1);
            }
        }

        cout<<cnt;

    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
from bisect import bisect_left, bisect_right

def solve():
    N = II()
    A = sorted(LI())
    B = LI()
    C = sorted(LI())

    # print(A)
    # print(B)
    # print(C)
    ans = 0
    for b in B:
        # a < b
        i = bisect_left(A, b)

        # b < c
        j = N - bisect_right(C, b)
        # print(b, i, j)
        ans += i * j
    print(ans)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 29208
import java.util.*;


import java.io.*;

class Main {

  public static void main(String[] args) throws Exception{
    try (Scanner sc = new Scanner(System.in)){
      int N = sc.nextInt();
      int T = sc.nextInt();
      int A = sc.nextInt();
      double min = Double.MAX_VALUE;
      int tmp = 0;
      for (int i = 0; i < N; i++) {
        int x = sc.nextInt();
        double tem = T - x * 0.006;
        if (min > Math.abs(tem - A)) {
          min = Math.abs(tem - A);
          tmp = i+1;
        }
      }
      System.out.println(tmp);
    }
  }
}


Measured memory_bytes: 24020
#include <iostream>


using namespace std;


int main()
{
    bool colours[8];
    for (int i = 0; i < 8; i++)
        colours[i] = false;

    int N;
    int free = 0;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int r;
        cin >> r;
        int index = r / 400;

        if (index < 8)
            colours[index] = true;
        else
            free++;
    }

    int b = 0;
    for (int i = 0; i < 8; i++) {
        if (colours[i]) {
            b++;
        }
    }

    cout << max(1, b) << " " << b + free << endl;
}


Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))

dp = [float('inf')]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
if n > 2:
    for i in range(2,n):
        dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))
print(dp[n-1])


Measured memory_bytes: 13980
package main

import "fmt"

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	s := make([][]int, M)
	var k int
	for i := 0; i < M; i++ {
		fmt.Scan(&k)
		s[i] = make([]int, k)
		for j := 0; j < k; j++ {
			fmt.Scan(&s[i][j])
			s[i][j]--
		}
	}

	p := make([]int, M)
	for i := 0; i < M; i++ {
		fmt.Scan(&p[i])
	}

	ans := 0
	for b := 0; b < 1<<uint(N); b++ {
		ok := true
		for i := 0; i < M; i++ {
			cnt := 0
			for _, v := range s[i] {
				if (b >> uint(v) & 1) == 1 {
					cnt++
				}
			}
			if cnt%2 != p[i] {
				ok = false
				break
			}
		}
		if ok {
			ans++
		}
	}
	fmt.Println(ans)
}


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

using ll = long long;

const int N = 2e5 + 10;

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

    int p;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        if (x == 0)
            p = i;
    }

    cout << p + 1;
}


Measured memory_bytes: 3648
import math

N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]


def check(x):
    cnt = 0
    for h in H:
        if h <= B * x:
            continue
        else:
            cnt += math.ceil((h - B * x) / (A - B))

    if cnt <= x:
        return True
    else:
        return False


lb = 0
ub = 10**15
while ub - lb > 1:
    mid = (lb + ub) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

ans = ub

print(ans)


Measured memory_bytes: 50392
#include <stdio.h>
#include <math.h>

int main(void){
    char text[100];
    double x, y, z;
    int angle;
    double radian;
    double s, l, h;
    fgets(text, 100, stdin);
    sscanf(text, "%lf %lf %d", &x, &y, &angle);
    
    radian = angle * (M_PI / 180);
    h = sin(radian) * y;
    s = x * h / 2;
    z = x*x + y*y - 2 * x * y * cos(radian);
    z = sqrt(z);
    l = x + y + z;
    printf("%lf\n", s);
    printf("%lf\n", l);
    printf("%lf\n", h);
    return 0;
}



Measured memory_bytes: 2052
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
using max_priority_queue = priority_queue<T>;
template <class T>
using min_priority_queue = priority_queue<T, std::vector<T>, std::greater<T>>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N, K;
const int MAX_N = 110;
const int MAX_K = 100010;
vector<int> A;
ll dp[MAX_N][MAX_K];

int main()
{
    cin >> N >> K;
    A.resize(N);
    for (auto &val : A)
    {
        cin >> val;
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int n = 0; n < N; n++)
    {
        for (int k = 0; k <= K; k++)
        {

            dp[n + 1][k] += dp[n][k];
            dp[n + 1][min(k + A[n], K) + 1] -= dp[n][k];
            dp[n + 1][min(k + A[n], K) + 1] += MOD;
            dp[n + 1][min(k + A[n], K) + 1] %= MOD;

            // for (int i = 0; i <= A[n]; i++)
            // {
            //     if (i + k > K)
            //     {
            //         break;
            //     }
            //     dp[n + 1][i + k] = max(0, dp[n + 1][i + k]);
            //     dp[n + 1][i + k] += dp[n][k];
            //     dp[n + 1][i + k] %= MOD;
            // }
        }
        for (int i = 0; i < MAX_K; i++)
        {
            dp[n + 1][i + 1] += dp[n + 1][i];
            dp[n + 1][i + 1] %= MOD;
        }
    }
    cout << dp[N][K] << endl;
    return 0;
}


Measured memory_bytes: 86144
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    string s;
    cin >> s;
    int n = s.length();
    if (s[0] == s[n - 1]) {
        if (n % 2 == 0)
            cout << "First"
                 << "\n";
        else
            cout << "Second"
                 << "\n";
    } else {
        if (n % 2 == 0)
            cout << "Second"
                 << "\n";
        else
            cout << "First"
                 << "\n";
    }
    return 0;
}

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

int main(){
  int n, ans = 0;
  cin >> n;
  while(cin >> n){
    if(n%2)
      ans++;
  }
  if(ans%2)
    cout << "NO" << endl;
  else cout << "YES" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
  char s[101];
  scanf("%s",s);
  for(int i=0;i<(strlen(s)+1)/2;i++){
    if(s[2*i]!='R' && s[2*i]!='U' && s[2*i]!= 'D'){
      puts("No");
      exit(0);
    }}
  for(int j=0;j<strlen(s)/2;j++){
    if(s[2*j+1]!='L' && s[2*j+1]!='U' && s[2*j+1]!='D'){
      puts("No");
      exit(0);
    }
  }
  puts("Yes");
  return 0;
}

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



signed main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    cout << fixed << setprecision(20);

    ll n,k,q;
    cin>>n>>k>>q;
    ll cnt[n]={};
    for(int i=0;i<q;i++){
        int a;
        cin>>a;
        a--;
        cnt[a]++;
    }
    for(int i=0;i<n;i++){
        ll t = q - cnt[i];
        if(t<k){
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
map<int, int> m;
int a[maxn];
int n, t1, t2; 
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) 
	{
		scanf("%d", &a[i]);
		m[a[i]]++;
	}
	for(auto v : m)
	{
		if(v.second % 2) ++t1;
		else ++t2;
	}
	printf("%d\n", t1 + t2 - (t2 & 1));
	return 0;
}

Measured memory_bytes: 5376
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String[] in = s.nextLine().split(" ");
        int a = Integer.parseInt(in[0]);
        int b = Integer.parseInt(in[1]);
        int t = Integer.parseInt(in[2]);
        int r=0;
        for(int i=1;i<=t;i++){
            if(i % a == 0){
                r++;
            }
        }
        System.out.println(r*b);
    }
}

Measured memory_bytes: 23764
#include<stdio.h>
int main()
{
    int a, b;
    scanf("%d %d",&a, &b);
    if(a>12){
        printf("%d",b);
    }
    else if (a<6){
     printf("0");
    }
    else{
        printf("%d",b/2);
    }
    }   

    

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<string>
#define MAXN 1000
using namespace std;
int main(){
	 int n;
	 cin>>n;
	 int ans;
	 for(int i=1;i<=n;i+=2){
	 	int sum=0;
	 	for(int j=1;j<=i;j++){
	 		if(i%j==0){
	 			sum++;
			 }
		 }
		 if(sum==8){
		 	ans++;
		 }
	 }
	 cout<<ans;
}

Measured memory_bytes: 256
//c++ テンプレ
#include<bits/stdc++.h>
using namespace std;

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

llint n,m;

void solve(){
    cin >> n >> m;
    vector<bool>f(n+1,true);
    for(int i=0;i<m;i++){
        int a;
        cin >> a;
        f[a]=false;
    }
    vector<llint>dp(n+1,0);
    dp[0]=1;
    for(llint p=0;p<n;p++){
        for(llint next=p+1;next<=min(n,p+2);next++){
            if(f[next]){
                dp[next]+=dp[p];
                dp[next]%=mod;
            }
        }
    }
    cout << dp[n] << endl;

}  

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define REP(i, n) for(int i=0;i<(n);++i)
#define MOD 1e9+7;
typedef long long ll;

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

	int n; ll k, a[100000];
	cin >> n >> k;
	REP(i, n) cin >> a[i];

	int cnt[40];	memset(cnt, 0, sizeof(cnt));

	REP(i, n){
		ll tmp = a[i]; int index = 0;
		while(tmp != 0){
			if(tmp % 2) cnt[index]++;
			tmp/=2; index++;
		}
	}

	ll ans = -1, tmpk = k+1;
	REP(i, 40){
		if(tmpk % 2){
			ll tmp = 1, MAX = 0, kk = k+1;
			REP(j, 40){
				if(i > j) MAX += tmp * (ll)max(cnt[j], n-cnt[j]);
				else if(i == j) MAX += tmp * (ll)(cnt[j]);
				else {
					if(kk % 2) MAX += tmp * (ll)(n-cnt[j]);
					else MAX += tmp * (ll)(cnt[j]);
				}
				kk /= 2; tmp *= 2;
			}
			if(MAX > ans) ans = MAX;
		}
		tmpk /= 2;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
 
int main(){
int n,x;
int min = 0;
int all = 0;
scanf("%d %d\n",&n,&x);
int j = n;
int m[j];
for(n = 0;n < j;n++){
scanf("%d\n",&m[n]);
 
all += m[n];
 
if(min == 0){
	min = m[n];
}
if(min > m[n]){
	min = m[n];
}}
printf("%d\n",n + (x - all) / min);
return 0;
}

Measured memory_bytes: 128
public class Main {
	public static void main(String[] args){
		java.util.Scanner scan = new java.util.Scanner(System.in);
		while(true){
			String x = scan.nextLine();
			if("0".equals(x)){
				break;
			}
			int sum = 0;
			for(char v : x.toCharArray()){
				sum += Integer.parseInt(String.valueOf(v));
			}
			System.out.println(sum);
		}
	}

}

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

int main(){
  int a, b;
  cin >> a >> b;
  if(a  == 1) a = 14;
  if(b == 1)  b = 14;
  if(a > b) cout << "Alice" << endl;
  else if(a < b)  cout << "Bob" << endl;
  else  cout << "Draw" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n  = sc.nextInt();
        int[] array = new int[n];
        int min = 0;
        int temp = 0;
        int swapCount = 0;
        int j = 0;
        for(int i=0;i<n;i++){
            array[i] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            min = i;
            for(j=i+1;j<n;j++){
                if(array[j] < array[min]){
                    min = j;
                }
             }
            if(min != i){
                swapCount++;
                temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
        }
        for(int i=0;i<n;i++){
            System.out.print(array[i]);
            if(i<n-1){
                System.out.print(" ");
            }
        }
        System.out.println("");
        System.out.println(swapCount);
        sc.close();
    }
}


Measured memory_bytes: 26304
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>

#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

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

int main() {
    uint64_t N;
    cin >> N;
    string ret;
    while(N > 26) {
        int mod = N % 26;
        N /= 26;
        if(mod == 0) {
            ret += 'z';
            N-=1;
        }
        else
            ret += 'a' + mod - 1;
    }
    ret += 'a' + N - 1;
    reverse(ret.begin(), ret.end());
    cout << ret << endl;
#if 0
    for(int i=0; i<26; ++i) {
        cout << (char)('a' + i) << endl;
    }
#endif

    return 0;
}


Measured memory_bytes: 3152