akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pof pop_front
#define pob pop_back
#define pb emplace_back
#define pf emplace_front
#define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
#define mp make_pair
#define mt make_tuple
#define inf 10000000000000
#define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
const double PI = acos(-1);
typedef complex<double> cd;
typedef long long ll;
ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef unordered_map<ll,ll> umap;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007 
#define N 100001

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

    // int T;cin>>T;while(T--) 
    {
        int n,m;
        cin>>n>>m;
        string s[n];
        ifr(i,0,n) cin>>s[i];
        bool a[n+1][m+1];
        ifr(i,0,n+1) ifr(j,0,m+1) a[i][j] = 0;
        ifr(i,0,n) {
            ifr(j,0,m) a[i+1][j+1] = (s[i][j]=='#');
        }
        ll dp[n+1][m+1],x,y;
        dp[0][0] = 0;
        ifr(i,1,n+1) dp[i][0] = inf;
        ifr(i,1,m+1) dp[0][i] = inf;
        dp[1][1] = a[1][1];
        ifr(i,1,n+1) {
            ifr(j,1,m+1) {
                if(i==1 && j==1) continue;
                x = dp[i-1][j];
                y = dp[i][j-1];
                if(a[i][j] && !a[i-1][j]) x++;
                if(a[i][j] && !a[i][j-1]) y++;
                dp[i][j] = min(x,y);
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

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

const int MOD = 1000000007;

int main() {
  int n; cin >> n;
  long long answer = 1;
  
  for (int i = 1; i <= n; i++) {
    answer *= i;
    answer %= MOD;
  }
  
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<pii> X(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i].fi;
        X[i].se = i;
    }
    SORT(X);
    int n = N/2;
    vector<pii> Y(N);
    REP(i, N){
        if(i<n){
            Y[i].fi = X[i].se;
            Y[i].se = X[n].fi;
        }
        else {
            Y[i].fi = X[i].se;
            Y[i].se = X[n-1].fi;
        }
    }
    SORT(Y);
    REP(i, N){
        pr(Y[i].se);
    }
}

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

const long M = 1000000000 + 7;

long long pro(long long a, long long b){
  return (a%M * b%M)%M;
}

long long fact(long long t){
  long long retVal = 1;
  for(long long i = 1;i<=t;i++){
    retVal = pro(retVal, i);
  }
  return retVal;
}

long long n,m;

int main(){
  cin >> n >> m;
  if(abs(n - m) >= 2){
    cout << 0 << endl;
    return 0;
  }else if(n == m){
    cout << (fact(n) * fact(n) * 2)%M << endl;
    return 0;
  }else{
    if(n > m) m = n;
    cout << (fact(m) * fact(m-1))%M << endl;
    return 0;
  }
}

Measured memory_bytes: 256
(N, ) = [int(n) for n in input().split()]

D = []
for _ in range(N):
    d = [int(n) for n in input().split()]
    D.append(d[0] == d[1])

ans = 'No'
for a, b, c in zip(D, D[1:], D[2:]):
    if a and b and c:
        ans = 'Yes'
print(ans)


Measured memory_bytes: 9176
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>
#include<deque>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

#define SIZ 200010

int n,t;
string sa,sb;

vector<vector<ll>> dp;

vector<vector<ll>> v2vec(int x,int y,int value=0){ return vector<vector<ll>>(y,vector<ll>(x,value)); }

int main(){
    
    cin>>sa>>sb;
    
    int xsiz=sa.size();
    int ysiz=sa.size();
    ll cq;
    bool debug=0;
    
    dp=v2vec(xsiz+1,ysiz+1,-1);
    
    dp[0][0]=0;
    
    for(int y=0;y<ysiz;y++){
        for(int x=0;x<=y+1;x++){
            if(dp[y][x]==-1)continue;
            if(dp[y+1][x]==-1 or dp[y+1][x]>dp[y][x]){
                dp[y+1][x]=dp[y][x];
            }
            cq=dp[y][x];
            while(cq<sb.size()){
                if(sa[y]==sb[cq])break;
                cq++;
            }
            
            if(cq!=sb.size() and (dp[y+1][x+1]==-1 or cq<dp[y+1][x+1])){
                dp[y+1][x+1]=cq+1;
            }
        }
    }
    int rr=0;
    for(int i=0;i<ysiz+1;i++){
        if(dp[ysiz][i]!=-1)rr=i;
    }
    
    string rs;
    for(int i=ysiz-1;i>=0;i--){
        
        if(rr==0)break;
        if(dp[i][rr]!=-1 and dp[i][rr]<=dp[i+1][rr]);
        else{
            rs.push_back(sa[i]);
            rr--;
        }
    }
    reverse(rs.begin(),rs.end());
    C rs E;
    
    //C dp[ysiz][rr] E;
    
    //C "sorry,I'm not an answer." E;
    
    
    if(debug){
        for(int y=0;y<ysiz+1;y++){
            for(int x=0;x<xsiz+1;x++){
                C dp[y][x]<<" ";
            }
            C "" E;
        }
    }
}

Measured memory_bytes: 70784
#[allow(unused_imports)]
use std::io::Write;

// {{{
#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}


macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut 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)*}
    };
}

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")
    };
}
// }}}

fn main() {
    input! {
        h: usize,
        a: usize,
    }

    println!("{}", (h + a - 1) / a);
}


Measured memory_bytes: 4352
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

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


char S[13][13];
int H,W;
vector<P> ps;
bool us[13],vs[13];
bool g();
bool f(){
#if 0
	if(ps.size()>10){
		for(auto p:ps){
			cerr << p.first << ", " << p.second << endl;
		}
		exit(0);
	}
#endif
	int t=0;
	while(us[t]){
		t++;
	}
	//cerr << t << ", " <<  H << endl;
	if(t==H){
		return g();
	}
	us[t]=true;
	int cnt=1;
	for(int s=t+1;s<H;s++){
		if(us[s])continue;
		us[s]=true;
		cnt++;
		ps.push_back(P(t,s));
		if(f()){
			//cerr << "f " << t << ", " << s << endl;
			return true;
		}
		ps.pop_back();
		us[s]=false;
	}
	if(cnt%2){
		ps.push_back(P(t,t));
		if(f()){
			//cerr << "f " << t << endl;
			return true;
		}
		ps.pop_back();
	}
	us[t]=false;
	return false;
}
bool g(){
	int t=0;
	while(vs[t]){
		t++;
	}
	if(t==W){
		return true;
	}
	vs[t]=true;
	int cnt=1;
	for(int s=t+1;s<W;s++){
		if(vs[s])continue;
		vs[s]=true;
		cnt++;
		bool ok=true;
		for(auto p:ps){
			if(S[p.first][s]!=S[p.second][t]||S[p.first][t]!=S[p.second][s]){
				ok=false;
				break;
			}
		}
		if(ok&&g()){
#if 0
			for(auto p:ps){
				cerr << S[p.first][s] << ", " << S[p.second][t] << ": ";
			}
			cerr << endl;
			cerr << "g " << t << ", " << s << endl;
#endif
			return true;
		}
		vs[s]=false;
	}
	if(cnt%2){
		bool ok=true;
		for(auto p:ps){
			if(S[p.first][t]!=S[p.second][t]){
				ok=false;
				break;
			}
		}
		if(ok&&g()){
			//cerr << "g " << t << endl;
			return true;
		}
	}
	vs[t]=false;
	return false;
}
int main() {
	cin >> H >> W;
	for(int i=0;i<H;i++){
		cin >> S[i];
	}
	if(f()){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}


	return 0;
}



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

int main() {
	string s,st;
	int q;
	cin >> s >> q;
	rep(i,q){
		int t;
		cin >> t;
		if(t == 1) swap(s,st);
		else{
			int f;
			char c;
			cin >> f >> c;
			if(f == 1){
				st.push_back(c);
			}else{
				s.push_back(c);
			}
		}
	}
	string ans;
	reverse(st.begin(),st.end());
	ans = st + s;
	cout << ans << endl;
}

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

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

	for(int n, p; cin >> n >> p, n;) {
		vector<int> num(n, 0);
		int stone = p;

		for(int i = 0;; i = (i + 1) % n) {
			if(stone) {
				--stone;
				if(++num[i] == p) {
					cout << i << endl;
					break;
				}
			}
			else {
				stone += num[i];
				num[i] = 0;
			}
		}
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1196
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    n=len(s)
    flag=-1
    for i in range(n):
        if s[i]=='W':
            flag=i
        else:
            break
    cunt_b=0
    cunt_w=0
    ans=0
    for i in range(n):
        if s[i]=='B':
            cunt_b+=1
        elif cunt_b>0:
            ans+=i-flag-1-cunt_w
            cunt_w+=1
    print(ans)



if __name__=='__main__':
    main()

Measured memory_bytes: 40048
#include<bits/stdc++.h>
using namespace std;
int main(){
 
 
		int n;
		string s;
		cin >> n >> s;
		int red = 0,white = 0;
		for(int i = 0;i < n; i++){
			red += (s[i] == 'R');
		}
		for(int i = 0; i < red; i++){
			white += (s[i] == 'W');
		}
		cout << white << "\n";
 
 
	return 0;
}

Measured memory_bytes: 3676
#include <iostream>
#define MAX_N 101
using namespace std;

int N, M;
char filed[MAX_N][MAX_N];
int path[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int res;

void dfs(int rx, int ry, char flag)
{
	filed[rx][ry] = '.';
	for(int i = 0; i < 4; i++){
		int dx = rx + path[i][0];
		int dy = ry + path[i][1];
		
		if(dx >= 0 && dy >= 0 && dx < M && dy < N && filed[dx][dy] == flag){
			dfs(dx, dy, flag);
		}
	}
} 

void solve()
{
	for(int i = 0; i < M; i++){
		for(int j = 0; j < N; j++){
			if(filed[i][j] != '.'){
				dfs(i, j, filed[i][j]);
				res++;
			}
		}
	}
	cout << res << endl;
}

int main()
{
	while(cin >> M >> N, N > 0){
		res = 0;
		for(int i = 0; i < M; i++){
			for(int j = 0; j < N; j++){
				cin >> filed[i][j];
			}
		}	
		solve();
	}
	return 0;
}


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




int main(){
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(int i = 0; i < n; i++)std::cin >> a[i];
    std::sort(a.begin(),a.end());
    a[n-1] /= 2;
    std::cout << std::accumulate(a.begin(),a.end(),0) << std::endl;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut 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)*}
    };
}

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")
    };
}

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize; n],
    }
    let mut a = a;
    a.sort();
    a.reverse();
    let threshold = a.iter().sum::<usize>() as f64 / (4 * m) as f64;
    if a[0..m].iter().any(|x| (*x as f64) < threshold) {
        println!("No")
    } else {
        println!("Yes")
    };
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000];
int main()
{
	string s;
	long long n,i,j,k,m,x,y,z;
	cin>>s;
	x=0;
	y=0;
	i=0;
	while (i<s.length()-1)
	{
		if (s[i]=='A')
		{
			x++;
			i++;
		}
		else if (s[i]=='B' && s[i+1]=='C')
		{
			if (x>0)
			{
				y=x+y;
				x=x;
				i=i+2;
			}
			else
			{
				i=i+2;
			}
		}	
		else
		{
			x=0;
			i++;
		}
	}
	cout<<y<<endl;
}

Measured memory_bytes: 640
#include<sstream>
using namespace std;
int main(){
	string s; getline(cin,s);
	for(int i=0;i<s.size();i++)if(s[i]=='.'||s[i]==',')s[i]=' ';
	
	stringstream ss; ss<<s;
	bool f=0;
	while(ss>>s)if(s.size()>2&&s.size()<7){
		if(f)cout<<" "; f=1;
		cout<<s;
	}
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 0
N = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(N):
    if p[i]-1 == i:
        if i + 1 <= N-1:
            p[i] = p[i+1]
            p[i+1] = i + 1
            ans += 1
        elif i - 1 >= 0:
            p[i] = p[i-1]
            p[i-1] = i + 1
            ans += 1
print(ans)

Measured memory_bytes: 14008
#include <bits/stdc++.h>  // ver1.9.4
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define mp make_pair
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define Vout(a) rep(i,0,a.size()-1)cout<<a[i]<<' ';cout<<a[a.size()-1]<<endl;
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
using namespace std;

signed main() {
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  Vi a(n);
  int ct=0;
  rep(i,0,n) cin >> a[i];
  repeq(i,1,n-1){
    repreq(j,n-1,i){
      if(a[j-1]>a[j]){
        ct++;
        swap(a[j-1],a[j]);
      }
    }
  }
  Vout(a);
  cout << ct << endl;
  return 0;
}



Measured memory_bytes: 3136
#include <stdio.h>
#include <math.h>
 
struct Point { double x, y; };
 
void koch(int n, Point a, Point b) {
    if(n == 0){
        return;
    }
     
    Point s, t, u;
    double th = M_PI * 60.0 / 180.0;
     
    s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
    s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
    t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
    t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
    u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
    u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;
     
    koch(n - 1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n - 1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n - 1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n -1, t, b);
}
 
int main() {
    Point a, b;
    int n;
     
    scanf("%d", &n);
     
    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;
     
    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);
     
    return 0;
}
 

 

Measured memory_bytes: 2728
#include <bits/stdc++.h>
using namespace std;
bool cmp(char x,char y)
{
  return x>y;
}
int main()
{
  string s,t;
  cin>>s>>t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end(),cmp);
  if(s<t)
  {
    cout<<"Yes";
  }
  else
  {
    cout<<"No";
  }
  return 0;
}

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

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

#define pb push_back
#define in ,
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int n;
  int a[100002] = {};
  cin >> n;

  rep(i, 0, n) {
    int b;
    cin >> b;
    a[b + 1]++;
    a[b]++;
    a[b - 1]++;
  }
  int ans = 0;
  rep(i, 0, 100001) ans = max(ans, a[i]);

  cout << ans << endl;
}


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

using namespace std;

const int mod = 1e9 + 7;


int main()
{
  int N, K, A[10000];

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

  int dp[10000][256] = {{}};
  for(int i = 0; i < N; i++) {
    for(int k = i; k >= 0; k--) {
      for(int j = 255; j >= 0; j--) {
        (dp[k + 1][A[i] ^ j] += dp[k][j]) %= mod;
      }
    }
    (dp[0][A[i]] += 1) %= mod;
  }

  int ret = 0;
  int fact = 1;
  for(int i = 0; i < N; i++) {
    fact = (1LL * fact * (i + 1) % mod);
    ret = (ret + 1LL * fact * dp[i][K] % mod) % mod;
  }
  cout << ret << endl;
}

Measured memory_bytes: 10368
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }
#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }
#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
const int inf = INT_MAX;
const int MOD = 1e9 + 7;



signed main(){
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif  
    IOS;

    int a, b;
    cin >> a >> b;
    if ((b - a) % 2 != 0) return cout << "IMPOSSIBLE\n", 0;
    cout << a + (b - a) / 2 << endl;
    return 0;
}

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

typedef tuple<int,int,bool> Tb;

bool tupleCompare(const Tb& firstElof, const Tb& secondElof)
{
    return get<1>(firstElof) > get<1>(secondElof);
}

int arc092_a(){
    int n;
    cin >> n;
    
    // 方針　→　青点をx座標昇順にソート、赤点をy座標降順にソートして1個ずつ調べる
    
    vector<Tb> pr(n),pb(n);
    for(int i=0;i<n;++i){
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        pr[i] = make_tuple(tmp1,tmp2,false); //赤点配列。第3引数のboolは赤点をもう使ったかの判定
    }
    for(int i=0;i<n;++i){
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        pb[i] = make_tuple(tmp1,tmp2,false); //青点。こっちのboolは使わない
    }
    int ans = 0;
    
    sort(pr.begin(), pr.end(),tupleCompare);
    sort(pb.begin(), pb.end());
    for(int i=0;i<n;++i){
        int pbx = get<0>(pb[i]); //青点x座標
        int pby = get<1>(pb[i]); //青点y座標
        for(int j=0;j<n;++j){ //青点x座標昇順、赤点y座標降順に調べる
            if((get<0>(pr[j])<pbx && get<1>(pr[j])<pby) && !get<2>(pr[j])){ //x座標y座標の条件、使ってない赤点の条件
                ++ans;
                get<2>(pr[j]) = true; //赤点を使った判定
                break;
            }
        }
    }
    
    cout << ans <<endl;
    return 0;
}

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


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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define AND(x,y,z) set_intersection((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define CONCAT(x,y) (x).insert((x).end(),(y).begin(),(y).end())
#define DUMP(xs) for (auto x:xs) cout<<x<<' ';cout<<endl
#define FOR(i,a,b) for (int i=(int)(a);i<(int)(b);++i)
#define OR(x,y,z) set_union((x).begin(),(x).end(),(y).begin(),(y).end(),inserter((z),(z).end()))
#define OUT(x) cout<<x<<endl
#define REP(i,n) FOR(i,0,n)

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

int main() {
  int N;cin>>N;
  VEC as(N);
  REP(i,N) {
    int a;cin>>a;
    as[i] = a;
  }
  sort(ALL(as));

  OUT(as.back()-as.front());

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
long long int max(long long x,long long y)
{
    long long q,yu=1,j,k;
    j=x,k=y;
    if(x<y)
    {
        q=x;x=y;y=q;
    }
    while(yu)
    {
        yu=x%y;
        x=y;
        y=yu;
    }
    return j/x*k;
}
int main()
{
	int n,i;
	long long a[105];
	while(scanf("%d",&n)!=EOF)
	{
		a[0]=1;
		for(i=1;i<=n;i++)
		{ 
		scanf("%lld",&a[i]);
		a[i]=max(a[i-1],a[i]);
	    }
		printf("%lld\n",a[i-1]);
	}
	return 0;
 } 


Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;

public class Prog
{
    public void run()
    {
        var input = Console.ReadLine().Split();
        int P = int.Parse(input[0]);
        int Q = int.Parse(input[1]);
        int R = int.Parse(input[2]);
        int A = P + Q;
        int B = P + R;
        int C = Q + R;
        Console.WriteLine(Math.Min(A, Math.Min(B, C)));
    }
    public static void Main()
    {
        //var input = Console.ReadLine().Split();
        //int[] X = Array.ConvertAll(input, int.Parse);
        var prog = new Prog();
        prog.run();
    }
}

//Array.ConvertAll(int.Parse)

Measured memory_bytes: 11092
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


n = val()
l = []
for i in range(n):l.append(li())

l.sort(key = lambda x:x[1] + x[0])

dp = [0] * (20001)

for i in l:
    for j in range(i[1], -1, -1):
        dp[j + i[0]] = max(dp[j + i[0]], dp[j] + i[-1])

print(max(dp))




Measured memory_bytes: 74928
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        n: usize,
        s: [String; n],
    }
    let mut s = s.iter().map(|si| si.chars().collect::<Vec<_>>()).collect::<Vec<_>>();
    for ref mut si in s.iter_mut() {
        si.sort();
    }
    s.sort();
    let mut count = 0;
    let mut index = 0;
    for i in 1..n {
        if s[index] == s[i] {
            count += i - index;
        } else {
            index = i;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 20732
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,K;
    cin >> N >> K;
    ll ans = 0;
    if(K % 2 == 0){
        ll k = K/2;
        ll cnt = 0;
        while(k <= N){
            cnt++;
            k += K;
        }
        ans += cnt * cnt * cnt;
        cnt = 0;
        k = K;
        while(k <= N){
            cnt++;
            k += K;
        }
        ans += cnt * cnt * cnt;
    }else{
        ll kk = K;
        ll cc = 0;
        while(kk <= N){
            cc++;
            kk += K;
        }
        ans += cc * cc * cc;
    }
    print(ans);


}


Measured memory_bytes: 256
//g++ t3.cpp -o t3 && t3 < p.txt

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

int main() {
  int n; cin >> n; string s; cin >> s;
  int a[n]; fill(a, a+n, 0);
  bool stop[n]; fill(stop, stop+n, false);

  int an = 0;
  for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
      if (s[i] == s[j]) {
        if (!stop[j-i] && j-i > a[j-i]) a[j-i]++;
        an = max(an, a[j-i]);
      } else if (a[j-i] > 0) a[j-i] = 0;
    }
  }
  
  /*
  int ans = 0; //cout << "A";
  for(int i=0; i<n; i++) {
    ans = max(ans, a[i]);
    //cout << a[i] << " ";
  }*/
  cout << an << endl;
}

Measured memory_bytes: 384
Q = int(input())
is_prime = [True for i in range(10**5+1)]
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5+1):
    if is_prime[i]:
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime[i] and is_prime[(i+1)//2])
for _ in range(Q):
    left, right = map(int, input().split())
    print(s[right+1]-s[left])

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

template <class T> using V = vector<T>;

using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;


#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;



int main() {
  ll n;
  ci(n);
  if(n<1200){
    co("ABC")
  }
  else if(n<2800){
    co("ARC")
  }
  else{
    co("AGC")
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <tuple>

using map_t = std::vector<std::vector<size_t>>;
using ans_t = std::vector<std::tuple<size_t, size_t, size_t, size_t>>;

void move(size_t y1, size_t x1, size_t y2, size_t x2,
          map_t& A, ans_t& ans) {
  A[y1-1][x1-1]--;
  A[y2-1][x2-1]++;
  ans.push_back(std::make_tuple(y1, x1, y2, x2));
}

int main() {
  size_t H, W;
  std::cin >> H >> W;

  map_t A(H, std::vector<size_t>(W));

  for (size_t y=0; y<H; y++) {
    for (size_t x=0; x<W; x++) {
      std::cin >> A[y][x];
    }
  }

  ans_t ans;

  for (size_t y=1; y<H+1; y++) {
    if (y%2==1) {
      for (size_t x=1; x<W+1; x++) {
        if (A[y-1][x-1] % 2 == 1) {
          if (x<W)
            move(y, x, y, x+1, A, ans);
          else if (y<H)
            move(y, x, y+1, x, A, ans);
        }
      }
    } else {
      for (size_t x=W; x>0; x--) {
        if (A[y-1][x-1] % 2 == 1) {
          if (x>1)
            move(y, x, y, x-1, A, ans);
          else if (y<H)
            move(y, x, y+1, x, A, ans);
        }
      }
    }
  }

  std::cout << ans.size() << std::endl;
  for (auto const& a : ans) {
    std::cout << std::get<0>(a) << ' ' << std::get<1>(a) << ' '
              << std::get<2>(a) << ' ' << std::get<3>(a) << std::endl;
  }

  return 0;
}


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

int main() {
    int n;
    cin>>n;
    int a[n][3];
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<3;j++) {
            cin>>a[i][j];
        }
    }
    
    int dp[n][3];
    for(int i = 0;i<n;i++) {
        for(int j = 0;j<3;j++) {
            dp[i][j] = 0;
        }
    }
    
    for(int i = 0;i<3;i++) 
        dp[0][i] = a[0][i];
        
        
    for(int i = 1;i<n;i++) {
       dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i][0];
       dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1];
       dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + a[i][2];
    }
    
    int ans = 0;
    
    for(int i = 0;i<3;i++) {
        ans = max(dp[n-1][i], ans);
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin>>n;
cout<<floor(n/3)<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=1e4+10;
int h,x;
pair<int,int>p[N];
int dp[N];
int dfs(int sum){
    if (sum>=h)
        return 0;
    if (dp[sum]!=-1)
        return dp[sum];
    int mn=1e9;
    for (int i=1;i<=x;i++)
        mn=min(mn,p[i].second+dfs(sum+p[i].first));
    return dp[sum]=mn;
}
int main()
{
    FASTINOUT;
    cin>>h>>x;
    for (int i=1;i<=x;i++)
        cin>>p[i].first>>p[i].second;
    memset(dp,-1,sizeof (dp));
    cout<<dfs(0);
    return 0;
}


Measured memory_bytes: 768
#include<cstdio>
#include<iostream>
using namespace std;
const int MOD=1e9+7;
long long quickm(long long a,long long k){
	long long ret=1;
	while (k>0){
		if (k&1) ret=ret*a%MOD;
		a=a*a%MOD;
		k=k/2;
	}
	return ret;
}
int main(){
	long long n,a,b;
	scanf("%lld%lld%lld",&n,&a,&b);
	long long res=quickm(2,n);
	long long c1=1,c2=1;
	for (long long i=n; i>=n-a+1; i--){
		c1=c1*i%MOD;
	} 
	for (long long i=1; i<=a; i++){
		c1=c1*quickm(i,MOD-2)%MOD;
	}
	for (long long i=n; i>=n-b+1; i--){
		c2=c2*i%MOD;
	} 
	for (long long i=1; i<=b; i++){
		c2=c2*quickm(i,MOD-2)%MOD;
	}
	res=(res-c1+MOD)%MOD;
	res=(res-c2+MOD)%MOD;
	printf("%lld",res-1);
	return 0;
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,a) for(int i = 0; i < (a); ++i)

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UI;

using namespace std;

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

    string s, t;
    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());

    int elem = min((int)s.size(), (int)t.size());

    REP(i, elem)
    {
        if (s[i] < t[i])
        {
            cout << "Yes" << endl;
            return 0;
        }
        else if (s[i] > t[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    if (s.size() < t.size())
    {
        cout << "Yes" << endl;
    }
    else if (s.size() >= t.size())
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int kk[1100001];
int n, m;

int binary_search(int x) {
    if (x <= 0) return 0;
    int l = 0, r = n * n;
    //dump(r - l);
    int i = 0;
    while(r - l >= 1) {
        i = (l + r) / 2;
        if (kk[i] == x) return i;
        else if (kk[i] < x) l = i + 1;
        else r = i;
    }
    while(kk[i] > x) i--;
    return i;
}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(true){
        cin >> n >> m;
        if(n == 0 && m == 0) return 0;
        int k[n+1];
        k[0] = 0;
        rep(i, n) cin >> k[i+1];
        rep(k, 1100001) kk[k] = 0;
        rep(c, n+1) {
            rep(d, n+1) {
                kk[c * n + d] = k[c] + k[d];
            }
        }

        sort(kk, kk + (n+1) * (n+1));
        int ans = 0;
        rep(a, n+1) {
            rep(b, n+1) {
                int index = binary_search(m - k[a] - k[b]);
                int tmp = kk[index] + k[a] + k[b];
                if(tmp <= m) ans = max(ans, tmp);
                tmp = kk[index+1] + k[a] + k[b];
                if(tmp <= m) ans = max(ans, tmp);

            }
        }
        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 7448
/*
─────────▄▄▄▄▄▄▄▄▄▄▄▄─────────
─────▄▄▀▀░░░░░░░░░░░░▀▀▄▄─────
───▄▀░░░░░░░░░░░░░░░░░░░░▀▄───
──█░░░░░▄▄▄▄▄░░░░▄▄▄▄▄░░░░░█──
─█░░░░░██░█░██▄▄██░█░██░░░░░█─
█░░░░░░░▀▀▀▀▀░░░░▀▀▀▀▀░░░░░░░█
█░░░░▄▄▄░░░░░░░░░░░░░░▄▄▄░░░░█
█░░░░██▀█▄▄▄▄▄▄▄▄▄▄▄▄██▀█░░░░█
─█░░░▀██▄████████▄▄▄▄██▄▀░░░█─
──█░░░░▀██▀▀▀▀████████▀░░░░█──
───▀▄░░░░▀▄▄▄▄██████▀░░░░▄▀───
─────▀▀▄▄░░░░░░░░░░░░▄▄▀▀─────
─────────▀▀▀▀▀▀▀▀▀▀▀▀─────────
*/
#include <bits/stdc++.h>

using namespace std;

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

	int a;
	string s;
	cin >> a >> s;
	cout << (a >= 3200 ? s : "red");

	return 0;
}

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    ab = []
    n, h = map(int, input().split())
    for _ in range(n):
        a, b = map(int, input().split())
        ab.append([a, 1])
        ab.append([b, 0])
    ab.sort()
    cnt = 0
    while h > 0:
        attack, type = ab.pop()
        if type:
            cnt += (h + attack - 1) // attack
            break
        else:
            h -= attack
            cnt += 1
    print(cnt)

main()


Measured memory_bytes: 30616
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	ll n, m;
	cin >> m >> n;
	vector<ll> a(n);
	ll sum = 0;
	rep(i, n) cin >> a[i], sum += a[i];
	if(m < sum) cout << -1 << endl;
	else cout << m - sum << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define RI(a) scanf("%d",&a)
#define RII(a,b) scanf("%d%d",&a,&b)
#define RIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
const ll maxn=100005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll mod=ll(1e9+7);

ll H;
ll a[maxn],b[maxn];
//pair<ll,ll> p[maxn];
int main()
{
	IOS;
   int n;
   cin>>n>>H;
   REP(i,n) cin>>a[i]>>b[i];
   REP(i,n) b[i]=max(a[i],b[i]);

   sort(a,a+n,greater<int>());sort(b,b+n,greater<int>());

   //REP(i,n) p[i]={b[i],a[i]};
   //sort(p,p+n,greater<pair<ll,ll>>());
   ll ans=0;
   int i=0;
   while(H>0&&i<n&&b[i]>a[0]){
      H-=b[i];
      ans++;
      i++;
   }

   if(H>0) ans+=(H-1)/a[0]+1;
   cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 1792
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int max = 0;
      int min = 1000000001;
      int[] array = new int[n];
      for(int i = 0;i < n;i++){
      	array[i] = sc.nextInt();
        max = Math.max(max,array[i]);
        min = Math.min(min,array[i]);
      }
      System.out.println(max-min);
    }
}


Measured memory_bytes: 23124
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int X = l[0], A = l[1], B = l[2];

            if (B <= A) Console.WriteLine("delicious");
            else if (B - A <= X) Console.WriteLine("safe");
            else Console.WriteLine("dangerous");
        }
    }
}


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

int main() {
    
    int n,a,b;
    cin >> n >> a >> b;
    unsigned long long d[n];
    for (int i=0; i <n; i++) cin>>d[i];
    
    unsigned long long v[n];
    v[n-1] = 0;
    for (int i=n-2; i>=0; i--) {
        v[i] = min(a*(d[i+1]-d[i])+v[i+1], b+v[i+1]);
    }
    
    cout << v[0];

    
    return 0;
}

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

using namespace std;

int main(){
    string a, b, c;
    cin >> a >> b >> c;
    if(a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0]){
        cout << "YES";
    }else{
        cout << "NO";
    }
    return 0;

}


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

int main(){
  int A, B, C;
  long X, Y;
  cin >> A >> B >> C >> X >> Y;
  long cost=1e9;
  if(cost>2*C*max(X,Y)){
    cost = 2*C*max(X,Y);
  }
  if(X>=Y && cost>2*C*Y+A*(X-Y)){
    cost = 2*C*Y+A*(X-Y);
  }
  if(X<Y && cost>2*C*X+B*(Y-X)){
    cost = 2*C*X+B*(Y-X);
  }
  if(cost>A*X+B*Y){
    cost = A*X+B*Y;
  }
  cout << cost << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var stdInScanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	stdInScanner.Scan()
	i, _ := strconv.Atoi(stdInScanner.Text())
	return i
}

func nextInt64() int64 {
	stdInScanner.Scan()
	i, _ := strconv.ParseInt(stdInScanner.Text(), 10, 64)
	return i
}

func main() {
	stdInScanner.Split(bufio.ScanWords)

	N := nextInt()
	M := nextInt()
	K := nextInt64()

	A := make([]int64, N+1)
	B := make([]int64, M+1)

	A[0] = 0
	for i := 1; i <= N; i++ {
		A[i] = nextInt64() + A[i-1]
	}
	B[0] = 0
	for i := 1; i <= M; i++ {
		B[i] = nextInt64() + B[i-1]
	}

	j := M
	var ans int
	for i := 0; i <= N; i++ {
		if A[i] > K {
			break
		}
		for B[j] > K-A[i] {
			j--
		}
		if ans < (i + j) {
			ans = i + j
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 8268
#include <bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 9999999999;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define pb push_back
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	ll a,b;
	char c;
	cin >> a >> c >> b;	

	if(c=='+') cout << a+b << endl;
	else cout << a-b << endl;


	return 0;
}



Measured memory_bytes: 256
#include <cstdio>

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 MOD = 1000000007;

template<u64 N>
class T
{
	public:
		constexpr T() : data()
		{
			for (int i = 0; i <= N; ++i)
			{
				data[i] = i;
			}
			for (int i = 2; i <= N; ++i)
			{
				if (data[i] != i) continue;
				for (int j = i; j <= N; j += i)
				{
					data[j] = data[j] / i * (i - 1);
				}
			}
			for (int i = 1; i <= N; ++i)
			{
				data[i] = (data[i] + data[i - 1]) % MOD;
			}
		}

		int data[N + 1];
};


template<typename T>
constexpr T pow_mod(T a, T b, T m)
{
	T r = 1;
	while (b > 0)
	{
		if ((b & 1) != 0) r = (r * a) % m;
		a = (a * a) % m;
		b >>= 1;
	}
	return r;
}

constexpr T<100000> t;

int main()
{
	i64 n, k;
	scanf("%lld%lld", &n, &k);
	i64 ans = 0;
	for (i64 i = 1; i <= k;)
	{
		i64 j = k / (k / i);
		ans = (ans + pow_mod(k / i, n, MOD) * (t.data[j] + MOD - t.data[i - 1])) % MOD;
		i = j + 1;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 1976
/**
 *    author:  [itmo] enot.1.10
 *    created: 25.02.2017 15:14:55       
**/
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),a.end()
#define pw(x) (1LL<<(x))

using namespace std;

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1.01e9;
const dbl eps = 1e-9;

/* --- main part --- */

const int N = 510;

char s[N][N];
int cnt[N];

int main()
{
    #ifdef home
        assert(freopen("1.in", "r", stdin));
        assert(freopen("1.out", "w", stdout));
    #endif
    int n;
    scanf("%d", &n);
    forn(i, n) scanf("%s", s[i]);
    forn(i, n)
    {
        forn(j, n) if (s[i][j] == '#') cnt[i]++;
    }
    int mn = inf;
    int total = 0;
    forn(i, n) total += cnt[i];
    forn(i, n)
    {
        if (cnt[i] == n) mn = 0;
        forn(j, n) if (s[i][j] == '#') mn = min(mn, n - cnt[j]);
        if (s[i][i] == '.' && total > 0) mn = min(mn, (n - cnt[i]) + 1);

    }
    int full =0;
    forn(j, n)
    {
        int ok = 1;
        forn(i, n) if (s[i][j] == '.') ok = 0;
        full += ok;
    }

    int res = mn + n - full;

    if (res >= inf) res = -1;
    printf("%d\n", res);
    #ifdef home
        eprintf("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string.h>
#include <iomanip>
using namespace std;
typedef long long ll;

int main() {
    int n, k; cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    double t = 0;
    for (int i = 0; i < k; i++) t += (p[i] + 1) / 2.0;
    double ans = t;
    for (int i = k; i < n; i++) {
        t = t - (p[i - k] + 1) / 2.0 + (p[i] + 1) / 2.0;
        ans = max(ans, t);
    }
    cout << setprecision(15) << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
bool mojitan(string s, char c){
  for(int k=0;k<s.size();k++){
    if(s.at(k) == c){
      return true;
    }
  }
  return false;
}
  
int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  string s1, s2;
  int cnt;
  int ma;
  for(int i=1; i<N; i++){
    s1 = S.substr(0,i);
    s2 = S.substr(i,N-i);
    cnt=0;
    for(char j='a'; j<='z'; j++){
      if(mojitan(s1,j)&&mojitan(s2,j)){
        cnt++;
      }
    }
    ma = max(ma,cnt);
  }
  cout << ma << endl;
}

Measured memory_bytes: 256
/*

Knapsack-2

3 8
3 30
4 50
5 60

*/


#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,w;
    cin>>n>>w;

    vector<ll> w_i(n);
    vector<ll> v_i(n);
    ll s=0;
    rep(i,n)
    {
    	cin>>w_i[i]>>v_i[i];
    	s += v_i[i];
    }
    vector<ll> dp(s+1,10e9+5);
    dp[0] = 0;

    rep(i,n){
    	if(i==0) dp[v_i[i]] = w_i[i];
    	else{
    		for(ll j = s;j>=v_i[i];--j)
    		{
    			dp[j] = min(dp[j], dp[j-v_i[i]] + w_i[i]);
    		}
    	}
    }
    ll ans = 0;
    for(ll i = 0;i<=s;i++)
    {
    	if(dp[i] <= w)
    		ans=max(ans,i);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1024
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))

Measured memory_bytes: 14180