akhauriyash/Code-Regression huggingface dataset:
// Problem : M - Candies
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_m
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define Ma7moud_7amdy                 \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define Open_Sesame Open()
#define all(v) ((v).begin()), ((v).end())
#define allr(v) ((v).rbegin()), ((v).rend())
#define clr(arr, x) memset(arr, x, sizeof arr)
#define endl "\n"
#define watch(x) cout << #x << " = " << x << endl;
#define RT(x) return cout << (x), 0;
#define Accepted 0
#define INF 0x3f3f3f3f3f3f3f3fLL
typedef long long ll;
typedef vector<int> vi;
const int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
void Open()
{
#ifndef ONLINE_JUDGE 
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}
const int mod = ll(1e9 + 7), N = 2000 + 5;
//“Nobody but you have to believe in your dreams to make them a reality.” ― Germany Kent
int n, k, a[101], mem[101][100005],dp[101][100005];
map<int, int>mp;
int solve(int i = 0, int rem = k) {
	if (!rem)return 1;
	if (i == n)
	{
		return rem == 0;
	}
	int& ret = mem[i][rem];
	if (~ret)return ret;
	ret = 0;
	for (int ch = 0; ch <= min(rem, a[i]); ch++) {
		ret += solve(i + 1, rem - ch) % mod;
		ret %= mod;
	}
	return ret;
}
int main()
{
	Ma7moud_7amdy;
//	Open_Sesame;
	//clr(mem, -1);
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
//	cout << solve() << endl;

	//baseCase
	for (int i = 0; i <= n; i++) {
		dp[i][0] = 1;
	}

	//itteration
	for (int i = n - 1; i >= 0;i--) {
		//perfixSum
		for (int rem = 1; rem <= k; rem++) {
			dp[i+1][rem] +=dp[i+1][rem-1]%mod;
			dp[i+1][rem]%=mod;
		}
		for (int rem = 0; rem <=k; rem++) {
			int& ret = dp[i][rem];
			ret = 0;
			/*for (int ch = 0; ch <= min(rem, a[i]); ch++) {
				ret += dp[i + 1][rem - ch];
				ret %= mod;
			}*/
			ret += ((dp[i + 1][rem] - dp[i + 1][rem - min(rem, a[i])-1])%mod+mod)%mod;
			ret%=mod;
		}
	}
	cout << dp[0][k] << endl;
}


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

using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> vec(n);
	vector<int> ranges(n);
	for (int i = 0; i < n; ++i) {
		cin >> vec[i];
	}

	int l, r;
	for (int i = 0; i < n; ++i) {
		l = vec[i];
		r = k - vec[i];
		if (l > r) {
			ranges[i] = 2 * r;
		} else {
			ranges[i] = 2 * l;
		}
	}

	int ret = 0;
	for (auto&& elm : ranges) {
		ret += elm;
	}

	cout << ret << endl;
}



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

using namespace std;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define sz size
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define FORRN(i,a,b) for (int i=(a);i>=(b);i--)
#define FORR(i,a,b) for (int i=(a);i>(b);i--)
typedef unsigned long long ull;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); //Fast I/O
    cin.tie(0);
    cout.tie(0);
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);

    int a,b,c;
    cin >> a >> b >> c;

    cout << (a*b)/2 << endl;

    return 0;
}


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

using namespace std;

int main(){
  string s;
  cin >> s;
  int count = 0;
  for(int i = 0; i < s.length(); i++){
    if(s[i] == 'o') count++;
  }
  if(count + 15 - s.length() >= 8) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int add(int a, int b){
  return (a % mod + b % mod) % mod;
}

int sub(int a, int b){
  return (a % mod - b % mod + mod) % mod;
}

int dp[102][100002];
int main(){
  ios::sync_with_stdio(0);
  int n, k; cin >> n >> k;
  vector<int>a(n);
  for(int i = 0; i < n; i++)
    cin >> a[i];

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

  for(int ind = n - 1; ind >= 0; ind--){
    for(int leftk = 0; leftk <= k; leftk++){
      int low = max(0, leftk - a[ind]);
      dp[ind][leftk] = sub(dp[ind + 1][leftk], low ? dp[ind + 1][low - 1] : 0);
      // cout << ind << ' ' << leftk << ' ' << dp[ind][leftk] << endl;
      if(leftk)
        dp[ind][leftk] = add(dp[ind][leftk], dp[ind][leftk - 1]);
    }
  }

  cout << sub(dp[0][k], dp[0][k - 1]) << endl;
  return 0;
}


Measured memory_bytes: 39680
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    int N;
    string s;
    cin >> N >> s;

    int ans = INF;
    vector<int> b(N+1, 0), w(N+1, 0);
    rep(i, N){
        if(0 <= i-1){
            if(s[i] == '#'){
                b[i] += b[i-1] + 1;
                w[i] = w[i-1];
            }else{
                b[i] = b[i-1];
                w[i] += w[i-1] + 1;
            }
        }else{
            if(s[i] == '#'){
                b[i] += 1;
                w[i] = 0;
            }else{
                w[i] += 1;
                b[i] = 0;
            }
        }
    }


    rep(i, N){
        int sum = 0;
        sum = (w[N-1] - w[N-i]) + b[N-i];

        ans = min(ans, sum);
    }
    if(N == 1) ans = 0;
    if(N == 2){
        if(s[0] == '.' && s[1] == '#') ans = 0;
    }
    cout << ans << endl;

    return 0;
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x,y;
    int a,b,c;
    cin>>x>>y>>a>>b>>c;

    priority_queue<int> aa;
    priority_queue<int> bb;
    priority_queue<int> cc;
    int d;
    for(int i=0;i<a;i++)
    {
        cin>>d;
        aa.push(d);
        bb.push(INT_MIN);
        cc.push(INT_MIN);
    }
    for(int i=0;i<b;i++)
    {
        cin>>d;
        bb.push(d);
        aa.push(INT_MIN);
        // bb.push(INT_MIN);
        cc.push(INT_MIN);
    }
    for(int i=0;i<c;i++)
    {
        cin>>d;
        cc.push(d);
        aa.push(INT_MIN);
        bb.push(INT_MIN);
        // cc.push(INT_MIN);
    }

    int s=x+y;
    int count=0;
    int counta=0;
    int countb=0;
    long long sum=0;
    for(int i=0;i<s;)
    {
        int t,r,v;
        if(!aa.empty() and !bb.empty() && !cc.empty())
        t=max({cc.top(),aa.top(),bb.top()});
        // cout<<t<<" ";
        if(t==aa.top() )
        {
             if(counta<x)
            {
                sum+=aa.top();
                counta++;
                i++;
            }
            aa.pop();
        }
        else if(t==bb.top())
        {

            if(countb<y)
            {
                sum+=bb.top();
                countb++;
                i++;
            }
            bb.pop();
            
        }
        else if(t==cc.top())
        {
            sum+=cc.top();
            cc.pop();
            count++;
            i++;
        }
        

        
    }

    cout<<sum;
    return 0;

}

Measured memory_bytes: 4576
// ABC 160-E
// 2020.3.28 bal4u

#include <stdio.h>
#include <string.h>

typedef long long ll;

#define gc() getchar_unlocked()
int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define QSIZE 350000

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

typedef struct { int t, c; } QUE;
QUE que[QSIZE + 5];
int qsize;

void max_heapify(int i) {
	int l, r, max;
	QUE qt;
	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t > que[i].t) max = l; else max = i;
	if (r < qsize && que[r].t > que[max].t) max = r;
	if (max != i) {
		qt = que[i], que[i] = que[max], que[max] = qt;
		max_heapify(max);
	}
}

void deq() {
	que[0] = que[--qsize];
	max_heapify(0);
}

void enq(int t, int c) {
	int i, max;
	QUE qt;

	i = qsize++;
	que[i].t = t, que[i].c = c;
	while (i > 0 && que[max = PARENT(i)].t < que[i].t) {
		qt = que[i]; que[i] = que[max], que[max] = qt;
		i = max;
	}
}

int H, W, K;
char S[12][1005];
int col[12];

int main()
{
	int g, X, Y, A, B, C;
	ll ans;

	X = in(), Y = in();
	A = in(), B = in(), C = in();
	while (A--) enq(in(), 1);
	while (B--) enq(in(), 2);
	while (C--) enq(in(), 0);
	ans = 0, g = X + Y;
	while (g) {
		if (que[0].c == 1) {
			if (X) X--, g--, ans += que[0].t;
		} else if (que[0].c == 2) {
			if (Y) Y--, g--, ans += que[0].t;
		} else g--, ans += que[0].t;
		deq();
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 2560
#pragma GCC optimize("-O3")
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#define LL long long
#define ui unsigned int
#define ull unsigned long long
using namespace std;
 
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Out(int x){
    if(x>9) Out(x/10);
    putchar('0'+x%10);
}
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
LL qpow(LL x,LL y,LL P){
    LL re=1;
    while(y){
        if(y&1) re=re*x%P;
        x=x*x%P;y>>=1;
    }
    return re;
}
const double ept=1e-8;
int a,b,c;
int main(){
	scanf("%d%d%d",&a,&b,&c);
	c=min(c,a+b+1);
	printf("%d\n",b+c);
	return 0;
}
/*
3 3 0
1 2
1 3
2 3
1 2
*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[1000000];
int main()
{
    string str;
    cin>>str;
    dp[0]=1;
    int n=str.length();
    for(int i=0;i<n;i++)
    {
        if(dp[i]==0)continue;
        if(i+5<=n && str.substr(i,5)=="dream")dp[i+5]=1;
        if(i+7<=n && str.substr(i,7)=="dreamer")dp[i+7]=1;
        if(i+5<=n && str.substr(i,5)=="erase")dp[i+5]=1;
        if(i+6<=n && str.substr(i,6)=="eraser")dp[i+6]=1;
    }
    if(dp[n]==1)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 896
from math import gcd
 
n=int(input())
mod = 10**9+7
 
d = dict()
zeros=0
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    zeros+=1
    continue
  if all((a,b)):
    g = gcd(a,b)*(a//abs(a))
  elif a:
    g = a
  else:
    g = b
  
  p = a//g,b//g
  d[p] = d.get(p,0)+1
 
ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v)+pow(2,w)-1)
  ans %= mod
print((ans+zeros-1+mod)%mod)

Measured memory_bytes: 71852
#include<iostream>
using namespace std;
int N,D,X,A,ans=0;
int main(void){
	cin>>N>>D>>X;
	ans=X;
	for(int i=0;i<N;i++){
		cin>>A;
		int sum=1;
		for(int i=A+1;i<=D;i+=A)sum++;
		ans+=sum;
	}
	cout<<ans;
	return 0;
}


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

int factorial(int x)
{
    int tmp = x;
    for (int i = 1; i < x - 1; ++i)
        tmp *= x - i;
    return tmp;
}
int main()
{
    int z[8][2];
    int n;
    cin >> n;
    for (int i = 0; i < n;i++)
    {
        int x, y;
        cin >> x >> y;
        z[i][0] = x;
        z[i][1] = y;
    }
    double sum = 0;
    for (int i = 0; i < n;i++)
    {
        for (int j = 0; j < n;j++)
        {
            sum += sqrt(((z[i][0] - z[j][0]) * (z[i][0] - z[j][0])) + ((z[i][1] - z[j][1]) * (z[i][1] - z[j][1])));
        }
    }
    sum /= n;
    cout << fixed << setprecision(10) << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    string s;cin >> s;
    ll k; cin >> k;

    bool one = true;
    if (k<=s.size()){
        for (ll i =0;i < k ;i++){
        if (s[i] !='1'){
            one = false;
        }   
    }
    }
    else {
        rep(i,s.size()){
            if (s[i] !='1'){
            one = false;
        }
    }
    }
    if (one) cout << 1 << endl;
    else if (!one){
        rep(i,s.size()){
            if (s[i] != '1'){
                cout << s[i] << endl;
                break;
            }
        }
    }   
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
    
    int counter = 0;
    int test_case;
    
    while(1){
        scanf("%d", &test_case);
        if(test_case == 0) break;
        else printf("Case %d: %d\n", counter+1, test_case);
        counter++;
    }

}



Measured memory_bytes: 2044
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();
		System.out.printf("%.8f %.8f", r * r * Math.PI, 2 * r * Math.PI);
	}
}


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

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

    ll ans = 0;
    for (ll i = 1; i <= 1000000; ++i) {
        ll a = (n - 1) / i;
        ans += a;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll N,K; cin >> N >> K;
    vector<ll> A(N); for(auto& in :A) cin >> in;
    vector<ll> x(200001);
    set<ll> s;
    for(int i = 0; i < N;i++){
        x[A[i]]++;
        s.insert(A[i]);
    }
    sort(x.begin(),x.end());
    for(int i = 0; i <= 200000; i++){
        if(s.size() <= K) break;
        if(x[i] == 0) continue;
        res += x[i];
        s.erase(*s.begin());
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int x;

main () {
	int c = 100;
	cin >> x;
	int timer = 0;
	while (c < x) {
		int d = c / 100;
		c += d;
		++timer;
	}

	cout << timer << endl;
}




Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vi2 = vector<vector<int>>;
using vb = vector<bool>;
using vb2 = vector<vector<bool>>;
using vc = vector<char>;
using vc2 = vector<vector<char>>;
using vs = vector<string>;
using si = set<int>;
using vs2 = vector<vector<string>>;
using pii = pair<int, int>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
const long double PI = acos(-1.0);
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)
#define sz(x) (int)(x).size()
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
 
#define ALL(x) (x).begin(),(x).end()
#define SORT(v) sort(ALL(v));
#define IN(type,a) type a;cin >> a;
#define VIN(type,a,n) vector<type> a(n);cin >> a;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl;
#define COUT(x) cout << (x) << endl;
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl;
#define ENDL cout << endl;
#define DB(s,x) cout << (s) << " : " << x << endl;

#define HOGE COUT("HOGE")

template<typename T>inline istream& operator>>(istream&i,vector<T>&v)
{REP(j,sz(v))i>>v[j];return i;}

template<typename T> bool chmax(T& a, const T& b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T& a, const T& b){if(a>b){a=b;return true;}return false;}
int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d ;
    COUT(a+b+c+d);
}



Measured memory_bytes: 3088
#使える整数の数 m = 1000
#そのまま計算すると
# m ^ 4 = １兆とおり
#なので、分割して計算する
#600万とおりですむ

# m * m = １００万とおり
dp2 = Array.new(2001).fill(0)
(0..1000).each do |a|
  (0..1000).each do |b|
    dp2[a + b] += 1
  end
end

#m * 2m = 200万とおり
dp3 = Array.new(3001).fill(0)
(0..1000).each do |c|
  dp2.size.times do |s|
    dp3[s + c] += dp2[s]
  end
end
dp2 = nil

# m * 3m = 300万とおり
dp4 = Array.new(4001).fill(0)
(0..1000).each do |d|
  dp3.size.times do |s|
    dp4[s + d] += dp3[s]
  end
end
dp3 = nil

while input = $stdin.gets do
  p dp4[input.to_i]
end

Measured memory_bytes: 6172
#include<stdio.h>
#include<string.h>
int main(){
int n,i,taro=0,hanako=0;
char card1[101],card2[101];
scanf("%d",&n);
for(i=0;i<n;i++){
 scanf("%s %s",card1,card2);
 if(strcmp(card1,card2)==0) taro+=1,hanako+=1;
 else if(strcmp(card1,card2)>0) taro+=3;
 else if(strcmp(card1,card2)<0) hanako+=3;
}
printf("%d %d\n",taro,hanako);
return 0; }


Measured memory_bytes: 2036
package main

import "fmt"

func main(){
	var n,last int
	fmt.Scan(&n)
	all := make([]int,n)
	for i:=0; i<n;i++{
		fmt.Scan(&all[i])
		if all[i] == last+1{
			last += 1
		}
	}
	if last == 0 {
		fmt.Printf("%d", -1)
	}else {
		fmt.Printf("%d", n-last)
	}
}

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

long rec(int w[], int v[], int n, int W, int id, long **mem)
{
  if(W<0)
    return -1;
  if(id==n)
    return 0;
  if(W==0)
    return 0;
  if(mem[id][W]!=-1)
    return mem[id][W];
  long a=rec(w,v,n,W,id+1,mem);
  long b=rec(w,v,n,W-w[id],id+1,mem);
  if(b!=-1)
    b+=v[id];
  mem[id][W]=max(a,b);
  return max(a,b);
  
}


int main(){
  int n,W;
  cin>>n>>W;
  int w[n],v[n];
  for(int i=0;i<n;i++)
    cin>>w[i]>>v[i];
  long **mem=new long*[n+1];
  for(int i=0;i<=n;i++)
  {
    mem[i]=new long[W+1];
    for(int j=0;j<=W;j++)
      mem[i][j]=-1;
  }
  cout<<rec(w,v,n,W,0,mem)<<endl;
	  
  
}

Measured memory_bytes: 79488
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int min = Math.abs(l);
        int k = 1;
        int sum = l;
        for (int i = 2; i <= n; i++) {
            if (min > Math.abs(l - 1 + i)) {
                min = Math.abs(l - 1 + i);
                k = i;
            }
            sum += l + i - 1;
        }
        System.out.println(sum - (l + k - 1));
        sc.close();
    }
}

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

#define ONLINE_JUDGE
#define pb(a) push_back(a)
#define ALL(a) a.begin(), a.end()
#define FOR(x,to) for(x=0;x<(to);x++)

using ll = long long;

const int E5 = 1e5;

//////////// Solution /////////////////////////////////

void solve() {
	int N,M,X;
	int A[101];
	cin >> N >> M >> X;
	int s1=0,s2=0;
	for (int i = 1; i <= M; ++i) {
		cin >> A[i];
		if (A[i] < X) {
			++s1;
		} else {
			++s2;
		}
	}

	cout << min(s1,s2) << '\n';
}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////

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

int main()
{
    int n; cin >> n;
    vector<vector<int>> graph(n);
    vector<vector<char>> A(n, vector<char>(n, '0'));
    int origin;
    for (int i = 0; i < n; ++i)
    {
        int u; cin >> u; u -= 1;
        int m; cin >> m;
        for (int k = 0; k < m; ++k)
        {
            int v;
            cin >> v;
            v -= 1;
            A[u][v] = '1';
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int k = 0; k < n; ++k)
        {
            cout << A[i][k];
            if (k < n-1)
            {
                cout << " ";
            }
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3168
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
typedef long long ll;
using namespace std;

int main() {
	int N; cin >> N;
	int sum = 0;
	int l[100010], r[100010];
	for (int i = 0; i < N; ++i) cin >> l[i] >> r[i];
	for (int i = 0; i < N; ++i) sum = sum + r[i] - l[i] + 1;
	cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n;
  cin >> n;
  cout << 180*(n-2) << newl;
  return 0;
}

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

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

	int n[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int ans = n[K - 1];

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a*b>c*d) cout << a*b << endl;
    else cout << c*d << endl;
    return 0;
}

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

vector <int> adia[100010];
int ans;

bool dfs(int nod, int tata)
{
    int nrfii(0), nrpusi(0);
    for (auto i : adia[nod]) {
        if (i == tata)
            continue;
        nrfii++;
        nrpusi += dfs(i, nod);
    }
    if (nrfii - nrpusi > 1) {
        ans += nrfii - nrpusi - 1;
        nrpusi = nrfii - 1;
    }
    return nrpusi != 0;
}

int main()
{
    int n, gmax(0), a, b;
    cin >> n;

    for (int i(1); i < n; i++) {
        cin >> a >> b;
        adia[a].push_back(b);
        adia[b].push_back(a);
        gmax = max(gmax, (int)max(adia[a].size(), adia[b].size()));
    }

    if (gmax <= 2) {
        cout << 1 << '\n';
        return 0;
    }

    for (int i(0); i < n; i++) {
        if (adia[i].size() >= 3) {
            dfs(i, -1);
            break;
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 9088
{-# LANGUAGE PartialTypeSignatures #-}
{-# LANGUAGE TypeApplications #-}
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L

main :: IO ()
main = readInts >>= output . solve

solve :: [Int] -> _
solve [x] = fst $ until ((x'<=).snd) (\(n,v) -> (n+1, fromIntegral @Int @Double . floor . (*rate) $ v)) (0, 100.0)
  where
    x' = fromIntegral @Int @Double x
    rate = 1.01 :: Double

output :: _ -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine

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

int main(){
  int s;
  cin >> s;
  int a=s;
  
  if(s == 1 || s == 2){
    cout << 4 << endl;
  }
  else if(s == 3){
    cout << 9 << endl;
  }
  else{
    for(int i=0;;i++){
      if(a==4){
        cout << i+4 << endl;
        break;
      }
      else{
        if(a%2 == 1){
          a = 3*a+1;
        }
        else{
          a = a/2;
        }
      }
    }
  }
  
  
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
char s[200005];
int a[2020];
int main()
{
	scanf("%s",&s);a[0]=1;
	int l=strlen(s)-1;int num=0,mod=2019;int ans=0,p=1;
	for(int i=l;i>=0;--i)
	{
	ans=(ans+(s[i]-'0')*p)%mod;
	num+=a[ans];a[ans]++;p=p*10%mod;
//	printf("ans:%d a[ans]:%d\n",ans,a[ans]);
	}
	printf("%d",num);
}

Measured memory_bytes: 3980
package main

import (
	"fmt"
)

// main is ...
func main() {
	var a, b, k int
	fmt.Scan(&a, &b, &k)

	fmt.Print(calc(a, b, k))
}

func calc(a, b, k int) (int, int) {
	if 0 < a {
		if k < a {
			a -= k
			return a, b
		}
		k -= a
		a = 0
	}

	if 0 < b {
		if b < k {
			return a, 0
		}
		return a, b - k
	}
	return a, b
}



Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using LL = long long;
using ULL = unsigned long long;

using namespace std;

int main()
{
    int n;
    vector<string> strs;
    string tempstr;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tempstr;
        strs.emplace_back(tempstr);
    }

    for (const auto& x : strs)
    {
        if (x == "Y")
        {
            cout << "Four" << endl;
            return 0;
        }
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mo=1e9+7,N=2e5+5;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
struct Node{
	LL a[2];
	bool operator < (const Node &b)const{
		if(a[0]!=b.a[0])return a[0]<b.a[0];
		return a[1]<b.a[1];
	}
};
map<Node,Node>mp;
int Pow[N];
int main(){
	int n,d;LL a,b,c,ans=1,w=0;scanf("%d",&n);
	Pow[0]=1;for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*2%mo;
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&a,&b);
		if(!(a|b)){w++;continue;}
		c=gcd(a,b),a/=c,b/=c;
		if(abs(b)<abs(a))d=1,swap(a,b),b=-b;
		else if(abs(a)==abs(b)&&(a|b)<0)d=1,a=abs(a),b=abs(b);
		else d=0;
		if(!a)b=1;if(a<0)a=-a,b=-b;
		mp[{a,b}].a[d]++;
	}
	for(auto x:mp)(ans*=Pow[x.second.a[0]]+Pow[x.second.a[1]]-1)%=mo;
	printf("%d",((ans+w-1)%mo+mo)%mo);
	return 0;
}

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

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

    vector<unsigned int> h(n);
    unsigned int count = 0;
    for(auto &e: h) {
        cin >> e;
        if ( e >= k) {
            ++count;
        }
    }
    cout << count << endl;

}



Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 10000
using namespace std;
typedef long long ll;

int main(){
  int n;
  int a[200100];
  cin >> n;
  rep(i, 1, n+1){
    cin >> a[i];
    a[i] -= i;
  }

  sort(a+1, a+n+1);

  int b = a[n/2 + 1];
  long long ans = 0;
  rep(i, 1, n+1){
    ans += abs(a[i]-b);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
  int n,m,i,num=0;
  int vote[1000];
  double x = 0;
  scanf("%d %d",&n,&m);
  for(i = 0; i < n; i++){
    scanf("%d",&vote[i]);
    x += vote[i];
  }
  x = x/(4*m);
  for(i = 0; i < n; i++){
    if(vote[i] >= x)
      num++;
  }
  if(num >= m)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;
}

Measured memory_bytes: 1668
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    string s; cin >> s;
    if (s.back() == 's') {
        cout << s << "es" << endl;
    } else {
        cout << s << "s" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int list[3][3];
  for(int i = 0; i<3; i++) {
    for(int j = 0; j<3; j++) {
      cin >> list[i][j];
    }
  }
  bool check = false;
  if(list[0][0] + list[1][1] == list[1][0] + list[0][1]
  && list[1][0] + list[2][1] == list[1][1] + list[2][0]
  && list[0][1] + list[1][2] == list[1][1] + list[0][2]
  && list[1][1] + list[2][2] == list[2][1] + list[1][2]
  ) check = true;

  cout << (check ? "Yes" : "No") << endl;

  return 0;
}

Measured memory_bytes: 256
/*g++ main.cpp -o main.out*/
/*./main.out*/

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

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

const int maxn = 400010;
const LL p = 1000000007;
LL f[maxn];
LL inv[maxn]; // 阶乘的逆元
LL Pow(LL a, LL n, LL m)
{
    LL t = 1;
    for (; n; n >>= 1, a = (a * a % m))
        if (n & 1)
            t = (t * a % m);
    return t;
}
void CalFact()
{
    f[0] = 1;
    for (int i = 1; i < maxn; i++)
        f[i] = (f[i - 1] * i) % p;
    inv[maxn - 1] = Pow(f[maxn - 1], p - 2, p);
    for (int i = maxn - 2; ~i; i--)
        inv[i] = inv[i + 1] * (i + 1) % p;
}
LL C(int n, int m)
{
    return f[n] * inv[m] % p * inv[n - m] % p;
}


int main()
{
    CalFact();
    LL ans=0;
    int n,k;
    cin>>n>>k;
    for(int i=0;i<min(n,k+1);++i)
        ans=(ans+C(n-1,i)*C(n,i)%Mod)%Mod;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
signed main(){
    int N;cin>>N;
    vector<pair<int,int>>Red(N);//y,xの順
    vector<pair<int,int>>Blue(N);//x,yの順
    REP(i,N){
        int x,y;cin>>x>>y;
        Red[i]=mp(y,x);
    }
    REP(i,N){
        int x,y;cin>>x>>y;
        Blue[i]=mp(x,y);
    }
    bool Aisused[N];
    bool Bisused[N];
    REP(i,N) Aisused[i]=Bisused[i]=false;
    sort(Red.rbegin(),Red.rend());
    sort(Blue.begin(),Blue.end());
    int ans=0;
    REP(i,N){
        REP(j,N){
            if(Red[i].first<Blue[j].second&&Red[i].second<Blue[j].first&&!Aisused[i]&&!Bisused[j]){
                ans++;
                Aisused[i]=true;
                Bisused[j]=true;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
from functools import reduce
def cmb(n,r,mod):
  r=min(r,n-r)
  if r==0:
    return 1
  over=reduce(lambda x,y:(x*y)%mod,range(n,n-r,-1))
  under=reduce(lambda x,y:(x*y)%mod,range(1,r+1))
  return (over*pow(under,mod-2,mod))%mod

mod=10**9+7
n, a, b = map(int, input().split())
print((pow(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))%mod)

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

template <long long mod>
struct modular {
    long long value;
    modular(long long x = 0LL) {
        value = x % mod;
        if (value < 0LL) value += mod;
    }
    modular& operator+=(modular other) {
        if ((value += other.value) >= mod) value -= mod;
        return *this;
    }
    modular& operator-=(modular other) {
        if ((value -= other.value) < 0LL) value += mod;
        return *this;
    }
    modular& operator*=(modular other) {
        value = value * other.value % mod;
        return *this;
    }
    modular& operator/=(modular other) {
        long long a = 0LL, b = 1LL, c = other.value, m = mod;
        while (c != 0LL) {
            long long t = m / c;
            m -= t * c;
            swap(c, m);
            a -= t * b;
            swap(a, b);
        }
        a %= mod;
        if (a < 0LL) a += mod;
        value = value * a % mod;
        return *this;
    }
    modular operator-() { return modular(-value); }
    modular operator+(modular rhs) { return modular(*this) += rhs; }
    modular operator-(modular rhs) { return modular(*this) -= rhs; }
    modular operator*(modular rhs) { return modular(*this) *= rhs; }
    modular operator/(modular rhs) { return modular(*this) /= rhs; }
    bool operator==(modular rhs) { return value == rhs.value; }
    bool operator!=(modular rhs) { return value != rhs.value; }
    bool operator<(modular rhs) { return value < rhs.value; }
};
template <long long mod>
string to_string(modular<mod> x) {
    return to_string(x.value);
}
template <long long mod>
ostream& operator<<(ostream& stream, modular<mod> x) {
    x.value %= mod;
    if (x.value < 0LL) x.value += mod;
    return stream << x.value;
}
template <long long mod>
istream& operator>>(istream& stream, modular<mod>& x) {
    stream >> x.value;
    x.value %= mod;
    if (x.value < 0LL) x.value += mod;
    return stream;
}
const long long mod = (long long)1e9 + 7;
using mint = modular<mod>;

inline mint pw(mint a, long long n) {
    mint res = 1;
    while (n > 0LL) {
        if (n & 1LL) {
            res *= a;
        }
        a *= a;
        n >>= 1;
    }
    return res;
}
vector<mint> fact, finv;
inline void cinit(int n) {
    fact.resize(n, mint(1LL));
    finv.resize(n, mint(1LL));
    for (int i = 2; i < n; i++) {
        fact[i] = fact[i - 1] * i;
    }
    finv[n - 1] /= fact[n - 1];
    for (int i = n - 2; i >= 2; i--) {
        finv[i] = finv[i + 1] * (i + 1);
    }
}
inline mint C(int n, int k) {
    if (n < k || k < 0 || n < 0) {
        return mint(0LL);
    }
    return fact[n] * finv[k] * finv[n - k];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int s;
    cin >> s;
    vector<mint> dp(s + 1);
    dp[0] = 1;
    for (int i = 1; i <= s; i++) {
        for (int j = 0; j + 3 <= i; j++) {
            dp[i] += dp[j];
        }
    }
    cout << dp[s] << '\n';
    return 0;
}

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

int main(){
    int n,ans=0,now=0;
    bool bef=false;
    cin>>n;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        if(a==b){
            bef=true;
            now++;
            ans=max(ans,now);
        }
        else{
            bef=false;
        }
        if(!bef){
            now=0;
        }
    }
    if(ans>=3){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,k,n) for(int i=k;i<n;++i)
#define repe(i,k,n) for(int i=k;i<=n;++i)

using namespace std;

int main()
{
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,0,n)
    {
        cin >> a[i];
    }

    int res = 1e9;
    repe(i,1,100)
    {
        int temp=0;
        for (auto c:a){
            temp += (c-i)*(c-i);
        }
        res = min(temp,res);
    }
    cout << res;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	ll n,h;
	cin >> n >> h;

	vector<ll> a,b;
	rep(i,n){
		ll x,y;
		cin >> x >> y;

		a.push_back(x);
		b.push_back(y);
	} 

	ll mx = -1;
	ll mxi = -1;

	rep(i,n) mx = max(mx,a[i]);

	sort(b.begin(),b.end(),greater<ll>());

	ll p = 0;
	ll ans = 0;
	while(p<n){
		if(b[p] < mx) break;
		if(b[p] >= h){
			cout << (ans+1) << endl;
			return 0;
		}
		h -= b[p];
		p++;
		ans++;
	}

	ans += (h % mx == 0 ? h / mx : h / mx + 1);

	cout << ans << endl;
}

Measured memory_bytes: 2036
import java.util.Scanner;
public class Main {
	static long mod=(long)(Math.pow(10.0, 9.0)+7);
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	//Arrays.sort(array, (a, b) -> Integer.compare(a[0], b[0]));
	
	public static void main(String[] args) {
		int a=scan.nextInt();
		long b=scan.nextInt();
		int c[]=setArray(a);
		long inner=0,oher=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++) {
				if(c[i]>c[j]) {
					oher++;
					if(i<j) {
						inner++;
					}
				}
			}
		}
		long kk=b*(b-1)/2%mod;
		long ans=oher*kk%mod+inner*b%mod;
		System.out.println(ans%mod);
	}
}

Measured memory_bytes: 26000
n = int(input())
a = list(map(int, input().split()))
cnt = [0 for _ in range(n+1)]


def num_comb(a):
    return a * (a - 1) // 2


for i in range(n):
    cnt[a[i]] += 1

num_combs = [num_comb(cnt[i]) for i in range(n+1)]
total = sum(num_combs)

for i in range(n):
    res = total - num_combs[a[i]] * 2 // cnt[a[i]]
    print(res)


Measured memory_bytes: 24748
#include <bits/stdc++.h>
#if LOCAL
#include "../cout.hpp"
#endif
using namespace std;

#define forn(i,n) for (unsigned i = 0; i < n; ++i)
#define foreach(a) for (auto it = a.begin(); it != a.end(); ++it)
#define foreach_r(a) for (auto it = a.rbegin(); it != a.rend(); ++it)

typedef long long ll;
typedef unsigned long long ull;

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

    unsigned n;
    cin >> n;

    unsigned total = 0;
    forn(i, n) {
	unsigned l, r;
	cin >> l >> r;
	total += r - l + 1;
    }
    cout << total;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

// Credits - github.com/EndlessCheng/codeforces-go
func solve(_r io.Reader, _w io.Writer) {
	in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()

	var n int
	Fscan(in, &n)
	a:=make([]int,n)
	for i:=0;i<n;i++ {
		Fscan(in, &a[i])
	}
	mn:=1000
	for i:=0;i+1<n;i++{
		if a[i]>=a[i+1]{
			continue
		}
		c:=mn/a[i]
		mn+=c*(a[i+1]-a[i])
		// Fprintln(out,i,mn)
	}
	Fprintln(out,mn)
}

func main() { solve(os.Stdin, os.Stdout) }



Measured memory_bytes: 1852
import sys

if sys.platform =='ios':
	sys.stdin=open('input_file.txt')
	
#+++++
n,m=list(map(int, input().split()))
aa={i:[] for i in range(1,n+1)}
for _ in range(m):
	a,b = list(map(int, input().split()))
	aa[a].append(b)
	aa[b].append(a)
for a in aa[1]:
	if n in aa[a]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")


Measured memory_bytes: 67172
if __name__=='__main__':
    n,k,*h=map(int,open(0).read().split())
    dp=[0]
    for i,t in enumerate(h):
        if i:
            j=max(0,i-k)
            dp.append(min(v+abs(t-w)for v,w in zip(dp[j:i],h[j:i])))
    print(dp[-1])

Measured memory_bytes: 13876
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))

# dp[i][p]: pの箱を開けられるときの最小コスト
dp = [[INF] * (1 << N) for _ in range(M + 1)]
for i in range(M):
    dp[i][0] = 0
for p in range(1 << N):
    dp[0][p] = 0

for i in range(1, M):
    a, b = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))

    pattern = 0
    for c in C:
        pattern += 1 << (c - 1)

    for p in range(len(dp[i])):
        dp[i + 1][p | pattern] = min(
            dp[i + 1][p | pattern],
            dp[i][p] + a
        )
        dp[i + 1][p] = min(
            dp[i + 1][p],
            dp[i][p]
        )

ans = dp[-1][-1]
if ans < INF:
    print(ans)
else:
    print(-1)


Measured memory_bytes: 192280
#include<bits/stdc++.h>
#define MAX 1e9 + 7
#define ll long long int
#define fo(i,n) for(int i=0;i<n;i++)
#define ull unsigned long long int
#define pb push_back
#define eb emplace_back
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    int t;
//    cin>>t;
//    int x=1;
//    while(t--) {
//
//    }
    int s,w;
    cin>>s>>w;
    if(w>=s){
        cout<<"unsafe"<<endl;
    }
    else{
        cout<<"safe"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3640
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)    (x).begin(),(x).end()
# define UNIQ(c)   (c).erase(unique(ALL((c))), end((c)))
# define mp        make_pair
# define eb        emplace_back
# define REP       (i, a) for (int i = 0; i < (a); i++)
# define INIT      std::ios::sync_with_stdio(false);std::cin.tie(0);


int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b < c + d) {
		cout << "Right" << endl;
	}
	else if (a + b > c + d) {
		cout << "Left" << endl;
	}
	else {
		cout << "Balanced" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define VE vector<int>
#define PB push_back
#define PA pair<int,int>
#define MA make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POS(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Pos(i) cout<<(i?"Possible":"Impossible")<<endl
#define co(i) cout<<i<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
using namespace std;

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

int n,m,s,t;

const int MAX_V=100001;
struct edge{ll to, cost;};
int V;
vector<edge> G[MAX_V];
vector<edge> G2[MAX_V];
ll d[MAX_V];
ll d2[MAX_V];
void dijkstra(int s){
    priority_queue<PA, vector<PA>, greater<PA>> que;
    fill(d,d+V,INF);
    d[s]=0;
    que.push(PA(0,s));
    while(!que.empty()){
        PA p=que.top(); que.pop();
        int v=p.SE;
        if(d[v]<p.FI) continue;
        FOR(i,0,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(PA(d[e.to],e.to));
            }
        }
    }
}
void dijkstra2(int s){
    priority_queue<PA, vector<PA>, greater<PA>> que;
    fill(d2,d2+V,INF);
    d2[s]=0;
    que.push(PA(0,s));
    while(!que.empty()){
        PA p=que.top(); que.pop();
        int v=p.SE;
        if(d2[v]<p.FI) continue;
        FOR(i,0,G2[v].size()){
            edge e=G2[v][i];
            if(d2[e.to]>d2[v]+e.cost){
                d2[e.to]=d2[v]+e.cost;
                que.push(PA(d2[e.to],e.to));
            }
        }
    }
}

void add_edge(int u,int v,int a,int b){
	G[u].PB(edge{v,a});
	G[v].PB(edge{u,a});
	G2[u].PB(edge{v,b});
	G2[v].PB(edge{u,b});
}

int main(){
	cin>>n>>m>>s>>t;
	V=n;
	FOR(i,0,m){
		int u,v,a,b;
		cin>>u>>v>>a>>b;
		add_edge(u-1,v-1,a,b);
	}
	dijkstra(s-1);
	dijkstra2(t-1);
	ll m=10e17;
	ll ans[MAX_V];
	ROF(i,0,n){
		d[i]+=d2[i];
		m=min(m,d[i]);
		ans[i]=(ll)10e14-m;
	}
	FOR(i,0,n) co(ans[i]);
}

Measured memory_bytes: 20580