akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

long long dp[101][21];

int main(void){

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

  dp[0][num[0]] = 1;

  for( int j = 1 ; j < n ; j++ ){
    for( int i = 0 ; i < 21 ; i++ ){
      if( i + num[j] <= 20 )
	dp[j][i + num[j]] += dp[j - 1][i];
      if( i - num[j] >= 0 )
	dp[j][i - num[j]] += dp[j - 1][i];
    }
  }
    cout << dp[n - 2][num[n - 1]] << endl;
  return 0;
}

Measured memory_bytes: 1172
n = int(input())
xy = []
for _ in range(n):
    xy.append([int(x) for x in input().split()])

dis = 0

for x1, y1 in xy:
    for x2, y2 in xy:
        dis += ((x1 - x2)**2 + (y1 - y2)**2)**0.5

print(dis/n)

Measured memory_bytes: 3188
input = raw_input

M = 2019
s = input()
#n = len(s)
#s = int(s)

div = 10

counts = [0] * M
#m = 1

counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    #m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)

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

int main() {
  string s;
  cin >> s;
  int num = 0;
  rep(i, 4) {
    if (s.at(i) == '+') num++;
    else num--;
  }
  cout << num << endl;
}

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

using namespace std;

int main()
{
    int i, j;
    long long  x;
    long long  ans = 0;
    long long  ans_tmp;

    cin >> x;

    ans += x / 500;
    x -= ans * 500;
    ans *= 1000;
    ans_tmp = x / 5;
    ans += ans_tmp * 5;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 768
#include <iostream>
using namespace std;
int main(void){
    int a1,b1,a2,b2,a3,b3,a4,b4,a5,b5,a6,b6,a7,b7;
   cin >> a1 >> b1 >> a2 >> b2 >> a3 >> b3 >> a4 >> b4 >> a5 >> b5 >> a6 >> b6 >> a7 >> b7;
   cout << a1-b1 << endl;
   cout << a2-b2 << endl;
   cout << a3-b3 << endl;
   cout << a4-b4 << endl;
   cout << a5-b5 << endl;
   cout << a6-b6 << endl;
   cout << a7-b7 << endl;
   return 0;
    
    
}



Measured memory_bytes: 3096
def gl
  gets.split.map(&:to_i)
end

def trapets(h, g)
  if g > h
    trapets(g, h)
  end
  if h == g
    return g
  elsif h % g == 0
    return 2 * h - g
  else
    return 2 * g *(h/g) + trapets(g,h%g)
  end
end

n, x = gl

puts n + trapets(n-x, x)


Measured memory_bytes: 1788
#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
int a[301][301];
int was[301];
int u[301];
 
 main () {
	ios_base::sync_with_stdio (0);	
	cin.tie (0), cout.tie (0);
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= n;i ++) {
		for (int j = 1;j <= m;j ++) {
			cin >> a[i][j];
		}
	}
	int ans = n;
	for (int id = 1;id < m;id ++) {
		memset (u, 0, sizeof u);
		int pos = 0, mx = 0;
		for (int i = 1;i <= n;i ++) {
			for (int j = 1;j <= m;j ++) {
				if (!was[a[i][j]]) {
					u[a[i][j]] ++;
					break;
				}
			}
		} 
		for (int i = 1;i <= m;i ++) {
			if (u[i] > mx) {
				mx = u[i];
				pos = i;
			}
		}
		was[pos] = 1;
		ans = min (ans, mx);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define hell 1000000007
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long int
#define pi 3.1415926536
using namespace std;

/*ll merge(vector<ll> &v,ll l,ll m,ll r)
{
	ll n1=m-l+1;
	ll n2=r-m;
	ll inv=0;
	vector<ll> a(n1),b(n2);
	for(ll i=0;i<n1;i++)
	a[i]=v[l+i];
	for(ll i=0;i<n2;i++)
	b[i]=v[m+1+i];
	ll i=0,j=0,k=l;
	while(i<n1&&j<n2)
	{
		if(a[i]<=b[j])
		{
			v[k]=a[i];
			i++;
		}
		else
		{   inv+=(m-i+1);
			v[k]=b[j];
			j++;
		}
		k++;
	}
	while(i<n1)
	{
		v[k]=a[i];
		i++;
		k++;
	}
	while(j<n2)
	{
		v[k]=b[j];
		j++;
		k++;
	}
	return inv;
}
ll mergesort(vector<ll> &v,ll l,ll r)
{  ll inv=0;
	if(l<r)
	{
		ll m=l+(r-l)/2;
		inv=mergesort(v,l,m);
		inv+=mergesort(v,m+1,r);
		inv+=merge(v,l,m,r);
	}
	return inv;
}*/

/*ll factorize(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            if((n/i)!=i)
            res.push_back(n/i);
        }
    }
    
    return (ll)res.size();
}*/

void solve()
{ll n,k,ans,z,q,l=INT_MIN,mini=0,prev;
   
   cin>>n;
   vector<double> v(n);
   double d=1.0;
   double p;
   for(ll i=0;i<n;i++)
   {
   	cin>>p;
   	v[i]=p;
   	d*=v[i];
   }
   double sum=0;
   for(ll i=0;i<n;i++)
   sum+=(d/v[i]);
   double x=d/sum;
   
   cout<<fixed<<setprecision(9)<<x;
}

int main()
{
  fast
ll t=1;

while(t--)
{solve();
 //cout<<ma<<endl;
}
return 0;}

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

int main() {
    int n;
    cin >> n;
    double ans = 0.0;
    cout << fixed << setprecision(7);
    for(int i=0; i<n; i++){
        double x;
        string u;
        cin >> x >> u;
        if(u == "BTC"){
            x *= 380000.0;
        }
        ans += x;
    }
    cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;
#define faster       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef long double ld;

// ll n,m,k;
// vector< vector<ll> > arr;
// vector< set<ll> >vs;
// vector< set<ll> >ans;
// set<ll> temp;
// set<ll> temp1;

// void query(ll b,ll h){
//   for(ll v:arr[h]){
//     if(temp.find(v)!=temp.end()){
//       continue;
//     }
//     else{
//       temp.insert(v);
//       temp1.insert(v);
//     }
//     query(b,v);
//   }
//   return;
// }

// int main(){
//   faster;
//   cin >> n >> m >> k;
//   arr.resize(n);
//   vs.resize(n);
//   vector< vector<ll> > block;
//   for(ll i=0;i<m;i++){
//     ll a,b;
//     cin >> a >> b;
//     arr[a-1].push_back(b-1);
//     arr[b-1].push_back(a-1);
//   }

//   for(ll i=0;i<n;i++){
//     if(temp1.find(i)!=temp1.end()){
//       continue;
//     }
//     temp1.insert(i);
//     temp.clear();
//     temp.insert(i);
//     query(i,i);
//     ans.push_back(temp);
//     if(temp1.size()==n){
//       break;
//     }
//   }
//   for(ll i=0;i<ans.size();i++){
//     for(auto it = ans[i].begin(); it != ans[i].end(); it++){
//       vs[*it]=ans[i];
//     }
//   }
//   for(ll i=0;i<k;i++){
//     ll c,d;
//     cin >> c >> d;
//     vs[d-1].erase(c-1);
//     vs[c-1].erase(d-1);

//   }
//   for(ll i=0;i<n;i++){
//     cout << vs[i].size()-arr[i].size()-1 << " ";
//   }
// }

ll n,m,k;
vector<ll> dsu;
vector< vector<ll> > arr;

ll parent(ll ind) {
  if (dsu[ind] < 0) return ind;
  return (dsu[ind] = parent(dsu[ind]));
}

void merge(ll a, ll b) {
  a = parent(a); b = parent(b);
  if (a == b) return ;
  if (dsu[a] < dsu[b]) swap(a, b);
  dsu[b] += dsu[a];
  dsu[a] = b;
}

bool query(ll a, ll b) {
  if (parent(a) == parent(b)) return true;
  return false;
}

int main() { 
  cin >> n >> m >> k;
  dsu.resize(n, -1);
  arr.resize(n);
  for (ll i = 0; i < m; i++) {
    ll a,b;
    cin >> a >> b;
    arr[a-1].push_back(b-1);
    arr[b-1].push_back(a-1);
    if(!query(a-1,b-1)){
      merge(a-1,b-1);
    }
  }
  vector<ll> ans(n);
  for(ll i=0;i<n;i++){
    ans[i]=-dsu[parent(i)];
  }
  for(ll i=0;i<k;i++){
    ll c,d;
    cin >> c >> d;
    if(parent(c-1)==parent(d-1)){
      ans[c-1]--;
      ans[d-1]--;
    }
  }
  for(ll i=0;i<n;i++){
    cout << ans[i]-arr[i].size()-1 <<" ";
  }
}

Measured memory_bytes: 8692
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long time[5];
  	long long minimal;minimal=1e15;
	long long minimal_n;  	
  	long long n;cin>>n;
  	for(int i=0;i<5;i++){
    	cin>>time[i];
      	if(time[i]<minimal){
        	minimal=time[i];
          	minimal_n=i;
        }
    }
  	long long output;output=0;
  	if(n%minimal==0){
  		output=n/minimal+4;
    }else{
    	output=n/minimal+5;
    }
    cout<<output<<endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int main(void){ 
    int N,T;
        cin>>N>>T;
        int c[N];
        int t[N];
        int ans=1000000;
    for(int i=0;i<N;i++){
        cin>>c[i]>>t[i];
        if(t[i]<=T){
            if(c[i]<=ans){
                ans=c[i];
            }
        }
    }
    if(ans==1000000){
        cout<<"TLE"<<endl;

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

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

const int MAXN = 2000;
char f[MAXN + 1][MAXN + 1];

int get(int **a, int x1, int y1, int x2, int y2) {
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}

int **take(int n, int m) {
    int **res = (int **)malloc(sizeof(int *) * (n + 1));
    for(int i = 0; i <= n; i++) {
        res[i] = (int *) malloc(sizeof(int) * (m + 1));
        for (int j = 0; j <= m; j++)
            res[i][j] = 0;
    }
    return res;
}

int main() {
    //ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    int **cnt, **cntV, **cntH;
    cnt = take(n + 1, m + 1);
    cntV = take(n + 1, m + 1);
    cntH = take(n + 1, m + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            cin >> f[i][j];
            cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + (f[i][j] == '1');

        }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i + 1 <= n && f[i][j] == '1' && f[i + 1][j] == '1')
                cntV[i][j]++;
            if(j + 1 <= m && f[i][j] == '1' && f[i][j + 1] == '1')
                cntH[i][j]++;
            cntV[i][j] += cntV[i - 1][j] + cntV[i][j - 1] - cntV[i - 1][j - 1];
            cntH[i][j] += cntH[i - 1][j] + cntH[i][j - 1] - cntH[i - 1][j - 1];
        }
    }
    for(int i = 0; i < q; i++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int ans = 0;
        ans += get(cnt, a, b, c, d);
        if(a < c)
            ans -= get(cntV, a, b, c - 1, d);
        if(b < d)
            ans -= get(cntH, a, b, c, d - 1);
        printf("%d\n", ans);
    }
    return 0;
}

Measured memory_bytes: 52736
def bubbleSort(lst,n):
    flag = True
    count = 0
    while flag:
        flag = False
        for i in range(n-1,0,-1):
            if lst[i] < lst[i - 1]:
                lst[i],lst[i-1] = lst[i-1],lst[i]
                count += 1
                flag = True
    return lst,count


num = int(input())
lst = [int(i) for i in input().split()]

lst = bubbleSort(lst,num)
print(*lst[0])
print(lst[1])


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


int main(){
	
	string s;
	cin>>s;
	
	vector<int> ltr(26,0);
	
	for(int i=0;i<s.size();i++) ltr[s[i]-'a']++;
	
	for(int i=0;i<26;i++){
		if(!ltr[i]) continue;
		if(ltr[i]%2) {
			cout<<"No";
			return 0;
		} 
	}
	cout<<"Yes";
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    int n; cin >> n;
    vector<int> A(n); rep(i, n) cin >> A[i];

    int cnt = 1, up_down = 0;
    rep(i, n-1){
        if(up_down == 0){
            if(A[i+1] > A[i]) up_down = 1;
            else if(A[i+1] < A[i]) up_down = -1;
        }else if(up_down == 1){
            if(A[i+1] >= A[i])continue;
            else{
                cnt++; up_down = 0;
            }
        }else if(up_down == -1){
            if(A[i+1] <= A[i]) continue;
            else{
                cnt++; up_down = 0;
            }
        }
    }
    cout << cnt << ln;
}

    

Measured memory_bytes: 640
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Main main = new Main();
    main.solve();
  }

  int a;
  int b;
  int ans;

  public Main() {
    Scanner sc = new Scanner(System.in);
    try {
      a = sc.nextInt();
      b = sc.nextInt();
    } finally {
      sc.close();
    }
  }

  void solve() {
    ans = a * b;
    show();
  }

  void show() {
    System.out.println(ans);
  }
}


Measured memory_bytes: 35628
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <utility>
#include <set>
#include <numeric>
#include <queue>
#include <sstream>
#include <map>
using namespace std;
using LLI = long long int;

#define Rep(i, N) for (int i = 0; i < N; i++)


map<int, int> primeFactorize(int n) {
    map<int, int> m;

    int k = 2;
    while (k<n+1) {
        if (n % k == 0) {
            n /= k;
            if (m.find(k) == m.end()) {
                m[k] = 1;
            } else {
                m[k] += 1;
            }
        } else {
            k++;
        }
    }

    return m;
}

int main(int argc, char *argv[])
{
    int N;
    cin >> N;

    // 2,...,N の各素因数分解を計算
    vector<map<int,int>> vm;
    for (int i=2; i<N+1; i++) {
        vm.push_back(primeFactorize(i));
    }

    vector<int> e(101);
    for (auto m : vm) {
        for (auto kv : m) {
            e[kv.first] += kv.second;
        }
    }

    // eの要素のうちn-1以上の個数
    // note: 0もあるためn-1以上ならn通り考えることができる
    auto num = [e](int n) {
        return count_if(e.cbegin(), e.cend(), [n](int v){
            return v >= n - 1;
        });
    };

    int s =
      num(3 * 5 * 5)
     + num(5 * 5) * (num(3) - 1)
     + num(3 * 5) * (num(5) - 1)
     + num(5) * (num(5) - 1) / 2 * (num(3) - 2);

    cout << s << endl;
   
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 2001
int useornouse(int,int);
int youko1,haire1[MAX];
int main()
{
  int youko2,haire2[MAX],i,j,k=1,youcou=1,han;
  scanf("%d",&youko1);
  for(i=1;i<=youko1;i++)
    {
      scanf("%d",&haire1[i]);
    }
  scanf("%d",&youko2);
  for(j=1;j<=youko2;j++)
    {
      scanf("%d",&haire2[j]);
    }
  while(k<=youko2)
    {
      han=useornouse(youcou,haire2[k]);
      if(han==1)
	{
	  printf("yes\n");
	}
      else
	{
	  printf("no\n");
	}
      k++;
    }
  return 0;
}

int useornouse(int youcou,int nokori)
{
  int yesno;
  if(nokori==0)
    {
      return 1;
    }
  if(youcou>youko1)
    {
      return 0;
    }
  //printf("%d\n",youcou);
  //printf("%d\n",nokori);
  yesno=(useornouse(youcou+1,nokori-haire1[youcou])||useornouse(youcou+1,nokori));
  //yesno=useornouse(youcou+1,nokori);
  return yesno;
}

/*
//printf("100\n");
while(l<=youko1)
{
//printf("100\n");
// printf("%d %d\n",l,haire2[k]);
if(haire2[k]==haire1[l])
{
//printf("100\n");
break;
}
else
{
l++;
}
}
*/



Measured memory_bytes: 2108
// JavaScript source code
"use strict";

let myFunc = (input) => {
    input = input.split("\n")
    let N = parseInt(input[0]);
    let ans = 0;
    for(let i = 1; i <= N; i++){
        let lr;
        lr = input[i].split(" ");
        let l, r;
        l = parseInt(lr[0]);
        r = parseInt(lr[1]);
        ans += (r - l + 1);
    }
    console.log(ans);
};

myFunc(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)
#define fi first
#define se second

using ll = long long;
using v_int = std::vector<int>;
using v2_int = std::vector<v_int>;
using v_ll = std::vector<ll>;
using v2_ll = std::vector<v_ll>;
using v_string = std::vector<std::string>;
using v_bool = std::vector<bool>;
using v2_bool = std::vector<v_bool>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;

const double PI = 3.1415926535897932;
const int INF = 2*(int)1e9;
const ll LINF = (ll)1e18;
const ll MOD = 1000000007;
//const int dc[4] = {1, -1, 0,  0};
//const int dr[4] = {0,  0, 1, -1};
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

using namespace std; 

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p)
{
    return o << "{" << p.first << "," << p.second << "}";
}

template<typename T> inline
istream& operator>>(istream &is, vector<T> &v)
{
    int len = (int)v.size();
    for(int i = 0; i < len; i++) {
        is >> v[i]; 
    }
    return is;
}

template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &v)
{
    int len = (int)v.size();
    for(int i = 0; i < len; i++) { 
        os << v[i];
        if(i != len-1) { os << ","; } 
    } 
    return os;
}

template<typename T> inline
void chmin(T &a, T b) { a = min(a, b); }

template<typename T> inline
void chmax(T &a, T b) { a = max(a, b); }

int main(void)
{
    string s;
    cin >> s;
    int n = s.size();

    int i = 0;
    int a = 0;
    ll ans = 0;
    while(i < n) {
        if(s[i] == 'A') {
            a++;
            i++;
        } else if(s[i] == 'B') {
            if(i + 1 < n && s.substr(i, 2) == "BC") {
                ans += a;
                i += 2;
            } else {
                a = 0;
                i++;
            }
        } else {
            a = 0;
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

/*atcoder*/


Measured memory_bytes: 3764
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n, c;
    cin >> n >> c;

    vector<ll> r(c + 1, 0);

    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;

        for (int j = c; j >= w; j--) {
            r[j] = max(r[j], r[j - w] + v);
        }
    }

    ll s = 0;
    for (int j = 0; j <= c; j++) {
        s = max(s, r[j]);
    }
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long

using namespace std;

// input
int n;
vector<int> card;

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

    cin >> n;

    int num;
    ll right = 0,left = 0;

    while(cin >> num){
        card.push_back(num);
        right += num;
    }

    right -= card[0];
    left += card[0];

    ll ans = abs(right - left);

    for(int i = 1;i < n-1;i++){
        ans = min(ans,abs(right - left));
        right -= card[i];
        left += card[i];
    }

    cout << ans << "\n";
}

Measured memory_bytes: 1400
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
int N;
ll A[200];

ll dp[205];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> A[i];
    dp[0] = 1000;
    for(int i = 1; i <= N; i++){
        dp[i] = max(dp[i-1], dp[i]);
        for(int j = i+1; j <= N; j++){
            ll rem = dp[i]%A[i-1];
            ll t = (dp[i]/A[i-1])*A[j-1]+rem;
            dp[j] = max(dp[j], t);
        }
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 3648
import sys


def main():
    tmp = input().split()
    h = int(tmp[0].replace('\n',''))
    a = int(tmp[1].replace('\n',''))
    n= h/a
    if (h%a >0):
        n+=1
    print(int(n))

if __name__ == '__main__':
    input = sys.stdin.readline
    main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
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;
}
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //xの方が常に大きい
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}

int main(){
    ll N;cin>>N;
    ll cnt=0;
    for(ll j=1;j<=N-1;j++){
        cnt+=(N-1)/j;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 3636
import math
import sys


scan = sys.stdin.readline


def is_palindrome(s):
    return s == s[::-1]


def main():
    s = scan().rstrip()  # type: str

    if not is_palindrome(s):
        print("No")
        return

    if is_palindrome(s[:len(s) // 2]) and is_palindrome(s[(len(s) + 1) // 2:]):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


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

int byou(int h,int m,int s){
  long long sum;
  sum = h * 3600 + m * 60 + s;
  return sum;
}

int main(){

  int h,m,s,h2,m2,s2,sum,sum2,sum1;
  int ah[3],am[3],as[3];
  
  for(int i = 0; i < 3; i++){
  cin >> h >> m >> s;
  sum1 = h * 3600 + m * 60 + s;
  cin >> h2 >> m2 >> s2;
  sum2 = h2 * 3600 + m2 * 60 + s2;

  sum = sum2 - sum1;

  ah[i] = sum / 3600;
  sum = sum - ah[i] * 3600;
  am[i] = sum / 60;
  sum = sum - am[i] * 60;
  as[i] = sum;
  }

  for(int i = 0; i < 3; i++){
    cout << ah[i] << ' '  << am[i] <<' ' <<  as[i] << endl;
  }

}

Measured memory_bytes: 1160
#include <iostream>
#include <cstring>
using namespace std;
char s[101];
int k;
int main()
{
    cin>>k>>s;
    if(k<strlen(s)){
        for(int i=0;i<k;i++){
            cout<<s[i];
        }
        cout<<"..."<<endl;
        return 0;
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3592
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

vector<E> v;

bool comp(E a, E b){
	return ((a.first==b.first)?(a.second.first<b.second.first):(a.first<b.first));
}

int main(void){
	int i,j,h,w,p;
	for(i=1; i<=150; ++i){
		for(j=(i+1); j<=150; ++j){
			v.push_back(E(i*i+j*j,P(i,j)));
		}
	}
	sort(v.begin(),v.end(),comp);
	while(true){
		cin >> h >> w;
		if(!(h&&w)){
			return 0;
		}
		p = (int)(upper_bound(v.begin(),v.end(),E(h*h+w*w,P(h,w)))-v.begin());
		cout << v[p].second.first << " " << v[p].second.second << endl;
	}
	return 0;
}



Measured memory_bytes: 3220
/**
 *   created: 09 August 2019  11:55:44
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#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;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================

int main()
{
	optimizeIO();
	int tt=1;
	// cin>>tt;
	while(tt--){
		int n,t;
		cin>>n>>t;
		vii v(n);
		rep(i,0,n)
			cin>>v[i].second>>v[i].first;
			sort(all(v));
		int res = INF;
		rep(i,0,n){
			if(v[i].first>t)
				break;
			res = min(res, v[i].second);
		}
		if(res==INF)
			cout<<"TLE";
		else
		cout<<res;
	}
	return 0;
}


Measured memory_bytes: 256
class tree:
    def __init__(self,name,parent):
        self.name = name
        self.parent = parent
        
        
n = int(input())
trees = {str(i):tree(str(i),'-1') for i in range(n)}
child = {}

for i in range(n):
    s = [i for i in input().split()]
    p = s[0]
    child[p] = s[2:]
    s_t = s[2:]
    for j in range(len(s_t)):
        trees[s_t[j]] = tree(s_t[j],p)

def getDepth(u):
    d = 0
    while trees[u].parent != '-1':
        u = trees[u].parent
        d += 1
    return d

def getChildren(u):
    c = []
    for i in trees.values():
        if i.parent == u:
            c.append(i.name)
    return c

for i in range(n):
    
    par = trees[str(i)].parent
    dep = getDepth(str(i))
    ch = [int(i) for i in child[str(i)]]
    
    if par == '-1':sit = 'root'
    elif len(ch) != 0:sit = 'internal node'
    else:sit = 'leaf'
    
    print('node {}: parent = {}, depth = {}, {}, {}'.format(i,par,dep,sit,ch))


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

using namespace std ;

int main () {

    long long m,n ,sum =0 ,mi=100000000;

    cin >> m >> n  ;

    long long a[500]={} ;

    for (int i=0;i<m;i++){
        a[i]= n+(i+1) -1 ;
        sum+=a[i] ;

    }


    for(int i=0;i<m;i++)
    {
        long long x =abs(a[i]-0) ;
        if (x<mi){
            mi=x ;
            n=a[i] ;
        }
    }






    cout << sum-n ;

    return 0 ;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {
    int a,b;
    while(~scanf("%d%d",&a,&b)){
        if((a*b)%2==0) printf("Even\n");
        else printf("Odd\n");
    }
    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 rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
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; }

vector<vector<int>> g(100005);
vector<int> dp(100005, -1);

int dfs(int v){
    if(dp[v] != -1) return dp[v];
    int res = 0;
    for(int u : g[v]){
        chmax(res, dfs(u)+1);
    }
    return dp[v] = res;
}

int main(){
    int n,m; cin >> n >> m;
    rep(i,m){
        int x,y; cin >> x >> y; x--; y--;
        g[x].pb(y);
    }
    int ans = 0;
    rep(i,n) chmax(ans, dfs(i));
    cout << ans << endl;
}


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

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

    long long int total_ht=0;
    int ht=0;
    for(int i=0;i<n;i++)
    {
        total_ht+=max(0,ht-a[i]);
        ht=max(ht,a[i]);
    }
    cout<<total_ht<<"\n";
    
}


Measured memory_bytes: 4332
#include<iostream>
#include<vector>
#include<set>
#include<utility>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<cinttypes>
#include<stack>
#include<ctgmath>
using namespace std;

typedef long long ll;


#define ceil(a,b)  ( !(a%b) ? a/b : a/b+1 )
#define all(a)  (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define endl '\n' 
#define debug(a) cin>>#a>>a;
//vector<ll> primes{ }
template<typename T>
T gcd( T a, T b ) { 
    return !a ? b : gcd( b%a, a); 
}

template<typename T>
T lcm( T a, T b ){
    return (a*b)/gcd(a,b); 
} 

int main(){
    int a = 0,b = 0, h = 0;
    cin >> a >> b >> h;
    cout << ((a+b)*h)/2 << '\n';
    return 0;
}


Measured memory_bytes: 3588
//タイトルが積読なので、2つのスタックがあるんじゃないかな～というエスパー。
#include <iostream>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n, m, k;
int a[200000];
int b[200000];

signed main() {
	int i, j;
	
	cin >> n >> m >> k;
	rep(i, n) cin >> a[i];
	rep(i, m) cin >> b[i];
	
	int sumb = 0;
	rep(j, m) { sumb += b[j]; }
	
	int ans = -1;
	int suma = 0;
	j = m - 1;
	rep(i, n) {
		while (j >= 0 && suma + sumb > k) {
			sumb -= b[j];
			j--;
		}
		if (suma + sumb <= k) ans = max(ans, i + j + 1);
		suma += a[i];
	}
	while (j >= 0 && suma + sumb > k) {
		sumb -= b[j];
		j--;
	}
	if (suma + sumb <= k) ans = max(ans, n + j + 1);
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6740
q=int(input())
def check(t,a,b):
    k=(2*a+t)//2
    return k*(2*a+t-k)<a*b

for i in range(q):
    a,b=sorted(map(int,input().split()))
    if a==b or a==b-1:
        print(2*a-2)
        continue
    l,r=1,b-a
    while l+1<r:
        t=(l+r)//2
        if check(t,a,b):
            l=t
        else:
            r=t
    
    if check(r,a,b):
        print(2*a-2+r)
    elif check(l,a,b):
        print(2*a-2+l)
    else:
        print(2*a-1)


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

#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define MOD 1000000007
#define EPS ((ld)(1e-9))

#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define rep(i, x)  for (int i = 0, _##i = (x); i < _##i; i++)
#define repp(i, x) for (int i = 1, _##i = (x); i <= _##i; i++)
#define repr(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)

#define L(x) ((x)*2)
#define R(x) ((x)*2+1)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
typedef pair<ll, ll> pll;

template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    os << pai.first << ' ' << pai.second;
	return os;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    rep(i, sz(v)) cout << v[i] << ' ';
    return os;
}

template<typename T, typename V>
istream &operator>>(istream &is, pair<T, V> &pai) {
	is >> pai.first >> pai.second;
	return is;
}

int N, A, B;

int main(void) {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    cin >> N >> A >> B;
    int n1 = 0, n2 = 0, n3 = 0;
    rep(i, N) {
        int t; cin >> t;
        if (t <= A) n1++;
        else if (t <= B) n2++;
        else n3++;
    }

    cout << min({n1, n2, n3});
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

int meuMax(int a, int b){
	if (a> b)
		return a;
	return b;
}

int main(){
	int a, b, eq1=0, eq2=0, eq3=0, maior=0, maior2=0;
	scanf("%d %d", &a, &b);
	eq1= a+b;
	eq2= a-b;
	eq3= a*b;

	maior= meuMax(eq1,eq2);
	maior2= meuMax(maior, eq3);
	printf("%d\n", maior2);

    return 0;
}

Measured memory_bytes: 128
def calcP(l, abcd):
    p = 0
    for a, b, c, d in abcd:
        if l[b-1] - l[a-1] == c:
            p += d
    return p

def update(l, i, m, n):
    if i > n:
        return [m for _ in range(n)]

    if l[-i] == m:
        return update(l, i+1, m, n)

    l[-i] += 1
    for j in range(i-1):
        l[-i+j+1] = l[-i]
    return l

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

mp = 0
l = [1 for _ in range(n)]
while True:
    p = calcP(l, abcd)
    if p > mp:
        mp = p
    update(l, 1, m, n)
    if l == [m for _ in range(n)]:
        break

p = calcP(l, abcd)
if p > mp:
    mp = p

print(mp)

Measured memory_bytes: 9156
// ABC 155-A
// 2020.2.16 bal4u

#include <stdio.h>

int a[15];
int main()
{
	int A, B, C;

	scanf("%d%d%d", &A, &B, &C);
	a[A]++, a[B]++, a[C]++;
	puts((a[B] == 2 || a[B] == 2 || a[C] == 2) ? "Yes": "No");
	return 0;
}


Measured memory_bytes: 128
N, M = map(int, input().split())  # N*Nの元の画像, M*Mの探したい画像

A = [input() for _ in range(N)]
B = [input() for _ in range(M)]


for i in range(N-M+1):
    for j in range(N-M+1):
        # print(i, j)
        if A[i][j] == B[0][0]:  # 今見ている元画像の場所と, 探したい画像の左上がマッチしたら探索開始
            flag = True
            # print("始まり")
            for n in range(i, i+M):
                for m in range(j, j+M):
                    # print(n, m)
                    if A[n][m] != B[n-i][m-j]:
                        flag = False
            if flag:
                print("Yes")
                exit()
print("No")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,val,k;
    
    cin>>n>>k;
    vector<int>vect(n);
    vector<int>dp(n,INT_MAX);
    for(int i=0;i<n;i++)
    {
        cin>>val;
        vect[i]=val;
    }
    
    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(vect[i]-vect[i+j]));
            }
        }
       
    }

    cout<<dp[n-1];

    return 0;
}

Measured memory_bytes: 1024
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    }
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! chmax {
    ($x:expr, $e:expr) => {
        if $x < $e {
            $x = $e;
        }
    };
}
macro_rules! chmin {
    ($x:expr, $e:expr) => {
        if $x > $e {
            $x = $e;
        }
    };
}

const INF: i64 = 1 << 60;

fn main() {
    input!{
        N: usize,
        M: usize,
        AB: [(usize, usize); N],
    }
    let mut m = HashMap::new();
    for (A, B) in AB {
        let e = m.entry(A).or_insert(Vec::new());
        e.push(B);
    }
    let mut ans = 0;
    let mut bh = BinaryHeap::new();
    for i in (0..M).rev() {
        let d = M - i;
        if let Some(v) = m.get(&d) {
            for i in v {
                bh.push(i);
            }
        }
        if let Some(&i) = bh.pop() {
            ans += i;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 21132
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve() {
	int n, d, a; cin >> n >> d >> a;
    vector<int> x(n), h(n);
    vector<P> m(n);
    rep(i, n) {
        cin >> x[i] >> h[i];
        m[i] = make_pair(x[i], h[i]);
    }
    priority_queue<P, vector<P>, greater<P>> pque;
    sort(all(m));
    int cnt = 0;
    int now = 0;
    rep(i, n) {
        int X = m[i].fr, H = m[i].sc;
        while(pque.size() > 0 && X > pque.top().fr) {
            int Z = pque.top().sc;
            now -= Z;
            pque.pop();
        }
        H -= now * a;
        if(H <= 0) continue;
        int co = (H + a - 1) / a;
        cnt += co;
        pque.push(make_pair(X + 2 * d, co));
        now += co;
    }
    cout << cnt << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}


Measured memory_bytes: 8692
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <bitset>
#include <functional>
#include <set>
#include <map>
#include <array>

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define fst first
#define snd second
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cout << #x << ": " << x << endl
//#define int long long int
const int MOD = 1000000007;
const int INF = 100100100;
const double EPS = 0.000000001;

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

bool pairCompare(const P& pair1, const P& pair2) {
    return pair1.second > pair2.second;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A, B, T;
  cin >> A >> B >> T;
  int count = T / A;
  int ans = count * B;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 300010, P = 1e9 + 7;
int H, W, n;
int fac[N], inv[N], f[N];
pair <int, int> p[N];
int C(int n, int m){
	return 1ll * fac[n] * inv[n - m] % P * inv[m] % P;
}
int power(int x, int y){
	int i = x; x = 1;
	while (y > 0){
		if (y % 2 == 1) x = 1ll * i * x % P;
		i = 1ll * i * i % P;
		y /= 2;
	}
	return x;
}
int main(){
	read(H); read(W); read(n);
	fac[0] = 1;
	for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[N - 1] = power(fac[N - 1], P - 2);
	for (int i = N - 2; i >= 0; i--) 
		inv[i] = (1ll * inv[i + 1] * (i + 1)) % P;
	for (int i = 1; i <= n; i++)
		read(p[i].first), read(p[i].second);
	sort(p + 1, p + n + 1);
	p[n + 1].first = H, p[n + 1].second = W;
	for (int i = 1; i <= n + 1; i++){
		f[i] = C(p[i].first + p[i].second - 2, p[i].first - 1);
		for (int j = 1; j < i; j++){
			if (p[i].first >= p[j].first && p[i].second >= p[j].second)
				f[i] = (f[i] - 1ll * f[j] * C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first) % P + P) % P;
		}
	}
	printf("%d\n", f[n + 1]);
	return 0;
}



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

using namespace std;

int n, nr = -1, st[22];
int Ap[17];
long long ans, p[17];

void back() {
    for(int i = 1; i <= n; ++i) {
        Ap[i] = 0;
    }
    for(int i = 1; i <= st[0]; ++i) {
        Ap[st[i]] = 1;
    }
    Ap[n + 1] = 1;
    long long s = 0;
    for(int i = 1; i <= n + 1; ++i) {
        if(Ap[i] == 0) {
            s = s * 10 + p[i];
        }
        else {
            ans += s;
            s = 0;
        }
    }
    for(int i = st[st[0]] + 1; i <= n; ++i) {
        st[++st[0]] = i;
        back();
        st[st[0]] = 0;
        --st[0];
    }
}
int main() {
    long long number;
    cin >> number;
    while(number) {
        p[++n] = number % 10;
        number /= 10;
    }
    reverse(p + 1, p + n + 1);
    back();
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	void run(){
		for(;;){
			int n=sc.nextInt();
			if(n==0){
				break;
			}
			LinkedList<Integer> list=new LinkedList<Integer>();
			for(int i=1; i<=n; i++){
				int c=sc.nextInt()*2-1;
				// 0:white,1:black
				// -:white, +:black
				int d=0;
				if(!list.isEmpty()){
					d=list.pop();
				}
				if(c*d>=0){
					list.push(c+d);
				}else{
					if(i%2==1){
						list.push(d);
						list.push(c);
					}else{
						int e=0;
						if(!list.isEmpty()){
							e=list.pop();
						}
						list.push((abs(e)+abs(d)+abs(c))*c);
					}
				}
			}
			int ans=0;
			for(int c : list){
				if(c<0){
					ans-=c;
				}
			}
			println(ans+"");
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double lld;
ll MOD = (1e9)+7;
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int kx[] = {+1, +2, -1, -2, +1, +2, -1, -2};
const int ky[] = {+2, +1, +2, +1, -2, -1, -2, -1};
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
inline void fastIO(){
  ios_base::sync_with_stdio(0);cin.tie(0);
}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }

#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

int main(){
  fastIO();
  int n;
  cin>>n;
  cout<<1-n<<endl;
  return 0;
}


Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<math.h>
#include<string>
#include <cctype>
#include <cstdlib>
#include<bitset>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl;
#define INF 1ll<<60;
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; }

using namespace std;
using ll = long long;
typedef pair<int, int> P;

int main(){
    set<int> mp;
    int n; cin >> n;
    int m;
    rep(i, n){
        cin >> m;
        mp.insert(m);
    }
    out(mp.size());

}

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

int main(){
  using int128 = __int128;
  int N;
  cin >> N;
  vector<int> P(N);
  for(int i = 0; i < N; ++i){
    cin >> P[i];
  }
  int ans = 0;
  for(int i = 1; i < (1<<N); ++i){
    int128 l = 1;
    for(int j = 0; j < N; ++j){
      if(i>>j&1) l *= P[j]/__gcd<int128>(l,P[j]);
    }
    bool f = true;
    for(int j = 0; j < N; ++j){
      if(i>>j&1) continue;
      if(l%P[j] == 0){
        f = false;
        break;
      }
    }
    // cerr << i << " " << f << " " << (long long)l << endl;
    ans += f;
  }
  cout << ans << endl;
}



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

using namespace std;

const int MOD = 1000000007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> C(N);
  vector<vector<int>> pos(200010);
  for (int i = 0; i < N; i++) {
    cin >> C[i];
    pos[C[i]].emplace_back(i);
  }
  vector<int64_t> dp(200010, 0);
  dp[0] = 1;
  for (int i = 1; i < N + 1; i++) {
    dp[i] += dp[i - 1];
    dp[i] %= MOD;
    int p = lower_bound(pos[C[i - 1]].begin(), pos[C[i - 1]].end(), i - 1) - pos[C[i - 1]].begin();
    if (p > 0) {
      int j = pos[C[i - 1]][p - 1];
      if ((i - 1) - j > 1) {
        dp[i] += dp[j + 1];
        dp[i] %= MOD;
      }
    }
  }
  cout << dp[N] << '\n';
  return 0;
}


Measured memory_bytes: 16212
#include <iostream>
using namespace std;
#define QSIZE 100000

struct pp {
    char name[10];
    int time;
};
struct pp queue[QSIZE];
int head=0,tail=0;

struct pp dequeue(){
    pp x = queue[head];
    head = (head + 1) % QSIZE;
    return x;
};
void enqueue(pp p){
    queue[tail] = p;
    tail = (tail+1)%QSIZE;    
};

#define min(a,b) (a > b ? b : a)
int main(){
    int n,q,ptime,elaps=0;
    struct pp prc;

    cin >> n >> q;
    for (int i=0; i<n; i++){
        cin >> prc.name >> prc.time;         
        enqueue(prc);
    }
    
    while(head != tail){
        prc = dequeue();
        elaps += min(prc.time, q);
        prc.time -= q;
        if( prc.time > 0)
            enqueue(prc);
        else
            cout << prc.name << " " << elaps << endl;
    }


}





Measured memory_bytes: 4544
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>
#include <string.h>

using namespace std;

int  k;
long long s;

int gcd(int a, int b) {
    int tmp;
    while(b != 0) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main () {
    cin >> k;
    for ( int i = 1; i <= k; i++) {
        for ( int j = 1; j <= k; j++) {
            for ( int z = 1; z <= k; z++) {
                s = s + gcd(gcd(i, j), z);
            }
        }
    }
    cout << s;
}


Measured memory_bytes: 3624