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

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin>>h[i];
    }
    for (int i = 1; i < n; ++i) {
        if(h[i]==h[i-1])continue;
        if(h[i]>h[i-1]){
            --h[i];
            continue;
        }

        --h[i];
        if (h[i]<h[i-1]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<map>
using namespace std;

#define ll long long

const int mod=1e9+7;
map<ll,ll> dp;

ll dfs(ll x)
{
    if(dp[x]) return dp[x];
    return dp[x]=(dfs(x/2)+dfs((x-1)/2)+dfs((x-2)/2))%mod;
}

int main()
{
    ll n;
    scanf("%lld",&n);
    dp[0]=1ll;dp[1]=2ll;
    printf("%lld",dfs(n));
    return 0;
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

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

const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// head

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

    int n;
    cin >> n;

    vll a(n);
    rep(i,0,n) cin >> a[i];
    sort(all(a));
    reverse(all(a));

    ll sum = 0;
    sum += a[0];
    int cnt = n - 2;
    int i = 1;
    while(i < n && cnt > 0) {
        sum += a[i];
        cnt--;
        if(cnt > 0) {
            sum += a[i];
            cnt--;
        }
        i++;
    }   
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 4800
S = input()

if S == "hi":
    print("Yes")
    exit()
if S == "hihi":
    print("Yes")
    exit()
if S == "hihihi":
    print("Yes")
    exit()
if S == "hihihihi":
    print("Yes")
    exit()
if S == "hihihihihi":
    print("Yes")
    exit()
    
print("No")

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

const int MAXN = 2e7 + 5;
const int MOD = 1e9 + 7;

int H, W, K;

void load() {
	scanf("%d%d%d", &H, &W, &K);
}

inline int add(int x, int y) {
	x += y;
	if (x >= MOD)
		x -= MOD;
	return x;
}

inline int mul(int x, int y) {
	return (long long)x * y % MOD;
}

int range(int lo, int hi) {
	int res = 1;
	for (int i = lo + 1; i <= hi; i++)
		res = mul(res, i);
	return res;
}

int solve() {
	int tot = mul(mul(K, K + 3), (MOD + 1) / 2);
	int sum = mul(mul(mul(K, K - 1), K + 1), (MOD + 1) / 3);
	return add(mul(tot, range(H + W - K, H + W)), mul(sum, mul(mul(H, W), range(H + W - K, H + W - 2))));
}

int main() {
	load();
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
#define mp make_pair
const int maxn=2e6+1;
int r1,c1,r2,c2;
ll fac[maxn+5];
ll inv[maxn+5];
ll C(int n,int m)
{
    //cout<<"C"<<n<<" "<<m<<"   :   "<<fac[n]*inv[m]%mod*inv[n-m]%mod<<endl;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int cal(int l,int r,int x)
{
    return (C(r+1,x+1)-C(l,x+1))%mod;
}
int main()
{

    ios::sync_with_stdio(false);cin.tie(0);
    fac[0]=1;
    for(int i=1;i<=maxn;++i) fac[i]=fac[i-1]*i%mod;
    inv[0]=inv[1]=1;
    for(int i=2;i<=maxn;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=maxn;++i) inv[i]=inv[i-1]*inv[i]%mod;
    cin>>r1>>c1>>r2>>c2;
    ll ans=0;
    for(int i=r1;i<=r2;++i)
    {
        ans+=cal(i+c1,i+c2,i);
        ans%=mod;
    }
    if(ans<0) ans+=mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

ll dp[100200];
void solve(long long N, long long K, std::vector<long long> h)
{
    for (int i = 0; i <= N; i++)
    {
        dp[i] = INF;
    }
    dp[1] = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= K; j++)
        {
            dp[i + j] = min(dp[i] + abs(h[i - 1] - h[i + j - 1]), dp[i + j]);
        }
    }

    cout << dp[N] << endl;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> h(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &h[i]);
    }
    solve(N, K, std::move(h));
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	double ans[n+1][n+1];
	ans[0][0]=1;
	for(int i=1;i<=n;i++){
		double p;
		cin>>p;
		ans[i][0]=ans[i-1][0]*(1-p);
		for(int h=1;h<=i;h++){
			ans[i][h]=(ans[i-1][h]*(1-p))+(ans[i-1][h-1]*p);
		}
	}
	double res=0.0;
	for(int i=n/2+1;i<=n;i++){
		res+=ans[n][i];
	}
	cout<<setprecision(10)<<res<<endl;
}

Measured memory_bytes: 70016
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextLong()
    var i = 1L
    var min = Long.MAX_VALUE
    while (i * i <= n) {
        if (n % i == 0L) {
            val j = n / i
            min = Math.min(min, i + j - 2)
        }
        i++
    }
    println(min)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 31392
package main

import "fmt"

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	for i := 0; i <= x; i++ {
		if 4*i+2*(x-i) == y {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}


Measured memory_bytes: 1752
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
typedef long long LL;

int int_vector_find(std::vector<int> vec, int num) {
	auto itr = std::find(vec.begin(), vec.end(), num);
	int index = std::distance(vec.begin(), itr);

	if (index != vec.size()) {
		return 1;
	}
	else {
		return 0;
	}
}

int main() {
	int n;
	std::cin >> n;
	std::vector<int> vec;

	for (int i = 0; i < n; ++i) {
		int a;
		std::cin >> a;
		vec.push_back(a);
	}

	std::sort(vec.begin(),vec.end());

	int temp = 0;

	for (int i = 0; i < vec.size() - 1; ++i) {
		temp += vec[i];
	}

	if (vec[vec.size()-1] < temp) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
}

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


int main() {
    int64_t x, y, z;
    cin >> x >> y >> z;
    int64_t c = 0;
    x -= z;
    while (x >= y+z) {
        c++;
        x -= (y+z);
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007;



int main() {
    ll X;
    cin>>X;
    vector<ll> five(1000),five2(1000);
    for(ll i=0;i<1000;i++){
        five.at(i)=i*i*i*i*i;
    }
    for(ll i=0;i<1000;i++){
        five2.at(i)+=five.at(i);
    }
    for(ll i=0;i<1000;i++){
        rep(j,1000){
            if(five.at(i)==five2.at(j)+X){
                cout<<i<<" "<<j<<endl;
                return 0;
            }
            if(five.at(i)+five2.at(j)==X){
                cout<<i<<" "<<-j<<endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3648
#include <atcoder/all>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
#include <vector>

using namespace std;
using ll = long long;
using P = pair<int, int>;

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& v) {
    os << "(" << v.first << ", " << v.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (int i = 0; i < v.size(); i++) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}

int main()
{
    int n, m;
    cin >> n >> m;
    atcoder::dsu d(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        d.merge(a, b);
    }
    cout << d.groups().size() - 1 << endl;
    return 0;
}

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

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CLEAR(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

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

const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


struct Edge
{
	int a, b, cost;
	Edge(int a, int b, int cost)
		: a(a), b(b), cost(cost) {}
};
bool operator<(const Edge& a, const Edge& b)
{
	return a.cost < b.cost;
}

class UnionFind
{
private:
	int* parent;

public:
	UnionFind(int n)
	{
		parent = new int[n];
		for (int i = 0; i < n; ++i)
			parent[i] = i;
	}
	int root(int v)
	{
		if (parent[v] == v)
			return v;
		else
			return parent[v] = root(parent[v]);
	}
	void unite(int a, int b)
	{
		parent[root(b)] = root(a);
	}
	bool same(int a, int b)
	{
		return root(a) == root(b);
	}
};

//template <class T>
//class UnionFind
//{
//public:
//	UnionFind(int n)
//		: n(n)
//	{
//		parent = new T[n];
//		rank = new T[n];
//		for (int i = 0; i < n; ++i)
//		{
//			parent[i] = i;
//			rank[i] = 0;
//		}
//	}
//
//	void unite(T a, T b)
//	{
//		T root_a = root(a);
//		T root_b = root(b);
//		if (root_a == root_b)
//			return;
//
//		if (rank[root_a] < rank[root_b])
//			parent[root_a] = root_b;
//		else if (rank[root_a] > rank[root_b])
//			parent[root_b] = root_a;
//		else
//		{
//			parent[root_a] = root_b;
//			++rank[root_a];
//		}
//	}
//
//	bool same(T a, T b)
//	{
//		return root(a) == root(b);
//	}
//
//private:
//	T* parent;
//	T* rank;
//	int n;
//
//	T root(T e)
//	{
//		if (parent[e] == e)
//			return e;
//		else
//			return parent[e] = root(parent[e]);
//	}
//};
int main()
{
	int n, m;
	while (cin >> n >> m, n)
	{
		vector<Edge> e;
		rep (i, m)
		{
			int a, b, w;
			cin >> a >> b >> w;
			--a, --b;
			e.push_back(Edge(a, b, w));
		}
		sort(all(e));

		const int INF = 1 << 26;
		int res = INF;
		for (int i = 0; i < e.size(); ++i)
		{
			int use = 0;
			UnionFind u(n);
			for (int j = i; j < e.size() && e[j].cost - e[i].cost < res; ++j)
			{
				if (!u.same(e[j].a, e[j].b))
				{
					u.unite(e[j].a, e[j].b);
					if (++use == n - 1)
					{
						res = e[j].cost - e[i].cost;
						break;
					}
				}
			}
		}

		if (res == INF)
			res = -1;
		cout << res << endl;
	}
}

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

int main(){
  int n;
  cin >> n;
  vector<int> h(20,0);
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  int ans = 1;
  int check = 1;
  for(int i=1; i<n; i++){
    for(int j=0; j<i; j++){
      if(h[j] > h[i]){
        check = 0;
        break;
      }
    }
    if(check){
      ans++;
    }
    check = 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[505],b[505],n,MOD;
vector<pair<pair<int,int>,int> > s;
int f[505][505];
int solve(int tp){
//	if(tp!=10) return 0;
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int i=1;i<=s.size();++i){
		int pos=s[i-1].second;
		for(int x=0;x<=n+n;++x){
			if(pos<n){
				if(x>0){
					f[i][x]=(f[i][x]+1ll*f[i-1][x-1]
						*max(0,b[pos]-(tp+x-1)))%MOD;
//					if(f[i][x]!=0) printf("<%d>",max(0,b[pos]-(tp+x-1)));
				}
				if(i-x>0){
					f[i][x]=(f[i][x]+MOD-1ll*f[i-1][x]
						*max(0,a[pos]-(i-x-1))%MOD)%MOD;
				}
			}else{
				if(i-x>0){
					f[i][x]=(f[i][x]+1ll*f[i-1][x]
						*max(0,b[pos]-(i-x-1)))%MOD;
//					if(f[i][x]!=0) printf("<%d>",max(0,b[pos]-(i-x-1)));
				}
			}
//			if(tp==10&&f[i][x]!=0) printf("(%d %d %d)",i,x,f[i][x]);
		}
	}
	return f[(int)s.size()][n+n-tp];
}
int main(){
	scanf("%d%d",&n,&MOD);
	for(int i=0;i<n+n;++i){
		a[i]=1e9,b[i]=-1e9;
		for(int j=0;j<n+n;++j)
			if(i*i+j*j>=n*n&&i*i+j*j<=(n+n)*(n+n)){
				a[i]=min(a[i],j);
				b[i]=max(b[i],j+1);
			}
//		printf("<%d %d>",a[i],b[i]);
		if(i<n) s.push_back(make_pair(make_pair(a[i],b[i]),i));
		else s.push_back(make_pair(make_pair(b[i],a[i]),i));
	}
	sort(s.begin(),s.end());
//	for(auto x:s) printf("(%d %d)",x.first,x.second);
	int ans=0;
	for(int x=n;x<=n+n;++x){
		int key=solve(x);
		ans=(ans+key)%MOD;
/*		if(key!=0){
			printf("|%d %d|",x,key);
		}
*/	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int l[N],r[N],v[N];
vector<int> path[N];
bool bo;
void dfs1(int o,int fa)
{
	if(v[o]>=0) l[o]=r[o]=v[o];
	for(int i=0;i<(int)path[o].size();i++)
	{
		int to=path[o][i];
		if(to==fa) continue;
		dfs1(to,o);
		
		
		
		if(l[to]==INT_MIN) continue;
		
		//cout<<"#"<<o<<" "<<to<<" "<<l[o]<<" "<<r[o]<<" "<<l[to]<<" "<<r[to]<<endl;
		
		if(l[o]==INT_MIN) l[o]=l[to]-1,r[o]=r[to]+1;
		else 
		{
			if(r[o]%2!=(r[to]+1)%2) bo=true;
			l[o]=max(l[o],l[to]-1);
			r[o]=min(r[o],r[to]+1);
		}
		if(l[o]>r[o]) bo=true;
	}
}
void dfs2(int o,int fa)
{
	for(int i=0;i<(int)path[o].size();i++)
	{
		int to=path[o][i];
		if(to==fa) continue;
		if(v[o]-1>=l[to]) v[to]=v[o]-1;
		else v[to]=v[o]+1;
		dfs2(to,o);
	}
}
int main()
{
	memset(v,-1,sizeof(v));
	int n,k,a,b;
	scanf("%d",&n);
	for(int i=1;i<n;i++) 
	{
		scanf("%d%d",&a,&b);
		path[a].push_back(b);
		path[b].push_back(a);
		l[i]=INT_MIN;
		r[i]=INT_MAX;
	}
	l[n]=INT_MIN;
	r[n]=INT_MAX;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&a,&b);
		v[a]=b;
	}
	dfs1(1,0);
	if(bo) {puts("No");return 0;}
	puts("Yes");
	v[1]=l[1];
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d\n",v[i]);
	return 0;
}

Measured memory_bytes: 15360
N = int(input())
A = [0]*N
B = [0]*N
tasks = [list(map(int,input().split())) for i in range(N)]
tasks.sort(key = lambda x:x[1])
can = True
S = 0
for i in range(N):
    S += tasks[i][0]
    if tasks[i][1] < S:
        can = False
if can:print('Yes')
else:print('No')




Measured memory_bytes: 56788
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

int main() {
  size_t N;
  scanf("%zu", &N);

  char buf[1024];
  scanf("%s", buf);
  std::string s = buf;

  std::vector<int> f(10);
  for (size_t i = 'a'; i <= 'z'; ++i) {
    ++f[std::count(s.begin(), s.end(), i)];
  }

  size_t res = -1;
  if (f[1] >= 1) {
    // a+b+c+d
    res += 2*f[1];
  }
  for (size_t i = 2; i <= 9; ++i) {
    if (f[i] == 1) {
      // A*a
      res += 4;
    } else if (f[i] > 1) {
      // A*(a+b)
      res += 4 + 2*f[i];
    }
  }

  printf("%zu\n", res);
}



Measured memory_bytes: 2876
#include <iostream>

using namespace std;

void call(int n) {
    int i;
    for (i=1; i<n+1; i++){
        int x=i;
        if ( x % 3 == 0 ){
            cout << " " << i;
        }else if(x % 10 == 3){
            cout << " " << i;
        } else{
            while (x) {
                x /= 10;
                if (x%10==3) {
                    cout <<" " << i;
                    break;
                }
                
            }
        }
    }
    cout << endl;
}


int main() {
    int n;
    cin >> n;
    call(n);
    return 0;
}

Measured memory_bytes: 1160
import copy

def bubble_sort(C):
    for i in range(len(C)):
        for j in range(len(C)-1, i, -1):
            if int(C[j][1]) < int(C[j-1][1]):
                C[j], C[j-1] = C[j-1], C[j]
    return C

def selection_sort(C):
    for i in range(len(C)):
        minj = i
        for j in range(i, len(C)):
            if int(C[minj][1]) > int(C[j][1]):
                minj = j
        C[minj], C[i], = C[i], C[minj]
    return C

if __name__ == '__main__':
    n = int(input())
    B = input().split()
    C_bubble = bubble_sort(copy.deepcopy(B))
    print(*C_bubble)
    print('Stable')
    C_selection = selection_sort(copy.deepcopy(B))
    print(*C_selection)
    if C_bubble == C_selection:
        print('Stable')
    else:
        print('Not stable')



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

using namespace std;

#define inf 1<<30
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> P;

llong n, x;
llong many[51] = {}, paty[51] = {};

llong solve(llong eat, int level){
	if(eat == 0) return 0;
	if(level < 0) return 0;
	if(eat == many[level]) return paty[level];

	llong ret = 0;

	if(eat <= many[level]/2){
		eat--;
	}else{
		eat -= many[level]/2+1;
		ret = paty[level-1]+1;
	}

	return ret + solve(eat, level-1);
}

int main(){
	many[0] = 1, paty[0] = 1;
	cin >> n >> x;
	for(int i = 1; i <= n; i++){
		many[i] = many[i-1]*2+3;
		paty[i] = paty[i-1]*2+1;
	}

	cout << solve(x, n) << endl;

	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<ll>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n;
    cin >> n;
    ll k;
    cin >> k;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }

    int num = 64-__builtin_clzll(k);
    if(k == 0) {
        num = 0;
    }

    ll K = 0;
    bool ch = true;

    rep(i_, num) {
        int i = num-1-i_;
        int z = 0, o = 0;
        rep(j, n) {
            if((a[j]>>i)&1) {
                ++o;
            } else {
                ++z;
            }
        }
        if(ch) {
            if((k>>i)&1) {
                if(z<=o) {
                    ch = false;
                }
            } else {
                z -= 1000000;
            }
        }

        K += (1LL<<i)*(o<z);
    }


    ll ans = 0LL;

    rep(i, n) {
        ans += K^a[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	d = [int(raw_input()) for i in range(n)]
	r = [d.count(i) for i in range(R)]
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans

Measured memory_bytes: 4468
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String s = scanner.next();
		String sub = s.substring(2,s.length()-1);

		if (s.startsWith("A") && sub.contains("C") && sub.indexOf('C')==sub.lastIndexOf('C')){
			int idxC = sub.indexOf('C')+2;
			for (int i=1;i<s.length(); i++){
				if (i==idxC) continue;
				if (Character.isUpperCase(s.charAt(i))) {
					System.out.println("WA");
					System.exit(0);
				}
			}
			System.out.println("AC");
		}else {
			System.out.println("WA");
		}
	}
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<string> str(H);

  for(int i=0 ; i<H ; i++)
    cin >> str.at(i);
  
  for(int i=0 ; i<W+2 ; i++)
    cout << '#';
  cout << endl;

  for(int i=0 ; i<H ; i++)
    cout << '#' << str.at(i) << '#' <<endl;

  for(int i=0 ; i<W+2 ; i++)
    cout << '#';
  cout << endl;
}


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

int main(){
  int H, W;
  char X[100][100];

  while(true){
  cin >> H >> W;
  if(H==0&&W==0) break;
  for(int i=0; i<H; i++){
    cin >> X[i];
  }

  char used[100][100];
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      used[i][j] = 0;
    }
  }

  int dx[] = {-1,0,1,0};
  int dy[] = {0,1,0,-1};
  int res = 0;
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      if(used[i][j]) continue;
      res++;
      used[i][j] = 1;
      queue<pair<int, int> > que;
      que.push(make_pair(i,j));
      while(!que.empty()){
        int k = que.front().first;
        int l = que.front().second;
        que.pop();
        for(int n=0; n<4; n++){
          if(0<=k+dx[n]&&k+dx[n]<H&&
             0<=l+dy[n]&&l+dy[n]<W&&
             X[k+dx[n]][l+dy[n]] == X[i][j] && !used[k+dx[n]][l+dy[n]]){
            used[k+dx[n]][l+dy[n]] = 1;
            que.push(make_pair(k+dx[n],l+dy[n]));
            //cout << i << ' ' << j << ' ' << k+dx[n] << ' ' << l+dy[n] << endl;
          }
        }
      }
    }
  }

  cout << res << endl;
  }

  return 0;
}

Measured memory_bytes: 3156
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=copy.copy(A)
ans=[]

for i in range(2**(N-1)):
    L=[0]*(N-1)
    total=0
    count=0
    for j in range(N-1):
        if ((i>>j)&1):
            L[j]=1
            count+=1
    if count>=K-1:
        A=copy.copy(B)
        for m in range(N-1):
            
            if L[m]==1:
                height=max(max(A[:m+1])+1,A[m+1])
                total+=height-A[m+1]
                A[m+1]=height
                
        ans.append(total)
        

print(min(ans))

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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin >> s >> t;
    int q;
    cin >> q;
    int n = s.length();
    int m = t.length();
    vector<int> sa(n + 1), ta(m + 1);
    for (int i = 1; i <= n; ++i) {
        sa[i] = sa[i - 1] + (s[i - 1] == 'A');
    }
    for (int i = 1; i <= m; ++i) {
        ta[i] = ta[i - 1] + (t[i - 1] == 'A');
    }
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int a1 = sa[b] - sa[a - 1];
        int b1 = (b - a + 1) - a1;
        int a2 = ta[d] - ta[c - 1];
        int b2 = (d - c + 1) - a2;
        if ((a1 - b1 - a2 + b2) % 3) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
    return 0;
}

Measured memory_bytes: 1744
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const string EMP = " ";
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

int gcd(int a, int b){
  if(a % b == 0) return b;
  return gcd(b, a%b);
}

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

  int ans; cin >> ans;
  for(int i = 1; i < n; i++){
    int a; cin >> a;
    ans = gcd(ans, a);
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int N;
  cin >> N;
  int t[N];
  int x[N];
  int y[N];
  for(int i =0; i < N; i++){
    int tmp1,tmp2,tmp3;
    cin >> tmp1 >> tmp2 >> tmp3;
    t[i] = tmp1;
    x[i] = tmp2;
    y[i] = tmp3;
  }
  
  int distance = 0, time = 0;
  string ans ="Yes";
  
  for(int i = 0; i < N; i++){
    if(i == 0){
      distance = x[i] + y[i];
      time = t[i];
    }else{
      distance = abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
      time = t[i] - t[i-1];
    }
    
    if(distance > time){
      ans = "No";
      break;
    }else{
      if(((distance - time) % 2) != 0){
        ans = "No";
        break;
      }
    }
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;

const size_t SIZE = 5010;
const ll inf = 5e15;
const ll mod = 1e9 + 7;
ll dp[SIZE][SIZE];

ll solve() {
    dp[0][0] = 1;
    ll N, M;
    cin >> N >> M;
    V<ll> books(N);
    for(auto &&ele : books) cin >> ele;
    V<ll> back_min(N);
    back_min.back() = inf;
    for(ll i = N - 2; 0 <= i; i--) back_min[i] = min(books[i + 1], back_min[i + 1]);
    ll cur_max = 0;
    
    auto check_size = [&](ll sum, ll h) {
        return 0 <= h && h <= M &&
               0 <= sum - h && sum - h <= M;
    };

    for(ll i = 1; i <= N; i++) {
        ll cur = books[i - 1];
        if(back_min[i - 1] < cur && cur < cur_max) return 0;

        if(cur_max < cur) {
            for(ll j = 0; j < SIZE; j++) if(check_size(i, j + 1)) dp[i][j + 1] = dp[i - 1][j] %= mod;
            if(cur_max && cur_max < back_min[i - 1]) for(ll j = 0; j < SIZE; j++) if(check_size(i, j)) (dp[i][i - j] += dp[i - 1][j]) %= mod;
            cur_max = cur;
        } else {
            for(ll j = 0; j < SIZE; j++) if(check_size(i, j)) dp[i][j] = dp[i - 1][j];
        }
    }

    ll ans = 0;
    for(ll i = 0; i < SIZE; i++) if(check_size(N, i)) (ans += dp[N][i]) %= mod;
    return ans * 2 % mod;
}

int main() {
    cout << solve() << endl;
    return 0;
}



Measured memory_bytes: 119784
package main

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

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

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

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type Val struct {
	id, num int
}
type ByNum []Val

func (a ByNum) Len() int           { return len(a) }
func (a ByNum) Less(i, j int) bool { return a[i].num < a[j].num }
func (a ByNum) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextStr()

	fmt.Fprintln(wtr, "ABC"+N)
	wtr.Flush()
}


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

int N, M;
int ncount = 0;

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

    if(N == 1){

    }
    else{
        ncount += (N*(N-1)) / 2;
    }

    if(M == 1){

    }
    else{
        ncount += (M*(M-1)) / 2;
    }

    cout << ncount << endl;
}

Measured memory_bytes: 256
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][0]) for _ in range(ps[0][1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# エントリーポイント
def main():
    H, W = input([[int], 2])

    def solve(a_max, b_max):
        min_diff = INF
        for a in range(a_max):
            # 横分割
            area1 = (a * b_max
                    , b_max // 2 * (a_max - a)
                    , (b_max // 2 + b_max % 2) * (a_max - a))
            # 縦分割
            area2 = (a * b_max
                    , (a_max - a) // 2 * b_max
                    , ((a_max - a) // 2 + (a_max - a) % 2) * b_max)
            min_diff = min(min_diff, max(area1) - min(area1), max(area2) - min(area2))
        return min_diff
    print(min(solve(H, W), solve(W, H)))

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


Measured memory_bytes: 3316
A,B,K=input().split(" ")

A=int(A)
B=int(B)
K=int(K)

for i in range(int(K/2)):
    if (A%2==1):
        A-=1
    B+=A/2
    A/=2
    
    if (B%2==1):
        B-=1
    A+=B/2
    B/=2

if (K%2==1):
    if (A%2==1):
        A-=1
    B+=A/2
    A/=2
    
print(int(A), int(B))

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

long ans;
long M, N, K;
long X, Y;
vector<long> A, B, C;
vector<long> P;
vector<vector<long>> S;

int main(void) {

    cin >> N >> M;
    S.resize(M);
    P.resize(M);

    for (long i = 0; i < M; i++) {
        long k; cin >> k; S[i].resize(k);
        for (long j = 0; j < k; j++) {
            cin >> S[i][j];
            S[i][j]--;
        }
    }

    for (long i = 0; i < M; i++) {
        cin >> P[i];
    }

    for (long bit = 0; bit < (1 << N); bit++) {
        bool flag = true;
        for (long j = 0; j < M; j++) {
            long counter = 0;
            for (long i = 0; i < N; i++) {
                if (bit & (1 << i) && find(S[j].begin(), S[j].end(), i) != S[j].end()) {
                    counter++;
                }
            }
            if (counter%2 != P[j]) flag = false;
        }
        if (flag) ans++;
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 3632
n=int(input())
l=list(map(int,input().split()))
odd=len([1 for i in l if i%2])
t4=len([1 for i in l if i%4==0])
if odd+t4==n:
  if odd-1<=t4:print("Yes")
  else:print("No")
elif odd<=t4:print("Yes")
else:print("No")

Measured memory_bytes: 15020
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int C = sc.nextInt();

			double S = a*b*Math.sin(Math.toRadians(C))/2;
			double L = a + b + Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2) - 2*a*b*Math.cos(Math.toRadians(C)));
			double h = b*Math.sin(Math.toRadians(C));

			System.out.println(S);
			System.out.println(L);
			System.out.println(h);
		}
	}
}




Measured memory_bytes: 26340
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MAXN 100000
#define DEBUG false

int N, s[MAXN + 3];
bool visited[MAXN + 3];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &s[i]);

    LL answer = 0;
    for (int C = 1; C < N - 1; C++) {
        LL currentProfit = 0;
        memset(visited, false, sizeof(visited));

        for (int k = 0; k * C < N - 1; k++) {
            if (N - 1 - k * C <= 1) break; //A must be > 1
            if (N - 1 - k * C - C < 1) break; //B must be > 0

            if (visited[N - 1 - k * C]) break;
            visited[N - 1 - k * C] = true;

            if (visited[k * C]) break;
            visited[k * C] = true;

            currentProfit += s[k * C];
            currentProfit += s[N - 1 - k * C];

            if (DEBUG) cout << "c, k, p: " << C << " " << k << " " << currentProfit << endl;

            answer = max(answer, currentProfit);
        }
    }

    printf("%lld\n", answer);
}


Measured memory_bytes: 896
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <iomanip>
#include <tuple>
#include <unordered_set>
#include <unordered_map>

using namespace std;

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

	double sum = 0.0;

	for (int i = 0; i < n; i++) {
		double temp;
		cin >> temp;
		sum += (1.0 / temp);
	}

	cout << 1.0 / sum;
}


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

int main() {
  string S;
  cin >> S;
  long sz = S.size();

  vector <long> T(sz+1);
  vector <long> T1(sz+1);
  vector <long> T2(sz+1);

  T1.at(sz) = 0;
  for (long i=sz-1; i>=0; i--)
  if (S.at(i)=='>') {
    T1.at(i) = T1.at(i+1)+1;
  } else {
    T1.at(i) = 0;
  }

  T2.at(0) = 0;
  for (long i=0; i<sz; i++)
  if (S.at(i)=='<') {
    T2.at(i+1) = T2.at(i)+1;
  } else {
    T2.at(i+1) = 0;
  }

  for (long i=0; i<sz+1; i++ ) T[i] = max( T1[i], T2[i] );

/*
  cout << T1[0] ;
  for (long i=0; i<sz; i++ ) {
    cout << S[i];
    cout << T1[i+1] ;
  }
  cout << endl;

cout << T2[0] ;
  for (long i=0; i<sz; i++ ) {
    cout << S[i];
    cout << T2[i+1] ;
  }
  cout << endl;
  
  cout << T[0] ;
  for (long i=0; i<sz; i++ ) {
    cout << S[i];
    cout << T[i+1] ;
  }
  cout << endl;
*/

  long ct =0;
  for (long i=0; i<sz+1; i++ ) ct = ct + T[i];
  cout << ct << endl;

}


Measured memory_bytes: 12548
n,m = map(int,input().split())
a = [list(map(int, input().split())) for i in range(n)]
c = [list(map(int, input().split())) for i in range(m)]

s = []
t = []

for i in range(n):
    for j in range(m):
        s.append(abs(a[i][0] - c[j][0]) + abs(a[i][1] - c[j][1]))
    t.append(s.index(min(s)) + 1)
    s = []

for i in range(len(t)):
    print(t[i])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  int i,j;
  int n,m;
  cin>>n>>m;
  string s;
  cin>>s;
  int po=n;
  VI v;
  while(1){
    if(po<=m) {
      v.pb(po);
      break;
    }
    for(i=m;i>=1;i--){
      if(s[po-i]=='0'){
        po=po-i;
        v.pb(i);
        break;
      }
      if(i==1){
        cout<<-1<<endl;
        return 0;
      }
    }
  }
  int u=v.size();
  for(i=0;i<v.size();i++){
    cout<<v[u-1-i]<<" ";
  }
  cout<<endl;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

ll dp[MAX_N][2];

ll add(ll x,ll y)
{
    return (x + y)%MOD;
}

ll sub(ll x,ll y)
{
    return (x+MOD-y)%MOD;
}

ll mul(ll x,ll y)
{
    return x*y%MOD;
}

int sa[MAX_N],sb[MAX_N];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,u,v;
    cin >> n >> u >> v;
    vl vec(n);
    rep(i,n){
        cin >> vec[i];
    }
    if(n == 1){
        cout << "2\n";
        return 0;
    }
    set<ll> st;
    map<ll,int> mp;
    rep(i,n){
        mp[vec[i]] = i;
        st.insert(vec[i]);
    }
    ll a,b;
    a = min(u,v),b = max(u,v);
    sa[0] = sb[0] = 1;
    rep(i,n-1){
        if(vec[i+1]-vec[i] < a){
            sa[i+1] = sa[i] + 1;
            sb[i+1] = sb[i] + 1;
        }else if(vec[i+1]-vec[i] < b){
            sa[i+1] = sa[i];
            sb[i+1] = sb[i] + 1;
        }else{
            sa[i+1] = sa[i];
            sb[i+1] = sb[i];
        }
    }
    dp[1][0] = 1,dp[1][1] = 1;
    srep(i,1,n){
        auto it = st.upper_bound(vec[i]-a);
        int id = mp[*it];
        if(i == id){
            dp[i+1][0] = add(dp[i+1][0],dp[i][0]+dp[i][1]);
        }else if(i - id == 1){
            dp[i+1][0] = add(dp[i+1][0],dp[i][1]);
        }
        it = st.upper_bound(vec[i]-b);
        id = mp[*it];
        if(i == id){
            dp[i+1][1] = add(dp[i+1][1],dp[i][0]+dp[i][1]);
        }else{
            if(sa[i-1]-sa[id] == 0){
                dp[i+1][1] = add(dp[i+1][1],dp[id+1][0]);
            }
        }
    }
    cout << add(dp[n][0],dp[n][1]) << "\n";
    return 0;
}


Measured memory_bytes: 14336
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int n,k;
int dp[110000],s[110000];

main(){
  cin>>n>>k;
  dp[0]=1;

  rep(i,n){
    int a;
    cin>>a;
    rep(j,k+1){
      s[j+1]=s[j]+dp[j];
      dp[j]=s[j+1]-s[max(j-a,0LL)];
      dp[j]+=M;
      dp[j]%=M;
    }

  }

  cout<<dp[k]<<endl;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();

void add(int &a, int b) {
  int MOD = pow(10, 9) + 7;
  a += b;
  if (a >= MOD) a %= MOD;
}


int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> a(H, vector<char>(W, ' '));
  REP(y, H) {
    REP(x, W) {
      cin >> a.at(y).at(x);
    }
  }
  vector<vector<int>> dp(H, vector<int>(W, 0));
  dp.at(0).at(0) = 1;
  REP(y, H) {
    REP(x, W) {
      if (y + 1 < H && a.at(y + 1).at(x) == '.' ) add(dp.at(y + 1).at(x), dp.at(y).at(x));
      if (x + 1 < W && a.at(y).at(x + 1) == '.') add(dp.at(y).at(x + 1), dp.at(y).at(x));
      
    }
  }
  cout << dp.at(H - 1).at(W - 1) << endl;
  return 0;
}

Measured memory_bytes: 5248
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, M, sum = 0;
    cin >> N >> M;
    REP(i, M) {
        int A;
        cin >> A;
        sum += A;
    }
    if (N < sum) cout << -1 << endl;
    else cout << N - sum << endl;
    return 0;
}

Measured memory_bytes: 3636
using System;
class abc124_c{
  static void Main(){
    var s=Console.ReadLine();
    
    var w='1';
    var b='0';
    var result=0;
    
    var Tile=s[0];
    
    for(int i=1;i<s.Length;i++){
      if(s[i].Equals(Tile)) result++;
      Tile=(Tile.Equals(w))?b:w;
    }
    
    Console.WriteLine(result);
    
    return;
  }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100000;

int a[MAX_N];

int main()
{
	int n;
	int ocnt=0;
	cin >> n;
	rep(i,n){
		scanf("%d",&a[i]);
		if(a[i]%2 == 1){
			ocnt++;
		}
	}
	if(ocnt%2 == 0){
		cout << "YES" << "\n";
	}else{
		cout << "NO" << "\n";
	}
}

Measured memory_bytes: 640
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
bool b[305];
int n,m,ans,a[305][305],B,cnt[305],k[305];
int main(){
    scanf("%d%d",&n,&m);
    ans=n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)scanf("%d",a[i]+j);
        k[i]=1;
    }
    ans=n;
    while(B<m){
        memset(cnt,0,sizeof(cnt));
        int o=0;
        for(int i=1;i<=n;++i){
            while(b[a[i][k[i]]])++k[i];
            int _=a[i][k[i]];
            ++cnt[_];
            if(cnt[_]>o)o=cnt[_];
        }
        ans=min(ans,o);
        for(int i=1;i<=m;++i)if(cnt[i]==o)++B,b[i]=1;
    }
    printf("%d\n",ans);
    //system("pause");
    return 0;
}


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

int main() {
	string s;
	cin >> s;
	if (stoi(s.substr(0, 4)) < 2019)
		cout << "Heisei" << endl;
	else if (stoi(s.substr(5, 2)) <= 4)
		cout << "Heisei" << endl;
	else cout << "TBD" << endl;

	return 0;
}

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

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  FOR(a,1,10)
    FOR(b,1,10)
      printf("%dx%d=%d\n",a,b,a*b);
  return 0;
}

Measured memory_bytes: 0
/**
 *    author:  math2do
 *    created: 18.05.2020 22:34:35 IST
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int k;
  cin >> k;
  string s;
  cin >> s;
  string res;
  int n = s.length();
  for (int i = 0; i < min(k, n); i++) {
    res += s[i];
  }
  if ((int) res.length() < n) {
    res += "...";
  } 
  cout << res << endl;
  return 0;
}


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

#define N 100009

using namespace std;

const long long int mod=1e9+7;
long long int fac[N],invfac[N],ans[N];
int cnt[N],a[N];

long long int mul(long long int base,long long int pows){
	if(pows==0){
		return 1;
	}
	else if(pows==1){
		return base%mod;
	}
	else if(pows%2==0){
		long long int buf1=mul(base,pows/2)%mod;
		return (buf1*buf1)%mod;
	}
	long long int buf1=mul(base,pows/2)%mod;
	buf1=(buf1*buf1)%mod;
	return (base*buf1)%mod;
}

int main(){
	int i,j,t1,t2,t3,t4,n,firstpos,secondpos;
	long long int buf1,buf2,buf3,buf4;
	scanf("%d",&n);
	firstpos=secondpos=-1;
	for(i=1;i<=n+1;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	fac[0]=fac[1]=1;
	invfac[0]=invfac[1]=mul(1,mod-2);
	for(i=2;i<=n+2;i++){
		fac[i]=(fac[i-1]*i)%mod;
		invfac[i]=mul(fac[i],mod-2);
	}
	for(i=1;i<=n;i++){
		if(cnt[i]==2){
			t1=i;
			break;
		}
	}
	firstpos=secondpos=-1;
	for(i=1;i<=n+1;i++){
		if(a[i]==t1){
			if(firstpos==-1){
				firstpos=i;
			}
			else{
				secondpos=i;
			}
		}
	}
	for(i=1;i<=n+1;i++){
		ans[i]=fac[n+1];
		ans[i]=(ans[i]*invfac[n+1-i])%mod;
		ans[i]=(ans[i]*invfac[i])%mod;
		t1=(firstpos-1)+(n+1-secondpos);
		if(t1>=i-1){
			buf1=fac[t1];
			buf1=(buf1*invfac[i-1])%mod;
			buf1=(buf1*invfac[t1-i+1])%mod;
			ans[i]-=buf1;
			if(ans[i]<0){
				ans[i]+=mod;
			}
		}
	}
	for(i=1;i<=n+1;i++){
		printf("%lld\n",ans[i]);
	}
    return 0;
}

Measured memory_bytes: 4352