akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define clr(x) memset(x,0,sizeof x)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef double ld;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=505;
struct node{
	int p,id;
	friend bool operator < (node a,node b){
		return a.p<b.p||a.p==b.p&&a.id>b.id;
	}
}a[N];
int l[N],r[N],f[N][N];
int n,mod,ans;

void add(int &x,int y){
	x=(x+y>=mod?x+y-mod:x+y);
}
int mul(int x,int y){
	return (ll)x*y%mod;
}

int main(){
	read(n),read(mod);
	rep(i,0,2*n-1){
		r[i]=min(2*n-1,(int)sqrt(4*n*n-i*i));
		if(i>=n) a[i+1]=(node){r[i],i};
		else{
			l[i]=ceil(sqrt(n*n-i*i));
			a[i+1]=(node){l[i]-1,i};
		}
	}
	sort(a+1,a+n*2+1);
	rep(k,0,n){
		clr(f),f[0][0]=1;
		int c0=0,c1=0;
		rep(i,1,n*2){
			int p=a[i].id;
			rep(j,0,min(n-k,i-1))
				if(f[i-1][j])
					if(p<n){
						add(f[i][j+1],mul(f[i-1][j],1+r[p]-(n+k+j)));
						add(f[i][j],mod-mul(f[i-1][j],l[p]-(c0+c1-j)));
					}
					else{
						add(f[i][j],mul(f[i-1][j],1+r[p]-(c0+c1-j)));
					}
			if(p>=n)c1++;
			else c0++;
		}
		ans=(ans+f[n*2][n-k])%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1280
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  vector<pair<int, int>> dat;
  for (int i = 0; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    dat.emplace_back(b, a);
  }
  sort(dat.begin(), dat.end());
  long long t = 0;
  for (auto task : dat) {
    t += task.second;
    if (t > task.first) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}


Measured memory_bytes: 2420
#include<stdio.h>

int main(){
  int i,j,n,sum,max,min,ex[5];
  do{
    scanf("%d",&n);
    if(!n) break;
    scanf("%d %d %d %d %d",ex,ex+1,ex+2,ex+3,ex+4);
    for(i=0,sum=0;i<5;i++) sum+=ex[i];
    max=min=sum;
    for(i=1;i<n;i++){
      scanf("%d %d %d %d %d",ex,ex+1,ex+2,ex+3,ex+4);
      for(j=0,sum=0;j<5;j++) sum+=ex[j];
      if(max<sum) max=sum;
      if(min>sum) min=sum;
    }
    printf("%d %d\n",max,min);
  }while(1);
  return 0;
}

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

int main(){
    ll a, b, k;
    cin >> a >> b >> k;
    rep(i, 0, k){
        if(i%2 == 0){
            a /= 2;
            b += a;
        }else{
            b /= 2;
            a += b;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()

def cal(k):
    M = 0
    C = 0
    MC = 0
    res = 0
    k = min(k,N)
    for i in range(k):
        if S[i] == 'M':
            M += 1
        elif S[i] == 'C':
            C += 1
            MC += M
    for i in range(N-k):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1
        if S[i+k] == 'M':
            M += 1
        elif S[i+k] == 'C':
            C += 1
            MC += M
    for i in range(N-k,N):
        if S[i] == 'D':
            res += MC
        elif S[i] == 'M':
            M -= 1
            MC -= C
        elif S[i] == 'C':
            C -= 1

    return res

Q = int(input())
K = list(map(int,input().split()))
for k in K:
    print(cal(k))

Measured memory_bytes: 70124
import java.util.Scanner;
class Main
{
	
	static int H,W,h,w;
	static int ans =0;
	static int  base[][];
	public static void main(String arg[])
	{
		Scanner in = new Scanner(System.in);
		for(;;)
		{
			ans=0;
			int W=in.nextInt();
			int H=in.nextInt();
			if((H|W)==0)
				return;
			base=new int [H][W];
			String str;
			for(int i=0;i<H;i++)
			{
				str=in.next();
				for(int j=0;j<W;j++)
				{
					if(str.charAt(j)=='#')
						base[i][j]=0;
					else if(str.charAt(j)=='.')
						base[i][j]=1;
					else if(str.charAt(j)=='@')
					{
						h=i;
						w=j;
						base[i][j]=1;
					}

				}
			}
			System.out.println(solve(h,w,H,W));
		}
	}
	
	public static int solve(int m, int n,int H,int W)
	{
		if((0<=m&&m<H)&&(0<=n&&n<W))
		{
			if(base[m][n]==0||base[m][n]==2)
				return 0;
			else if(base[m][n]==1)
			{
				ans++;
				base[m][n]=2;
				if(m-1>=0&&base[m-1][n]==1)
					solve(m-1,n,H,W);
				if(m+1<H&&base[m+1][n]==1)
					solve(m+1,n,H,W);
				if(n-1>=0&&base[m][n-1]==1)
					solve(m,n-1,H,W);
				if(n+1<W&&base[m][n+1]==1)
					solve(m,n+1,H,W);
			}
		}
		return ans;
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vvchar vector<vector<char>>
#define vchar vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

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

    int h,n;cin>>h>>n;
    vint a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];

    //i-1番目までの魔法でhpjの魔物を倒すときの最小魔力
    vvint dp(n+10,vint(h+10,INF));
    dp[0][0]=0;
    
    

    for(int i=0; i<n; i++){
        for(int j=0; j<=h; j++){
            dp[i+1][j]=min(dp[i+1][j],dp[i+1][max(0LL,j-a[i])]+b[i]);
            chmin(dp[i+1][j],dp[i][j]);
        }
    }
    cout<<dp[n][h]<<endl;
}

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

ll a,b,v,w,t;
ll labs(ll x){
	if(x<0){
		return -x;
	}
	return x;
}

int main(void){
	scanf("%lld%lld",&a,&v);
	scanf("%lld%lld",&b,&w);
	scanf("%lld",&t);
	ll dif=v-w;
	ll dist=labs(a-b);
	if(dif<=0){
		printf("NO\n");
	}else if(dif*t>=dist){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}


Measured memory_bytes: 3656
#!python3

def resolve():
    S = input().rstrip()

    N = len(S)

    a, i, aa = "<", 0, []
    for c in S:
        if c == a:
            i += 1
        else:
            aa.append((a, i))
            i = 1
            a = c
    aa.append((a, i))

    if S[-1] == "<":
        aa.append((">", 0))

    pt = 0
    aaa = iter(aa)
    n = 0
    for a, b in zip(aaa, aaa):
        x, y = a
        n += y * (y - 1) // 2

        pt = y

        x, y = b

        if y > pt:
            pass
        else:
            n += pt
            y -= 1

        n += y * (y + 1) // 2

    print(n)




if __name__ == "__main__":
    resolve()


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

int main() {
	long H;	
	cin >> H;
	vector<long> a(H+1);
	// 1-origin
	for (long i=1; i<a.size(); ++i) scanf("%ld", &a[i]);

	// node id: key = k, parent key = pk, left key = lk, right key = rk, 	
	for (long i=1; i<a.size(); ++i) {
		long id = i;
		long key = a[i];
		cout << "node " << id << ": key = " << key << ", ";

		long p_key = a[i/2]; 
		if (i != 1) cout << "parent key = " << p_key << ", ";
		long lc_key = a[2*i];
		if (2*i <= H) cout << "left key = " << lc_key << ", ";
		long rc_key = a[2*i+1];
		if (2*i + 1 <= H) cout << "right key = " << rc_key << ", ";
		cout << endl;
	}
	return 0;
}




Measured memory_bytes: 3152
import collections 
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,m = inpl()
s = [0] * m
for i in range(m):
    s[i] = inpl()
p = inpl()
ans = 0

for flag in itertools.product([0,1], repeat=n):
    cnt = 0
    bb = [False] * n
    for i,j in enumerate(flag):
        if j :
            bb[i] = True
    for i in range(m):
        tmp = 0
        for j in range(1,len(s[i])):
            if bb[s[i][j]-1] == True:
                tmp += 1
        if tmp % 2 == p[i]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

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

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

int main()
{
  int n; cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(rALL(a));
  ll ans = a[0];
  rep(i, n-2) ans += a[(i+2)/2];
  cout << ans << endl;
}

Measured memory_bytes: 4048
#include <stdio.h>
#include<math.h>
#include <algorithm>

#define EPS 1e-10

using namespace std;


int main(){
	double x1,x2,x3,x4,y1,y2,y3,y4,slope1,slope2;

	while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4) != EOF){
		if(x1 == x2){
			if(y3 == y4)printf("YES\n");
			else{
				printf("NO\n");
			}
		}else{ //x1 != x2
			if(x3 == x4){
				if(y1 == y2)printf("YES\n");
				else{
					printf("NO\n");
				}
			}else{
				slope1 = (double)((y2-y1)/(x2-x1));
				slope2 = (double)((y4-y3)/(x4-x3));
				if(fabs(slope1*slope2 + 1) < EPS){
					printf("YES\n");
				}else{
					printf("NO\n");
				}
			}
		}
	}

    return 0;
}

Measured memory_bytes: 2692
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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(){
    int n; cin >> n;
    vector<int> A(n+2); rep(i, n)cin >> A[i+1];

    int sum = 0, cur = A[0];
    rept(i,1, n+1){
        sum += abs(cur - A[i]);
        cur = A[i];
    }
    sum += abs(A[n]);//最後に座標0に戻る
    
    vector<int> ans(n);
    rept(i,1, n+1){
        int dist = sum;
        dist -= abs(A[i] - A[i-1]);
        dist -= abs(A[i+1] - A[i]);
        dist += abs(A[i+1] - A[i-1]);
        ans[i-1] = dist;
    }

    for(auto a: ans){
        cout << a << ln;
    }
}
    


Measured memory_bytes: 4032
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;




int main() {
    int n;
    cin >> n;
    double a[111111];
    rep(i, n)cin >> a[i];
    double s = 0;
    rep(i, n) {
        s += (1 / a[i]);
    }

    cout << 1 / s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define M (L+R)/2
#define N 500009
#define inf 99999999999
#define ll long long
using namespace std;
ll n,ans,sum,A,B,a[20],c[20];
vector <pair<ll,ll> > b[20];
vector <ll> v;
int main(){

	ios::sync_with_stdio(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<=a[i];j++){
			cin>>A>>B;
			b[i].pb({A,B});
		}
	}
	
	for(int bit=1;bit<(1<<n);bit++){
	//	cout<<bit<<" bit "<<endl;
		sum=0;
		A=bit;
		v.clear();
		while(A){
			sum++;
			if(A&1){
				v.pb(sum);
			}
			A=(A>>1);
		}
		sum=v.size();
		if(sum<=ans)continue;
		for(int i=1;i<=n;i++){
			c[i]=0;
		}
		for(int i=0;i<sum;i++){
			c[v[i]]=1;
		}
	//	cout<<sum<<endl;
	//	for(int i=1;i<=n;i++){
	//		cout<<c[i]<<" ";
	//	}
	//	cout<<endl;
		B=0;
		for(int i=0;i<sum;i++){
			for(int j=0;j<b[v[i]].size();j++){
				if(c[b[v[i]][j].f]!=b[v[i]][j].s){
					B=-1;
					break;
				}
			}
			if(B==-1)break;
		}
		if(B==0)ans=sum;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include <stdio.h>
#include <bitset>
#include<math.h>
#include<list>
#include<map>
using namespace std;
typedef long long ll;
#define PI 3.14159265358979323846  

int main() {
	int count=0, value=1, sin, n;
	cin >> n >> sin;
	while (true) {
		if (n < value) {
			break;
		}
		count++;
		value *= sin;
	}
	cout << count  << endl;
}

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

int main()
{

            /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

        int n,i,j,k,x=1e6,cnt=0;

        cin>>n;
        int p[n];
        for(i=0;i<n;i++)
            cin>>p[i];

        for(i=0;i<n;i++)
        {
            if(p[i]<=x)
            {
                x=p[i];
                cnt++;
            }
        }
        cout<<cnt<<endl;

}


Measured memory_bytes: 1024
h,w = map(int,input().split())
a = [[x for x in input()] for _ in range(h)]

b = []
def solve(ls,i,j,h,w):
	flg = 0
	for k in range(w):
		if ls[i][k] == "#":
			flg += 1
			break
	for l in range(h):
		if ls[l][j] == "#":
			flg += 1
			break
			
	if flg ==2:
		return True
	else:
		return False

			

for i in range(h):
	c = []
	for j in range(w):
		if a[i][j] == "#":
			c.append("#")
		elif solve(a,i,j,h,w):
			c.append(".")
		else:
			pass
	b.append(c)

for i in b:
	print("".join(i))

Measured memory_bytes: 42220
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include <cstdint>
#include <boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int main() {
	string s;
	cin >> s;
	string a = "dream", b = "dreamer", c = "erase"
		, d = "eraser";
	bool flag = true;
	while (s.size() > 0) {
		int tmp = s.size();
		if (s.size() > 4) {
			if (s.substr(s.size()-5, 5) == a 
				or s.substr(s.size()-5, 5) == c) {
				s.erase(s.size()-5, 5);
			}
		}
		if (s.size() > 5) {
			if (s.substr(s.size()-6, 6) == d) {
				s.erase(s.size()-6, 6);
			}
		}
		if (s.size() > 6) {
			if (s.substr(s.size()-7, 7) == b) {
				s.erase(s.size()-7, 7);
			}
		}
		if (s.size() == tmp) {
			flag = false;
			break;
		}
		//cout << s << endl;
	}
	if (flag) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public final class Main {

    public static void main(String[] args) {
        final FastScanner fs = new FastScanner();
        final int n = fs.nextInt();
        int l = n / 2;
        int r = n / 2 + n % 2;
        System.out.println(l * r);
    }

    static final class Util {
        public static void shuffleSort(int[] x) {
            shuffle(x);
            Arrays.sort(x);
        }

        public static void shuffleSort(long[] x) {
            shuffle(x);
            Arrays.sort(x);
        }

        public static void shuffle(int[] x) {
            final Random r = new Random();

            for (int i = 0; i <= x.length - 2; i++) {
                final int j = i + r.nextInt(x.length - i);
                swap(x, i, j);
            }
        }

        public static void shuffle(long[] x) {
            final Random r = new Random();

            for (int i = 0; i <= x.length - 2; i++) {
                final int j = i + r.nextInt(x.length - i);
                swap(x, i, j);
            }
        }

        public static void swap(int[] x, int i, int j) {
            final int t = x[i];
            x[i] = x[j];
            x[j] = t;
        }

        public static void swap(long[] x, int i, int j) {
            final long t = x[i];
            x[i] = x[j];
            x[j] = t;
        }

        private Util() {}
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        private String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int[] nextIntArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long[] nextLongArray(int n) {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++) { a[i] = nextLong(); }
            return a;
        }
    }
}


Measured memory_bytes: 32424
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private void solve(Scanner sc) {
        BigInteger A = new BigInteger(sc.nextLine());
        BigInteger B = new BigInteger(sc.nextLine());

        int r;
        if ((r = A.compareTo(B)) > 0) {
            _out.println("GREATER");
        } else if (r < 0) {
            _out.println("LESS");
        } else {
            _out.println("EQUAL");
        }
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
using namespace std;

int main (){
ll N, Ans1 = 0, Ans2 = 0;cin >> N;
string S;cin >> S;
map<char, ll> M;

rep(i, 0, N)M[S[i]]++;

rep(i, N - M['W'], N){
    if(S[i] == 'W')Ans1++;
}

rep(i, 0, M['R']){
    if(S[i] == 'R')Ans2++;
}

if(Ans1 >= Ans2)cout << M['W'] - Ans1;

else cout << M['R'] - Ans2;
}


Measured memory_bytes: 3768
def main():
    n, m = map(int, input().split())
    s = [0] * m
    c = [0] * m
    for i in range(m):
        s[i], c[i] = map(int, input().split())
    ans = list()
    for i in range(n):
        ans.append(0)
    for i in range(m):
        if n != 1 and s[i] == 1 and c[i] == 0:
            print(-1)
            exit()
        if ans[s[i]-1] == 0 or ans[s[i]-1] == c[i]:
            ans[s[i]-1] = c[i]
        elif ans[s[i]-1] != 0 and ans[s[i]-1] != c[i]:
            print(-1)
            exit()
    if n != 1:
        if ans[0] == 0:
            ans[0] = 1
        print(*ans, sep='')
    else:
        print(*ans, sep='')

if __name__ == '__main__':
    main()

Measured memory_bytes: 9032
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << a[qwq];\
		else cerr << ", " << a[qwq];\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

const LL P = 998244353;
LL qpow(LL a, LL b) {
	LL r = 1;
	while(b) {
		if(b & 1) (r *= a) %= P;
		(a *= a) %= P; b >>= 1;
	}
	return r;
}
const int maxN = 500000 * 3 + 1000000 + 5;
int n, m;
LL fac[maxN], ifac[maxN];

LL choose(int n, int k) {
	if(n < 0 || k < 0 || k > n) return 0;
	else return fac[n] * ifac[k] % P * ifac[n - k] % P;
}

LL mc(int n, int k) {
	return choose(n + k - 1, k - 1);
}


int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	fac[0] = 1;
	for(int i = 1; i < maxN; ++i) fac[i] = fac[i - 1] * i % P;
	ifac[maxN - 1] = qpow(fac[maxN - 1], P - 2);
	for(int i = maxN - 2; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % P;
	LL ans = 0;
	for(int i = 0; i <= n && i <= m; ++i) if((3 * m - i) % 2 == 0) {
		int cd = (3 * m - i) / 2;
		LL dans = mc(cd, n) - i * mc(cd - m, n) - (n - i) * mc(cd - m - 1, n);
//		display(mc(cd, n));
//		display(mc(cd - m, n));
//		display(mc(cd - m - 1, n));
		dans = (dans % P + P) % P;
//		eprintf("i = %d, dans = %lld\n", i, dans);
		(ans += dans * choose(n, i)) %= P;
	}
	cout << (ans % P) << endl;
	return 0;
}


Measured memory_bytes: 39296
#include<stdio.h>
int main(void)
{
  int i,j,k,m,n,a[101][101],b[101],c[101];

  scanf("%d %d",&n,&m);

  for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){
      scanf("%d",&a[i][j]);
    }
  }
  for(j=1;j<=m;j++){
    scanf("%d",&b[j]);
    c[j]=0;
  }

  for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){
      c[i]=c[i]+a[i][j]*b[j];
    }
  }
  for(i=1;i<=n;i++){
    printf("%d\n",c[i]);
  }

  return 0;
}

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

int main() {
  int x,n;
  cin >> x >> n;
  
  vector<int>	map(102);
  for(int i=0;i<n;i++){
    int key;
    cin >> key;
    map.at(key)=key;
  }
  
  for(int sa=0;sa<100;sa++){
    if(map.at(x-sa)==0){
      cout << x-sa;
      return 0;
    }
    if(map.at(x+sa)==0){
      cout << x+sa;
      return 0;
    }
  }
    
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, y;
    cin >> x >> y;
    rep(i, 0, 60){
        if(x * 2 > y){
            cout << i + 1 << endl;
            return 0;
        }
        x *= 2;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define mp make_pair
using namespace std;

using ll = long long;
using ii = pair<int, int>;
const int INF = (int)10e9;
int dp[3][100005];

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin>>N;
	vector<int> a(N), b(N), c(N);
	for(int i = 0; i < N; i++) {
		cin>>a[i]>>b[i]>>c[i];
	}
	
	dp[0][0] = a[0];
	dp[1][0] = b[0];
	dp[2][0] = c[0];
	for(int i = 1; i < N; i++) {
		dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
		dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
		dp[2][i] = c[i] + max(dp[0][i-1], dp[1][i-1]);
	}
	cout << max(max(dp[0][N-1], dp[1][N-1]), dp[2][N-1]) <<endl;

    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int N; cin>>N;
    vector<int64_t> A(N);
    rep(n,0,N) cin>>A.at(n);

    sort(ToEnd(A));

    int64_t ans=A.back()-A.front();
    int idx1=N/2-(N%2==0),idx2=N/2;

    rep(n,0,N/2-(N%2==0)){
        cerr<<idx1-n-1<<" "<<idx2+n+1<<endl;
        ans+=abs(A.at(idx1-n-1)-A.at(idx2+n));
        ans+=abs(A.at(idx1-n)-A.at(idx2+n+1));
    }
    if(N%2) ans-=min(abs(A.at(idx1-1)-A.at(idx2)),abs(A.at(idx1)-A.at(idx2+1)));

    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  string res;
  
  cin >> a >> b >> c >> d;
  
  for (int i = 0; i <= 101; i++){
    c -= b;
    a -= d;
    if(c <= 0){
      res = "Yes";
      break;
    }else if(a <= 0){
      res = "No";
      break;
    }
  }
  cout << res << endl;
 }

Measured memory_bytes: 3592
#include <iostream>
using namespace std ;
#include<list>
int main (){

    int x1  , x2 ;
    cin >> x1 >> x2 ;
    if(x1==1&&x2==2)
    cout << 3 ;
    else if(x1==2&&x2==1)
    cout << 3 ;
    else if(x1==2&&x2==3)
    cout << 1 ;
    else if(x1==3&&x2==2)
    cout << 1 ;
    else if(x1==3&&x2==1)
    cout << 2 ;
    else if(x1==1&&x2==3)
    cout << 2 ;
return 0 ;
}


Measured memory_bytes: 256
n = int(input())
cnd = list(list(map(int, input().split())) for _ in range(n))

a = [0]*n
b = [0]*n

for i in range(n):
    a[i] = cnd[i][0]
    b[i] = cnd[i][1]
    
a.sort()
b.sort()

if n%2 == 1:
    a_cen = a[n//2]
    b_cen = b[n//2]
else:
    a_cen1 = a[n//2 - 1]
    a_cen2 = a[n//2]
    b_cen1 = b[n//2 - 1]
    b_cen2 = b[n//2]
    a_cen = a_cen1 + a_cen2
    b_cen = b_cen1 + b_cen2
    
ans = b_cen - a_cen + 1
print(ans)

Measured memory_bytes: 49180
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    cin>>n;
    vi f(n+1);
    f[0]=f[1]=1;
    REP(i,2,n){
        f[i]=f[i-1]+f[i-2];
    }
    cout<<f[n]<<endl;
}


Measured memory_bytes: 3116
#include <iostream>

using namespace std;

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

    if(N == 1) cout << "1" << endl;
    else if(N <= 3) cout << "2" << endl;
    else if(N <= 7) cout << "4" << endl;
    else if(N <= 15) cout << "8" << endl;
    else if(N <= 31) cout << "16" << endl;
    else if(N <= 63) cout << "32" << endl;
    else cout << "64" << endl;
}

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

int main() {
	int n;	string s;	cin >> n >> s;
  	ll r = 0, g = 0, b = 0;

//  	cout << b << endl;

  	rep(i,n){
    	if(s.at(i) == 'R') r++;
    	if(s.at(i) == 'G') g++;
    	if(s.at(i) == 'B') b++;
    }
  	
  	ll u = r*g*b;
//  	cout << u << endl;
  	ll cnt = 0;	
  	for(int i = 0; i < n; i++){
    	for(int j = i+1; j < n; j++){
        	int k = 2*j - i;
          	if(k >= n  || s.at(j) == s.at(k) || s.at(i) == s.at(k) || s.at(i) == s.at(j)) continue;
          	cnt++;
        }
    }
  	cout << (ll)u - cnt << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    bitset<30> v[n];
    forn(i, 0, n) {
        int k;
        cin >> k;
        while (k--) {
            int a;
            cin >> a;
            v[i][a-1] = 1;
        }
        if (i) v[i] &= v[i-1];
    }
    cout << v[n-1].count() << endl;
}


Measured memory_bytes: 3680
#include <stdio.h>
#include <stdlib.h>

#define N 100000
#define INF 0x3f3f3f3f

int main() {
	static int aa[N];
	int n, i, a, b, c, x;

	scanf("%d", &n);
	a = -1;
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		if (a < aa[i])
			a = aa[i];
	}
	b = INF;
	c = -1;
	for (i = 0; i < n; i++)
		if (aa[i] < a) {
			x = abs(aa[i] - (a + 1) / 2);
			if (b > x) {
				b = x;
				c = i;
			}
		}
	printf("%d %d\n", a, aa[c]);
	return 0;
}


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

int main() {
  int n, d, x; cin >> n >> d >> x;
  vector<int> intervals(n);
  for (int i = 0; i < n; i++) cin >> intervals.at(i);
  
  int answer = x;
  
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= d; j += intervals.at(i)) answer++;
  }
  
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int q;
int l[100000],r[100000];
bool IsPrime[100001];
int x[100001],sum[100001];

int main(){
    for(int i=2;i<=100000;i++)IsPrime[i]=true;
    int p=2;
    while(p<=50000){
        for(int i=p*2;i<=100000;i+=p)IsPrime[i]=false;
        p++;
        while(!IsPrime[p])p++;
    }
    x[3]=1;
    for(int i=5;i<=100000;i+=4)if(IsPrime[i]&&IsPrime[(i+1)/2])x[i]=1;
    for(int i=1;i<=100000;i++)sum[i]=sum[i-1]+x[i];
    cin>>q;
    for(int i=0;i<q;i++)cin>>l[i]>>r[i];
    for(int i=0;i<q;i++){
        cout<<sum[r[i]]-sum[l[i]-1]<<endl;
    }
    return 0;
}

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

using ll = long long;
const ll MOD = 1e9 + 7;

ll dp[22][1<<22] = {};

vector<int> b[22];

int f(int x) {
	int cou = 0;
	while(x) {
		if(x&1) cou++;
		x/=2;
	}
	return cou;
}

int main() {
	int N;
	scanf("%d", &N);
	dp[0][0] = 1;
	for(int i=0;i<(1<<N);i++) {
		b[f(i)].push_back(i);
	}
	for(int i=1;i<=N;i++) {
		for(int j=0;j<N;j++) {
			int a;
			scanf("%d", &a);
			if(a == 1) {
				for(int k=0;k<b[i-1].size();k++) {
					if(((1<<j)&b[i-1][k]) == 0) {
						dp[i][(1<<j)|b[i-1][k]] = (dp[i][(1<<j)|b[i-1][k]] + dp[i-1][b[i-1][k]])%MOD;
					}
				}
			}
		}
	}
	cout << dp[N][(1<<N)-1];
}

Measured memory_bytes: 333244
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007; 
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}






int main(){
    int N, M; std::cin >> N >> M;
    std::vector<std::vector<int>> G(N);
    {
        int A, B;
        for(int i(0); i < M; ++i){
            std::cin >> A >> B;
            --A; --B;
            G[A].push_back(B);
            G[B].push_back(A);
        }
    }
    std::vector<int> prv(N, -1);
    std::queue<int> que;
    prv[0] = 0;
    que.push(0);
    while(!que.empty()){
        int v(que.front()); que.pop();
        for(int e: G[v]){
            if(prv[e] != -1) continue;
            prv[e] = v + 1;
            que.push(e);
        }
    }
    std::cout << "Yes\n";
    for(int i(1); i < N; ++i){
        std::cout << prv[i] << "\n";
    }
    return 0;
}


Measured memory_bytes: 10328
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, M;
vector<int> G[MAX_N];
bool used[MAX_N];

void loop(int v) {
	used[v] = true;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(!used[n]) loop(n);
	}
}

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b, c; cin >> a >> b >> c; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	int res = 0;
	rep(i, 0, N) {
		if(!used[i]) {
			loop(i);
			res++;
		}
	}
	cout << res << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



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

int N;
vector<double> P;
double memo[3000][3000];

double solve(int i, int head) {
    if(i == N)
        return head >= (N/2+N%2) ? 1.0 : 0.0;
    else if(memo[i][head] != -1)
        return memo[i][head];
    else
        return memo[i][head] = P[i] * solve(i+1, head+1) + (1.0 - P[i]) * solve(i+1, head);
}

int main() {
    cin >> N;
    P.resize(N);
    for(double & x :P)  
        cin >> x;
    
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) 
            memo[i][j] = -1;
            
    cout.precision(10);
    cout << solve(0, 0) << "\n";   
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
#define int long long int
vi vals;
int n, k;
bool check(int mid){
    //debug(mid);
    //debug(vals[mid]);
    bitset<5005> prev;
    bitset<5005> dp;
    prev[0] = 1;
    FOR(i, vals.size()){
        if(i == mid)continue;
       // FOR(i, 5){   cout << i << " " << prev[i] << endl;  }
 //       cout <<endl;
        dp |= (prev << vals[i]);
        dp |= prev;
        swap(dp, prev);
    }
    //for(int i = k - 1; i >= 0; i--)  cout << i << " " << prev[i] << endl;
   
    for(int i = k -1; i >= max(0LL, k - vals[mid]); i--){
        // is necessary 
//        cout << i << " " << prev[i] << endl;
        if(prev[i])return false;
    }
    return true;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> k;
    vals.resize(n);
    int sum = 0;
    FOR(i, n)cin >> vals[i], sum += vals[i];
    sort(vals.begin(), vals.end());
    int s = 0, e = vals.size() - 1;
    int ans = -1;
    while(s <= e){
        int mid = (s+e)/2;
        if(check(mid)){
            s = mid+1;
            ans = mid;
        }else{
            e = mid -1;
        }
    }
    cout << ans + 1;
}




Measured memory_bytes: 256
fn input_pair<T: std::str::FromStr + Copy> () -> (T, T) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let arr: Vec<_> = s.trim().split_whitespace().flat_map(str::parse).collect();
    (arr[0], arr[1])
}

fn input_trio<T: std::str::FromStr + Copy> () -> (T, T, T) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let arr: Vec<_> = s.trim().split_whitespace().flat_map(str::parse).collect();
    (arr[0], arr[1], arr[2])
}

fn input_one<T: std::str::FromStr> () -> Result<T, T::Err> {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).unwrap();
    n.trim().parse()
}

fn w(c: char) -> char {
    match c {
        'r' => 'p',
        'p' => 's',
        's' => 'r',
        _ => ' ',
    }
}

fn main() {
    let (n, k) = input_pair::<usize>();
    let (r, s, p) = input_trio::<usize>();
    let t = input_one::<String>().unwrap();
    let ts: Vec<_> = format!("{}{}", " ".repeat(k), t).chars().map(w).collect();

    let mut result = 0;
    let mut won = vec![false; n + k];
    for i in k..n+k {
        if ts[i] != ts[i - k] || !won[i - k] {
            result += match ts[i] {
                'r' => r,
                'p' => p,
                's' => s,
                _ => 0,
            };
            won[i] = true;
        }
    }
    println!("{}", result);
}


Measured memory_bytes: 3120
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<math.h>
#define Max 100005*2
#define INF 1000000000000000000
#define getMax(a,b) a<b?b:a
#define getMin(a,b) a<b?a:b
using namespace std;



int main(){

	int n,h,x,sum=0;
	scanf("%d%d",&h,&n);
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		sum += x;
	}

	if(sum < h)
		printf("No\n");
	else
		printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll K;
  cin>>K;
  ll N = 50;
  ll b[N];
  ll tmp = K;
  ll one = 1;
  for(int i=0;i<N;++i) {
    if(i<N-1) {
      b[i] = K/N;
      if(i<K%N) b[i]++;
      tmp -= b[i];
    }
    else {
      b[i] = tmp;
    }
  }
  ll a[N];
  for(int i=0;i<N;++i) {
    a[i] = (N+1)*b[i]+N-K-1;
  }
  cout<<N<<endl;
  for(int i=0;i<N;++i) cout<<a[i]<<" ";
  cout<<endl;
}



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

#define MAXN 5000005
#define ll long long int

int main(){
    int x;
    cin>>x;
    if(x<=599)cout<<"8\n";
    else if(x<=799)cout<<"7\n";
    else if(x<=999)cout<<"6\n";
    else if(x<=1199)cout<<"5\n";
    else if(x<=1399)cout<<"4\n";
    else if(x<=1599)cout<<"3\n";
    else if(x<=1799)cout<<"2\n";
    else cout<<"1\n";
    return 0;
}


Measured memory_bytes: 3604
using System;
    public　class Program
    {
        public static string s;
        static void Main(string[] args)
        {
            String S = Console.ReadLine();
            char[] c = S.ToCharArray();
            int[] c2 = new int[c.Length];
            Array.Reverse(c);
            s = new String(c);
            Console.WriteLine(s);
        }
    }


Measured memory_bytes: 15808
#include <stdio.h>

int View(int N){
  int i, H, c, M;
  c = 0;
  M = 0;
  for(i = 0;i < N;i++){
    scanf("%d", &H);
    if(M <= H){
      M = H;
      c++;
    }
  }
  return c;
}

int main(void){
  int N;
  scanf("%d", &N);
  printf("%d\n", View(N));
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
static class Program{
	const int mod=(int)1e9+7;
	static readonly int[][] di=new int[][]{new int[]{-1,0},new int[]{1,0},new int[]{0,-1},new int[]{0,1}};
	static void Main(){
		Sc sc=new Sc();
		int[] s=sc.Ia;
		string[] h=new string[s[0]+2];
		bool[][] b=new bool[s[0]+2][];
		Queue<Tuple<int,int,int>> qu=new Queue<Tuple<int,int,int>>();
		for(int i = 1;i<=s[0];i++) {
			h[i]="#"+sc.S+"#";
			b[i]=new bool[s[1]+2];
			for(int j = 1;j<=s[1];j++) {
				if(h[i][j]=='#'){
					qu.Enqueue(Tuple.Create(0,i,j));
					b[i][j]=true;
				}
			}
		}
		h[0]=new string('#',s[1]+2);
		h[s[0]+1]=new string('#',s[1]+2);
		b[0]=new bool[s[1]+2];
		b[s[0]+1]=new bool[s[1]+2];
		int ans=0;
		while(qu.Count>0){
			var q=qu.Dequeue();
			ans=q.Item1;
			for(int i = 0;i<4;i++) {
				if(h[q.Item2+di[i][0]][q.Item3+di[i][1]]=='.'&&!b[q.Item2+di[i][0]][q.Item3+di[i][1]]){
					qu.Enqueue(Tuple.Create(q.Item1+1,q.Item2+di[i][0],q.Item3+di[i][1]));
					b[q.Item2+di[i][0]][q.Item3+di[i][1]]=true;
				}
			}
		}
		Console.WriteLine("{0}",ans);
	}
}

class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
}

Measured memory_bytes: 57388
n,k = map(int,input().split())
n_O = 0
n_E = 0
for i in range(1,n+1):
    if (2*i) % k == 0:
        if (2*i//k)%2 == 0:
            n_E += 1
        else:
            n_O += 1
print(n_E**3+n_O**3)


Measured memory_bytes: 9044
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

const i32 mod = 1000000007;

i32 mod_pow (i32 r, i32 n) {
  i32 t = 1;
  i32 s = r;
  while (n > 0) {
    if (n & 1) t = (i64) t * s % mod;
    s = (i64) s * s % mod;
    n >>= 1;
  }
  return t;
}

i32 inv (i32 a) {
  return mod_pow (a, mod - 2);
}

i32 *fact = NULL;
i32 *iFact = NULL;
void init_fact (const i32 n) {
  fact = (i32 *) calloc (n + 1, sizeof (i32));
  fact[0] = 1;
  for (i32 i = 1; i <= n; ++i) {
    fact[i] = (i64) i * fact[i - 1] % mod;
  }
  iFact = (i32 *) calloc (n + 1, sizeof (i32));
  iFact[n] = inv (fact[n]);
  for (i32 i = n - 1; i >= 0; --i) {
    iFact[i] = (i64) (i + 1) * iFact[i + 1] % mod;
  }
}

i32 comb (i32 n, i32 k) {
  if (!(0 <= k && k <= n)) return 0;
  return (i64) fact[n] * iFact[k] % mod * iFact[n - k] % mod;
}

void run (void) {
  i32 n, a, b, c;
  scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32 "%" SCNi32, &n, &a, &b, &c);
  i32 p = (i64) a * inv (a + b) % mod;
  i32 q = (1 + mod - p) % mod;
  init_fact (2 * n);
  i64 ans = 0;
  for (i32 i = 0, t = 1, x = mod_pow (p, n), y = mod_pow (q, n); i < n; ++i, x = (i64) x * q % mod, y = (i64) y * p % mod) {
    i64 prob = (i64) comb (n + i - 1, i) * (x + y);
    t = (t + (i64) mod * mod - prob) % mod;
    ans += t;
  }
  ans = (ans + n) % mod * 100 % mod * inv (100 - c) % mod;
  printf ("%" PRIi64 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 1792