akhauriyash/Code-Regression huggingface dataset:
def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Damage, Cost = [], []
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        Damage.append(a)
        Cost.append(b)

    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    dp = [[float('inf')] * (H + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(1, N + 1):
        for j in range(H + 1):
            # i 番目の魔法を使わない場合
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            # i 番目の魔法を使う場合
            dp[i][min(j + Damage[i - 1], H)] = min(dp[i][min(j + Damage[i - 1], H)],
                                                   dp[i][j] + Cost[i - 1])
    return dp[N][H]

print(e_crested_ibis_vs_monster())

Measured memory_bytes: 286344
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>

typedef long long ll;
using namespace std;

int main()
{
    int a[50000];
    int n,m;
    double sum=0;
    int k=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sum=sum/(4*m);
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=sum)
        {
            k++;
        }
    }
    if(k>=m)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=300005;
int n,a[N],su[N],i,s1,s2,l,r,m,mx;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",a+i),su[i]=su[i-1]+(i&1?a[i]:-a[i]);
	for(i=1;i<=n;i+=2)s1+=a[i];for(i=2;i<=n;i+=2)s2+=a[i];
	if(!(n&1)){printf("%d %d\n",max(s1,s2),min(s1,s2));return 0;}
	r=s1;
	for(;l<r;){
		m=l+r+1>>1;mx=0;
		for(i=2;i<=n;i+=2)if(su[i-1]+mx>=m)mx=max(mx,-su[i]);
		if(mx+su[n]>=m)l=m;else r=m-1;
	}
	printf("%d %d\n",l+s2,s1-l);
	return 0;
}

Measured memory_bytes: 2560
#include"bits/stdc++.h"
#include<cassert>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;
vector<P>v;
int kj[200006],kji[200006];
int dp[3003][3003][2];

int modpow(int a,int x,int mod){
	int res=1;
	while(x){
		if(x&1)res=res*a%mod;
		a=a*a%mod;
		x>>=1;
		}
	return res;
	}
void kjinit(){
	kj[0]=1;
	for(int i=0;i<200003;i++){
		kj[i+1]=kj[i]*(i+1)%mod;
		kji[i]=modpow(kj[i],mod-2,mod);
		}
	}
int comb(int r,int c){
	int res=kj[r]*kji[c]%mod;
	return res*kji[r-c]%mod;
	}
signed main(){
	int h,w,n;cin>>h>>w>>n;
	rep(i,n){
		int r,c;cin>>r>>c;v.push_back(P(r,c));
		}
	v.push_back(P(1,1));	
	sort(v.begin(),v.end());	
	kjinit();
	
	dp[0][0][0]=1;
	
	rep(i,n){
		rep(j,i+1){
			rep(k,2){
				dp[i+1][j][k]+=dp[i][j][k];
				dp[i+1][j][k]%=mod;
				int x=v[i+1].first-v[j].first,y=v[i+1].second-v[j].second;
				if(x>=0&&y>=0)dp[i+1][i+1][k^1]+=dp[i][j][k]*comb(x+y,x);
				dp[i+1][i+1][k^1]%=mod;
				}
			}
		}
	
	int sum=0;
	rep(i,n+1){
		int L=h-v[i].first,R=w-v[i].second;
		sum+=dp[n][i][0]*comb(L+R,L);
		sum%=mod;
	}
	rep(i,n+1){
		int L=h-v[i].first,R=w-v[i].second;
		sum-=dp[n][i][1]*comb(L+R,L)%mod;
		sum=(sum+mod)%mod;
	}
	
	cout<<sum<<endl;	

	}


Measured memory_bytes: 142592
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    set<int> S;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        S.insert(x);
    }

    cout << S.size() << '\n';
    
    return 0;
}


Measured memory_bytes: 256
import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for b in range(n-2):
  for c in range(b+1, n-1):
    count += max(0, bisect.bisect_left(l, l[b]+l[c])-c-1)

print(count)

Measured memory_bytes: 43372
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE RankNTypes #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import Data.List
import qualified Data.Vector.Unboxed as VU
-- import qualified Data.Vector.Unboxed.Mutable as VUM
-- import Control.Monad
-- import Control.Monad.ST
import Debug.Trace
-- trace _ = id

solve :: String -> Int
solve spec = VU.foldl' mAdd 0 dp
  where
  blues = VU.postscanl' mAdd 0 (VU.fromList (map f spec))
    where f c = read [c]
  len = VU.length blues
  totBlue = blues VU.! (len-1)
  dp = VU.ifoldl' f initV (blues VU.++ (VU.replicate len totBlue))
    where
    initV = VU.fromList [1]
    -- f vec i nb = traceL "vect" (i,x) x
    --      where x = fX vec i nb
    f vec i nb = VU.generate (i+2) g
      where
      nr | i < len   = (i+1)*2 - nb
         | otherwise = len*2 - nb
      g j | nb < j || nr < (i+1 - j) = 0
          | j == 0                   = vec VU.! 0
          | j == i+1                 = vec VU.! i
          | otherwise                = (vec VU.! (j-1)) `mAdd` (vec VU.! j)

----------------------------------------------------------------------
mPrime = 998244353

-- mAdd x y = (x + y) `mod` mPrime
mAdd :: Int -> Int -> Int
mAdd x y = let w = x + y in if w < mPrime then w else w - mPrime

-- mSub x y = (x - y) `mod` mPrime    -- ok even if x < y
mSub :: Int -> Int -> Int
mSub x y = let w = x - y in if w >= 0 then w else w + mPrime

mMul :: Int -> Int -> Int
mMul x y = (x * y) `mod` mPrime

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_spec]:remLines1 = remLines0
      spec = B.unpack bs_spec
  in solve spec

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents

traceL :: Show a => String -> a -> b -> b
traceL label showObj val = trace (label ++ " " ++ show showObj) val

traceLM :: (Monad m, Show a) => String -> (b -> a) -> m b -> m b
traceLM label showFn act = do
  aaa <- act
  traceL label (showFn aaa) (return ())
  return aaa


-------------------------------------------------------------------------------

inp1 = "02\n"
inp2 = "1210\n"
inp3 = "12001021211100201020\n"
tv1 = tmain $ B.pack inp1
tv2 = tmain $ B.pack inp2
tv3 = tmain $ B.pack inp3
test1 = tv1 == 3
test2 = tv2 == 55
test3 = tv3 == 543589959
alltest = test1 && test2 && test3



Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  int l[Q];
  int r[Q];
  for(int i=0;i<Q;i++){
    cin >> l[i] >> r[i];
  }
  int L[N];
  int R[N];
  int A=0;
  int count=0;
  for(int i=0;i<N;i++){
    if (A==1 && S[i]=='C') count++;
    if (S[i]=='A') A=1;
    else A=0;
    L[i]=count;
  }
  count=0;
  A=0;
  for(int i=N-1;i>=0;i--){
    if (A==1 && S[i]=='A') count++;
    if (S[i]=='C') A=1;
    else A=0;
    R[i]=count;
  }
  for(int i=0;i<Q;i++){
    cout << L[r[i]-1]-L[l[i]-1] << endl;
  }
}


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

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

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

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		if ((double)a[i] >= (double)all / (4 * m))
		{
			ans++;
		}
	}

	if (ans >= m)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int a[4][4],b[4][4];
int main()
{
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            cin>>a[i][j];
    int n,x=0,cnt=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>x;
        for(int i=1; i<=3; i++)
            for(int j=1; j<=3; j++)
                if(a[i][j]==x)
                {
                    cnt++;
                    b[i][j]=1;
                }
    }
    for(int i=1; i<=2; i++)
        {


                if(b[1][1]>0&&b[1][2]>0&&b[1][3]>0&&cnt>=3)
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }



                if(b[2][1]>0&&b[2][2]>0&&b[2][3]>0&&cnt>=3)
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }



                if(b[3][1]>0&&b[3][2]>0&&b[3][3]>0&&cnt>=3)
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }



                if(b[1][1]>0&&b[3][1]>0&&b[2][1]>0&&cnt>=3)
                    {
                        cout<<"Yes"<<endl;
                        return 0;
                    }



                if(b[1][2]>0&&b[2][2]>0&&b[3][2]>0&&cnt>=3)
                    {
                        cout<<"Yes"<<endl;
                        return 0;
                    }



                if(b[1][3]>0&&b[2][3]>0&&b[3][3]>0&&cnt>=3)
                    {
                        cout<<"Yes"<<endl;
                        return 0;
                    }


                if(b[1][1]>0&&b[2][2]>0&&b[3][3]>0&&cnt>=3)
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }



                if(b[1][3]>0&&b[2][2]>0&&b[3][1]>0&&cnt>=3)
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }

        }
        cout <<"No"<<endl;
        return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

n, k = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)

mod = 10**9+7
N = 2*10**5
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def prm(n, r, mod):
    if r <0 or r > n:
        return 0
    if r == 0:
        return 1
    return fac[n] * finv[n-r] % mod

s = [0]
visit = [-1]*n
visit[0] = 0
ans = 1
while s:
    v = s.pop()
    if v != 0:
        c = len(g[v])-1
        K = k-2
    else:
        c = len(g[v])+1
        K = k
    ans *= prm(K, c, mod)
    ans %= mod
    for u in g[v]:
        if visit[u] == -1:
            visit[u] = 0
            s.append(u)
print(ans)


Measured memory_bytes: 43996
#include<stdio.h>
int main()
{
  int n,a,b;
  scanf("%d%d%d",&n,&a,&b);
  if(a>=b)
    printf("%d ",b);
  else
    printf("%d ",a);
  if((n-a-b)>=0)
    printf("0");
  else
    printf("%d",a+b-n);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  char c[h][w];
  vector<bool> exist(h, false);
  rep(i, h) {
    rep(j, w) {
      cin >> c[i][j];
      if (c[i][j] == '#') exist[i] = true;
    }
  }
  int id[h][w], idx = 0;
  memset(id, 0, sizeof(id));
  rep(i, h) {
    if (!exist[i]) continue;
    idx++;
    int cnt = 0;
    rep(j, w) {
      if (c[i][j] == '#') {
        cnt++;
        if (cnt > 1) idx++;
      }
      id[i][j] = idx;
    }
  }

  rep(k, h) {
    if (!exist[k]) {
      int res = k + 1;
      while (!exist[res] && res < h) {
        res++;
      }
      if (res == h) {
        FORR(i, h - 1, k) {
          exist[i] = true;
          rep(j, w) {
            id[i][j] = id[k - 1][j];
          }
        }
        break;
      }
      FOR(i, k, res) {
        exist[i] = true;
        rep(j, w) {
          id[i][j] = id[res][j];
        }
      }
    }
  }


  rep(i, h) {
    rep(j, w) {
      if (j) cout << " ";
      cout << id[i][j];
    }
    cout << endl;
  }

  
  return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
 
int main()
{
	char S[3];
	int check_char[3]={0,0,0};
	scanf("%s",&S);
	for(int i=0;i<3;i++){
		if(S[i]=='a') check_char[0]=1;
		if(S[i]=='b') check_char[1]=1;
		if(S[i]=='c') check_char[2]=1;
	}
	if(check_char[0]==0||check_char[1]==0||check_char[2]==0)printf("No\n");
	else printf("Yes\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1e9+7
#define m_p make_pair
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pr;

const double pi = acos(-1.0);
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    ll n,m,ans=0;
    cin >> n;
    string s[n];
    rep(i,n) cin >> s[i];
    cin >> m;
    string t[m];
    rep(i,m) cin >> t[i];
    rep(i,n){
        ll cnt=0;
        rep(j,n){
            if(s[i]==s[j]) cnt++;
        }
        rep(j,m){
            if(s[i]==t[j]) cnt--;
        }
        ans=max(ans,cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String a = scan.next();

        scan.close();

        String[] aArray = a.split("");

        if (aArray[2].equals(aArray[3]) && aArray[4].equals(aArray[5])) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }

}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n; cin >> n;
  vll t(n), a(n);
  REP(i, n) cin >> t[i];
  REP(i, n) cin >> a[i];


  if(a[0] != t[n-1]) {
    cout << 0 << endl;
    return 0;
  }

  FOR(i, 1, n-1) {
    if(t[i] != a[i] && t[i-1] != t[i] && a[i] != a[i+1]) {
      cout << 0 << endl;
      return 0;
    }
  }

  FOR(i, 1, n) {
    if(a[i] < t[i] && t[i-1] != t[i]) {
      cout << 0 << endl;
      return 0;
    }
  }

  RREP(i, n-2) {
    if(a[i] > t[i] && a[i] != a[i+1]) {
      cout << 0 << endl;
      return 0;
    }
  }

  if((t[0] != a[0] && a[0] != a[1]) || (a[n-1] != t[n-1] && t[n-1] != t[n-2])) {
    cout << 0 << endl;
    return 0;
  }

  vll v(n, -1);
  v[0] = t[0];
  FOR(i, 1, n) {
    if(t[i] != t[i-1]) v[i] = t[i];
  }
  v[n-1] = a[n-1];
  RREP(i, n-2) {
    if(a[i] != a[i+1]) v[i] = a[i];
  }

  
  ll ans = 1;
  REP(i, n) {
    if(v[i] == -1) {
      ans *= min(t[i], a[i]);
      ans %= MOD;
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	static int A;
	static int B;
	static int H;
	static int M;
	static double h;
	static double m;
	static double N;
	static double X;
	static double Y;
	public  static void main(String[]args) {
		Scanner sc= new Scanner(System.in);
		A=sc.nextInt();
		B=sc.nextInt();
		H=sc.nextInt();
		M=sc.nextInt();
		h=H*30+M*0.5;
		m=M*6;
		N=Math.abs(h-m);
		N=Math.toRadians(N);
		N=Math.cos(N);
		X=A*A+B*B-2*A*B*N;
		X=Math.sqrt(X);
		System.out.println(X);
	}
}

Measured memory_bytes: 35964
a,b,k = map(int,input().split())
a = a-k
if a <= 0:
  b = b+a
  if b<=0:
    print('{} {}'.format(0,0))
  else:
    print('{} {}'.format(0,b))
else:
  
  print('{} {}'.format(a,b))

Measured memory_bytes: 2940
#include <stdio.h>

int main()
{
    int i, j, n = 0, num;
    char s;
    scanf("%d", &n);
    int array[4][13];
    for (i = 0; i < 4; i++)
        for (j = 0; j < 13; j++)
            array[i][j] = 0;

    for (i = 0; i < n; i++)
    {
        scanf("%c", &s);
        scanf("%c %d", &s, &num);
        switch (s)
        {
        case 'S':
            array[0][num - 1] = 1;
            break;
        case 'H':
            array[1][num - 1] = 1;
            break;
        case 'C':
            array[2][num - 1] = 1;
            break;
        case 'D':
            array[3][num - 1] = 1;
            break;

        default:
            break;
        }
    }
    for (i = 0; i < 4; i++)
        for (j = 0; j < 13; j++)
            if (array[i][j] == 0)
                switch (i)
                {
                case 0:
                    printf("S %d\n", j + 1);
                    break;
                case 1:
                    printf("H %d\n", j + 1);
                    break;
                case 2:
                    printf("C %d\n", j + 1);
                    break;
                case 3:
                    printf("D %d\n", j + 1);
                    break;

                default:
                    break;
                }
    return 0;
}


Measured memory_bytes: 2728
def factorials_with_inv(k,mod):
    """
    0! ... k! とそれらのmod逆元を求めて返す
    """
    fac = [1]*(k+1)
    inv = [1]*(k+1)
    t = 1
    for i in range(1,k+1):
        t *= i
        t %= mod
        fac[i] = t

    t = pow(t,-1,mod)
    for i in reversed(range(1,k+1)):
        inv[i] = t
        t *= i
        t %= mod

    return fac, inv

MOD = 10**9+7

def solve(N,M):
    fac,inv = factorials_with_inv(max(N,M), MOD)

    # (M-k)!/(k!(N-k)!) * N!M!/((M-N)!^2)

    res = 0
    sign = True
    for k in range(N+1):
        t = fac[M-k]*inv[k]*inv[N-k]
        if sign:
            res += t
        else:
            res -= t
        res %= MOD
        sign = not sign

    res *= fac[N]*fac[M]*inv[M-N]**2
    res %= MOD
    return res

from itertools import permutations

def naive(N,M):
    res = 0
    for A in permutations(range(M),N):
        for B in permutations(range(M),N):
            res += all(a != b for a,b in zip(A,B))
    return res%MOD

if __name__ == '__main__':
    N,M = map(int,input().split())

    # print(naive(N,M))
    print(solve(N,M))

Measured memory_bytes: 48424
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 200010
inline ll read()
{
    ll x=0; char c=getchar(),f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
    return x*f;
}
inline void write(ll x)
{
    static int buf[20],len; len=0;
    if(x<0)x=-x,putchar('-');
    for(;x;x/=10)buf[len++]=x%10;
    if(!len)putchar('0');
    else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
struct Segment_Tree{
	int sgt[4*maxn];
	void build(int now,int l,int r,int k)
	{
		sgt[now]=k;
		if(l<r){
			int mid=(l+r)>>1;
			build(now<<1,l,mid,k); build(now<<1|1,mid+1,r,k);
		}
	}
	void modify(int now,int l,int r,int x,int k)
	{
		if(l==r)sgt[now]=k;
		else{
			int mid=(l+r)>>1;
			if(x<=mid)modify(now<<1,l,mid,x,k);
			else modify(now<<1|1,mid+1,r,x,k);
			sgt[now]=std::max(sgt[now<<1],sgt[now<<1|1]);
		}
	}
	int query(int now,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return sgt[now];
		else{
			int mid=(l+r)>>1,cur=-inf;
			if(x<=mid)cur=std::max(cur,query(now<<1,l,mid,x,y));
			if(mid<y)cur=std::max(cur,query(now<<1|1,mid+1,r,x,y));
			return cur;
		}
	}
}t0,t1;
int a[maxn],val[maxn];
int f[maxn][2],g[maxn][2];
int ans[maxn];
int n;
int check(int cnt0,int mx0,int cnt1,int mx1,int rest)
{
	// printf("%d %d %d %d %d\n",cnt0,mx0,cnt1,mx1,rest);
	if(mx0<n&&cnt1-cnt0+rest>=0){
		if((cnt1-cnt0+rest)&1){
			if(t1.query(1,1,n,mx0+1,n)>=cnt1-cnt0+rest)return 1;
		}
		else if(t0.query(1,1,n,mx0+1,n)>=cnt1-cnt0+rest)return 1;
	}
	if(mx1<n&&cnt0-cnt1+rest>=0){
		if((cnt0-cnt1+rest)&1){
			if(t1.query(1,1,n,mx1+1,n)>=cnt0-cnt1+rest)return 1;
		}
		else if(t0.query(1,1,n,mx1+1,n)>=cnt0-cnt1+rest)return 1;
	}
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	t0.build(1,1,n,0); t1.build(1,1,n,-inf);
	int mx=0;
	for(int i=1;i<=n;i++)
		if(a[i]>mx){
			mx=a[i]; val[i]=1;
		}
		else val[i]=0;
	for(int i=n;i;i--){
		if(!val[i]){
			f[i][0]=t1.query(1,1,n,a[i],n)+1;
			f[i][1]=t0.query(1,1,n,a[i],n)+1;
		}
		else{
			f[i][0]=t0.query(1,1,n,a[i],n)+2;
			f[i][1]=t1.query(1,1,n,a[i],n)+2;
		}
		t0.modify(1,1,n,a[i],f[i][0]);
		t1.modify(1,1,n,a[i],f[i][1]);
	}
	// for(int i=1;i<=n;i++)
	// 	printf("%d : %d %d\n",i,f[i][0],f[i][1]);
	int rest=0;
	for(int i=1;i<=n;i++)
		rest+=val[i];
	int cnt0=0,cnt1=0,mx0=0,mx1=0;
	if(!check(cnt0,mx0,cnt1,mx1,rest)){
		puts("-1"); return 0;
	}
	for(int i=1;i<=n;i++){
		t0.modify(1,1,n,a[i],0);
		t1.modify(1,1,n,a[i],-inf);
		// printf("%d %d *****************\n",i,val[i]);
		rest-=val[i];
		if(check(cnt0+(a[i]>mx0),std::max(mx0,a[i]),cnt1,mx1,rest)){
			ans[i]=0;
			cnt0+=(a[i]>mx0); mx0=std::max(mx0,a[i]);
		}
		else{
			ans[i]=1;
			cnt1+=(a[i]>mx1); mx1=std::max(mx1,a[i]);
		}
	}
	for(int i=1;i<=n;i++)
		putchar(ans[i]+'0');
	putchar('\n');
	return 0;
}

Measured memory_bytes: 9728
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	vector<int> v(5);
	for (int i = 0; i < 5; i++) {
		cin >> v[i];
	}

	int k;
	cin >> k;

	for (int i = 0; i < 4; i++) {
		for (int j = i + 1; j < 5; j++) {
			int d = abs(v[i] - v[j]);
			if (d > k) {
				cout << ":(" << endl;
				return 0;
			}
		}
	}

	cout << "Yay!" << endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;
using piii = pair<pii, int>;
using ll = long long;
using vint = vector<int>;
using vvint = vector<vector<int>>;

#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,b) for(int i=a; i<b; i++)
#define fi first
#define se second


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

    int ans = a[0];
    rep(i, n) {
        ans = __gcd(ans, a[i]);
    }

    cout << ans << endl;
}

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

char S[200010];
char T[200010];

struct UnionFind {
	vector<int> par;

	UnionFind(int N) : par(N) {
		for (int i = 0; i < N; i++) par[i] = i;
	}

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

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

int main()
{
	cin >> S;
	cin >> T;
	auto len = strlen(S);
	UnionFind s(len);
	for (int i = 'a'; i <= 'z'; ++i) {
		int root = -1;
		for (int j = 0; j < len; ++j) {
			if (root < 0) {
				if (i == S[j])
					root = j;
			}
			else {
				if (i == S[j])
					s.unite(root, j);
			}
		}
	}
	bool e = true;
	UnionFind t(len);
	for (int i = 'a'; i <= 'z'; ++i) {
		int root = -1;
		for (int j = 0; j < len; ++j) {
			if (root < 0) {
				if (i == T[j])
					root = j;
			}
			else {
				if (i == T[j])
					t.unite(root, j);
			}
		}
		if (root < 0)
			e = false;
	}
	if (e) {
		for (int i = 0; i < len; ++i) {
			int root = s.root(i);
			if (root != t.root(i)) {
				t.unite(root, i);
			}
		}
	}
	bool b = true;
	for (int i = 0; i < len; ++i) {
		if (s.root(i) != t.root(i)) {
			b = false;
			break;
		}
	}
	cout << (b ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 3200
import sys
input = sys.stdin.readline
import heapq

x, y, a, b, c = map(int, input().split())
P = sorted(map(int, input().split()))[-x:]
Q = sorted(map(int, input().split()))[-y:]
heapq.heapify(P)
heapq.heapify(Q)
for r in map(int, input().split()):
  p = P[0]
  q = Q[0]
  if r > p or r > q:
    if p <= q:
      heapq.heapreplace(P, r)
    else:
      heapq.heapreplace(Q, r)
ans = sum(P) + sum(Q)
print(ans)

Measured memory_bytes: 19488
// at_dp_c.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include<algorithm>
using namespace std;
#define FOR(i,a) for(int i=0;i<a;i++)
int main()
{
	//dp[i][a] --> maximum sum on the first i days with a being the most recent activity completed
	int dp[100001][3]; dp[0][0] = dp[0][1] = dp[0][2] = 0;
	int value[100001][3];
	int n; cin >> n;
	FOR(i, n) {
		cin >> value[i][0] >> value[i][1] >> value[i][2];
	}
	for (int i = 1; i < n+1;i++) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][2])+value[i-1][0];
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + value[i-1][1];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + value[i-1][2];
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2]))<<"\n";
}



Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		long a = scan.nextLong();
		long total = 1;
		
		for(int i=0;i<a;i++) {
			long n = scan.nextLong();
			if(n == 0) {
				total = 0;
			}
			else {
				if(total <= ((long)Math.pow(10,18)/n)) {
					if(total >= 0) {
						total *= n;
					}
				}else {
					total = -1;
				}
			}
		}
		System.out.print(total);
		
	}

}

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

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

const int INF=1e9;
const int MOD=1e9+7;

int main(){
    int D,T,S; cin >> D >> T >> S;
    if(S*T>=D){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3628
#include<iostream>
#include<functional>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

typedef long long ll;

template <class T> struct SegTree {
	int N;
	vector<T> node;
	std::function<T(T, T)> operation;
	T unit;//単位元

	SegTree(vector<T>& data, std::function<T(T, T)> op, T U) {
		//データ　演算　単位元
		operation = op;
		unit = U;
		int size = data.size();
		N = 1;
		while (N < size)N <<= 1;
		node.resize(2 * N - 1, unit);

		for (int i = 0; i < size; i++) {
			node[i + N - 1] = data[i];
		}

		for (int i = N - 2; i >= 0; i--) {
			node[i] = operation(node[i * 2 + 1], node[i * 2 + 2]);
		}
	}

	void update(int pos, T val) {
		pos += N - 1;
		node[pos] = val;
		while (pos > 0) {
			pos = (pos - 1) / 2;
			node[pos] = operation(node[pos * 2 + 1], node[pos * 2 + 2]);
		}
	}

	T getval(int a, int b, int idx, int l, int r = -1) {
		//[a, b)を求める。　使い方はgetval(a, b, );
		if (r == -1)r = N;
		if (b <= l || r <= a)return unit;
		if (a <= l && r <= b)return node[idx];
		T left = getval(a, b, idx * 2 + 1, l, (l + r) / 2);
		T right = getval(a, b, idx * 2 + 2, (l + r) / 2, r);
		return operation(left, right);
	}

	T getval(int a, int b) {
		//ラッパー。
		return getval(a, b, 0, 0, -1);
	}
};

int main() {
	int n, q;
	cin >> n >> q;
	vector<int> v;
	v.resize(n, INT_MAX);
	SegTree<int> st(v,
		[](int a, int b) {return min(a, b); },
		INT_MAX);

	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		if (c == 0) {
			int a, b;
			cin >> a >> b;
			st.update(a, b);
		}
		else {
			int a, b;
			cin >> a >> b;
			cout << st.getval(a, b + 1) << endl;
		}
	}

	return 0;
}


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

int main()
{
    
   int a,b,h,m;
   cin >> a >> b >> h >> m;
   double aa = (5.5*m - 30*h);
   if(aa < 0){
    aa+=360;
   }
  //cout << aa << endl;
   double ans = sqrt(a*a + b*b - 2*a*b*cos(aa/180*acos(-1.0)));
   printf("%.20f\n",ans);
    return 0;
}
 
 

Measured memory_bytes: 4188
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MN = 1e5+5;

int main() {
	if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
	ios_base::sync_with_stdio(0), cin.tie(0);

	int N, L, T; cin >> N >> L >> T;

	int p = 0;
	vector<int> v;
	for (int i = 0; i < N; ++i) {
		int x, w; cin >> x >> w;
		if (w == 2) w = -1;
		v.push_back(((x+w*T)%L+L)%L);
		if (w == 1) p = (p+(x+T)/L)%N;
		else p = ((p-(L-x+T-1)/L)%N+N)%N;
	}
	sort(begin(v), end(v));
	for (int i = 0; i < N; ++i) cout << v[(i+p)%N] << '\n';
}


Measured memory_bytes: 3904
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define MAX 1000001
#define mod 1000000007
#define pie 3.14159265358979323846
void solve()
{
	ll int n,d,i,cnt=0;
	cin>>n>>d;
	for(i=0;i<n;i++){
		ll int x,y;
		cin>>x>>y;
		if((((x*x)+(y*y))<=(d*d)))
		cnt++;
	}
	cout<<cnt;
}
int main()
{ 
    cool;
    int t;
    //cin>>t;
    t=1;
    while(t--){
    	solve();
	}
    return 0;
}


Measured memory_bytes: 3640
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int y = scanner.nextInt();
			System.out.println(
					Arrays.stream(getResult(n, y)).mapToObj(i -> String.valueOf(i)).collect(Collectors.joining(" ")));
		}
	}

	/**
	 * @param n 合計枚数
	 * @param y 合計金額
	 * @return [1万円札の枚数, 5千円札の枚数, 1千円札の枚数]の配列
	 */
	private static int[] getResult(final int n, final int y) {
		for (int i = 0; i <= y / 5000; i++) {
			int count = n - i;
			int sum = y - i * 5000;
			int diff = sum - count * 1000;
			if ((diff >= 0) && (0 == diff % 9000) && (diff / 9000 <= count)) {
				return new int[] { diff / 9000, i, count - diff / 9000 };
			}
		}
		return new int[] { -1, -1, -1 };
	}
}


Measured memory_bytes: 27220
//============================================================================
// Name        : atcoder.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;
double A,B;
int main(){

	cin>>A;
	cin>>B;

	if(A>B)cout<<"GREATER"<<endl;
	else if(A<B)cout<<"LESS"<<endl;
	else cout<<"EQUAL"<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  vector<ll> l(100,-1);
  int n;
  cin >> n;
  l[0] = 2;
  l[1] = 1;
  
  for (int i = 2; i <= n; i++){
    l[i] = l[i-1] + l[i-2];
  }
  
  cout << l[n];
  
  return 0;
}

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

int c2i(char);

int main(){
  int i=0,top=0,x;
  int stack[1000];
  char s[1000];
  scanf("%[^\n]",s);
  
  while(s[i]!='\0'){
    
    if(48<= (int)s[i] && (int)s[i] <=57){

      if(48<= (int)s[i-1] && (int)s[i-1] <=57){
	x=c2i(s[i]);
	stack[top-1]=(stack[top-1]*10)+x;
      }
      else {
	stack[top]=c2i(s[i]);
	top++;
      }
    }

    else if(s[i]=='+'){
      stack[top-2]=stack[top-2]+stack[top-1];
      top--;
    }
    else if(s[i]=='-'){
      stack[top-2]=stack[top-2]-stack[top-1];
      top--;
    }
    else if(s[i]=='*'){
      stack[top-2]=stack[top-2]*stack[top-1];
      top--;
    }
    i++;
    
  }
  printf("%d\n",stack[top-1]);
  return 0;
}

int c2i(char c){

  return c-'0';
}
 



Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define rrep1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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;
    cout << (n+1) / 2 << endl;
}


Measured memory_bytes: 256
//Author : Ayush Jain

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

#define ull unsigned long long
#define ll long long
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define PI acos(-1.0)
const int N=1e5 + 5;
const int M=1e5 + 5;


int main()
{
	ios_base::sync_with_stdio(false);
	int n,foo;
	string s;
	cin>>n;
	int low=0,high=n-1,mid;
	cout<<0<<endl;
	cin>>s;
	if(s=="Vacant"){
		return 0;
	}
	if(s=="Male") foo=0;
	else foo=1;
	while(low<=high){
		mid=(low+high)/2;
		cout<<mid<<endl;
		cin>>s;
		if(s=="Vacant"){
			return 0;
		}
		if(foo==0){
			if(mid%2==0 && s=="Female") high=mid;
			else if(mid%2==1 && s=="Male") high=mid;
			else low=1+mid;
		}
		else{
			if(mid%2==0 && s=="Male") high=mid;
			else if(mid%2==1 && s=="Female") high=mid;
			else low=1+mid;	
		}
		//cout<<low<<" "<<high<<endl;
	}
		
	
		
	return 0;
}

Measured memory_bytes: 852
import java.util.*;
 
public class Main { //クラス名はMain
    public static void main(String[] args) {
      //整数の入力
      List<String> list = new ArrayList<String>();
      Scanner sc = new Scanner(System.in);
      Integer ndate = Integer.parseInt(sc.next());
      Integer msyuku = Integer.parseInt(sc.next());
      
      //宿題の日数の記録
      List<Integer> num = new ArrayList<>();
      for (int i=0; i<msyuku; i++) {
          int di = sc.nextInt();
          num.add(di);
      }

      int asobu = 0;
      //日数を減らす
      for (int n : num){
          ndate -= n;
      }

      //宿題を終わらせられなければ-1
      if(ndate < 0){
          ndate = -1;
      }

      System.out.println(ndate);
    }
    
}


Measured memory_bytes: 46776
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 1000000007
#define MAXN 200002
int n;
long long inv[MAXN],s[MAXN];
long long Powmod(long long a,int b)
{
	long long ret=1;
	while(b)
	{
		if(b&1)ret=ret*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ret;
}
void Pre()
{
	s[0]=1;
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]*i%MOD;
	inv[0]=1;
	inv[n]=Powmod(s[n],MOD-2);
	for(int i=n-1;i>0;i--)
		inv[i]=inv[i+1]*(i+1)%MOD;
}
long long C(int a,int b)
{
	if(a<0||b<0)return 1;
	return s[a]*inv[b]%MOD*inv[a-b]%MOD;
}
int main()
{
	int h,w,A,B;
	scanf("%d%d%d%d",&h,&w,&A,&B);
	n=h+w-2;
	Pre();
	long long ans=C(h+w-2,h-1);
	for(int i=1;i<=B;i++)
	{
		ans-=C(h-A+i-2,h-A-1)*C(A-1+w-i,A-1)%MOD;
		ans=(ans%MOD+MOD)%MOD;
	}
	printf("%lld",ans);
}

Measured memory_bytes: 3328
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))

typedef long long ll;

int main(){
    int n; cin >> n;
    vector<long long int> a(n); rep(i,n) cin >> a[i];
    int q; cin >> q;
    vector<long long int> b(q), c(q);
    rep(i, q) cin >> b[i] >> c[i];
    map<long long int, int> mp;
    set<long long int> st;
    rep(i,n){
        if(mp.count(a[i])==0) mp[a[i]] = 1;
        else mp[a[i]]++;
        st.insert(a[i]);
    }
    long long int sum = 0;
    for(auto x: st){
        if(mp.count(x)==0) continue;
        else sum += mp[x] * x;
    }

    rep(i,q){
        if(mp.count(b[i])==0){cout << sum << endl; continue;}
        int t = mp[b[i]];
        mp.erase(b[i]);
        if(mp.count(c[i])==0) mp[c[i]] = t;
        else mp[c[i]] += t;
        sum = sum + (c[i] - b[i]) * t;
        cout << sum << endl;
    }
    return 0;
}

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

int main()
{
    int i,j,res=-1,m,n;
    scanf("%d %d",&n,&m);
    for(i=1;i<=sqrt(m);i++)
    {
        if(m%i==0)
        {
            if(m/i>=n)
            {
                res=max(i,res);
            }
            if(i>=n)
            {
                res=max(m/i,res);
            }
        }
    }
    printf("%d\n",res);
}


Measured memory_bytes: 256
fun main() {
    val n= readLine()!!.toInt()
    val d= readLine()!!.split(" ").map { it.toLong() }.toLongArray()
    var ans:Long=0
    for (i in 0 until n){
        for (j in i+1 until n){
            ans+=d[i]*d[j]
        }
    }
    println(ans)
}

Measured memory_bytes: 36604
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */

void solve(istream &cin) {
    ll N, A;
    cin >> N >> A;
    if(!cin) return;
    map<ll, ll> d;
    for (int i = 0; i < N; ++i) {
        ll x;
        cin >> x;
        ll T = x - A;
        map<ll, ll> dt = d;
        for (auto &&a : d) {
            dt[a.first + T] += a.second;
        } // end a
        dt[T]++;
        d = dt;
    } // end i

    cout << d[0] << endl;
}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    cerr << "DEBUG MODE" << endl;
    string test_cases = "test.txt";
    auto fs = fstream(test_cases, fstream::in);
    while(fs) {
        solve(fs);
    }
#else
    solve(cin);
#endif
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main () {
    string S, T;
    cin >> S >> T;
    int A, B;
    cin >> A >> B;
    string U;
    cin >> U;
    if (S == U) A--;
    else B--;
    cout << A << ' ' << B << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
//mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9+7, N = 2e5+5;

int a[N], n, m, k;

void solve(int test_case){
	int i, j;
	cin >> n;
	a[0] = 1;
	for(i=3;i<=n;i++){
		for(j=3;j<=n;j++){
			if(i-j>=0){
				a[i] += a[i-j];
				a[i] %= mod;
			}
		}
	}
	cout << a[n];
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}



Measured memory_bytes: 3620
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a>=b){
            System.out.println("delicious");
        }else if(x>=b-a){
            System.out.println("safe");
        }else{
            System.out.println("dangerous");
        }
    }
}

Measured memory_bytes: 23764
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>

namespace lib 
{
	template<std::uint64_t Mod>struct modnum;
	template<class T>constexpr T pow(T base, std::size_t p)
	{
		if (p == 0)
		{
			return T(1);
		}
		else if (p == 1)
		{
			return base;
		}
		else if (p == 2)
		{
			return base*base;
		}
		else if (p % 2 == 0)
		{
			return pow(pow(base, p / 2), 2);
		}
		else
		{
			return pow(pow(base, p / 2), 2)*base;
		}
	}
	template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod> const&);

	template<std::uint64_t Mod>struct modnum
	{
		static constexpr auto mod = Mod;
		std::uint64_t val;
		modnum() = default;
		constexpr modnum(std::uint64_t v) :val(v)
		{

		}

		constexpr modnum& operator+=(modnum const& v)
		{
			val += v.val;
			val %= mod;
			return *this;
		}
		constexpr modnum& operator-=(modnum const& v)
		{
			val += mod - v.val;
			val %= mod;
			return *this;
		}
		constexpr modnum& operator*=(modnum const& v)
		{
			val *= v.val;
			val %= mod;
			return *this;
		}
		constexpr modnum& operator/=(modnum const& v)
		{
			return operator*=(inverse(v));
		}
	};
	template<std::uint64_t Mod>constexpr auto operator+(modnum<Mod> lhs, modnum<Mod>const& rhs)
	{
		return lhs += rhs;
	}
	template<std::uint64_t Mod>constexpr auto operator-(modnum<Mod> lhs, modnum<Mod>const& rhs)
	{
		return lhs -= rhs;
	}
	template<std::uint64_t Mod>constexpr auto operator*(modnum<Mod> lhs, modnum<Mod>const& rhs)
	{
		return lhs *= rhs;
	}
	template<std::uint64_t Mod>constexpr auto operator/(modnum<Mod> lhs, modnum<Mod>const& rhs)
	{
		return lhs /= rhs;
	}

	template<std::uint64_t Mod>constexpr auto inverse(modnum<Mod>const& base)
	{
		return pow(base, Mod - 2);
	}


}

void Main();
int main()	
{
	std::cin.sync_with_stdio(false);
	Main();
}

void Main()
{
	int N, M;
	std::cin >> N >> M;
	std::vector<std::set<int>> edge(N);
	for (int i{}; i < M; ++i)
	{
		int a, b;
		std::cin >> a >> b;
		--a; --b;
		edge[a].emplace(b);
		edge[b].emplace(a);
	}
	std::vector<int> flag(N);
	std::vector<int> root = { 0 };
	std::vector<int> reverse = { 0 };
	flag[0] = 1;
	while (true)
	{
		int target{};
		for (int v : edge[root.back()])
		{
			if (!flag[v])
			{
				target = v;
				break;
			}
		}
		if (target == 0)
		{
			break;
		}
		flag[target] = true;
		root.emplace_back(target);
	}
	while (true)
	{
		int target{};
		for (int v : edge[reverse.back()])
		{
			if (!flag[v])
			{
				target = v;
				break;
			}
		}
		if (target == 0)
		{
			break;
		}
		flag[target] = true;
		reverse.emplace_back(target);
	}
	std::cout << reverse.size() + root.size() - 1 << std::endl;
	for (auto ite = reverse.rbegin(); ite != std::prev(reverse.rend()); ++ite)
	{
		std::cout << (*ite) + 1 << " ";
	}
	for (auto v : root)
	{
		std::cout << (v + 1) << " ";
	}
	std::cout << std::endl;
}

Measured memory_bytes: 15736
#include <stdio.h>
int main(void){
    int N, K, X, Y, kane=0;
    scanf("%d%d%d%d", &N, &K, &X, &Y);
    for(int i=1; i<=N; i++){
        if(i<=K) kane+=X;
        else if(i>K) kane+=Y;
    }
    printf("%d", kane);
    return 0;
}

Measured memory_bytes: 1692
#include<iostream>
using namespace std;
 
int main(){
int n;
  bool c=false;
  char s[105];
  cin>>n;
  for(int i=0;i<n;i++){
  cin>>s[i];
    if(s[i]=='Y')c=true;
  }
if(c==true)cout<<"Four"<<endl;
  else cout<<"Three"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
using vint = vector<int>;
using vLL = vector<LL>;

int main(){
	int N, K;
	cin >> N >> K;
	vint v(N+1), vv(N+1);
	for(int i = 1;i <= N;i++)	cin >> v[i];
	for(int i = 1;i <= N;i++)	vv[N-i+1] = v[i];
	int ans = 0;
	for(int i = 1;i <= min(K, N);i++){
		for(int j = 0;j <= i;j++){
			vint vp;
			int cnt = K-i;
			int res = 0;
			for(int k = 1;k <= j;k++)	vp.push_back(v[k]);	
			for(int k = 1;k <= i-j;k++)	vp.push_back(vv[k]);
			sort(vp.begin(), vp.end());
			for(int k = 0;k < vp.size();k++){
				if(vp[k] < 0 && cnt > 0)	cnt--;
				else	res += vp[k];
			}
			ans = max(ans, res);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>

using namespace std;
typedef long long ll;

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


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()

S = [input().split() for _ in range(N)]

T = input()
flag = 0
cnt = 0
for i in range(N):
    if S[i][0] == T:
        flag = 1
    elif flag:
        cnt += int(S[i][1])
print(cnt)

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

bool isPalindromic(int n) {
  string s = to_string(n);
  string t = s;
  reverse(s.begin(), s.end());
  return s == t;
}

int main() {
  int a, b;
  cin >> a >> b;

  int res = 0;
  for (int i = a; i <= b; ++i) {
    if (isPalindromic(i)) ++res;
  }

  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3680
#include <bits/stdc++.h>
using namespace std;
inline int rd() {
    int x=0,f=1;char ch=getchar();
    while (ch>'9'||ch<'0') {if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int main() {
    long long n,m;
    cin >> n >> m;
    cout << 3LL * (n-__gcd(n,m));
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
long x[1000],y[1000];
vector<long>d;
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
		if((abs(x[i])+abs(y[i]))%2!=(abs(x[0])+abs(y[0]))%2)
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	for(int i=32;i>=0;i--)d.push_back(1LL<<i);
	d.push_back(1);
	d.push_back(1);
	if((abs(x[0])+abs(y[0]))%2==0)d.push_back(1);
	cout<<d.size()<<endl;
	for(int i=0;i<d.size();i++)cout<<d[i]<<(i+1==d.size()?"\n":" ");
	for(int i=0;i<n;i++)
	{
		long X=x[i],Y=y[i];
		string s="";
		for(int j=0;j<d.size();j++)
		{
			if(abs(X)>abs(Y))
			{
				if(X>0)
				{
					X-=d[j];
					s+="R";
				}
				else
				{
					X+=d[j];
					s+="L";
				}
			}
			else
			{
				if(Y>0)
				{
					Y-=d[j];
					s+="U";
				}
				else
				{
					Y+=d[j];
					s+="D";
				}
			}
		}
		cout<<s<<endl;
	}
}


Measured memory_bytes: 256