akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
using LL = long long;
using P = pair<int,int>;
const int Max_N=15;
const int Max_M=1e3+5;
int c[Max_M][Max_N];
const int INF=1e9;

int main(){
	int N, M;
	cin >> N >> M;
	vector<int> a(M), b(M);
	rep(i,M){
		cin >> a[i] >> b[i];
		rep(j,b[i]) cin >> c[i][j];
		rep(j,b[i]) c[i][j]--;
	}
	vector<int> dp(1<<N,INF);
	dp[0]=0;
	rep(bit,1<<N){
		rep(i,M){
			bool rev=true;
			rep(j,b[i]){
				if(!(bit&1<<c[i][j])){
					rev=false;
					break;
				}
			}
			if(!rev) continue;
			rep(j,1<<b[i]){
				int bit_prev=bit;
				rep(k,b[i]) if(j&1<<k) bit_prev-=1<<c[i][k];
				dp[bit]=min(dp[bit],dp[bit_prev]+a[i]);
			}
		}
	}
	if(dp[(1<<N)-1]==INF) cout << -1 << endl;
	else cout << dp[(1<<N)-1] << endl;

	return 0;
}

Measured memory_bytes: 384
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
hashmap = defaultdict(int)
for a in A:
  hashmap[a]+=1
ans = 0
for k, v in hashmap.items():
  if k < v:
    ans+=v-k
  elif k > v:
    ans+=v
print(ans)

Measured memory_bytes: 22488
#include <iostream>
#include <algorithm>
#include <cmath>
#include <functional>
#include <string>
#include <vector>
#include <set>
using namespace std;

#define int long long
#define rep(n, i) for (int i = 0; i < n; i++)
#define rep2(m, n, i) for (int i = m; i < n; i++)
#define rep_r(n, i) for (int i = n - 1; i >= 0; i--)

const int INF = 1LL << 60;
const int MOD = 1e9 + 7;

signed main() {
    int n;
    cin >> n;
    int a[n], b[n], c[n - 1];
    rep(n, i) {
        cin >> a[i];
        a[i]--;
    }
    rep(n, i) {
        cin >> b[i];
    }
    rep(n - 1, i) {
        cin >> c[i];
    }
    int sum = b[a[0]];
    rep2(1, n, i) {
        sum += b[a[i]];
        if (a[i] == a[i - 1] + 1) sum += c[a[i - 1]];
    }
    cout << sum << endl;
    return 0;
}

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

int main(int argc, char **argv)
{
    int K, A, B;

    std::cin >> K >> A >> B;

    for(int i = A; i <= B; i++){
        if(i % K == 0){
            std::cout << "OK" << std::endl;
            return 0;
        }
    }
    std::cout << "NG" << std::endl;
    
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  int h, w;
  cin >> h >> w;
  string hw[h];
  rep(i,h)
    cin >> hw[i];
  rep(i,h)
    rep(j,w)
    {
      if (hw[i][j] == '#') {
        if ((i > 0 && hw[i - 1][j] == '#') || (j > 0 && hw[i][j - 1] == '#')
            || (i < h - 1 && hw[i + 1][j] == '#')
            || (j < w - 1 && hw[i][j + 1] == '#')) {
        } else {
          cout << "No";
          return 0;
        }
      }
    }
  cout << "Yes";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <typeinfo>
#include <set>
#include <bitset>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
    int n, c;
    cin >> n >> c;
    vector<vector<ll>> d(c,vector<ll>(c));
    ll dij;
    for(int i=0; i<c; i++){
        for(int j=0; j<c; j++){
            cin >> dij;
            d[i][j] = dij;
        }
    }

    vector<vector<ll>> cost(3, vector<ll>(c,0));

    ll cij;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> cij;
            for(int k=0; k<c; k++){
                cost[(i+j)%3][k] += d[cij-1][k];
            }
        }
    }

    ll ans = 3000000000;
    for(int i=0; i<c; i++){
        for(int j=0; j<c; j++){
            for(int k=0; k<c; k++){
                if(i!=j and j!= k and i!=k){
                    ans = min(ans,cost[0][i]+cost[1][j]+cost[2][k]);
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
  int A,B,T;
  cin>>A>>B>>T;
  int t; t = 0;
  int maisu; maisu = 0;
  while(t <= T + 0.5) {
    t += A;
    maisu += B;
  }
  cout<<maisu-B<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
const int IINF = 1000000000;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    ll ans = INF;
    ll count = 0;
    ll sum = 0;
    int sign = 1;
    rep(i,n){
        int now  = a[i];
        if (sign*(sum + now) <= 0) now = sign*(abs(sum)+1);
        sum += now;
        count += abs(now-a[i]);

        sign *= -1;
    }
    ans = count;
    
    sum = 0;
    count = 0;
    sign = -1;
    rep(i,n){
        int now  = a[i];
        if (sign*(sum + now) <= 0) now = sign*(abs(sum)+1);
        sum += now;
        count += abs(now-a[i]);

        sign *= -1;
        //cout << sum << endl;

    }
    ans = min(ans, count);
    cout << ans << endl;
}

Measured memory_bytes: 3956
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
 
signed main() 
{
    int x1,y1,x2,y2,x3,y3,x4,y4; 
    cin >> x1 >> y1 >> x2 >> y2; 
 
    x3 = x2 -(y2-y1); 
    y3 = y2 +(x2-x1); 
 
    x4 = x1 - (y2-y1);
    y4 = y1 + (x2-x1);
 
    cout << x3 << " " << y3 <<" " << x4 << " " << y4; 
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
  using namespace std;
  long long MOD=1000000007;
  #define IOS() ios_base::sync_with_stdio(0); cin.tie(0);
  typedef long long ll;
  #define pb push_back
  typedef pair<ll,ll> pi;
  // double dp[305][305][305];


int main()
{
  IOS();
  int n;int k;
  cin>>n>>k;
  int dp[k+1];
  memset(dp, 0 , sizeof dp);
  int a[n];
  for (int i = 0; i <n; ++i)
  {
    cin>>a[i];
  }

  //have all ready


  for(int i=0;i<=k;i++)
  {
    for(int j=0;j<n;j++)
    {
      if(i>=a[j])
      {
          if(dp[i-a[j]]==0){
            dp[i]=1;
            break;
          }
      }
    }
  }

    // for(int i=0;i<=k;i++)
    //   cout<<i<<" "<<dp[i]<<endl;



  if(dp[k]==1)
    cout<<"First"<<endl;
  else
    cout<<"Second"<<endl;

  return 0;
}

Measured memory_bytes: 4044
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
	const int mod=1000000007;
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		long[] a=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
		long[] b=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
		long d=0,o=0;
		long[][] h=new long[n][];
		for(int i=0;i<n;i++){
			h[i]=new long[]{a[i],b[i]};
			if(a[i]<b[i]){
				d++;
				o+=b[i]-a[i];
			}
		}
		Array.Sort(h,ca);
		//Console.WriteLine("{0} {1}",d,o);
		long p=0;
		for(int i=0;i<n;i++){
			if(h[i][0]>h[i][1]){
				o-=h[i][0]-h[i][1];
				p++;
				if(o<=0){break;}
			}
			//Console.WriteLine("{0} {1}",h[i][0],h[i][1]);
		}
		if(d==0){Console.WriteLine(0);}
		else if(o>0){Console.WriteLine(-1);}
		else{Console.WriteLine("{0}",d+p);}
		
	}
	static int ca(long[] a,long[] b){
		if(a[0]-a[1]<b[0]-b[1]){return 1;}
		else if(a[0]-a[1]>b[0]-b[1]){return -1;}
		else{return 0;}
	}
}

Measured memory_bytes: 38108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define FOR(itr, v) for (auto itr = (v).begin(); itr != (v).end(); ++itr)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

const int MAX = 210000;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main()
{
    int n, m; cin >> n >> m;
    COMinit();
    auto vec = prime_factorize(m);
    ll ans = 1;
    for (auto pa : vec)
    {
        int num = pa.second;
        ll tmp = COM(num + n - 1, num);
        ans = (ans * tmp) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5248
import sys
def input() : return sys.stdin.readline().strip()

def main():
    N, A, B, C = map(int, input().split())
    s = list(input() for _ in range(N))
    d = {}
    d["A"] = A
    d["B"] = B
    d["C"] = C
    
    ans = []
    s.append("XX")
    for i in range(N):
        l1, r1 = s[i]
        l2, r2 = s[i+1]

        def func(a, b):
            d[a] += 1
            d[b] -= 1
            ans.append(a)

        if d[l1] == 0 and d[r1] == 0:
            print("No")
            exit()
        
        if d[l1] == 0:
            func(l1, r1)
        elif d[r1] == 0:
            func(r1, l1)
        else:
            if l1 in [l2, r2]:
                func(l1, r1)
            else:
                func(r1, l1)

    print("Yes")
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Measured memory_bytes: 18676
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;

//typedef modint998244353 mint;

const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

const ll MAX = 1e9 + 5;

int main() {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	//cout << s << endl;
	vector<int> ans;
	int p = 0;
	while (p < n) {
		int a = 0;
		for (int i = 1; i <= m; i++) {
			if (p + i > n) {
				break;
			}
			if (s[p + i] == '0') {
				a = i;
			}
		}
		if (a == 0) {
			cout << -1 << endl;
			return 0;
		}
		ans.emplace_back(a);
		p += a;

		
	}

	reverse(ans.begin(),ans.end());

	for (int ai: ans) {
		cout << ai << " ";
	}
}

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

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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  vector<vector<char>> a(h, vector<char>(w));
  vector<bool> show_y(h, false), show_x(w, false);
  rep(i, h) {
    rep(j, w) {
      cin >> a[i][j];
      if (a[i][j] == '#') {
        show_y[i] = true;
        show_x[j] = true;
      }
    }
  }
  rep(i, h) {
    if (show_y[i]) {
      rep(j, w) {
        if (show_x[j]) {
          cout << a[i][j];
        }
      }
      cout << '\n';
    }
  }
  return 0;
}

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

using namespace std;

int n, m, X, Y;
int arrX[105], arrY[105];

int main()
{
    while(cin >> n >> m >> X >> Y)
    {
        for(int i = 0; i < n; i++)
            cin >> arrX[i];
        for(int i = 0; i < m; i++)
            cin >> arrY[i];
        sort(arrX, arrX + n);
        sort(arrY, arrY + m);
        if(arrX[n - 1] >= Y || arrX[n - 1] >= arrY[0] || X >= Y || X >= arrY[0])
        {
            cout << "War" << endl;
        }
        else
        {
            cout << "No War" << endl;
        }
    }
    return 0;
}


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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int N;
  cin >> N;

  vector<int> order(N, 0);
  REPI(i, 0, N) { order[i] = i + 1; }
  int seq = 1;
  string key = "";
  map<string, int> perm;
  do {
    key = "";
    REP(i, N) { key += to_string(order[i]); }
    perm.insert(make_pair(key, seq));
    ++seq;
  } while (next_permutation(order.begin(), order.end()));

  // for (auto e : perm) {
  //   cout << e.first << ":" << e.second << endl;
  // }

  int a, b;
  char tmp_c;
  string tmp_s = "";

  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  a = perm.at(tmp_s);

  tmp_s = "";
  REP(i, N) {
    cin >> tmp_c;
    tmp_s += tmp_c;
  }
  b = perm.at(tmp_s);

  cout << abs(a - b) << endl;

  return 0;
}


Measured memory_bytes: 4736
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

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

	count := 0
	for i := 1; i < n - 1; i++ {
		if ps[i-1] < ps[i] && ps[i] < ps[i+1] {
			count++
		} else if ps[i+1] < ps[i] && ps[i] < ps[i-1] {
			count++
		}
	}
	fmt.Println(count)
}

Measured memory_bytes: 512
/**
 *    Creator :  bizarre
 *    Date : 4/2020
 *    Problem Number : 427
**/
#include <bits/stdc++.h>
using namespace std;
#define bizarre     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
/*
vector<int> prime_Numbers;
int primes[1000005];
void prime(int n)
{
    primes[1]=primes[0]=0;
    for(int i=2; i<=n; i++)
        primes[i]=true;
    for(int i=2; i<=n; i++)
    {
        if(primes[i]==true)
        {
            prime_Numbers.push_back(i);
            for(int j=i+i; j<=n; j+=i)
                primes[j]=false;
        }
    }
    for(int i=2; i<=n; i++)
        primes[i]+=primes[i-1];
}

void move1step(long long& a, long long& b, long long q)
{
    long long c= a-q*b;
    a=b;
    b=c;
}
long long egcd(long long r0,long long r1,long long& x0,long long& y0)
{
    long long x1=0,y1=1;
    x0=1;
    y0=0;
    while(r1)
    {
        long long q=r0/r1;
        move1step(r0,r1,q);
        move1step(x0,x1,q);
        move1step(y0,y1,q);
    }
    return r0;
}
bool  solve (long long a, long long b, long long c,long long&x, long long& y)
{
    long long g=egcd(a,b,x,y);
    int m=c/g;
    x*=m;
    y*=m;
    return c%g==0;
}



int npr(long long n, long long r)
{
    return (fact[n] * inv[n - r]) % mod;
}

int gcd(int a, int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
void PrimeFactorization(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        int c=0;
        if(n%i==0)
        {
            while(n%i==0)
            {
                n/=i;
            }

        }
    }

}
const int inf = 2e9, mod = 1e9 + 7,N=1e5+5;
long long fact[N], inv[N];
long long fp(long long base, long long exp)
{
    if (exp == 0)
        return 1;
    long long ans = fp(base, exp / 2);
    ans = (ans * ans) % mod;
    if (exp % 2 != 0)
        ans = (ans * (base % mod)) % mod;
    return ans;
}
void pre(long long n)
{
    fact[0] = 1;
    inv[0] = 1;
    for (long long i = 1; i <= n; i++)
    {
        fact[i] = (i * fact[i - 1]) % mod;
        inv[i] = fp(fact[i], mod - 2);
    }
}
int ncr(long long n, long long r)
{
    return (((fact[n] * inv[n - r]) % mod) * inv[r]) % mod;
}
long long ncrtane(long long n, long long r)
{
    long long ans=1,cntr=1;
    for(int i=n;i>n-r;i--)
    {
        ans*=i;
        ans/=cntr;
        cntr++;
    }
    return ans;
}
*/
long long dp[100005],v[100005],w[100005],V;
int main()
{
    bizarre
     long long n,x,ans=0;
     cin>>n>>x;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
        V+=v[i];
    }
    memset(dp,0x3f3f3f3f,sizeof dp);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=V;j>0;j--)
        {
            if(j-v[i]>=0)
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    for(int i=0;i<=V;i++)
    {
        if(dp[i]<=x)
            ans=max(ans,(long long)i);
    }
    cout <<ans;
    return 0;
}


Measured memory_bytes: 1024
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, X;
	cin >> N >> X;
	vector<int> L(N, 0);
	vector<int> D(N + 1, 0);

	REP(i, N) {
		cin >> L[i];
	}

	for(int i = 1; i < N + 1; i++) {
		D[i] = D[i - 1] + L[i - 1];
	}

	int cnt = 0;
	REP(i, N + 1) {
		if (D[i] <= X) {
			cnt++;
		}
	}

	cout << cnt << 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 = Integer.parseInt(sc.next());
        long[] a1 = new long[n];
        long[] a2 = new long[n];
        for (int i = 0; i < n; i++) {
            long temp = Long.parseLong(sc.next());
            a1[i] = temp;
            a2[i] = temp;
        }
        long ans1 = 0;
        long ans2 = 0;
        long temp = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && temp + a1[i] >= 0) {
                ans1 += temp + a1[i] + 1;
                a1[i] -= temp + a1[i] + 1;
            }
            if (i % 2 != 0 && temp + a1[i] <= 0) {
                ans1 += Math.abs(temp + a1[i] - 1);
                a1[i] += Math.abs(temp + a1[i] - 1);
            }
            temp += a1[i];
        }
        temp = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && temp + a2[i] <= 0) {
                ans2 += Math.abs(temp + a2[i] - 1);
                a2[i] += Math.abs(temp + a2[i] - 1);
            }
            if (i % 2 != 0 && temp + a2[i] >= 0) {
                ans2 += temp + a2[i] + 1;
                a2[i] -= temp + a2[i] + 1;
            }
            temp += a2[i];
        }
        System.out.println(Math.min(ans1, ans2));
    }
}

Measured memory_bytes: 49200
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;




int main(){
    ll n,h;

    cin>>n>>h;
    vector<ll> a(n);
    vector<ll> b(n);
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        a.push_back(x);
        b.push_back(y);
    }
    
    sort(a.rbegin(),a.rend());
    sort(b.rbegin(),b.rend());
    
    ll nage=0;
    ll nokori=0;
    ll ans=0;
    
    
    ll mi=10000000000;
  
    
    
    for(ll i=0;i<n;i++){
        nage+=b[i];
        nokori=h-nage;
        if(nokori>0){
        ans=nokori/a[0];
        if(nokori%a[0]!=0)ans++;
        ans+=i+1;
        }else{
            ans=i+1;
        }
        mi=min(ans,mi);
    }
    
    cout<<mi<<endl;
    

return 0;
}


Measured memory_bytes: 3424
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <complex>
#include <numeric>
#include <list>
using namespace std;

#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 FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef vector<int> vi;

void dfs(int p, vector<vi> &g, vector<set<int> > &out, vi &ans) {
	FOR(e, g[p]) {
		out[(*e)].erase(p);
	}
	//REP(i, out.size()) cout << p << " " << i << " " << out[i].size() << endl;
	FOR(e, g[p]) {
		if(out[(*e)].empty()) {
			if(ans[(*e)] != -1) continue;
			ans[(*e)] = p;
			dfs((*e), g, out, ans);
		}
	}
}

int main(void) {
	int n, m;
	cin >> n >> m;
	vector<set<int> > out(n);
	vector<vi> g(n);
	REP(i, n + m - 1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		out[b].insert(a);
	}
	int rt = -1;
	REP(i, n){
		if(out[i].empty()){
			rt = i;
		}
	}
	vi ans(n, -1);
	dfs(rt, g, out, ans);
	REP(i, n){
		printf("%d\n", ans[i] + 1);
	}
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll a[25][25];
ll N;
ll dp[1<<21];

ll rec(ll mask, ll ones){
	if(dp[mask]>=0) return dp[mask];
	if(mask==0) return 1;
	ll i = N - ones;
	ll res = 0;
	REP(j, N){
		if(a[i][j]==1 && (mask>>j)&1==1){
			res += rec(mask - (1<<j), ones-1);
			res %= mod;
		}
	}
	dp[mask] = res;
	return res;
}

int main(){
	cin >> N;
	REP(i, N)REP(j, N){
		cin >> a[i][j];
	}
	REP(i, 1<<21) dp[i] = -1;

	cout << rec((1<<N)-1, N) << endl;

    return 0;
}

Measured memory_bytes: 16640
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
	    int x=sc.nextInt();
	if(500*k>=x){
    System.out.println("Yes");
    }else{
    System.out.println("No"); 
    }
  
    }
}

Measured memory_bytes: 23124
// Words are flowing out like endless rain into a paper cup
// They slither while they pass they slip away across the universe
// Pools of sorrow, waves of joy are drifting through my open mind
// Possessing and caressing me

#include <bits/stdc++.h>
using namespace std;

using LL = long long;

namespace _buff {

const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
    if (ib == ie) {
        ib = ibuf;
        ie = ibuf + fread(ibuf, 1, BUFF, stdin);
    }
    return ib == ie ? -1 : *ib++;
}

}

LL read() {
    using namespace _buff;
    LL ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
        assert(~c);
    }
    if (c == '-') {
        pos = false;
        c = getc();
    }
    for (; c >= '0' && c <= '9'; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

bool ok(char c) {
    return c == '0' || c == '1' || c == '?';
}

size_t reads(char *s) {
    using namespace _buff;
    size_t ret = 0;
    char c = getc();
    for (; !ok(c); c = getc()) {
        assert(~c);
    }
    for (; ok(c); c = getc()) {
        s[ret++] = c;
    }
    s[ret] = '\0';
    return ret;
}

const int MOD = 1e9 + 7;

struct Z {
    uint v;

    Z(uint v = 0) : v(v) {}

    Z& operator += (const Z &z) {
        v += z.v;
        if (v >= MOD) v -= MOD;
        return *this;
    }

    Z& operator -= (const Z &z) {
        if (v < z.v) v += MOD;
        v -= z.v;
        return *this;
    }

    Z& operator *= (const Z &z) {
        v = static_cast<uint64_t>(v) * z.v % MOD;
        return *this;
    }
};

ostream& operator << (ostream &os, const Z &z) {
    return os << z.v;
}

Z operator + (const Z &x, const Z &y) {
    return Z(x.v + y.v >= MOD ? x.v + y.v - MOD : x.v + y.v);
}

Z operator - (const Z &x, const Z &y) {
    return Z(x.v < y.v ? x.v + MOD - y.v : x.v - y.v);
}

Z operator * (const Z &x, const Z &y) {
    return Z(static_cast<uint64_t>(x.v) * y.v % MOD);
}

Z qpow(Z base, uint e) {
    Z ret(1);
    for (; e; e >>= 1) {
        if (e & 1) {
            ret *= base;
        }
        base *= base;
    }
    return ret;
}

const size_t N = 3e5 + 5;
const int trans[7][2] {
    {1, 3}, {2, 0}, {1, 1}, {4, 6}, {5, 3}, {4, 4}, {6, 6}
};

char s[N];

Z dp[2][7];

int main() {
    uint n = reads(s);
    if (n == 1) {
        cout << (s[0] != '0' ? 1 : 0);
        return 0;
    }
    dp[0][0] = 1;
    uint ci = 0, ni = 1;
    for (uint i = 0; i < n; ++i) {
        memset(dp[ni], 0, sizeof dp[ni]);
        for (uint j = 0; j < 7; ++j) {
            if (s[i] != '1') {
                dp[ni][trans[j][0]] += dp[ci][j];
            } if (s[i] != '0') {
                dp[ni][trans[j][1]] += dp[ci][j];
            }
        }
        swap(ci, ni);
    }
    cout << dp[ci][3] + dp[ci][6];
    return 0;
}


Measured memory_bytes: 768
/*
[yahoo-procon2019-qual] D - Ears
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_L = 2e5;
const ll INF = 1e18;

int L;
int A[MAX_L + 1];
ll dp[MAX_L + 1][5];

ll solve() {
    for (int i = 0; i <= L; i++) {
        for (int j = 0; j < 5; j++) {
            dp[i][j] = INF;
        }
    }

    for (int j = 0; j < 5; j++) {
        dp[0][j] = 0;
        for (int i = 1; i <= L; i++) {
            ll x;
            switch (j) {
                case 1:
                case 3:
                    x = (A[i] == 0) ? 2 : (A[i] % 2);
                    break;
                case 2:
                    x = (A[i] + 1) % 2;
                    break;
                default:
                    x = A[i];
            }
            dp[i][j] = min(dp[i - 1][j] + x, j > 0 ? dp[i][j - 1] : INF);
        }
    }

    return dp[L][4];
}

int main() {
    cin >> L;
    for (int i = 1; i <= L; i++) {
        cin >> A[i];
    }

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 8832
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

const int N = 10010;
const int M = 100010;

struct Edge {
	int x, y, w;
} es[M];

int p[N]; // parent id

bool cmp(const Edge &a, const Edge &b) {
	return a.w < b.w;
}

// find the root of x;
int find(int x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void run() {
	int n, m, x, y, w;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &x, &y, &w);
		es[i].x = x;
		es[i].y = y;
		es[i].w = w;
	}
	std::sort(es, es + m, cmp);
	int sum = 0;
	for (int i = 0; i < n; i++)
		p[i] = i;
	for (int i = 0; i < m; i++) {
		int x = find(es[i].x);
		int y = find(es[i].y);
		if (x != y) {
			p[p[x]] = p[y];
			sum += es[i].w;
		}
	}
	printf("%d\n", sum);
}

int main() {
	run();
}

Measured memory_bytes: 3828
n,k,q = [int(x) for x in input().split()]
a = []
for i in range(q):
  a.append(int(input()))
res = [0] * n
for i in range(q):
  res[a[i]-1] += 1
b = q - k
#print(res)
for i in range(n):
  if res[i] > b:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 13788
n,m = map(int, input().split())
d = [0]*n
for _ in range(m):
    a,b = map(int, input().split())
    d[a-1] += 1
    d[b-1] += 1

for x in d:
    if x%2==1:
        print("NO")
        exit()
print("YES")

Measured memory_bytes: 3956
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For(i, 0, n)
#define rrep(i, n) rFor(i, n, 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

typedef struct UnionFindTree{
    vector<int> par;

    UnionFindTree(int n){
        par.resize(n, -1);
    }

    bool is_root(int x){
        return par[x]<0;
    }

    int find(int x){
        if(is_root(x)) return x;
        return par[x] = find(par[x]);
    }

    int size(int x){
        return -par[find(x)];
    }

    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }
}UF;

template<typename T> struct edge{
    int from, to; T cost;
    edge(int f, int t, T c): from(f), to(t), cost(c){}
};
 
template<typename T> struct Graph{
    vector<vector<edge<T>>> G;
    int n;
 
    Graph(int n_): n(n_){
        G.resize(n);
    }
 
    void add_edge(int f, int t, T c){
        G[f].emplace_back(f, t, c);
    }
};

int n, m;

void solve(){
    vector<edge<int>> E;
    rep(i, m){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        --a; --b;
        E.emplace_back(a, b, c);
    }
    UF uf(n);
    sort(E.begin(), E.end(), [](const edge<int> &e1, const edge<int> &e2){
        return e1.cost < e2.cost;
    });
    vector<int> mst;
    for(auto &e: E){
        if(uf.unite(e.from, e.to)) mst.push_back(e.cost);
    }
    printf("%d\n", mst[n / 2 - 1]);
}

int main(){
    while(scanf("%d%d", &n, &m) && n){
        solve();
    }
}


Measured memory_bytes: 3408
#include <iostream>
#include <algorithm>
#include <cstring>

#define rep2(i, s, n) for(int i=s; i < n; ++i)
#define rep(i, n) rep2(i, 0, n)
#define MEMZERO(x) memset(x, 0, sizeof(x))
#define MEMSET(x, y) memset(x, y, sizeof(x))

using namespace std;

bool isPrime[50000];
int prime[5150];
int count[50001];

void setPrime( bool *p, int n ) {
	p[0] = p[1] = false;
	rep2(i, 2, n) {
		if(!p[i]) continue;
		for(int j=i+i; j < n; j+=i) {
			p[j] = false;
		}
	}
}

int main( void )
{
	MEMZERO(prime);
	MEMSET(isPrime, true);
	setPrime(isPrime, 50000);
	int pnt = 1;
	prime[0] = 2;
	for(int i=3; i < 50000; i+=2) {
		if(isPrime[i]) {
			prime[pnt++] = i;
		}
	}

	MEMZERO(::count);
	rep(i, pnt) {
		rep2(j, i, pnt) {
			int pp = prime[i] + prime[j];
			if(pp < 50001) ++(::count[pp]);
		}
	}

	int n;
	
	while(cin >> n, n) {
		cout << ::count[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 1132
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int a, b;
  cin >> a >> b;
  cout << 6 - a - b << endl;
}

Measured memory_bytes: 256
using System;
class Therefore
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var length = input.Length;
            /*if (input[length - 1] == '3') Console.WriteLine("bon");
            else*/
            switch (input[length - 1])
            {
                case '3':
                    Console.WriteLine("bon");
                    break;
                case '2':
                    Console.WriteLine("hon");
                    break;
                case '4':
                    Console.WriteLine("hon");
                    break;
                case '5':
                    Console.WriteLine("hon");
                    break;
                case '7':
                    Console.WriteLine("hon");
                    break;
                case '9':
                    Console.WriteLine("hon");
                    break;
                case '0':
                    Console.WriteLine("pon");
                    break;
                case '1':
                    Console.WriteLine("pon");
                    break;
                case '6':
                    Console.WriteLine("pon");
                    break;
                case '8':
                    Console.WriteLine("pon");
                    break;

            }
        }
    }

Measured memory_bytes: 25676
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mood;
		}
		x = x * x % mood;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n;
string s;
int ans = 1;

signed main() {
	cin >> n >> s;
	for (int i = 1; i < n; i++) {
		if (s[i - 1] != s[i])ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 512
#pragma GCC optimze("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define md 998244353
#define trace(...)
#define ll long long int
#define ld long double
#define fi first
#define se second
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define frr(i,b,a) for(ll i=b;i>=a;i--)
#define mem(a) memset(a, 0, sizeof(a))
#define vpi std::vector<pair<int,int>>
#define pii pair<int,int>
#define pb push_back
#define sall(v) sort(v.begin(),v.end())
#define all(v) (v.begin(),v.end())
#define minf -10000000
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}
ll power(ll x, ll y,ll p) { 
    ll res = 1;      // Initialize result 
    x = x % p;  // Update x if it is more than or equal to p 
    while (y > 0) {  
        if (y & 1) // If y is odd, multiply x with result
            res = (res*x) % p;  
        y = y>>1; // y = y/2 // y must be even now
        x = (x*x) % p;   
    } 
    return res; 
}
ll power(ll x, ll y) { 
    ll res = 1;      // Initialize result 
    while (y > 0) {    
        if (y & 1)// If y is odd, multiply x with result 
            res = (res*x) ;  
        y = y>>1; // y = y/2 // y must be even now 
        x = (x*x);   
    } 
    return res; 
}
 
ll max3(ll a,ll b,ll c){
    return max(a,max(b,c));
}
ll min3(ll a,ll b,ll c){
    return min(a,min(b,c));
}
bool isPrime(ll n) { // Corner cases 
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
}

void solve() {
    int n;cin>>n;
    vector<pair<int,int>> v(n);
    fr(i,0,n-1)cin>>v[i].second>>v[i].first;
    sall(v);
    // for(auto x:v)
        // cout<<x.first<<" "<<x.second<<endl;
    int cur=0;
    fr(i,0,n-1){
        if((cur+v[i].second)>v[i].first){
            cout<<"No\n";
            return;
        }
        cur+=v[i].second;
    }
    cout<<"Yes\n";
    return ;
}

int main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    // cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int main() {

	int s[15];

	int i,j;

	int tof = 0;

	for (i = 0; i < 9; i++) {
		scanf("%d", &s[i]);
	}
	s[9] = s[0];
	s[10] = s[1];
	s[11] = s[2];

	for (j = 0; j < 9; j=j+3) {

		for (i = 0; i < 2; i++) {

			if (s[i + j] - s[i + j + 3] != s[i + j + 1] - s[i + j + 4]) {
				tof = 1;
				break;
			}


		}
	}
	
	
	for (j = 0; j < 2; j++) {

		for (i = 0; i < 9; i=i+3) {

			if (s[i + j+1] - s[i + j ] != s[i + j + 4] - s[i + j + 3]) {
				tof = 1;
				break;
			}


		}
	}

	if (tof == 1) {
		printf("No");
	}
	else {
		printf("Yes");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>

bool isprime( int n )
{
	for( int i = 2; i * i <= n; i++ ){
	 	if( n % i == 0 ) return false;
	}
	
	return true;
}

int main()
{
	int n;
	
	while( 1 ){
		std::cin >> n;
		if( !n ) break;
		
		int i = 2, p = 0, s = 0;
		while( p < n ){
			if( isprime( i ) ){
				s += i;
				p++;
			}
			i++;	
		}
	
		std::cout << s << std::endl;
	}

 	return 0;
}

Measured memory_bytes: 1160
n = int(input())

if n >= 64:
      print(64)
elif n >= 32:
      print(32)
elif n >= 16:
      print(16)
elif n >= 8:
      print(8)
elif n >= 4:
      print(4)
elif n >= 2:
      print(2)
else:
      print(1)

Measured memory_bytes: 9148
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abcdef
{
    public class QuestionC
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            //Input int array
            int[] inputArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int x = inputArray[0];
            int n = inputArray[1];
            
            if (n == 0) 
            {
                Console.WriteLine(x.ToString());
                Console.Out.Flush();
                return;
            }

            var hashSet = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToHashSet<int>();

            //Write Code
            bool foundUpper = false, foundLower = false;
            int lowerResult = 0, upperResult = 0;
            int diff = 0;
            while (foundLower == false && foundUpper == false) 
            {
                if (!hashSet.Contains(x - diff))
                {
                    foundLower = true;
                    lowerResult = x - diff;
                }
                if (!hashSet.Contains(x + diff)) 
                {
                    foundUpper = true;
                    upperResult = x + diff;
                }
                diff++;
            }

            if (foundLower == true)
            {
                Console.WriteLine(lowerResult.ToString());
            }
            else
            {
                Console.WriteLine(upperResult.ToString());
            }

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28296
import java.util.*;
import java.math.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String[] sa = S.split("");
    int f0 = 0;
    int f1 = 0;
    for(int i=0; i<S.length(); i++) {
      if(i%2 == 0 && sa[i].equals("1")){
        f0++;
      } else if(i%2 == 1 && sa[i].equals("0")){
        f0++;
      }
    }
    for(int i=0; i<S.length(); i++) {
      if(i%2 == 0 && sa[i].equals("0")){
        f1++;
      } else if(i%2 == 1 && sa[i].equals("1")){
        f1++;
      }
    }
    System.out.println(Math.min(f0, f1));
  }
}


Measured memory_bytes: 32708
// " --- IN THE NAME OF ALLAH --- " // ;)
// ------------sphr_agz------------ // ;)
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

typedef long double ld;
typedef long long int lli;
typedef pair <lli, lli> pii;
#define pb push_back
#define recout(x) return cout << (x), 0
#define f first
#define s second
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define stp(x) cout << setprecision(x) << fixed
#define mk make_pair
#define all(x) x.begin(), x.end()
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
const lli N = 1e5 + 10, N2 = 2e5, delta = 46639, mod = 1e9 + 7, oo = 1e18, LOG = 20, SQ = 300;
const ld PI = 3.141592653589793;

lli a[N], dp[105][N], ps[N];

lli f (lli x) {
	return (x % mod + mod) % mod;
}

int32_t main() {
	fast;
	lli n, k;
	cin >> n >> k;
	for (lli i = 1; i <= n; i++)
		cin >> a[i];
	dp[0][0] = 1;
	for (lli i = 1; i <= n; i++)
		for (lli j = 0; j <= k; j++) {
			ps[j] = f ((j? ps[j - 1]: 0) + dp[i - 1][j]);
			if (j <= a[i])
				dp[i][j] = ps[j];
			else
				dp[i][j] = f (ps[j] - ps[j - a[i] - 1]);
		}
	cout << dp[n][k] << '\n';
	return 0;
}


Measured memory_bytes: 79360
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int gcd(int a,int b)
{
	if(b==0)
	return a;
	
	return gcd(b,a%b);
}
int power(int x,int y,int p)
{
	int res=1;
	x=x%p;
	while(y>0)
	{
		if(y&1)
		res=(res*x)%p;
		
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
struct Matrix{ 
	int a[2][2] = {{0,0},{0,0}};
	Matrix operator *(const Matrix& other){
		Matrix product;
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
						product.a[i][k] =product.a[i][k] + (ll)a[i][j]*other.a[j][k];
				}
			}
		}
		return product;
	}
};
int modInverse(int n,int p)
{
	return power(n,p-2,p);
}
const int ma = 1e6+7;
vector<bool> prime(ma,true);
set<int> st;
bool p_prime = true;
void findPrime()
{
	prime[1] = false;
	for(int i=2;i<ma;i++)
	{
		if(prime[i])
		{
			for(ll p=(ll)i*i;p<ma;p+=i)
			{
				prime[p] = false;
			}
		}
	}
}
void findFactor(int n)
{
	if(n%2==0)
	{
		if(st.find(2) != st.end())
		{
			p_prime = false;
			return ;
		}
		st.insert(2);
		while(n%2==0)
		{
			n/=2;
		}
	}
	for(int i=3;i<=sqrt(n);i+=2)
	{
		if(prime[n])
		break;
		
		if(n%i == 0)
		{
			if(st.find(i) != st.end())
			{
				p_prime = false;
				return ;
			}
			st.insert(i);
			while(n%i==0)
			{
				n/=i;
			}
		}
	}
	if(n!=1)
	{
		if(st.find(n) != st.end())
		{
			p_prime = false;
			return ;
		}
		st.insert(n);
	}
}
int main() {
	// your code goes here
	 ios_base::sync_with_stdio(0);
	 cin.tie(0);
	 int n;
	 cin>>n;
	 vector<int> v(n);
	 for(int i=0;i<n;i++)
	 {
		 cin>>v[i];
	 }
	 findPrime();
	 int hcf = v[0];
	 findFactor(v[0]);
	 for(int i=1;i<n;i++)
	 {
		 hcf = gcd(hcf,v[i]);
		 if(p_prime == true)
		 {
			 findFactor(v[i]);
		 }
	 }
	 if(p_prime)
	 {
		 cout<<"pairwise coprime"<<'\n';
	 }
	 else if(hcf == 1)
	 {
		 cout<<"setwise coprime"<<'\n';
	 }
	 else
	 {
		 cout<<"not coprime"<<'\n';
	 }
	 
	 return 0;
}


Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n,tem;
    cin>>n;
    vector<long int>p;
    for(long int i=0;i<n;i++)
    {
        cin>>tem;
        p.push_back(tem);
    }
    long int c=1,mini=p[0];
     for(long int i=1;i<n;i++)
    {
       if(mini>=p[i])
       {
           c++;
           mini=p[i];
       }
    }
    cout<<c<<"\n";
return 0;}


Measured memory_bytes: 5344
class Dice:
    def __init__(self, p):
        self.y = [p[0], p[1], p[5], p[4]]
        self.x = [p[0], p[2], p[5], p[3]]
        self.z = [p[1], p[2], p[4], p[3]]
    def roll(self, c):
        if c == 'y':
            self.y.append(self.y.pop(0))
            self.x[0] = self.y[0]
            self.x[2] = self.y[2]
            self.z[0] = self.y[1]
            self.z[2] = self.y[3]
        elif c == 'x':
            self.x.append(self.x.pop(0))
            self.y[0] = self.x[0]
            self.y[2] = self.x[2]
            self.z[1] = self.x[1]
            self.z[3] = self.x[3]
        elif c == 'z':
            self.z.append(self.z.pop(0))
            self.x[1] = self.z[1]
            self.x[3] = self.z[3]
            self.y[1] = self.z[0]
            self.y[3] = self.z[2]
    def num(self, n):
        n = n - 1;
        pos_y = [0, 1, 5, 4]
        pos_x = [0, 2, 5, 3]
        if n in pos_y:
            return self.y[pos_y.index(n)]
        else:
            return self.x[pos_x.index(n)]
    def same(self, other):
        for _ in range(4):
            if self == other:
                return True
            other.roll('x')
            for _ in range(4):
                if self == other:
                    return True
                other.roll('y')
                for _ in range(4):
                    if self == other:
                        return True
                    other.roll('z')
        return False
    def __eq__(self, other):
        for i in range(1,7):
            if (self.num(i) != other.num(i)):
                return False
        return True

p1 = [ int(n) for n in input().split()]
p2 = [ int(n) for n in input().split()]

dice1 = Dice(p1)
dice2 = Dice(p2)

print('Yes' if dice1.same(dice2) else 'No')



Measured memory_bytes: 5620
#include <iostream>                                             
#include <cmath>                                                
using namespace std;                                            
                                                                
bool isPrime(int a) {                                           
  if (a==2) {                                                   
    return true;                                                
  }                                                             
  if (a<2 || a%2==0) {                                          
    return false;                                               
  }                                                             
  int i = 3;                                                    
  while (i<=sqrt(a)) {                                          
    if (a%i==0) {                                               
      return false;                                             
    }                                                           
    i = i+2;                                                    
  }                                                             
  return true;                                                  
}                                                               
                                                                
int main() {                                                    
  int n;                                                        
  cin >> n;                                                     
  int ans = 0;                                                  
  while (n--) {                                                 
    int x;                                                      
    cin >> x;                                                   
    if (isPrime(x)) {                                           
      ans++;                                                    
    }                                                           
  }                                                             
  cout << ans << endl;                                          
  return 0;                                                     
}                                                               
                                                                
                                                                
                              

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		List<int[]> list = new ArrayList<>();
		for(int i=0;i<m;i++) {
			int[] a = new int[2];
			a[0] = in.nextInt();
			a[1] = in.nextInt();
			list.add(a);
		}
		list.sort((a1,a2)->a1[1]-a2[1]);
		List<Integer> remove = new ArrayList<>();
		for(int[] a : list) {
			boolean solved = false;
			for(int bridge : remove) {
				if(a[0]<=bridge && bridge<a[1]) {
					solved = true;
					break;
				}
			}
			if(!solved) remove.add(a[1]-1);
		}
		System.out.println(remove.size());
	}

}


Measured memory_bytes: 96192