akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <deque>
#include <map>
#include <queue>
#include <climits>
#include <set>
#include <stack>

using namespace std;

#define ll long long
#define MAX 100000
#define MAX1 10000
#define MAX2 100000
#define inf 1000000000
#define eps 1e-12
#define MOD 1000000007

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    char c;
    cin >> c;
    if (c >= 'a' and c <= 'z') {
        cout << "a";
    } else {
        cout << "A";
    }

    return 0;
}

Measured memory_bytes: 3028
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
int dp[200001][5];
int main() {
	string S;
	cin >> S;
	memset(dp, -1, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j <= min(i, 4); j++) {
			if (dp[i][j] == -1) continue;
			for (int k = 1; k <= 4; k++) {
				if (i + k > S.size()) break;
				if (S.substr(i - j, j) != S.substr(i , k)) {
					dp[i + k][k] = max(dp[i + k][k], dp[i][j] + 1);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= 4; i++) ans = max(ans, dp[S.size()][i]);
	cout << ans << endl;
}


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

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

    vector <int> A(N); //食べた順番
    vector <int> B(N); //基本点
    vector <int> C(N-1); //コンボ点
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for(int i = 0; i < N; i++) {
        cin >> B[i];
    }
    for(int i = 0; i < N-1; i++) {
        cin >> C[i];
    }

    int ans = 0;
    int last_eat = 99999;
    int now_eat;
    for(int i = 0; i < N; i++) {
        now_eat = A[i];
        ans += B[now_eat-1];
        if(last_eat + 1 == now_eat) {
            ans += C[last_eat-1];
        }
        last_eat = now_eat;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repeq(i,a,b) for(int i=a;i<=(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int K=100;
map<string,int> mp;
const ll MOD = 998244353;
ll f(const string &s) {
    if(s.empty()) return 1;
    if(mp.count(s)) return mp[s];
    ll cnt = 0;
    if(s[0]=='0') cnt=(cnt+f(s.substr(1)))%MOD;
    else cnt=(cnt+2*f(s.substr(1)))%MOD;
    int n =sz(s);
    for(int k=1;k*2<=n;++k) {
        string t = s.substr(0,k);
        for(int l=k;(l+k)<=n;l+=k) {
            rep(j,0,k) t[j]=min(t[j],s[l+j]);
            cnt=(cnt+f(t)*f(s.substr(l+k)))%MOD;
        }
    }
    mp[s] = cnt;
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout<<f(s)<<endl;
}


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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const ll mod=1e9+7;
int main()
{
    cin.tie( 0 );
    ios::sync_with_stdio( false );
	
	int n,k;cin>>n>>k;
	
	int ans = n-k;
	if(k==1) ans=0;
	cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

struct Node {
  size_t v;
  bool used[20];
  char padding[4];

  Node() : v(0) {
    memset(used, false, 20);
  }
};

static vector<int> FindPossibleValues(const size_t* A, int n, size_t size) {
  vector<int> values(size + 1);
  values[size] = 1;

  queue<Node> q;
  Node root;
  q.push(root);
  while (!q.empty()) {
    const Node p = q.front();
    q.pop();

    for (int i = 0; i < n; ++i) {
      if (p.used[i] || values[p.v + A[i]])
        continue;
      Node new_node;
      new_node.v = p.v + A[i];
      memcpy(new_node.used, p.used, static_cast<size_t>(n));
      new_node.used[i] = true;
      q.push(new_node);
      values[new_node.v] = 1;
    }
  }

  return values;
}

int main() {
  int n;
  size_t A[20];

  scanf("%d", &n);
  size_t sum = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%lu", &A[i]);
    sum += A[i];
  }

  vector<int> values = FindPossibleValues(A, n, sum);

  int q;
  scanf("%d", &q);
  size_t m = 0;
  for (int i = 0; i < q; ++i) {
    scanf("%lu", &m);
    if (m < values.size() && values[m]) {
      printf("yes\n");
    } else {
      printf("no\n");
    }
  }

  return 0;
}

Measured memory_bytes: 1060
#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(){
  ll k, q;
  cin >> k >> q;
  vector<ll> ans(q);
  ll d[k];
  rep(i,k) cin >> d[i];
  rep(i,q) {
    ll n, x, m;
    cin >> n >> x >> m;
    ll dm[k];
    ll s = 0;
    rep(j,k) {
      dm[j] = d[j] % m;
      if(dm[j] == 0) dm[j] = m;
      s += dm[j];
    }
    ll f = x;
    f += s * ((n-1) / k);
    rep(j,(n-1) % k) f += dm[j];
    ans[i] = n - 1 - (f / m - x / m);
  }
  for(auto t : ans) cout << t << endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>

using namespace std;
#define MAXN 100001
typedef long long ll;
ll a[MAXN*3];
int main(){
    int N;
    cin >> N;
    for(int i=0;i<3*N;i++){
        cin >> a[i];
    }
    sort(a,a+3*N);
    ll ans = 0;
    for(int i=3*N-2;i>=N;i-=2){
        ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
<?php
// Your code here!
$day = trim(fgets(STDIN));
$c = explode(' ',trim(fgets(STDIN)));

for ($i = 0; $i < $day; $i++) {
     $scores = explode(' ',trim(fgets(STDIN)));
     foreach($c as $ck => $cv){
         $scores[$ck] -= $cv * (365 - $i -1);
     }
     arsort($scores);
     echo array_key_first($scores) +1;
     if($i != 364){
        echo "\n";
     }
}



?>




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

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int ans=-1,sum=0,cnt=0;
  while(ans==-1&&cnt++<2000000)
    if(sum%60+a<c||sum%60>c)sum+=a+b;
    else ans=sum+(c-sum%60);
  cout <<ans<<endl;
  return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

int solve(int s, int N, vector<int> &C, vector<int> &S, vector<int> &F){
    int time = 0;
    for(int i=s; i<N-1; i++){
        time = max(time, S[i]);
        int tmp = (time - S[i]) % F[i];
        int j = (time - S[i]) / F[i];
        if(tmp != 0) j++;
        time = S[i] + j * F[i];
        time += C[i];
    }
    return time;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> C(N-1), S(N-1), F(N-1);
    for(int i=0; i<N-1; i++){
        cin >> C[i] >> S[i] >> F[i];
    }
    for(int i=0; i<N; i++){
        cout << solve(i, N, C, S, F) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import math
n = int(input())
cout = 0

def func(a):
    if a < 2:
        return False
    elif a == 2:
        return True
    elif a % 2 == 0:
        return False
    b = int(math.floor(math.sqrt(a)))
    for j in range(3,b+1,2):
        if a % j == 0:
            return False
    return True

for i in range(n):
    a = int(input())
    if func(a):
        cout += 1
print(cout)


Measured memory_bytes: 5676
#include <bits/stdc++.h> 
 
using namespace std;
 
 template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const LL MOD=(LL)1e9+7LL; 

int main(){
    int N;cin>>N;
    vector<LL>p((N/2+N%2),0);
    REP(i,N){
        int a;cin>>a;
        p[a/2]++;
    }
    bool flag=true;
    REP(i,SZ(p)){
        if(N%2==1&i==0){
            if(p[i]!=1){
                flag=false;break;
            }
        }else{
            if(p[i]!=2){
                flag=false;break;
            }
        }
    }
    if(!flag){
        cout<<0<<endl;return 0;
    }
    LL res=1LL;
    REP(i,SZ(p))res=(res*p[i]%MOD);
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            var HN = ReadSplitLong();
            var A = ReadSplitLong();

            Func<long, bool> func = hp =>
            {
                for (int i = 0; i < HN[1]; i++)
                {
                    hp -= A[i];

                    if (hp <= 0)
                    {
                        return true;
                    }
                }

                return false;
            };

            YesOrNo(func(HN[0]));
        }

        static List<long> ReadLines(long n)
        {
            var l = new List<long>();
            for (long i = 0; i < n; i++)
            {
                l.Add(ReadLong());
            }
            return l;
        }

        static void YESOrNO(bool e) => Println(e ? "YES" : "NO");

        static void YesOrNo(bool e) => Println(e ? "Yes" : "No");

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int SumDigits(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
        static long Lcm(long a, long b) => a / Gcd(a, b) * b;

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());
        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}



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

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

    string S;
    cin >> S;

    vector<int> x(26);

    for(int i = 0; i < S.length(); i++) {
        x[S[i] - 'a']++;
    }

    for(int i = 0; i < 26; i++) {
        if(x[i] == 0) {
            cout << char(i + 'a') << endl;
            return 0;
        }
    }

    cout << "None" << endl;
}

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

int64_t calc(vector<int64_t> &memo, int x){
  if(x == 0){
    return memo.at(x) = 2;
  }else if(x == 1){
    return memo.at(x) = 1;
  }
  
  if(memo[x] != 0){
    return memo[x];
  }else{
    return memo[x] = calc(memo, x-2) + calc(memo, x-1);
  }
}

int main(){
  int n = 0;
  cin >> n;
  vector<int64_t> memo(n+1);
  cout << calc(memo, n) << endl;
}

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

int main(void){
    std::string s;
    std::cin >> s;

    if(s.at(0) == s.at(1) && s.at(1) == s.at(2)){
            std::cout << "Yes" << std::endl;
            return 0;
    }
    
    if(s.at(1) == s.at(2) && s.at(2) == s.at(3)){
            std::cout << "Yes" << std::endl;
            return 0;
    }

    std::cout << "No" << std::endl;
    return 0;

}

Measured memory_bytes: 256
import java.io.{BufferedReader, InputStreamReader}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val Array(n, m) = in.readLine().split("\\s+").map(_.toInt)

    val pss = (1 to m).map { _ =>
      in.readLine().split("\\s+") match {
        case Array(p, s) => (p.toInt, s)
      }
    }

    var penalties = 0
    var acs = 0
    val results = Array.ofDim[Int](n)

    pss.foreach {
      case (p, s) =>
        if (results(p - 1) != -1) {
          if (s == "AC") {
            penalties += results(p - 1)
            results(p - 1) = -1
            acs += 1
          } else {
            results(p - 1) += 1
          }
        }
    }

    System.out.println(List(acs, penalties).mkString(" "))
  }
}


Measured memory_bytes: 76588
open =  "Opened by {}"
close = "Closed by {}"
unknown = "Unknown {}"
lock = True

n = input()

keys = []
for _ in xrange(n):
	keys.append(raw_input())
	
m = input()
operator = []
for _ in xrange(m):
	operator.append(raw_input())
	
for var in operator:
	if var in keys:
		if lock:
			print open.format(var)
			lock = False
		else:
			print close.format(var)
			lock = True
	else:
		print unknown.format(var)

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

int main() {
  int a,b;
  cin >> a >> b;
  if((a + b) % 2 == 0){
    cout <<(a+b)/2 << endl;
  }else{
    cout << (a+b)/2 + 1 << endl;
  }
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define str(n) to_string(n)
#define int(w) stoi(w)
#define len(l) l.size()
#define append(l,i) l.push_back(i)
int main() {
    int n;
    cin>>n;
    vector<long long> l;
    rep(i,n){
        long long n1;
        cin>>n1;
        append(l,n1);
    }
    long long n1=0,ans1=0;
    long long n2=0,ans2=0;
    rep(i,n){
        n1+=l.at(i);
        if (i%2==0){
            if (n1>0){
                continue;
            }
            else{
                ans1+=1-n1;
                n1=1;
            }
        }
        else{
            if (n1<0){
                continue;
            }
            else{
                ans1+=n1+1;
                n1=-1;
            }

        }

    }
    rep(i,n){
        n2+=l.at(i);
        if (i%2==1){
            if (n2>0){
                continue;
            }
            else{
                ans2+=1-n2;
                n2=1;
            }
        }
        else{
            if (n2<0){
                continue;
            }
            else{
                ans2+=n2+1;
                n2=-1;
            }

        }

    }
    cout<<min(ans1,ans2)<<endl;
    

    return 0;
}

Measured memory_bytes: 1400
#include<stdio.h>
int main(){
  int n,m,i,sum=0;
  scanf("%d",&n);
  int t[n+1];
  for(i=0;i<n;i++){
    scanf("%d",&t[i]);
    sum+=t[i];
  }
  scanf("%d",&m);
  int p[m+1][2];
  for(i=0;i<m;i++)
    scanf("%d%d",&p[i][0],&p[i][1]);
  for(i=0;i<m;i++)
    printf("%d\n",sum-t[p[i][0]-1]+p[i][1]);
  return 0;
}

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

int N, K;
int x[MAX_N];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N;
  cin >> K;
  rep(i, N) cin >> x[i];

  int total = 0;
  rep(i, N){
      total += min( abs(x[i] - K), abs(x[i]) ) * 2;
  }

  cout << total << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main(){
    int a,b,gcd;
    cin >> a >> b;
    int a1=max(a,b);
    int b1=min(a,b);
    gcd=min(a,b);
    while((b1!=-1)&&max(a1,b1)%gcd!=0){
        gcd=a1%b1;
        a1=b1;
        b1=gcd;
        if(gcd==0){
            gcd=b1;
            break;
        }
    }
    cout << gcd << endl;
    return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>
int main (){
	char str [20];
	scanf ("%s", str);
	 for (int i = 0; i < 19; i++) {
    if (i == 5 || i == 13) {
        printf(" ");
        continue;
    }
    printf("%c", str[i]);
	}
    
	puts("");
    
	return 0;
    }

Measured memory_bytes: 1616
#include <iostream>

using namespace std;

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

	int ans = 1, max;
	cin >> max;

	for (int i = 1, temp; i < N; i++){
		cin >> temp;
		if(temp >= max){
			ans++;
			max = temp;
		}
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main () {
  vector<bool>sosu(1000005, true);
  vector<long long>num;
  sosu[0] = sosu[1] = false;
  for (int i = 0; i < 1000005; i ++) {
    if (sosu[i]) {
      num.push_back((long long)i);
      for (int j = 2; j <= 1000005 / i; j ++) {
        if (i * j == 1000005) continue;
        sosu[i * j] = false;
      }
    }
  }
  int N = (int)num.size();
  int ans = 0;
  long long A;
  cin >> A;
  for (int i = 0; i < N; i ++) {
    int kj = 0;
    while (A % num[i] == 0) {
      kj ++;
      A /= num[i];
    }
    int mi = 0;
    int ma = 100;
    if (kj == 0) ma = mi = 1;
    while (mi != ma) {
      //cout << kj << ' ';
      int mu = (mi + ma) / 2;
      int p = mu * (mu + 1);
      p /= 2;
	  //cout << p << ' ' << mi << ' ' << mu << ' ' << ma << endl;
      if (p > kj) ma = mu;
      else mi = mu + 1;
    }
    //cout << ma << endl;
    ans += ma;
    ans --;
  }
  if (A != 1) ans ++;
  cout << ans << endl;
}



Measured memory_bytes: 4248
#include <iostream>
#include <cstdio>
#include <string.h>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
using namespace std;

int T, D, L;

void solve()
{
  int res = 0;
  int f = 0;
  rep(i, T-1) {
    int x;
    cin >> x;
    if (x >= L) {
      res++;
      f = D - 1;
    } else if (f) {
      res++;
      f--;
    }
  }
  int t;
  cin >> t;
  cout << res << endl;
}

bool init()
{
  cin >> T >> D >> L;
  return T > 0;
}

int main(void)
{
  while (init()) {
    solve();
  }
}



Measured memory_bytes: 3076
#include<cstdio>
#include<iostream>

using namespace std;

#define fr(i,a,b) for(register long long i=a;i<=b;i++)
#define fv(i,a,b) for(register long long i=a;i>=b;i--)
#define fmax(a,b) ((a)>(b)?(a):(b))
#define fmin(a,b) ((a)<(b)?(a):(b))

long long q,a,b;

inline long long v_in(){
	char ch=getchar();long long sum=0,f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch^48),ch=getchar();
	return sum*f;
}

long long found(long long x,long long y){
	if(y>=x) return y+1;
	else return y;
}

bool judge(long long x){
	int d=x>>1;
	fr(i,d-200,d+200) if(found(a,i)*found(b,x-i+1)>=a*b) return false;
	return true;
}

int main(){
	scanf("%lld",&q);
	while(q--){
		scanf("%lld%lld",&a,&b);
		long long l=0,r=2000000000,ans=0;
		while(l<r){
			long long mid=(l+r+1)>>1;
			if(judge(mid)) l=mid;
			else r=mid-1;
		}
		printf("%lld\n",l);
	}
	return 0;
}

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

int main() {
    int N; cin >> N;
    vector<int> D(N);
    rep(i, N){
        cin >> D[i];
    }

    sort(D.begin(), D.end());
    int x = N/2;
    int ans = D[x] - D[x-1];

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 3756
from collections import defaultdict as dd
N,A = map(int,input().split())
src = list(map(int,input().split()))

dp = [dd(lambda:0)]
dp[0][0] = 1
for i,a in enumerate(src):
    dp.append(dd(lambda:0))
    for j in reversed(range(i+1)):
        for k,v in dp[j].items():
            dp[j+1][k+a] += v
ans = 0
for i in range(1,N+1):
    ans += dp[i][i*A]
print(ans)

Measured memory_bytes: 5524
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<iomanip>
#include<map>
#include<fstream>
#include<queue>

using namespace std;


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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  map<string,int> mp;
  int cnt=0;
  rep(i,n){
    string s; cin>>s;
    mp[s]++;
    cnt = max(cnt,mp[s]);
  }
  
  vector<string> p;
  for(auto to:mp){
    if(to.S==cnt){ p.emplace_back(to.F); }
  }
  sort(p.begin(),p.end());
  for(auto q:p){
    cout << q << endl;
  }
  return 0;
}


Measured memory_bytes: 26868
/*
 * FileName:     C
 * CreatedDate:  2020-05-31 20:58:51 +0900
 * LastModified: 2020-05-31 22:00:20 +0900
 */

#include <stdio.h>

int main(void){
    long double a,b;
    scanf("%Lf%Lf",&a,&b);
    printf("%lld\n",(long long int)(a*b));
    return 0;
}


Measured memory_bytes: 1760
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i)
      ans += j;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3600
#include <iostream>
using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int mat[100][100] = {};
	int vec[100] = {};

	int i, j, k;
	for(i = 0; i < n; ++i){
		for(j = 0; j < m; ++j){
			cin >> k;
			mat[i][j] = k;
		}
	}

	for(i = 0; i < m; ++i){
		cin >> k;
		vec[i] = k;
	}

	for(i = 0; i < n; ++i){
		int t = 0;
		for(j = 0; j < m; ++j){
			t += mat[i][j] * vec[j];
		}
		cout << t << "\n";
	}

	return 0;
}

Measured memory_bytes: 1208
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define all(a) (a).begin(), (a).end()


int main(){
    int a, b;
    cin >> a >> b;
    if(a < b){
        int ans = 0;
        for(int i = 0; i < b; i++){
            ans*=10;
            ans+=a;
        }
        cout << ans << endl;
    }else{
        int ans = 0;
        for(int i = 0; i < a; i++){
            ans*=10;
            ans+=b;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3488
N = int(input())
A = list(map(int,input().split()))

x2 = [0 for _ in range(N)]

for i in range(N):
    x2[0] += (-1)**i * A[i]

for j in range(1,N):
    x2[j] = 2*A[j-1] - x2[j-1]

print(*x2)

Measured memory_bytes: 14032
#include <bits/stdc++.h>
#define endl '\n'
// using namespace std;

std::string hasSeven(int N) {
    while(N>0){
         
        int tmp = N%10;
        N = N/10;
        if (tmp == 7) {
            return "Yes";
        }
    }
    return "No";
}
int main() {
    int N;
    std::cin >> N;
    std::cout << hasSeven(N) << endl;
    return 0;
}

Measured memory_bytes: 3596
#!/usr/bin/env perl

use strict;
use warnings;
use 5.18.2;

my $input = do { local $/; <> };

chomp $input;

my ($amount, $numbers) = split /\n/, $input;

my @numbers = split / /, $numbers;

say run(\@numbers);

sub run {
    my ($numbers, $count) = @_;

    $count //= 0;

    if (!has_odd_number(\@numbers)) {
        $count++;
        @$numbers = div_by_2(\@numbers);
    } else {
        return $count;
    }

    run($numbers, $count);
}

sub div_by_2 {
    my $numbers = shift;
    return map { $_ / 2 } @$numbers;
}

sub has_odd_number {
    my $numbers = shift;
    return grep { $_ % 2 == 1 } @$numbers;
}

Measured memory_bytes: 768
def cross(a, b):
  return a.real * b.imag - a.imag*b.real

def convex_hull(p):
  pp = sorted(p, key=lambda x:(x.imag, x.real))
  n = len(pp)
  ans = [0] * (n+1)
  j = 0

  #上側を入れていく
  for i in range(n):
    while j > 1 and cross(ans[j-1] - ans[j-2], pp[i]-ans[j-1]) < 0: #常に次の点が下側に
      j -= 1
    ans[j] = pp[i]
    j += 1
  k = j
  #下側を入れていく
  for i in range(n-2, -1, -1):
    while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: #常に次の点が下側に
      j -= 1
    ans[j] = pp[i]
    j +=1
  return ans[0:j-1]

n = int(input())
p=[]
for i in range(n):
  x,y = list(map(int, input().split()))
  p.append(complex(x,y))
ans = convex_hull(p)
print(len(ans))

for i in ans:
  print(int(i.real), int(i.imag))



Measured memory_bytes: 22948
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def nC2(n):
    return n*(n-1) // 2

N = INT()
A = LIST()

C = Counter(A)
total = 0
for k, v in C.items():
    total += nC2(v)

ans = [0] * N
for i, a in enumerate(A):
    ans[i] = total - nC2(C[a]) + nC2(C[a]-1)
[print(a) for a in ans]


Measured memory_bytes: 28564
a = int(input())
b = list(input() for i in range(a))
c = set(b)
d = 0

if len(c)!=a:
  print("No")
else:
  for i in range(a-1):
    if b[i][-1]!=b[i+1][0]:
      d = 1
  else:
    if d==0:
      print("Yes")
    else:
      print("No")

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

#define T1 1000000LL
#define T2 1000LL

long long W, H, X, Y, R;
long long x[1000][1000];
long long d[1000][1000];
long long p1, p2, p3;
long long y_1[1000000], y_2[1000000], cnt, cnt2, v, minx;

priority_queue<long long, vector<long long>, greater<long long>> Q, S;

int main() {
	while (true) {
		cnt = 1; cnt2 = 1; minx = 1145141919810LL;
		memset(x, 51, sizeof(x));
		memset(d, 51, sizeof(d));
		cin >> R;
		if (R == 0) { break; }
		cin >> W >> H >> X >> Y;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				scanf("%lld",&x[i][j]);
			}
		}
		d[Y][X] = 0;
		Q.push(Y*T2 + X);
		while (!Q.empty()) {
			p1 = Q.top() / T1;
			p2 = (Q.top() / T2) % T2;
			p3 = Q.top() % T2;
			if (max(p1, x[p2 - 1][p3]) < d[p2 - 1][p3]) {
				d[p2 - 1][p3] = max(p1, x[p2 - 1][p3]);
				S.push(d[p2 - 1][p3] * T1 + (p2 - 1)*T2 + p3);
			}
			if (max(p1, x[p2 + 1][p3]) < d[p2 + 1][p3]) {
				d[p2 + 1][p3] = max(p1, x[p2 + 1][p3]);
				S.push(d[p2 + 1][p3] * T1 + (p2 + 1)*T2 + p3);
			}
			if (max(p1, x[p2][p3 - 1]) < d[p2][p3 - 1]) {
				d[p2][p3 - 1] = max(p1, x[p2][p3 - 1]);
				S.push(d[p2][p3 - 1] * T1 + p2*T2 + (p3 - 1));
			}
			if (max(p1, x[p2][p3 + 1]) < d[p2][p3 + 1]) {
				d[p2][p3 + 1] = max(p1, x[p2][p3 + 1]);
				S.push(d[p2][p3 + 1] * T1 + p2*T2 + (p3 + 1));
			}
			Q.pop();
			while (!S.empty()) {
				Q.push(S.top());
				S.pop();
			}
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				y_1[cnt] = d[i][j];
				cnt++;
			}
		}
		memset(x, 51, sizeof(x));
		memset(d, 51, sizeof(d));
		cin >> W >> H >> X >> Y;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				scanf("%lld",&x[i][j]);
			}
		}
		d[Y][X] = 0;
		Q.push(Y*T2 + X);
		while (!Q.empty()) {
			p1 = Q.top() / T1;
			p2 = (Q.top() / T2) % T2;
			p3 = Q.top() % T2;
			if (max(p1, x[p2 - 1][p3]) < d[p2 - 1][p3]) {
				d[p2 - 1][p3] = max(p1, x[p2 - 1][p3]);
				S.push(d[p2 - 1][p3] * T1 + (p2 - 1)*T2 + p3);
			}
			if (max(p1, x[p2 + 1][p3]) < d[p2 + 1][p3]) {
				d[p2 + 1][p3] = max(p1, x[p2 + 1][p3]);
				S.push(d[p2 + 1][p3] * T1 + (p2 + 1)*T2 + p3);
			}
			if (max(p1, x[p2][p3 - 1]) < d[p2][p3 - 1]) {
				d[p2][p3 - 1] = max(p1, x[p2][p3 - 1]);
				S.push(d[p2][p3 - 1] * T1 + p2*T2 + (p3 - 1));
			}
			if (max(p1, x[p2][p3 + 1]) < d[p2][p3 + 1]) {
				d[p2][p3 + 1] = max(p1, x[p2][p3 + 1]);
				S.push(d[p2][p3 + 1] * T1 + p2*T2 + (p3 + 1));
			}
			Q.pop();
			while (!S.empty()) {
				Q.push(S.top());
				S.pop();
			}
		}
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				y_2[cnt2] = d[i][j];
				cnt2++;
			}
		}

		sort(y_1, y_1 + cnt);
		sort(y_2, y_2 + cnt2);

		for (int i = 0; i < cnt; i++) {
			v = R - i;
			if (v >= 0 && v < cnt2) {
				minx = min(minx, y_1[i] + y_2[v]);
			}
		}
		cout << minx << endl;
	}
}

Measured memory_bytes: 22820
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int a = scn.nextInt();
      	int b = scn.nextInt();
      	int aa = a*n;
      	int ans = 0;
      	if(aa>=b){
          ans = b;
        }else{
          ans = aa;
        }
      	System.out.println(ans);
	}
}

Measured memory_bytes: 35996
#include <iostream>
#include <cmath>
#include <string>
#include <typeinfo>
#include <climits>
#include <algorithm>
#include <cctype>
#include <stdio.h>
#include <cstdlib>
using namespace std;

int main(){
    char s[2][4];
    for(int i=0;i<2;i++){
        cin >> s[i];
    }
    if(s[0][0]==s[1][2] && s[0][1]==s[1][1] && s[0][2]==s[1][0]){
        cout << "YES";
    }else{
        cout << "NO";
    }
}

Measured memory_bytes: 256
n=int(input())
abc=[list(map(int,input().split())) for _ in [0]*(n-1)]
q,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in [0]*q]
k-=1
tree=[[] for _ in [0]*n]
dist=[-1]*n
dist[k]=0
[tree[a-1].append([b-1,c]) for a,b,c in abc]
[tree[b-1].append([a-1,c]) for a,b,c in abc]

q=[k]

while(q):
	qq=[]
	for i in q:
		for j,k in tree[i]:
			if dist[j]<0:
				dist[j]=dist[i]+k
				qq.append(j)
	q=qq

for x,y in xy:
	print(dist[x-1]+dist[y-1])

Measured memory_bytes: 91044
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
using ll = long long;
using namespace std;
 
int main(){
    string s;
    cin >> s;
    int p = 0;
    bool flag;
    string t = "";
    string dic[6] = { "dreameraser", "dreamerase", "dreamer", "dream", "eraser", "erase"};
    while(s != t){
        flag = true;
        REP(i, 6){
            if(s.substr(p, dic[i].length()) == dic[i]){
                t += dic[i];
                p += dic[i].length();
                flag = false;
                break;
            }
        }
        if(flag){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 640
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input


def main():
    h, n = lin()
    a = lin()
    sm = sum(a)
    print('Yes' if h<=sm else 'No')



            
        

        
main()
# threading.Thread(target=main).start()


Measured memory_bytes: 53316
#include<stdio.h>

int main() {
	int n;
	int len;
	int max, sum = 0;

	scanf("%d",&n);
	scanf("%d", &len);
	
	max = len;


	for (int i = 1;i < n;i++) {
		scanf("%d", &len);
		if (len > max) {
			sum += max;
			max = len;
		}
		else {
			sum += len;
		}
	}

	if (max < sum) {
		printf("Yes");
	}
	else {
		printf("No");
	}
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

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

int main() {
    int n, W; cin >> n >> W;
    vector<int> v(n), w(n);
    REP(i, n) cin >> v[i] >> w[i];
    
    auto dp = make_v(n + 1, W + 1, 0);
    
    REP(i, n)REP(j, W + 1) {
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        if (j + w[i] <= W) {
            dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }

    cout << dp[n][W] << endl;

    return 0;
}



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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 110, M = 110, mod = 1e9 + 7;

int n, k;

int main()
{
	cin >> n >> k;
	
	int res = 0;
	for (int i = k; i <= n + 1; i ++ )
	{
		int l = (LL)(i - 1) * i / 2 % mod;
		int r = (LL)(2 * n - i + 1) * i / 2 % mod;
		res = (res + r - l + 1) % mod;
	}
	
	res = (res % mod + mod) % mod;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
  int cnt[26] = {};
  char ch;
  while(cin >> ch) {
	if(isalpha(ch)) {
	  cnt[tolower(ch) - 'a']++;
	}
  }
  for(int i = 0; i < 26; i++) {
	cout << char(i + 'a') << " : " << cnt[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3088
#include <stdio.h>

int A[2000010];
int n;

void maxheapify(int i) {
    if (i > n) {
        return;
    }
    int left = i * 2, right = i * 2 + 1, largest = i;
    if (left <= n && A[left] > A[largest]) {
        largest = left;
    }
    if (right <= n && A[right] > A[largest]) {
        largest = right;
    }
    if (largest != i) {
        int t = A[i];
        A[i] = A[largest];
        A[largest] = t;
        maxheapify(largest);
    }
}

void buildHeap() {
    for (int i = n / 2; i >= 1; i--) {
        maxheapify(i);
    }
}

void buildHeap2() {
    for (int i = 2; i <= n; i++) {
        int j = i;
        while (j > 1 && A[j / 2] < A[j]) {
            int t = A[j / 2];
            A[j / 2] = A[j];
            A[j] = t;
            j /= 2;
        }
    }
}

void insert(int x) {
    n++;
    A[n] = x;
    int j = n;
    while (j > 1 && A[j / 2] < A[j]) {
        int t = A[j / 2];
        A[j / 2] = A[j];
        A[j] = t;
        j /= 2;
    }
}

int getMaxVal() {
    int val = A[1];
    A[1]=A[n];
    n--;
    maxheapify(1);
    return val;
}

int main() {
    char cmd[100];
    int x;
    while(1) {
        scanf("%s %d", cmd, &x);
        if (cmd[2]=='d'){
            break;
        }else if(cmd[0] =='i'){
            insert(x);
        }else{
            printf("%d\n",getMaxVal());
        }
    }
    return 0;
}



Measured memory_bytes: 6496
import java.util.Scanner;

public class Main {
    
    public static int Fibonacci(int n) {
        int[] fib = new int[50];
        fib[0] = fib[1] = 1;
        for(int i = 2; i <= n; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        return fib[n];
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();        
        System.out.println(Fibonacci(n));
    }
    
}

Measured memory_bytes: 26160
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename A,typename B>istream&operator>>(istream&is,pair<A,B> &p){is>>p.fi>>p.se;return is;}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B> &p){os<<"("<<p.fi<<","<<p.se<<")";return os;}
template<typename T>istream&operator>>(istream&is,vector<T> &t){REP(i,t.size())is>>t[i];return is;}
template<typename T>ostream&operator<<(ostream&os,const vector<T>&t){os<<"{";REP(i,t.size()){if(i)os<<",";os<<t[i];}cout<<"}";return os;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n;
    cin>>n;
    vi vec(n);
    cin>>vec;
    int ans=0;
    REP(i,n){
        if(vec[i]!=i+1){
            ans++;
        }
    }
    if(ans<=2){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((LL)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	return modpow(x, MOD-2);
}

LL factorial(LL x){
	static vector<LL> memo((int)2e5, 0);
	memo[1]=1;
	if(x<=1)return 1;
	if(memo[x]>=1)return memo[x];
	int i;
	for(i=memo.size()-1;!memo[i];--i);
	LL res = memo[i];
	for(i=i+1;i<=x;++i){
		res *= i;
		res %= MOD;
		memo[i] = res;
	}
	return memo[x];
}


LL C(LL a, LL b){
	return factorial(a) * modinv(factorial(b) * factorial(a-b) % MOD) % MOD;
}

LL H(LL a, LL b){
	return C(a+b, b);
}

int main(){
	LL h, w, a, b;
	cin >> h >> w >> a >> b;
	LL ans = 0;
	for(int x = b+1;x<=w;++x){
		ans += H(x-1, h-a-1) * H(w-x, a-1);
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
const int N=5005;
int n,m;
int Fac[N],Inv[N];
int C(int n,int m){
	if (m<0||m>n)
		return 0;
	return (LL)Fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
int dp[N][N];
int main(){
	n=read(),m=read();
	Fac[0]=1;
	For(i,1,m)
		Fac[i]=(LL)Fac[i-1]*i%mod;
	Inv[m]=Pow(Fac[m],mod-2);
	Fod(i,m,1)
		Inv[i-1]=(LL)Inv[i]*i%mod;
	dp[0][1]=1;
	For(i,1,n){
		For(j,1,m){
			int v=dp[i-1][j];
			if (!v)
				continue;
			int val=(LL)v*(j+1)%mod;
			Add(dp[i][j],val);
			Del(dp[i][j+1],val);
			val=(LL)v*j*2%mod;
			Add(dp[i][j+1],val);
		}
		For(j,1,m)
			Add(dp[i][j],dp[i][j-1]);
	}
	int ans=0;
	For(i,1,m)
		Add(ans,(LL)dp[n][i]*C(m-1,i-1)%mod);
	cout<<ans<<endl;
	return 0;
}

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

int main() {
    int n;
    cin >> n;
    int odd = 0;
    rep(i, n) {
        if ((i + 1) % 2) odd++;
    }
    out(float(odd) / n);
    return 0;
}


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

int main(){
    int n;
    cin>>n;
    for(int i=1;;i++){
        if(i*i>n){
            cout<<(i-1)*(i-1)<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3604
# coding : UTF-8

n = gets.to_i

n.times do
   score = 0
   runner = 0
   out = 0
   loop do
      event = gets
      case event
         when /HIT/
            runner += 1
            if runner == 4
              runner = 3
              score += 1
            end
         when /HOMERUN/
            score += runner + 1
            runner = 0
         when /OUT/
            out += 1
      end
      break if out == 3
   end
   puts score
end

Measured memory_bytes: 5396
input_lines = raw_input()
n1_n2_n3 = input_lines.rstrip().split(" ")
n1 = int(n1_n2_n3[0])
n2 = int(n1_n2_n3[1])
n3 = int(n1_n2_n3[2])
num_list = []
num_list.append(n1)
num_list.append(n2)
num_list.append(n3)
num_list.sort()
print str(num_list[0]) + " " + str(num_list[1]) + " " + str(num_list[2])

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

int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    while (n--) {
        int x;
        scanf("%d", &x);
        while (x % 2 == 0) {
            ans++;
            x /= 2;
        }
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
N_X = list(map(int,input().split()))
data = list(map(int,input().split()))
k = 0

for i in data:
    data[k] = abs(i - N_X[1])
    k += 1

m = min(data)
a = []
for i in range(1,m+1):
    if m % i == 0:
        a.append(i)
        a.append(int(m/i))
    if i**2 > m:
        break

a.sort()
a.reverse()

for i in a:
    if all(c%i == 0 for c in data):
        print(i)
        break
        

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

using namespace std;

#define M_DEBUG if (0)
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


/******************************************************************************
	typedef
******************************************************************************/
using lint = long long;
typedef unsigned long long int ullint;



/******************************************************************************
	Main
******************************************************************************/
int main()
{
    string s;
    cin >> s;
    assert(s.size() >= 3 && s.size() <= 100);
	string rev_s = s;
	reverse(rev_s.begin(), rev_s.end());

    string ret = "Yes";

    if (s != rev_s) {
        ret = "No";
    }

    string sub_left = s.substr(0, (s.size()-1) / 2);
    string rev_sub_left = sub_left;
    reverse(rev_sub_left.begin(), rev_sub_left.end());
    M_DEBUG { cout << "sub_left: " << sub_left << endl; }
    if (ret == "Yes" && rev_sub_left != sub_left) {
        ret = "No";
    }

    string sub_right = s.substr(((s.size()+3) / 2) - 1, s.size());
    string rev_sub_right = sub_right;
    reverse(rev_sub_right.begin(), rev_sub_right.end());
    M_DEBUG { cout << "sub_right: " << sub_right << endl; }
    if (ret == "Yes" && rev_sub_right != sub_right) {
        ret = "No";
    }

	cout << ret << endl;

	return 0;
}


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

int main() {
	int n,k;
	cin>>n>>k;
	long double ans =0.0;
	for(int i=1;i<=n;++i)
	{
	    double y=(double)k/i;
	    double temp=log(y)/log(2);
	    int temp1=ceil(temp);
	    //cout<<temp1<<" ";
	    if(i>=k)
	    {
	        ans+=1;
	    }
	    else
	    {
	        ans+=pow(0.5,temp1);
	    }
	}
	ans=ans*(1.0/n);
	cout<<setprecision(16)<<ans<<endl;
}


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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  ll m = (ll)1e15 + 1;
  for (int i = 0; i < 5; i++) {
    ll a;
    cin >> a;
    m = min(m, a);
  }
  cout << 4 + (n + m - 1) / m << '\n';
  return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int n;
		while((n=sc.nextInt())!=0) {
			solve(n);
		}
	}
	static void solve(int n) {
		long ans = 0L;
		for(int warusu = 5;warusu<=n;warusu*=5) {
			ans += n / warusu;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 26116
#include <stdio.h>

int get_len(int a, int b) {
	int ans;

	ans = a - b;
	
	if(ans < 0)
		return -ans;
	else
		return ans;
}

int main(void) {
	int x, a, b, la, lb;

	scanf("%d %d %d", &x, &a, &b);

	la = get_len(a, x);
	lb = get_len(b, x);

	if(la < lb)
		printf("A");
	else
		printf("B");

	return 0;
}

Measured memory_bytes: 128