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

int main(){
	int n;
	long x;
	cin >> n >> x;
	vector<long> a(n);
	for (int i=0; i<n; i++){
		cin >> a.at(i);
	}
	sort(a.begin(), a.end());
	int num=0;
	long sum=0;
	for(int i=0; i<n; i++){
		sum += a.at(i);
	}
	if(sum == x) {
		num = n;
	}
	if(sum != x) {
		long newsum=0;
		for(int i=0; i<n-1; i++){
			newsum += a.at(i);
			if(newsum > x) {
				break;
			}
			if(newsum <= x) {
				num++;
			}
		}
	}
	cout << num << endl;
}



Measured memory_bytes: 3556
#include <stdio.h>

int main(void){
	int n,a[100],c=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(!i)continue;
		if(a[i]==a[i-1]){
			c++;
			i++;
			scanf("%d",&a[i]);
			if(a[i-2]+a[i]>10000)a[i-1]=0;
			else a[i-1]=a[i-2]+a[i];
		}
	}
	printf("%d\n",c);	
	return 0;
}

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

#define int long long

#define REP(i,n) for(int i=0;i<n;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 pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 99999999999
 
using namespace std;

int32_t main(){
    vector<int> n(3);
    REP(i, 3) cin >> n[i];
    SORT(n);

    if(n[2]%2){
        cout << n[0]*n[1] << endl;
    }
    else{
        cout << 0 << endl;
    }
}

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

#define M 1046527
#define NIL -1
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
  else return 0;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key%M; }
int h2(int key){ return 1+key%(M-1); }

int find(char str[]){
 long long key,i,h;
 key=getKey(str);
 for(i=0;;i++){
 h=(h1(key)+i*h2(key))%M;
 if(strcmp(H[h],str)==0){return 1;}
 else if(strlen(H[h])==0){return 0;}
}
return 0;
}

int insert(char str[]){
long long key,i,h;
key=getKey(str);
for(i=0;;i++){
h=(h1(key)+i*h2(key))%M;
if(strcmp(H[h],str)==0){return 1;}
 else if(strlen(H[h])==0){strcpy(H[h],str);return 0;}
}
return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}


Measured memory_bytes: 16056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n;
    ll a[200005] = {}, z = 0, z2 = 0, c = 0, c2 = 0, a0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a0 = a[1];
    if (a[1] <= 0) z += 1 - a[1], a[1] = 1;
    c = a[1];
    for (int i = 2; i <= n; i++) {
        if (c > 0) {
            if (c + a[i] < 0) c += a[i];
            else z += c + a[i] + 1, c = -1;
        } else {
            if (c + a[i] > 0) c += a[i];
            else z -= c + a[i] - 1, c = 1;
        }
    }
    a[1] = a0;
    if (a[1] >= 0) z2 += a[1] + 1, a[1] = -1;
    c2 = a[1];
    for (int i = 2; i <= n; i++) {
        if (c2 > 0) {
            if (c2 + a[i] < 0) c2 += a[i];
            else z2 += c2 + a[i] + 1, c2 = -1;
        } else {
            if (c2 + a[i] > 0) c2 += a[i];
            else z2 -= c2 + a[i] - 1, c2 = 1;
        }
    }
    cout << min(z, z2) << '\n';
}


Measured memory_bytes: 1792
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)
#define RALL(x) (x).rbegin(), (x).rend()


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int n, v[111111];

  std::cin >> n;

  std::map<int, int> map1, map2;

  for (int i = 0; i < n; i ++) {
    std::cin >> v[i];

    (i % 2 == 0 ? map1 : map2)[v[i]] ++;
  }

  std::vector<std::pair<int, int>> a, b;

  for (const auto& kv : map1)
    a.emplace_back(kv.second, kv.first);

  for (const auto& kv : map2)
    b.emplace_back(kv.second, kv.first);

  std::sort(RALL(a));
  std::sort(RALL(b));

  int cm = MOD;
  
  for (int i = 0, size1 = std::min<int>(a.size(), 1000); i < size1; i ++)
    for (int j = 0, size2 = std::min<int>(b.size(), 1000); j < size2; j ++) {
      if (a[i].second == b[j].second)
        continue;

      int c = n - (a[i].first + b[j].first);

      if (c < cm)
        cm = c;
    }

  if (cm == MOD)
    cm = n / 2;

  std::cout << cm << std::endl;

  return 0;
}


Measured memory_bytes: 6524
#include<bits/stdc++.h>
using namespace std;
#define rkc ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
#define fl(i,a,b) for(ll i=a;i<b;i++)
#define rfl(i,a,b) for(ll i=a;i>b;i--)
#define pb push_back
#define mp make_pair
#define test ll t;cin>>t;while(t--)
#define lld long double
#define vpp vector<pair<ll,ll>>
#define ff first
#define ss second
const ll M = 1e9 + 7;
const double pi  =3.141592653589793238463;
int main()
{
    rkc;
    ll n;
    cin>>n;
    ll a[n];
    fl(i,0,n)cin>>a[i];
    ll l[n+1],r[n+1];
    l[0]=0;
    r[n]=0;
    fl(i,0,n)l[i+1]=__gcd(l[i],a[i]);
    rfl(i,n,0)r[i-1]=__gcd(r[i],a[i-1]);
    ll ans=0;
    fl(i,0,n)ans=max(ans,__gcd(l[i],r[i+1]));
    cout<<ans;
}

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

int main() {
	string S, T;
	cin >> S;
	cin >> T;

	int cnt = 0;
	rep(i, S.size()) {
		if(S[i] != T[i]) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3844
import java.util.*;

import static java.lang.System.*;

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

        long[] a = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextLong();
        }

        long sunuke = a[0];
        long araiguma = 0;
        for (int i = 1; i < N; i++) {
            araiguma += a[i];
        }

        long diffMin = Math.abs(sunuke - araiguma);
        for (int i = 1; i < N - 1; i++) {
            sunuke += a[i];
            araiguma -= a[i];
            diffMin = Math.min(diffMin, Math.abs(sunuke - araiguma));
        }

        out.println(diffMin);
    }
}

Measured memory_bytes: 87232
// Aizu Vol-2 0210: The Squares
// 2017.9.11 bal4u@uu

#include <stdio.h>

#define W 1
#define S 2
#define E 3
#define N 4

typedef struct { int r, c, d; } MAN;
MAN man[1000]; int n, safe;
char map[33][33]; int w, h;
char tr['Z'];
int mov[5][4][3] = { { 0 },
	{ { -1, 0, N }, {  0,-1, W }, {  1, 0, S }, {  0, 1, E } },
	{ {  0,-1, W }, {  1, 0, S }, {  0, 1, E }, { -1, 0, N } },
	{ {  1, 0, S }, {  0, 1, E }, { -1, 0, N }, {  0,-1, W } },
	{ {  0, 1, E }, { -1, 0, N }, {  0,-1, W }, {  1, 0, S } },
 };

int main()
{
	int i, j, r, c, d, rr, cc, dd, t;

	tr['W'] = W, tr['S'] = S, tr['E'] = E, tr['N'] = N;
	while (scanf("%d%d", &w, &h) && w) {
		for (r = 0; r < h; r++) scanf("%s", map[r]);
		for (n = r = 0; r < h; r++) for (c = 0; c < w; c++) {
			int p = map[r][c];
			if (tr[p] > 0) man[n].r = r, man[n].c = c, man[n++].d = tr[p], map[r][c] = 'P';
		}
		for (safe = 0, t = 1; t <= 180; t++) {
			for (i = 0; i < n; i++) if (man[i].r >= 0) {
				r = man[i].r, c = man[i].c, d = man[i].d;
				for (j = 0; j < 4; j++) {
					rr = r + mov[d][j][0], cc = c + mov[d][j][1];
					if (rr < 0 || rr >= h || cc < 0 || cc >= w) continue;
					if (map[rr][cc] == '.' || map[rr][cc] == 'X') {	man[i].d = mov[d][j][2]; break;	}
				}
			}
			for (dd = 1; dd <= 4; dd++) for (i = 0; i < n; i++) if (man[i].r >= 0) {
				if ((d = man[i].d) == dd) {
					r = man[i].r, c = man[i].c;
					rr = r + mov[d][1][0], cc = c + mov[d][1][1];
					if (rr < 0 || rr >= h || cc < 0 || cc >= w) continue;
					if (map[rr][cc] == 'X') {
						map[r][c] = 'p', man[i].r = -1, map[rr][cc] = 'x'; 
						if (++safe == n) { printf("%d\n", t); goto Done; }
					} else if (map[rr][cc] == '.') {
						map[r][c] = 'p', man[i].r = rr, man[i].c = cc, map[rr][cc] = 'P';
					}
				}
			}
			for (r = 0; r < h; r++) for (c = 0; c < w; c++) {
				if      (map[r][c] == 'x') map[r][c] = 'X';
				else if (map[r][c] == 'p') map[r][c] = '.';
			}
//			for (r = 0; r < h; r++) puts(map[r]);putchar('\n');
		}
		puts("NA");
		Done:;
	}
	return 0;
}

Measured memory_bytes: 1824
#include<iostream>
using namespace std;
#define MAX 200000
#define SENTINEL 2000000000
typedef long long llong;
int L[MAX/2+2],R[MAX/2+2];

llong merge(int A[],int left,int right,int mid){
    int i=0,j=0;
    int n1=mid-left,n2=right-mid;
    llong cnt=0;
    for(int k=0;k<n1;k++)L[k]=A[left+k];
    for(int k=0;k<n2;k++)R[k]=A[mid+k];
    L[n1]=R[n2]=SENTINEL;
    for(int k=left;k<right;k++){
        if(L[i] <= R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
            cnt += n1-i;
        }
    }
    return cnt;
}


llong inversion(int A[],int left,int right){
    llong cnt1,cnt2,m;
    int mid;
    if(left+1<right){
        mid=(left+right)/2;
        cnt1 = inversion(A,left,mid);
        cnt2 = inversion(A,mid,right);
        m = merge(A,left,right,mid);
        return cnt1 + cnt2 + m;
    }else{
        return 0;
    }
}

int main(){
    int n,A[MAX];
    //scanf("%d",&n);
    cin >> n;
    for(int i=0;i<n;i++)cin >> A[i];
    //for(int i=0;i<n;i++)scanf("%d",&A[i]);
    llong ans = inversion(A,0,n);
    cout << ans << endl;
    //printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 4640
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int stk[200010],tp,a[200010],L[200010],R[200010],n;
void work(int*A){
	tp=0;
	for(int i=1;i<=n;++i){
		while(tp&&a[stk[tp]]>a[i])--tp;
		A[i]=i-stk[tp];
		stk[++tp]=i;
	}
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=gi();
	for(int i=1;i<=n;++i)a[i]=gi();
	work(L);std::reverse(a+1,a+n+1);work(R);
	ll ans=0;
	for(int i=1;i<=n;++i)
		ans+=1ll*a[i]*L[n-i+1]*R[i];
	printf("%lld\n",ans);
	return 0;
}


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

#define W 5
#define DELETE -1

int main(void){
  while(true){
    int H;
    cin >> H;
    if(H == 0){ break; }

    // ?????¢???????????????
    vector<vector<int> > puyo(H, vector<int>(W));
    for(int i = 0; i < H; i++)
      for(int j = 0; j < W; j++)
        cin >> puyo[i][j];

    // ???????¶????????????§??°?????????
    int flag, ans = 0;
    do{
      // ?????????????????°????????£?????????
      flag = false;

      // ??????????????°???????????????
      for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          if(puyo[i][j] == DELETE){ continue;}
          
          // ??????[i][j]?????????????????¨??????
          // ??????????????§????????????????±???????
          int seg;
          for(seg = 1; j + seg < W; seg++)
            if(puyo[i][j] != puyo[i][j + seg])
              break;

          // ??£?¶??????????3??\????????£???????¶????
          if(seg >= 3){
            for(int k = 0; k < seg; k++){
              // ?¶??????´??????????????°????????????????????????????????????
              flag = true;
              ans += puyo[i][j + k];
              puyo[i][j + k] = DELETE;
            }
          }
        }
      }

      // DELETE ????????£????????????????????????????????????
      // (???????????????????????????)
      for(int k = 0; k < H; k++){
        for(int i = 1; i < H; i++){
          for(int j = 0; j < W; j++){
            if(puyo[i][j] == DELETE){
              int tmp = puyo[i][j];
              puyo[i][j] = puyo[i - 1][j];
              puyo[i - 1][j] = tmp;
            }
          }
        }
      }
      
    }while(flag);

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

Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e15;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// __uint128_t
const ll MOD = 1e9+7;


int main(){
    ll N; cin >> N;
    vector<vector<ll>> A(N, vector<ll>(N)), C(N, vector<ll>(N)), B(N, vector<ll>(N, INF));
    ll temp = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++) {
            cin >> A[i][j];
            if(i<j) temp += A[i][j];
        }
        C[i][i] = 0;
    }

    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(k == i || k == j) continue;
                if(A[i][j] == A[i][k]+A[k][j]){
                    C[i][k] = B[i][k] = A[i][k];
                    C[k][j] = B[k][j] = A[k][j];
                }
                else if(A[i][k] + A[k][j] < A[i][j]){
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }
    ll ans = 0;
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(k == i || k == j) continue;
                if(C[i][j] == C[i][k]+C[k][j] && C[i][k] != 0 && C[k][j] != 0) C[i][j]= C[j][i]= 0;
                B[i][j] = min(B[i][j], B[i][k] + B[k][j]);
            }
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(B[i][j] != INF && A[i][j] < B[i][j]) C[i][j] = A[i][j];
        }
    }

    for(int i = 0; i < N-1; i++){
        for(int j = i+1; j < N; j++) if(C[i][j] != INF)ans += C[i][j];
    }
    if(!ans) cout << temp << endl;
    else cout << ans << endl;


}


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

int main() {
  int A;
  int B;
 
  cin >> A >> B;
  
  if (A == B){
    cout << A + B << endl;
  }
    else if (A > B){
      cout << A + A - 1 << endl;
    }
  	else {
      cout << B + B - 1 << endl;
    }
}


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

#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;

int main() {
  ll n, k;
  cin >> n >> k;

  int ans = 0;
  while (n > 0) {
    n /= k;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX/2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

string s;
vi sj;
int k;

int dp(int i, int j, bool b) {

	if (b) {
		if (j == sj[i])return 1;
		else return 0;
	}
	if (i == 0 || j < 0)return 0;

	int t = s[i - 1] - '0';

	return 9 * dp(i - 1, j - 1, false) + dp(i - 1, j, false) + (9 + t) / 10 * dp(i - 1, j, true) + max(t - 1, 0) * dp(i - 1, j - 1, true);

}

int main() {

	cin >> s >> k;
	sj.resize(s.size()+1);
	sj[0] = 0;
	int h = 0;
	rep(i, s.size()) {
		if (s[i] != '0')h++;
		sj[i+1] = h;
	}
	cout << dp(s.size(), k, true) + dp(s.size(), k, false) << endl;

}

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

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int n;
	int ans = INF;
	int max11 = 0, max11i = -1;
	int max12 = 0, max12i = -1;
	int max21 = 0, max21i = -1;
	int max22 = 0, max22i = -1;
	
	vector<int> v;
	map<int,int> mp1, mp2;
	
	cin>>n;
	
	v.resize(n);
	
	for(int i = 0; i < n; i++){
		cin>>v[i];
		
		if(i%2) {
			mp1[v[i]]++;
		} else {
			mp2[v[i]]++;
		}
	}
	
	for(pair<int,int> p : mp1){
		if(max11 <= p.second) {
			max12 = max11;
			max12i = max11i;
			
			max11 = p.second;
			max11i = p.first;
			
			
		} else if(max12 <= p.second) {
			max12 = p.second;
			max12i = p.first;
			
		}
	}
	
	for(pair<int,int> p : mp2){
		if(max21 <= p.second) {
			max22 = max21;
			max22i = max21i;
			
			max21 = p.second;
			max21i = p.first;
		} else if(max22 <= p.second) {
			max22 = p.second;
			max22i = p.first;
			
		}
	}
	
	// n /= 2;
	
	ans = n;

	// cout<<max11i<<" <>  "<<max21i<<endl;
	// cout<<max11<<" <>  "<<max21<<endl;cout<<endl;
	if(max11i != max21i) {
		ans = min(ans, n - max11 - max21);
	}
	// cout<<max12i<<" <>  "<<max21i<<endl;
	// cout<<max12<<" <>  "<<max21<<endl;cout<<endl;
	if(max12i != max21i) {
		
		ans = min(ans, n - max12 - max21);
	}
	
	// cout<<max11i<<" <>  "<<max22i<<endl;
	if(max11i != max22i) {
		ans = min(ans, n - max11 - max22);
	}
	
	// cout<<max12i<<" <>  "<<max22i<<endl;
	if(max12i != max22i) {
		ans = min(ans, n - max12 - max22);
	}
	
	cout<<ans<<endl;
	return 0;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int N;
    cin >> N;
    
    map<int,int> mapD;
    rep(i,0,N){
        int D;
        cin >> D;
        ++mapD[D];
    }
    
    int M;
    cin >> M;
    rep(i,0,M){
        int T;
        cin >> T;
        if(mapD[T]>0) --mapD[T];
        else{
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 9600
N = int(input())
h = []
h = list(map(int, input().split()))

def l_r(lis):
    l = 0
    r = 0
    for i in range(len(lis)):
        if lis[i] > 0:
            l = i
            break
    if l == len(lis)-1:
        r = l
    else:
        for i in range(l+1,len(lis)):
            if lis[i] <= 0:
                r = i
                break
            else:
                r = len(lis)-1
    return l,r

if h == []:
    print(0)
else:
    counta = 0
    while True:
        if all([x<=0 for x in h]):
            break
        else:
            l,r = l_r(h)
            for i in range(l,r+1):
                h[i] = h[i] - 1
            counta += 1
    print(counta)

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1001001001;
const int max_a = 1e4;

struct Solver{
  int h;
  int n;
  vector<pii> magic;
  vector<ll> dp;
  explicit Solver(int H, int N): h(H), n(N){
    magic.resize(n);
    dp.resize(h+max_a);
  }
  
  void init(){
    for(int i=0; i<n; i++) cin >> this->magic[i].first >> this->magic[i].second;
    for(int i=0; i<h+max_a; i++) dp[i] = INF;
  }
  
  void solve(){
    this->init();
    for(int i=0; i<h+max_a; i++){
      if(i==0) dp[i]=0;
      if(dp[i]==INF) continue;
      for(int j=0; j<n; j++){
        ll jm=i+this->magic[j].first;
        if(jm>h+max_a) continue;
        dp[jm] = min(dp[jm], dp[i]+this->magic[j].second);
      }
    }
    auto min = *std::min_element(this->dp.begin()+h, this->dp.end());
    cout << min << "\n";
  }
};


int main(){
  int H, N; cin >> H >> N;  
  Solver solver(H,N);
  solver.solve();
}

Measured memory_bytes: 384
/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-8
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 998244353

const int N = 600031;

long long n,a,b,k;

long long pw(long long a,long long b){
	if (b==0)
		return 1;
	if (b%2)
		return a*pw(a,b-1)%bs;
	return pw(a*a%bs,b/2);
}

long long inv(long long x){
	return pw(x,bs-2);
}

long long fact[N];

long long C(long long n,long long m){
	if (m>n)
		return 0;
	long long res=fact[n];
	res*=inv(fact[m]);
	res%=bs;
	res*=inv(fact[n-m]);
	return res%bs;
}

int main(){
//	freopen("apache.in","r",stdin);
//	freopen("apache.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
//	cin.tie(0);

	cin>>n>>a>>b>>k;

	long long paint_all=n*(a+b);
	long long ohead=paint_all-k;
	if (ohead<0){
		cout<<0<<endl;
		return 0;
	}

	long long ans=0;

	fact[0]=1;
	for (int i=1;i<N;i++){
		fact[i]=fact[i-1]*i%bs;
	}

	for (long long removed_a=0;removed_a<=n;removed_a++){
		long long new_ohead=ohead-removed_a*a;
		if (new_ohead<0)
			continue;
		if (new_ohead%b)
			continue;
		long long removed_b=new_ohead/b;
		if (removed_b<0||removed_b>n)
			continue;
		long long here=C(n,removed_a)*C(n,removed_b);
		ans+=here%bs;
		ans%=bs;
	}

	cout<<ans%bs<<endl;

//	cin.get(); cin.get();
	return 0;
}


Measured memory_bytes: 5120
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
#include<deque>
#include <iterator>     // std::back_inserter
const double PI = acos(-1);
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
using ll =long long;
const int mod = 1000000007;
const ll inf = 1e18+1;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
};
//fixed << setprecision(2)
bool  Array_check(ll y, ll x,ll d,ll w) {
	if (x < 0 || x >= w || y<0 || y>=d) {
		return false;
	}
	else {
		return true;
	}
	
}
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
//小文字=大文字+32
int main() {
	
	int N,W;
	cin >> N>>W;
	vector<ll>w(N), v(N);
	vector < vector<ll>>dp(N+1, vector<ll>(N*1000+1,inf));
	rep(i, N) {
		cin >> w[i] >> v[i];
	}
	dp[0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N*1000 ; j++) {
			if (j >= v[i]) {
			chmin(dp[i+1][j], dp[i][j - v[i]] + w[i]);
			}
			chmin(dp[i+1][j], dp[i][j]);
		}
	}
	ll ans=0;
	for (int i = 0; i <= N * 1000; i++) {
		if (dp[N][i] <= W) {
			ans = i;
		}

	}
	cout << ans;
}


Measured memory_bytes: 83160
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

long long dp[100000];
int h[100000];
int n, k;
const long long INF = (1LL << 60);

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}

	for (int i = 0; i < n; i++)
		dp[i] = INF;

	dp[0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 1; j <=k; j++) {
			if (i+j < n)
				dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]));
		}
	}

	cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1408
N,L = map(int,input().split())
E = []
a=0
for i in range(1,N+1):
  E.append(L+i-1)
  a += L+i-1
if E[0]<=0 and E[N-1]>=0:
  print(a)
else:
  if E[0]>0:
    print(a-E[0])
  else:
    print(a - E[N-1])

Measured memory_bytes: 3060
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
 
using namespace std;
 
double EPS = 1e-10;
 
double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
 
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}
 
  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }
 
  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }
 
  point operator * (double d){
    return point(x*d,y*d);
  }
};
 
struct segment{
  point a,b;
};
 
double dot(point a, point b) {
  return (a.x * b.x + a.y * b.y);
}
 
double cross(point a, point b) {
  return (a.x * b.y - a.y * b.x);
}

int is_intersected_ls(point a1, point a2, point b1, point b2) {
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
         ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

int is_point_on_line(point a, point b, point c) {
  return cross(b-a, c-a)==0.0 &&
         (dot(b-a, c-a) > -EPS) &&
         (dot(a-b, c-b) > -EPS);
}

int inside(point p, vector<point> ps, int n){
  segment t;
  t.a=t.b=p;
  t.b.x=DBL_MAX;
  ps.push_back(ps[0]);
  double ymx=-DBL_MAX,ymn=DBL_MAX;
  for(int i=0;i<n;i++){
    ymx=max(ymx,ps[i].y);
    ymn=min(ymn,ps[i].y);
  }
  if(t.a.y<=ymn||t.a.y>=ymx)return 0;

  int cnt1=0;
  for(int i=0;i<n;i++)
    if(is_point_on_line(t.a,t.b,ps[i]))cnt1++;
  
  int cnt=0;
  for(int i=0;i<n;i++)
    if(is_intersected_ls(ps[i],ps[i+1],t.a,t.b))cnt++;

  return (cnt-cnt1)%2;
}

int main(void){
  int n;
  point k,s,in;
  vector<point>p; 

  cin >> n;
  while(n--){
    p.clear();
    for(int i=0;i<3;i++){
      cin >> in.x >> in.y;
      p.push_back(in);
    }     

    cin >> k.x >> k.y >> s.x >> s.y;

    if(inside(k,p,3)!=inside(s,p,3))cout << "OK" << endl;
    else cout << "NG" << endl;
     
  }
 
  return 0;
}

Measured memory_bytes: 952
#include<iostream>
    using namespace std;
    int main(){
    	int N,dir,D[100000]={0},maxD=0;
    	long long sum;
    	cin>>N>>dir;
    	if(dir!=0){
    		cout<<0;
    		return 0;
    	}
    	D[0]=1;
    	for(int i=1;i<N;i++){
    		cin>>dir;
    		if(dir>maxD)maxD=dir;
    		D[dir]++;
    	}
    	if(D[0]!=1){
    		cout<<0;
    		return 0;
    	}
    	sum=D[0];
    	for(long i=2;i<=maxD;i++){
    		if(D[i]!=0){
    			for(int j=0;j<D[i];j++){
    				sum*=D[i-1];
    				sum%=998244353LL;
    			}
    		}else{
    			sum=0;
    			break;
    		}
    	}
    	cout<<sum;
    	return 0;
    }

Measured memory_bytes: 640
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000

int gcd(int x, int y){
	if (x > y)swap(x, y);
	if (x == 0)return y;
	else return gcd(y%x, x);
}


int main(){
	int a[N];
	f(i, N)a[i] = 0;
	int n, k;
	int x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%d %d", &n,&k);
	f(i, n){
		scanf("%d", &a[i]);
		if (i == 0)ans = abs(a[0] - k);
		if (i > 0){
			ans = gcd(ans, abs(a[i] - k));
		}
	}


	printf("%lld\n", ans);


	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
const int INF = 200010;

int N, M;
int a[100010], cnt[25];
vector<int> pos[100010];
int toy[1 << 20], dp[1 << 20];

int solve() {
    queue<int> q; q.push(0);
    while(!q.empty()) {
        int bit = q.front(); q.pop();
        rep(i,0,M) {
            if(bit >> i & 1) continue;
            int nbit = bit | (1 << i);
            int lb = toy[bit], ub = toy[nbit];
            // printf("debug: lb = %d, ub = %d\n", lb, ub);
            int rng = ub - lb;

            int ub2 = lower_bound(pos[i].begin(), pos[i].end(), ub) - pos[i].begin();
            int lb2 = lower_bound(pos[i].begin(), pos[i].end(), lb) - pos[i].begin();
            // printf("lb = %d, ub = %d\n", lb2, ub2);
            int cnt = ub2 - lb2;

            // printf("bit = %d, nbit = %d, rng = %d, cnt = %d\n", bit, nbit, rng, cnt);

            if(dp[nbit] > dp[bit] + (rng - cnt)) {
                dp[nbit] = dp[bit] + (rng - cnt);
                q.push(nbit);
            }
        }
    }
    return dp[(1 << M) - 1];
}

int main() {
    cin >> N >> M;
    rep(i,0,1<<M) dp[i] = INF;
    dp[0] = 0;

    rep(i,0,N) {
        cin >> a[i]; a[i]--;
        pos[a[i]].push_back(i);
        cnt[a[i]]++;
    }
    rep(bit,0,1<<M) rep(i,0,M) if(bit >> i & 1) toy[bit] += cnt[i];
    cout << solve() << endl;
    return 0;
}

Measured memory_bytes: 16800
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

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

    vector<long long> A(N);

    for (int i=0;i<N;++i) {
        cin >> A[i];
    }

    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()), A.end());

    while (A.size() > 1) {
        sort(A.begin(),A.end());
        A.erase(unique(A.begin(),A.end()), A.end());
        if (A[0] == 0) A.erase(A.begin());

        for (int i=1;i<A.size();++i) {
            A[i] %= A[0];
        }
    }

    cout << A[0] << endl;
    return 0;
}

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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    int n, t, a;
    cin>> n>> t>> a;

    long double h[n], mi= 10000, ind= 0;

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

        if( (abs( a -(t - (h[i] * 0.006) ) )) <mi)
        {
            mi= abs ( a-(t- (h[i] * 0.006) ) );
            ind= i+1;
        }


    }


cout << ind;
 nl;



    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

int dx[2] = {1, 0};
int dy[2] = {0, 1};

int W, H;
vector<string> m;
bool m1[100][100] = {0};
string m2[100][100];
string beautify(string s) {
	if (s.size() == 0) return "";
	int l = (int)s.size()-1;
	REP(i,s.size()) {
		if (s[i] != '0') {
			l = i;
			break;
		}
	}
	return s.substr(l, s.size()-l);
}
bool gt(string s1, string s2) {
	bool r = s1.size() > s2.size();
	s1 = beautify(s1);
	s2 = beautify(s2);
	if (s1.size() == s2.size()) {
		if (s1 == s2) {
			return r;
		}
		return s1 > s2;
	}
	return s1.size() > s2.size();
}
string dp(int x, int y) {
	string res = "";
	if (x < 0 || x >= W || y < 0 || y >= H) return "";
	if ( !isdigit(m[y][x]) ) return "";
	if (m1[y][x]) return m2[y][x];
	REP(i, 2) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		string a = ""; a += m[y][x];
		a += dp(nx, ny);
		if ( gt(a, res) ) res = a;
	}
	return m1[y][x] = true, m2[y][x] = res;
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	while (cin >> W >> H, W || H) {
		m.resize(H); cin >> m;
		fill(m1[0], m1[100], false);
		string ans = "0";
		REP(y, H) REP(x, W) {
			if ( gt( dp(x, y), ans ) ) ans = beautify( dp(x, y) );
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3344
#include <iostream>
#include <vector>

using namespace std;

int N,M,K;
int user_1;
int user_2;

void print_vec(vector<int> foo) {
    return;
    for(int i = 0; i < foo.size(); i++) {
        cout << foo[i];
        if(i != foo.size()-1) {
            cout << " ";
        }
    } cout << endl;
}

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

    vector<int> parent(N+1);
    for(int i = 1; i <=N;i++) parent[i] = i;
    vector<int> clique_count(N+1, 0);
    vector<int> count_friend_cands(N+1, -1);

    auto get_root = [&](int user) {
        while(parent[user] != user) {
            user = parent[user];
        }
        return user;
    };

    auto merge = [&](vector<int>& parent, int user_1, int user_2) {
        int user_1_root = get_root(user_1);
        int user_2_root = get_root(user_2);

        while(user_2 != parent[user_2]) {
            int user_2_ = parent[user_2];
            parent[user_2] = user_1_root;
            user_2 = user_2_;
        }
        parent[user_2] = user_1_root;
    };

    print_vec(parent);
    print_vec(clique_count);
    print_vec(count_friend_cands);

    for(int i = 0; i < M; i++) {
        cin >> user_1 >> user_2;

        merge(parent, user_1, user_2);
        count_friend_cands[user_1]--;
        count_friend_cands[user_2]--;
    }


    for(int i = 1; i <= N; i++) {
        clique_count[get_root(i)]++;
    }


    for(int i = 1; i <= N; i++) {
        count_friend_cands[i] += clique_count[get_root(i)];
    }

//    cout << endl; 
//    for(int i = 1; i <= N; i++) {
//        cout << "root of " << i << " is " << get_root(i) << endl;
//    }
//    print_vec(clique_count);
//    print_vec(count_friend_cands);


    for(int i = 0; i < K; i++) {
        cin >> user_1 >> user_2;
        if (get_root(user_1) == get_root(user_2)) {
            count_friend_cands[user_1]--;
            count_friend_cands[user_2]--;
        }
    }

    for(int i = 1; i <= N; i++) {
        cout << count_friend_cands[i];
        if(i != N) {
            cout << " ";
        }
    } cout << endl;

}


Measured memory_bytes: 2424
//Bismillahir-Rahmanir-Rahim
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int llu;
#define f1(i,n) for(i=1;i<=n;i++)
#define f(i,n) for(i=0;i<n;i++)
#define Max 100009
#define pb push_back
#define mp make_pair
using namespace std;
int main()
{
    	ll n,m,x,i,l,j,k,c=0,d=0;
    	cin>>n>>m>>k;
    	l=k;
    	ll a[n],b[m];
    	f(i,n) cin>>a[i];
    	f(i,m) cin>>b[i];
    	vector<ll>suma(n+1);
    	vector<ll>sumb(m+1);
        f(i,n)
        {
            suma[i+1]=suma[i]+a[i];
        }
        f(i,m)
        {
            sumb[i+1]=sumb[i]+b[i];
        }
        for(i=0;i<=n;i++)
        {
            d=k-suma[i];
            if(d<0)
                continue;
            l=lower_bound(sumb.begin(),sumb.end(),d)-sumb.begin();
            if(l>m||sumb[l]>d)
                l--;
            c=max(c,i+l);
        }
        cout<<c;
}


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

using namespace std;
 
#define int1(a) scanf("%d",&a)
#define int2(a,b) scanf("%d %d",&a,&b)
#define int3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define int4(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
 
#define lint1(a) scanf("%lld",&a)
#define lint2(a,b) scanf("%lld %lld",&a,&b)
#define lint3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define lint4(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define ll long long int
#define lli long long int
 
#define pint(x) printf("%d",x)
#define plint(x) printf("%lld",x)
#define endl '\n'
#define nl printf("\n");
#define ps printf(" "); 
 
#define all(x) x.begin(),x.end()
#define pb push_back
#define Set(a, s) memset(a, s, sizeof (a))
#define mod1 (lli)(1e9 + 7)
#define mod2 (lli)(1e9 + 9)
#define EPS 1e-9

#define fore(i,n) for(int i=n; i>=0; i--)
#define fors(i,a,n) for(int i=a; i<n; i++)
#define fora(i,ele) for(auto i: ele)
 
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<lli> vli;
 
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
 
double tick(){static clock_t oldt,newt=clock();double diff=1.0*(newt-oldt)/CLOCKS_PER_SEC;oldt=newt;return diff;}
float roundoff(float val, float p){ return floor(val*pow(10.0,p)+0.5)/pow(10.0,p);}
lli power(lli a, lli b, lli mod){lli x=1,y=a; while(b > 0){if(b&1){x=(x*y)%mod;}y = (y*y)%mod; b /= 2;}return x;}
 
const int INF = 0x3f3f3f3f;
const float pi = 3.14159265;
 
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};
//int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1};



int main(){
    int n;
    int1(n);
    
    //~ priority_queue<pair<int,int> > pq;
    vi arr1,arr;
    
    fors(i,0,n){
		int temp;
		cin>>temp;
		
		arr1.pb(temp);
	}
    arr = arr1;
    sort(arr.rbegin(), arr.rend());
    
    int m = arr[0], mm = arr[1];
    
    fors(i,0,n){
		if(arr1[i] == m) cout<<mm<<endl;
		else cout<<m<<endl;
	}
    
    return 0;
}


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin >> N;
  int h, n, w;
  for (long long i = 1; i <= 3500; i++){
    for (long long j = 1; j <= 3500; j++){
      long long a = 4 * i * j - N * (i + j);
      long long b = N * i * j;
      if (a > 0){
        if (b % a == 0){
          h = i;
          n = j;
          w = b / a;
        }
      }
    }
  }
  cout << h << ' ' << n << ' ' << w << endl;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; i++)
        cin >> a[i];
    vector<int>dp(k+1, 2);
    sort(a, a+n);
    for(int i = 1; i <= k ;i++){
        int j = 0;
        while(j<n && a[j] <= i){
            if(dp[i-a[j]] == 2){
                dp[i] = 1;
                break;
            }
            j ++;
        }
    }
    if(dp[k] == 1){
        cout << "First\n";
    }
    else{
        cout << "Second\n";
    }
    return 0;
}

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

#define ll long long

void chmin(ll& a, ll b) {
  if (a > b) a = b;
}

int main() {

  int N, K;
  cin >> N >> K;
  
  vector<ll> a(N);
  
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  
  // i番目までで最も高いもの
  vector<ll> height(N);
  height[0] = 0;
  
  ll SUBMAX = a[0];
  for (int i = 1; i < N; i++) {
    height[i] = SUBMAX;
    
    if (a[i] > SUBMAX) {
      SUBMAX = a[i];
    }
  }
  

  

  
  ll ans = 10000000000000;
  
  // bit 全探索
  for (int bit = 0; bit < (1 << N); bit++) {
    ll color = 0;
    ll cost = 0;
    
    ll temp = 0; 
    for (int i = 0; i < N; i++) {
      
      if (!(bit & 1)) continue;
          
      if (bit & (1 << i)) {
        color++;

        // 次の建物に必要な最低限の高さを temp で現す
        if (temp >= height[i]) {
          temp++;
        } else {
          temp = height[i]+1;
        }
        
        // cost の計算
        if (i == 0) {
          temp = a[0];
          continue;
        }
        if (a[i] > temp) {
           temp = a[i];
           continue;
        }
        cost += temp -a[i];
      }
    }
    
    
    if (color >= K) chmin(ans, cost);
    
  }  
  
  cout << ans << endl;

}

Measured memory_bytes: 3568
n = int(input())
arr = list(map(float, input().split()))

dp = [[0.0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1.0

for i in range(n):
    for j in range(i + 1):
        dp[i + 1][j + 1] += dp[i][j] * arr[i]
        dp[i + 1][j] += dp[i][j] * (1 - arr[i])

dp = dp[-1]

print(sum(dp[-(n + 1) // 2:]))

Measured memory_bytes: 111532
#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 200500
using namespace std;
inline int read()
{
  int X=0;char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
vector<int> g[MaxN],l[MaxN];
int tp[MaxN],tn,ms[MaxN],siz[MaxN];
bool vis[MaxN];
void pfs(int u,int fa)
{
  tp[++tn]=u;
  siz[u]=1;ms[u]=0;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=fa&&!vis[v]){
      pfs(v,u);
      siz[u]+=siz[v];
      ms[u]=max(ms[u],siz[v]);
    }
}
int getrt(int u)
{
  tn=0;pfs(u,0);
  int rt=0;
  for (int i=1;i<=tn;i++){
    ms[tp[i]]=max(ms[tp[i]],tn-siz[tp[i]]);
    if (ms[tp[i]]<ms[rt])rt=tp[i];
  }return rt;
}
ll w[MaxN],dep[MaxN],mp;
void dfs(int u,int fa)
{
  if (w[mp]+dep[mp]>w[u]+dep[u])mp=u;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=fa&&!vis[v]){
      dep[v]=dep[u]+l[u][i];
   	  dfs(v,u);
    }
}
struct Line
{int f,t;ll len;}s[MaxN<<5];
int tot;
void solve(int u)
{
  dep[u]=mp=0;dfs(u,0);
  ll sav=w[mp]+dep[mp];
  for (int i=1;i<=tn;i++)
    s[++tot]=(Line){tp[i],mp,sav+w[tp[i]]+dep[tp[i]]};
  vis[u]=1;
  for (int i=0,v;i<g[u].size();i++)
    if (!vis[v=g[u][i]])
   	  solve(getrt(v));
}
int n,f[MaxN];
bool cmp(const Line &A,const Line &B)
{return A.len<B.len;}
int findf(int u)
{return f[u]==u ? u : f[u]=findf(f[u]);}
bool merge(int x,int y)
{
  x=findf(x);y=findf(y);
  if (x==y)return 0;
  f[x]=y;return 1;
}
int main()
{
  n=read();w[0]=1ll<<60;ms[0]=n+1;
  for (int i=1;i<=n;i++)w[i]=read();
  for (int i=1,fr,to,len;i<n;i++){
    fr=read();to=read();len=read();
    g[fr].push_back(to);
    l[fr].push_back(len);
    g[to].push_back(fr);
    l[to].push_back(len);
  }solve(getrt(1));
  ll ans=0;
  for (int i=1;i<=n;i++)f[i]=i;
  sort(s+1,s+tot+1,cmp);
  for (int i=1;i<=tot;i++)
    if (merge(s[i].f,s[i].t))
      ans+=s[i].len;
  printf("%lld",ans);
}

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

int main()
{
    int n, l;
    cin >> n >> l;
    vector<string> s(n);
    rep(i, n) cin >> s.at(i);

    sort(s.begin(), s.end());

    rep(i, n) cout << s.at(i);

    cout << endl;
}

Measured memory_bytes: 3596
#include<iostream>

using namespace std;
typedef long long ll;

int main(){
	ll a,b,c,k;
	cin >> a >> b >> c >>k;
	
	if(k % 2 ==0){
		cout << a-b << endl;
	}else{
		cout << b-a << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import math
def keisan(x,y):
    z = (x[0]*x[1])//math.gcd(x[0],x[1])
    for i in range(y-2):
        z = (z*x[i+2])//math.gcd(z,x[i+2])
    return z
    
n = int(input())    
a = list(map(int,input().split()))
print(keisan(a,n))


Measured memory_bytes: 5668
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
using namespace std;

typedef long long ll;

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

//--------------------



int main() {

  string s, t;
  cin >> s;
  t = s;
  reverse(t.begin(), t.end());

  if(s==t) {
    int l = s.size();
    string s1 = s.substr(0, (l-1)/2);
    string s2 = s1;
    reverse(s2.begin(), s2.end());
    if(s1==s2) {
      s1 = s.substr((l+3)/2-1, l-((l+3)/2-1));
      s2 = s1;
      reverse(s2.begin(), s2.end());
      if(s1==s2) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
n,m=gets.split.map &:to_i
a=(1..n).map{gets.chomp}
b=(1..m).map{gets.chomp}
puts (0..n-m).any?{|y|(0..n-m).any?{|x|(0..m-1).all?{|d|a[y+d][x,m]==b[d]}}}?:Yes: :No

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace::std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define dump(x) cout << (x) << endl

int main() {
  string str;
  int k;
  cin >> str >> k;
  
  vector<string> x;
  FOR(i, 1, 5+1) {
    REP(j, (int)str.size()-i+1) {
      x.push_back(str.substr(j, i));
    }
  }
  sort(x.begin(), x.end());
  // REP(i, (int)x.size()) {
  //   dump(x[i]);
  // }
  int i;
  for (i = (int)x.size()-1; 0 < i; --i) {
    if (x[i] == x[i-1]) {
      x.erase(x.begin()+i);
    }
  }
  cout << x[k-1] << endl;
  return 0;
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

const int maxN = 100005;

class TaskB {
private:
	Debugger debugger;

public:
	void solveOne(int it){
		long long x;
		cin >> x;
		long long have = 100;
		for(long long d = 1; ; d++){
			have = (double)have * (1.01);
			if(have >= x){
				cout << d << endl;
				return;
			}
		}
	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};


int main(){
	ios_base::sync_with_stdio(false);
	TaskB solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 3644
#include<stdio.h>
#include<string.h>
int main(){
  char x[1001];
  int ans;
  int i,len;
  while(scanf("%s",x)){
    ans=0;
    if(x[0]=='0')break;
   len=strlen(x);
  for(i=0;i<len;i++){
    x[i]-='0';
    ans+=x[i];
  }
  printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 536