akhauriyash/Code-Regression huggingface dataset:
from collections import Counter

def nCr(n,r):
    return fac[n]//fac[r]//fac[n-r]

N,A,B=map(int,input().split())
v=sorted(map(int,input().split()),reverse=True)
fac=[1]
for i in range(N):
    fac.append(fac[-1]*(i+1))
print(sum(v[:A])/A)
c=Counter(v)
if v[0]==v[A-1]:
    Cnt=c[v[0]]
    res=0
    for i in range(A,B+1):
        res+=nCr(Cnt,i)
    print(res)
else:
    All=c[v[A-1]]
    M=v[:A].count(v[A-1])
    print(nCr(All,M))

Measured memory_bytes: 65136
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


ll n, k;
ll a[500];

bool f(ll div) {
    ll b[n];
    for (int i = 0; i < n; i++) {
        b[i] = a[i] % div;
    }

    sort(b, b + n);
    for (int i = 1; i < n; i++) {
        b[i] += b[i - 1];
    }

    for (int i = 0; i < n; i++) {
        if (b[i] == (n - 1 - i) * div - (b[n - 1] - b[i]) && b[i] <= k) {
            return true;
        }
    }

    return false;
}



int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


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

    ll ans = 0;
    ll sum = accumulate(a, a + n, (ll) 0);

    for (ll div = 1; div * div <= sum; div++) {
        if (sum % div == 0) {
            if (f(div)) {
                ans = max(ans, div);
            }

            if (f(sum / div)) {
                ans = max(ans, sum / div);
            }
        }
    }

    cout << ans;

}

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

int main(){
    string s,t;
    cin>>s>>t;
    int ans=0;
    rep(i,s.size()-t.size()+1){
        int count=0;
        for(int j=0;j<t.size();j++){
            if(s[j+i]==t[j]){
                count++;
            }
        }
        ans=max(ans,count);
    }
    cout<<t.size()-ans<<endl;
}

Measured memory_bytes: 3596
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int w, a, b;
    cin >> w >> a >> b;
    if(a<=b){
    a+=w;
    cout<<max(0,b-a)<<"\n";
    }
    else{
        b+=w;
        cout<<max(0,a-b)<<"\n";
    }
}


Measured memory_bytes: 256
import java.util.*;
import javax.lang.model.util.ElementScanner6;
import java.lang.Math;

public class Main {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);

        // 入力
        int a = sc.nextInt();
        int b = sc.nextInt();
        int h = sc.nextInt();
        int m = sc.nextInt();
        //String s = sc.next();

        // 処理
        //時針(0-11)
        double ao = 2*Math.PI / (12 * 60);
        double ax = a * (Math.sin((h * 60 + m) * ao));
        double ay = a * (Math.cos((h * 60 + m) * ao));;

        //分針(0-59)
        double bx = b * (Math.sin(2*Math.PI * m / 60));
        double by = b * (Math.cos(2*Math.PI * m / 60));;

        //距離
        double out = Math.sqrt(Math.pow(ax - bx, 2) + Math.pow(ay - by, 2));

        // 出力
        System.out.println(out);
    }
}


Measured memory_bytes: 36012
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

bool ok = true;

int f(int u, int x, vector<vector<int> >& G, vector<int>& vis) {
	vis[u] = x;
	int sum = 1;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v] == x) ok = false;
		if (vis[v] != -1) continue;
		sum -= f(v, !x, G, vis);
	}
	return sum;
}

int main() {
	int N, M; cin >> N >> M;
	vector<vector<int> > G(N);
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	vector<int> vis(N, -1);
	int n = 0;
	vector<int> a(N + 1);
	for (int u = 0; u < N; u++)
		if (vis[u] == -1) {
			int x = abs(f(u, 0, G, vis));
			n += x;
			a[x]++;
		}
	if (!ok) {
		cout << -1 << endl;
		return 0;
	}
	vector<bool> dp(n + 1);
	dp[0] = true;
	for (int x = 1; x <= N; x++)
		for (int y = 1; a[x]; y *= 2) {
			int z = min(a[x], y);
			a[x] -= z;
			for (int k = n; k - z * x >= 0; k--)
				if (dp[k - z * x])
					dp[k] = true;
		}
	ll ma = 0;
	for (int k = 0; k <= n; k++)
		if (dp[k])
			ma = max(ma, (ll)((N - n) / 2 + k) * ((N - n) / 2 + (n - k)));
	cout << ma - M << endl;
}

Measured memory_bytes: 9728
#include <bits/stdc++.h>
#include <variant>
#include <atcoder/all>
#define FOR(i,k,n) for(ll i=(k);i<(ll)(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) begin(x),end(x)
 
using namespace std;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,q;
  cin>>n>>q;
  atcoder::dsu d(n);
  REP(i,q) {
    int t,u,v;
    cin>>t>>u>>v;
    if (t == 0) {
      d.merge(u,v);
    } else {
      if (d.same(u, v)) {
        cout<<1<<"\n";
      } else {
        cout<<0<<"\n";
      }
    }
  }
  return 0;
}


Measured memory_bytes: 4028
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 2e5 + 10 , P = 1e9 + 7;
int n , vis[N] , fac[N] = {1} , ifac[N] , du[N] , root[N];
vi g[N] , G[N];
void output(vi v){
    rep(i,0,sz(v)) printf("%d%c",v[i]," \n"[i+1==sz(v)]);
}

int inverse(int x){return x == 1 ? 1 : P - ll(P/x)*inverse(P%x)%P;}

void dfs(int c,int fa){
    for(auto e : g[c]) if(e < fa) G[c].pb(e) , root[e] = false;
    for(auto e : g[c]) if(du[e] == 1 && e != fa) dfs(e , c);
}

pii solve(int c,int fa){
    pii res=mp(1,0);
    for(auto e : G[c]) if(e != fa){
        pii get=solve(e,c);
        res.se+=get.se;
        res.fi=1ll*res.fi*get.fi%P*ifac[get.se]%P;
    }
    res.fi=1ll*res.fi*fac[res.se]%P;
    res.se+=1;
    return res;
}

int solve(vi cir,vi all){
    for(auto e : all) G[e].clear() , root[e] = true;
    int rt = N - 1;G[rt].clear();
    cir.pb(cir[0]);
    rep(i,1,sz(cir)) dfs(cir[i] , cir[i-1]);
    for(auto e : all) if(root[e]) G[rt].pb(e);
    return solve(rt , -1).fi;
}

int main(){
    scanf("%d",&n);
    rep(i,1,(n<<1)+1) fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[n<<1] = inverse(fac[n<<1]);
    per(i,0,(n<<1)) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    rep(i,0,n<<1){
        int x,y;
        scanf("%d%d",&x,&y);
        --x;--y;
        g[x << 1].pb(y << 1 | 1);
        g[y << 1 | 1].pb(x << 1);
    }
    int ans = fac[n<<1];
    rep(i,0,n<<1) if(!vis[i]){
        vi q;q.pb(i);vis[i]=1;
        rep(i,0,sz(q)) for(auto e : g[q[i]]) if(!vis[e])
            q.pb(e) , vis[e]=1;
        vi noncir,cir;int edgecnt(0);
        rep(i,0,sz(q)) {
            int c=q[i];
            edgecnt+=sz(g[c]);
            du[c] = sz(g[c]);
            if(sz(g[c]) == 1) noncir.pb(c);
        }
        if(edgecnt / 2 != sz(q)) {
            ans = 0;
            break;
        }
        rep(i,0,sz(noncir)){
            int c=noncir[i];
            for(auto e : g[c]) if(du[e] != 1 && (--du[e]) == 1)
                noncir.pb(e);
        }
        rep(i,0,sz(q)) if(du[q[i]] == 2){
            for(int c=q[i],t=-1;c!=-1;c=t){
                cir.pb(c);du[c]=0;t=-1;
                for(auto e : g[c]) if(du[e] == 2) t=e;
            }
        }
        int way = solve(cir , q);
        reverse(all(cir));
        (way += solve(cir , q)) %= P;
        ans = 1ll * ans * way % P * ifac[sz(q)] % P;
    }
    printf("%d\n",ans);
    return 0;
}


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

int main() {
	int n;
  	cin>>n;
  
  	rep(i,n)cin>>b[i];
  
  	int ans=b[n-2]+b[0];
  
  	for(int j=0;j<n-1;j++){
    	ans += min(b[j-1],b[j]);
    }
  
  cout<<ans<<endl;


}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
ll strtoint(string str);
int main(){
	fast;
	ll h,f=0,cnt=0; cin>>h;
	while(h>0){
		++cnt;
		h/=2;
	}
	f=1;
	for(auto i=0;i<cnt;++i)f=f*2;
	cout<<f-1<<'\n';
	return 0;
}
ll strtoint(string str){
	ll x=0;
	stringstream ss;
	ss<<str;
	ss>>x;
	return x;
}

Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]
k = []
s = []
for i in range(m):
    tmp = [int(i) for i in input().split()]
    k.append(tmp[0])
    s += [tmp[1:]]
p = [int(i) for i in input().split()]
cnt0 = 0

for b in range(1 << n):

    sw = [0] * n
    for i in range(n):
        if b & (1 << i): sw[i] = 1

    status = True
    for i in range(m):
        cnt1 = 0
        for j in s[i]:
            if sw[j - 1] == 1: cnt1 += 1
        if cnt1 % 2 != p[i]: status = False
    
    if status: cnt0 += 1

print(cnt0)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
	
typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
	
#define MOD 1000000007
#define mini 18446744073709551615
#define ff first
#define ss second
#define pb push_back
#define vii vector<int>
#define pii pair<int,int>
#define vpii vector<pii>

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	//cin>>T;
	while(T--)
	{
		ll s,ans;
		cin>>s;
		ll a[2001];
		a[1]=0;a[2]=0;
		a[3]=1;a[4]=1;a[5]=1;
		for(int i=6;i<=s;i++)
		{
			a[i]=(a[i-1]+a[i-3])%MOD;
		}
		cout<<a[s]%MOD;
	}
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;


struct UnionFind {
	VI par;
	UnionFind(int N) :par(N) {
		REP(i, N)par[i] = i;
	}
	int root(int x) {
		if (par[x] == x)return x;
		return par[x] = root(par[x]);
	}
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}
	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

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

	int N, M; cin >> N >> M;
	VI ans(N, 0);
	REP(i, M) {
		int a, b; cin >> a >> b;
		a--; b--;
		ans[a]++; ans[b]++;
	}
	REP(i, N)cout << ans[i] << endl;
	return 0;
}



Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fcout cout << fixed << setprecision(10)
#define rep(i,n)    for(int i=0; i<(int)n; i++)
#define mp(a,b) make_pair(a,b)
#define pb push_back
const ll inf = 1e18;
const ll mod = 1e9 + 7;

ll pow (ll x, ll n){
    ll ans = 1;
    while(n>0){
        if(n & 1 == 1){
            ans *= x;
        }
        x = x * x;
        n >>= 1;
    }
    return ans;
}


int main(){
    int n, k;   cin >> n >> k;
    int ans =0;
    vint a(n);
    rep(i,n)    cin >> a[i];
    if((n-1)%(k-1) ==0){
        ans += (n-1)/(k-1);
    }else{
        ans = ans + (n-1)/(k-1) +1;
    }

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int r, c, i, j;
  scanf("%d %d", &r, &c);
  int a[r + 1][c + 1];
  for(i = 0; i < r + 1; i++){
    for(j = 0; j < c + 1; j++) a[i][j] = 0;
  }

  for(i = 0; i < r; i++){
    int col_sum = 0;
    for(j = 0; j < c; j++){
      scanf("%d", &a[i][j]);
      col_sum += a[i][j];
      a[r][c] += a[i][j];
      a[r][j] += a[i][j];
    }
    a[i][c] = col_sum;
  }
  
  for(i = 0; i < r + 1; i++){
    for(j = 0; j < c; j++) printf("%d ", a[i][j]);
    printf("%d\n", a[i][c]);
  }
  
}


Measured memory_bytes: 3220
//#pragma GCC optimize("O3,unroll-loops")
//#pragma loop_opt(on)
#include <bits/stdc++.h>
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;

#ifdef DEBUG
#define FAST ;
#else
#define FAST ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif
#define _ <<' '<<
#define Fr(i, s, e) for(auto i = s; i < e; ++i)
#define Ft first
#define Sd second
using ll = long long;
using pii = pair<int, int>;
constexpr ll MAX = 1e6+5;
constexpr ll INF = 2134567890;
constexpr ll MOD = 998244353;

ll fpow(ll b, ll a, ll MOD = MOD) {
    b %= MOD;
    ll r = 1;
    for(; a; b=b*b%MOD, a>>=1)
        a&1 && (r = r*b%MOD);
    return r;
}

signed main() {
    FAST;

    int a, b, c;
    cin >> a >> b >> c;
    bool can = !(a==b&&b==c);
    if (can) {
        if (!(a == b || b == c || c == a)) can = false;
    }
    cout << (can ? "Yes" : "No") << endl;

}


Measured memory_bytes: 508
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c, s;
            string[] word = Console.ReadLine().Split(' ');

          a = int.Parse(word[0]);
          b  = int.Parse(word[1]);
          c  = int.Parse(word[2]);


            s = 0;
            if (a + b > a + c && b + c > a + c)
                s = a + c;
            else if (a + c > a + b && b + c > a + b)
                s = a + b;
            else if (a + c > b + c && a + b > b + c)
                s = b + c;
            else
                s = a + b;

            Console.WriteLine(s);

            //Console.ReadKey();
        }
    }
}


Measured memory_bytes: 27512
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


#define MOD 1000000007


#define MAXN 2000
long long inv[MAXN + 1];//MODを法とする乗法の逆元
long long fact[MAXN + 1];//階乗
long long ifact[MAXN + 1];//階乗の逆元
void init() {
	inv[1] = 1;
	for (int i = 2; i <= MAXN; i++) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
	fact[0] = ifact[0] = 1;
	for (int i = 1; i <= MAXN; i++) {
		fact[i] = i * fact[i - 1] % MOD;
		ifact[i] = ifact[i - 1] * inv[i] % MOD;
	}
}
long long C(int n, int r) {
	if (n < 0 || r < 0 || r > n)return 0;
	if (r > n / 2)r = n - r;
	return fact[n] * ifact[n - r] % MOD * ifact[r] % MOD;
}




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

	init();

	int n, k;
	cin >> n >> k;

	int r = n - k;

	for (int i = 1; i <= k; i++) {
		long long ans = C(k - 1, i - 1);

		int rem = r - (i - 1);
		ans *= C(i + 1 + rem - 1, rem);
		ans %= MOD;

		cout << ans << endl;
	}






	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 2097152;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif



int dp[21][N];
int arr[21][21];

signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    memset(dp, 0, sizeof(dp));
    int n; cin>>n;
    For(i, 0, n){
        For(j, 0, n){
            cin>>arr[i][j];
        }
    }
    int mx = pow(2, n);
    for(int i=0; i<n; i++){
        for(int j=0; j<mx; j++){
            int mask = j;
            int x = __builtin_popcountl(mask);
            if(x!=i+1)
                continue;            
            int bit[n];
            for(int k=0; k<n; k++){
                if(mask%2){
                    bit[k]=1;
                }
                else{
                    bit[k]=0;
                }
                mask /= 2;
            }
            dp[i][j]=0;
            for(int k=0; k<n; k++){
                if(bit[k] && arr[i][k]){
                    if(i==0){
                        dp[i][j]=1;
                    }
                    else{
                        dp[i][j]+=dp[i-1][j^(1<<k)];
                    }
                }
            }
            dp[i][j]%=MOD;
        }
    }
    cout<<dp[n-1][mx-1];
    return 0;
}





Measured memory_bytes: 344448
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
typedef long double ld;
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; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};
vector<ll> divisor(ll n){
  vector<ll> res;
  for(ll i=1; i*i<=n ; i++){
    while(n%i==0){
      ++res[i];
      n /= i;
    }
  }
  if(n!=1) res[n]=1;
  return res;
}
int main(){
  int N;  cin>>N;
  vector<ll> a(N), b(N);
  rep(i,0,N){
    ll x,y; cin>>x>>y;
    a[i] = x+y; b[i] = x-y;
  }
  sort(all(a)); sort(all(b));
  ll ans = max(a[N-1]-a[0], b[N-1]-b[0]);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 6420
N = int(input())
A = list(map(int,input().split()))
count = 0
dicta = {}
for i in range(N):
    if i - A[i] in dicta:
        count += dicta[i-A[i]]
    if i + A[i] in dicta:
        dicta[i+A[i]] += 1
    else:
        dicta[i+A[i]] = 1
print(count)

Measured memory_bytes: 40476
#include<iostream>
using namespace std;
int main(){
    int list[6]={};
    int q,a,b;
    
    for(int i=0;i<6;i++){
        cin >> list[i];
    }
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> a >> b;
        if(a==list[0] && b==list[1]){
            cout << list[2] << endl;
        }else if(a==list[0] && b==list[3]){
            cout << list[1] << endl;
        }else if(a==list[0] &&b==list[2]){
            cout << list[4] <<endl;
        }else if(a==list[0] && b==list[4]){
            cout << list[3] << endl;
        }else if(a==list[1] && b==list[5]){
            cout << list[2] << endl;
        }else if(a==list[1] && b==list[2]){
            cout << list[0] << endl;
        }else if(a==list[1] && b==list[3]){
            cout << list[5] << endl;
        }else if(a==list[1] && b==list[0]){
            cout << list[3] << endl;
        }else if(a==list[2] && b==list[5]){
            cout << list[4] << endl;
        }else if(a==list[2] && b==list[4]){
            cout << list[0] << endl;
        }else if(a==list[2] && b==list[0]){
            cout << list[1] << endl;
        }else if(a==list[2] && b==list[1]){
            cout << list[5] << endl;
        }else if(a==list[3] && b==list[4]){
            cout << list[5] << endl;
        }else if(a==list[3] && b==list[0]){
            cout << list[4] << endl;
        }else if(a==list[3] && b==list[1]){
            cout << list[0] << endl;
        }else if(a==list[3] && b==list[5]){
            cout << list[1] << endl;
        }else if(a==list[4] && b==list[2]){
            cout << list[5] << endl;
        }else if(a==list[4] && b==list[0]){
            cout << list[2] << endl;
        }else if(a==list[4] && b==list[3]){
            cout << list[0] << endl;
        }else if(a==list[4] && b==list[5]){
            cout << list[3] << endl;
        }else if(a==list[5] && b==list[4]){
            cout << list[2] << endl;
        }else if(a==list[5] && b==list[2]){
            cout << list[1] << endl;
        }else if(a==list[5] && b==list[1]){
            cout << list[3] << endl;
        }else if(a==list[5] && b==list[3]){
            cout << list[4] << endl;
        }
    }
}


Measured memory_bytes: 3076
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProblemA
{
    class Program
    {
        static void Main(string[] args)
        {

            var read = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = read[0];
            var M = read[1];
            Console.WriteLine(N * M);
        }
            
    }
}


Measured memory_bytes: 28300
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
	
    private static int cnt = 0;
    private static Graph g;

    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		g = new Graph(N);
		for (int i=0; i<M; i++) {
		    g.add(sc.nextInt(), sc.nextInt());
		}
		boolean[] history = new boolean[N+1];
		Arrays.fill(history, false);
		search(1, history);
		System.out.println(cnt);
		sc.close();
	}
    
    public static void search(int current, boolean[] history) {
        history[current] = true;
        if (finish(history)) {
            cnt++;
            return;
        }
        for (int next: g.getNeighbors(current)) {
            if (history[next]) continue;
            search(next, Arrays.copyOf(history, history.length));
        }
    }
    
    public static boolean finish(boolean[] history) {
        for (int i=1; i<history.length; i++) {
            if (!history[i]) return false;
        }
        return true;
    }
	
	
    public static class Graph {
        private final Map<Integer, List<Edge>> graph = new HashMap<>();
        
        public Graph(int num) {
            for (int i=0; i<=num; i++) graph.put(i, new ArrayList<Edge>());
        }
        
        public void add (int v1, int v2) {
            graph.get(v1).add(new Edge(v1, v2));
            graph.get(v2).add(new Edge(v2, v1));
        }
        
        public List<Integer> getNeighbors(int v) {
            List<Integer> neighbors = new ArrayList<>();
            for (Edge e: graph.get(v)) {
                neighbors.add(e.to());
            }
            return neighbors;
        }
    }
    
    public static class Edge implements Comparable<Edge> {
        private final int _v1;
        private final int _v2;
        
        public Edge(int v1, int v2) { this._v1 = v1; this._v2 = v2; }
        public int from() { return _v1; }
        public int to() { return _v2; }
        
        @Override
        public int compareTo(Edge o) {
            if (from()!=o.from()) return Integer.compare(this.from(), o.from());
            return Integer.compare(this.to(), o.to());
        }
    }
}


Measured memory_bytes: 26708
S = str(input())

flag = False
if len(S) % 2 == 1:
    flag = False
else:
    for count in range(int(len(S)/2)):
        if S[count*2] != "h" or S[count*2 + 1] != "i":
            flag = False
            break
        else:
            flag = True

if flag == True:
    print("Yes")
else:
    print("No")

     

Measured memory_bytes: 2940
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

// 端点 (x0, y0), (x1, y1) の線分と (x0, y0), (x1, y1) の線分が共有点を持つかを返す
template <typename T>
bool intersection(T x0, T y0, T x1, T y1, T x2, T y2, T x3, T y3){
	T a1 = y1 - y0, b1 = x0 - x1, c1 = x0 * (y1 - y0) - y0 * (x1 - x0);
	T a2 = y3 - y2, b2 = x2 - x3, c2 = x2 * (y3 - y2) - y2 * (x3 - x2);
	// 線分が平行な場合
	if(a1 * b2 == b1 * a2){
		// 同一直線上にない場合
		if(x0 * a1 + y0 * b1 != x2 * a1 + y2 * b1){
			return false;
		}
		// 線分が重なってない場合
		else if(max(x0, x1) < min(x2, x3) || max(x2, x3) < min(x0, x1) || max(y0, y1) < min(y2, y3) || max(y2, y3) < min(y0, y1)){
			return false;
		}
		// 線分が重なっている場合
		return true;
	}
	// 一方の端点がもう一方の直線をまたいでいる場合、交点を持つ
	return (a1 * x2 + b1 * y2 - c1) * (a1 * x3 + b1 * y3 - c1) <= 0 && (a2 * x0 + b2 * y0 - c2) * (a2 * x1 + b2 * y1 - c2) <= 0;
}

int main(){
	int q;
	cin >> q;
	for(int loop = 0; loop < q; loop++){
		int x0, y0, x1, y1, x2, y2, x3, y3;
		cin >> x0 >> y0 >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
		cout << intersection<long long int>(x0, y0, x1, y1, x2, y2, x3, y3) << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long 
#define INF 1e9
#define LINF 1e18
 
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;
 
const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };
 
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

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

    int n;
    cin >> n;
    int res = 4, mini = LINF;
    for(int i = 0; i < 5; ++i) {
        int a;
        cin >> a;
        chmin(mini, a);
    }
    cout << res + (n / mini) + ((n % mini == 0) ? 0 : 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int i,ans=0;
	string s,t;
	cin>>s>>t;
	for(i=0;i<3;i++)
	{
		if(s[i]==t[i])
		{
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []

for i in range(M):
    x[i],y[i],z[i] = map(int,(input().split()))
    line[x[i]].append(y[i])
    dot.append(x[i])
    dot.append(y[i])

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

Tree = UnionFind(N)

for i in range(N):
    for j in line[i]:
        Tree.union(i-1,j-1)

nohint = 0
hint = []
for i in range(N):
    if Tree.size(i) == 1:
        nohint += 1
    else:
        hint.append(Tree.root(i))

print(nohint + len(set(hint)))

Measured memory_bytes: 107168
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in x,y;
  cin>>x>>y;
  if(x==y+1 || x==y-1 || x==y)
    cout<<"Brown"<<endl;
  else
    cout<<"Alice"<<endl;
  return 0;
}


Measured memory_bytes: 256
using System;

namespace ConsoleApp2
{
	class Program
	{
		static void Main(string[] args)
		{
			var input = Console.ReadLine().Split();
			int a = int.Parse(input[0]);
			int b = int.Parse(input[1]);

			int taps = 0;
			int remain = 1;

			for (; ; )
			{
				if (b <= remain)
				{
					break;
				}
				else
				{
					remain--;
					taps++;
					remain += a;
				}
			}
			Console.WriteLine(taps);
		}
	}
}


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

int main() {
  int n;
  cin >> n;
  vector<char> s(n);

  int e = 0;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    if (s[i] == 'E') {
      e++;
    }
  }

  int ans = 900000;
  int left_w = 0;
  int right_e = e;

  for (int i = 0 ; i < n; i++) {
    if (s[i] == 'E') {
      right_e--;
    }

    if (i > 0 && s[i-1] == 'W') {
      left_w++;
    }

    ans  = min(ans,left_w + right_e);

  }

  cout << ans << endl;

}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> v(N); rep(i, 0, N) { cin >> v[i]; }
	sort(all(v));
	cout << v.back() - v[0] << endl;
	return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include<queue>
#include <sstream>
#include <set>

const long long INF = 1000000007;
using namespace std;
typedef long long llong;

//int isalpha(char ch): ch がアルファベットなら true を返す
//int isdigit(char ch): ch が数字なら true を返す
//int islower(char ch): ch が小文字なら true を返す
//int isupper(char ch): ch が大文字なら true を返す
//int tolower(char ch): ch の小文字を返す
//int toupper(char ch): ch の大文字を返す

//string型
//size()	文字数を返す
//Insert()	（指定した場所に）文字・文字列を挿入する
//erase()	（指定した場所の）文字・文字列を削除する
//clear()	すべての文字を削除する
//substr()	文字列の（指定した）部分文字列を返す
//replace()	（指定した）部分文字列を新しい文字列に置換する
//c_str()変換
//文字列の比較は、<=や==などを使え
//replace関数を使い、簡単に文字列を置換
//リバース関数：reverse(str.begin(), str.end());
//map<type, type> dict;で宣言
//グラフ理論用変数
//vector<vector<llong> > graph(N);

//ソート
//降順sort(v.begin(), v.end(), std::greater<Type>());

//大文字から小文字へんかん
//w[i] = w[i]-'A'+'a';

//vector
//assignメソッド　引数：サイズ、値
//与えられたサイズと値でvectorを初期化する

//queueクラス
//find()次に取り出す値の表示をする。
//pop()値を取り出す。戻り値はなし
//push()キューに値をプッシュする

//priority_queueクラス

//切り上げ
//ceil
//floor

int main(){
    llong A,B,C,X;
    cin >> A >> B >> C >> X;
    llong ans=0;
    for(int a=0; a<=A; a++){
        for(int b=0; b<=B; b++){
            for(int c=0; c<=C; c++){
                if(500*a+100*b+50*c==X){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3124
#include <cstdio>
#include <algorithm>

using namespace std;

long long N, A, B;

int main()
{
    scanf("%lld%lld%lld", &N, &A, &B);
    if ((B - A) % 2 == 0)
    {
        printf("%lld\n", (B - A) / 2);
    }
    else
    {
        long long movesToEven = min(A, N - B + 1);
        printf("%lld\n", movesToEven + (B - A) / 2);
    }
    return 0;
}


Measured memory_bytes: 128
K = input()
N = len(K)
D = int(input())
mod = 10**9+7

dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    a = ord(K[i])-48
    for j in range(D):
        for k in range(10):
            b = (j+k)%D
            dp[i+1][1][b] += dp[i][1][j]
            if k<a:
                dp[i+1][1][b] += dp[i][0][j]
            dp[i+1][1][b] %= mod
    
    for j in range(D):
        b = (j+a)%D
        dp[i+1][0][b] += dp[i][0][j]
        dp[i+1][0][b] %= mod

print((dp[N][1][0]+dp[N][0][0]-1)%mod)

Measured memory_bytes: 61920
#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
#define INF  2000000000
//#define int ll
#define ll long long
#define ld long double
#define vi vector<int>
#define p pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC(type, c, n) vector<type> c(n);for(auto& i:c)cin>>i;
#define MAT(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
 
#define BR cout << "\n";
#define SP cout << " ";
#define ENDL cout<<endl;
#define OUT(d) cout<<d;
#define OUTL(d) cout<<d; BR;
#define YES OUTL("YES")
#define Yes OUTL("Yes")
#define NO OUTL("NO")
#define No OUTL("No")
#define RET return 0;
#define SUM(a, n) accumulate(a, a+n, 0)
#define VSUM(v) accumulate(ALL(v), 0);
 
#define REP(i, n) for(int i=0;i<(n);i++)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define FOR(i, m, n) for(int i = m;i < n; i++)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define AREP(a, n) for(auto (a):(n))
#define ALL(a) (a).begin(),(a).end()
#define IN(n, a, b) ((a)<=(n)&&(n)<(b))

signed main(){ INIT;
    double a, b, c, d, e, f;
    double x, y;
    while(cin >> a >> b >> c >> d >> e >> f){
        x=(e*c - b*f) / (a*e - d*b);
        y=(a*f - c*d) / (a*e - d*b);
        if(x==-0) x = 0;
        if(y==-0) y = 0;
        printf("%.3lf %.3lf\n",x,y);
    }
RET;}

Measured memory_bytes: 3280
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		Scanner vd = new Scanner(System.in);
		int h =vd.nextInt();
		int w =vd.nextInt();
		for(int i= 0;i<w+1;++i)System.out.print("#");
		System.out.println("#");
		for(int i= 0;i<h;++i)System.out.println("#"+vd.next()+"#");
		for(int i= 0;i<w+1;++i)System.out.print("#");
		System.out.println("#");
	}

}


Measured memory_bytes: 21460
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <stdio.h>
#include <set>
#include <string.h>

typedef long long ll;

using namespace std;

ll gcd(ll l, ll k) {
    ll tmp=k+(l/k)*2*k+(l%k);
    if (l%k==0) return tmp-k;
    else return tmp+gcd(k-l%k, l%k);
}

int main() {
    std::ios::sync_with_stdio(false);
    ll n, x, n_x, ans=0; cin>>n>>x;

    n_x=n-x;
    ans=x;
    ans+=gcd(x, n_x);

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 1e5
#define INF 1<<30
#define EPS 1e-5
#define all(a) (a).begin(),(a).end()
constexpr ll mod = 1e9 + 7;
using namespace std;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

template<ll mod>
class Fp {
public:
	ll val;

private:
	inline void calc_mod(ll& v) {
		if (v >= mod)v -= mod;
	}
public:
	Fp() {}
	Fp(ll v) :val(v%mod) {
		if (val < 0)val += mod;
	}

	Fp operator+=(const Fp &in) {
		val += in.val;
		calc_mod(val);
		return *this;
	}

	Fp operator+(const Fp &in) const {
		return Fp(*this) += in;
	}

	Fp &operator-=(const Fp &in) {
		val -= in.val;
		calc_mod(val);
		if (val < 0)val += mod;
		return *this;
	}

	Fp operator-(const Fp &in) const {
		return Fp(*this) -= in;
	}

	Fp& operator*=(const Fp& in) {
		val = val * in.val % mod;
		return *this;
	}

	Fp operator*(const Fp &in) const {
		return Fp(*this) *= in;
	}

	Fp& operator/=(const Fp& in) {
		*this *= modpow(in, mod - 2);
		return *this;
	}

	Fp operator/(const Fp& in) const {
		return Fp(*this) /= in;
	}

	bool operator==(const Fp&in)const {
		return val == in.val;
	}

	bool operator!=(const Fp&in)const {
		return val != in.val;
	}

	friend Fp modpow(const Fp& in, ll n) {
		if (n == 0)return 1;
		if (n & 1) {
			return in * modpow(in*in, n / 2);
		}
		else {
			return modpow(in*in, n / 2);
		}
	}
};
using modll = Fp<mod>;

class Factorial {
public:
	vector<modll> fact, finv;
	Factorial(ll n) :fact(n + 1, modll(1)), finv(n + 1, modll(1)) {
		for (int i = 2; i <= n; i++) {
			modll tmp(i);
			fact[i] = fact[i - 1] * tmp;
			finv[i] = finv[i - 1] / tmp;
		}
	}

	modll com(const ll& n, const ll& k) {
		if (n < k || n < 0 || k < 0)return modll(0);
		return fact[n] * finv[k] * finv[n - k];
	}
};


int main() {
	cin >> N >> M;
	vector<int> s(N), t(M);
	for (int i = 0; i < N; i++)cin >> s[i];
	for (int i = 0; i < M; i++)cin >> t[i];
	vector<vector<modll>> dp(N, vector<modll>(M,0));
	if (s[0] == t[0])dp[0][0] = 1;
	for (int i = 1; i < N; i++) {
		if (s[i] == t[0])dp[i][0] = dp[i - 1][0] + 1;
		else dp[i][0] = dp[i - 1][0];
	}
	for (int i = 1; i < M; i++) {
		if (s[0] == t[i])dp[0][i] = dp[0][i - 1] + 1;
		else dp[0][i] = dp[0][i - 1];
	}
	for (int n = 1; n < N; n++) {
		for (int m = 1; m < M; m++) {
			dp[n][m] = dp[n - 1][m] + dp[n][m - 1] + 1;
			if (s[n] != t[m])dp[n][m] -= dp[n - 1][m - 1] + 1;
		}
	}
	cout << dp[N - 1][M - 1].val + 1 << endl;
}


Measured memory_bytes: 31616
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    string s;
    cin >> s;

    int zero_num = 0;
    int one_num = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            zero_num++;
        } else {
            one_num++;
        }
    }
    cout << s.size() - abs(zero_num - one_num) << endl;
}


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

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define pp pop_back
#define pf push_front
#define sqr(a) (a)*(a)
#define mpr(a,b) make_pair(a, b)
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mpii;
typedef map<string, int> mpsi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pair<int, int>> qpi;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pair<int,int>> pqpi;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T> T gcd(T a, T b){return b ? gcd(b, a % b) : a;}
template<class T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template<class T, class TT>bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0, 31, 28, 31, 30, 31,30, 31, 31, 30, 31, 30, 31};

int main()
{
	ll n,k;
	cin >> n >> k;
	vll a(n + 2, 0);
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	ll ans = 0;
	while(n > 0)
	{
		ans ++;
		if(n <= k)
			break;
		n -= k - 1;
	}
	cout << ans;
	getchar();
	getchar();
	return 0;
	//freopen("Ganiyev.txt", "r", stdin);
	//freopen("Asadullo.txt", "w", stdout);
	//ios::sync_with_stdio(0);
	//cin.tie(0);cout.tie(0);
	
	
	
	
	
	
	
	
	
	
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;

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

    int H, W, h, w;
    cin >> H >> W >> h >> w;
    H -= h, W -= w;
    cout << H * W << endl;
}

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

const ll INF = 1e18;

int main()
{
	ll A, B, C, K;
	cin >> A >> B >> C >> K;
	cout << (K & 1 ? B - A : A - B) << endl;
	return 0;
}


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

int main(){
  int s;
  cin>>s;
  vector<int>L;
  int ans=1;
  int flag=0;
  while(1){
    L.push_back(s);
    if(s%2==0){
      s=s/2;
    }else{
      s=3*s+1;
    }
    ans++;

    for(int i=0;i<L.size();i++){
      if(L.at(i)==s){
        flag=1;
        break;}
    }
    if(flag==1)break;
  }

 cout<<ans<<endl;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if (a>=k)   cout<<k;
	else if (a+b>=k)   cout<<a;
	else   cout<<a-(k-a-b);
	return 0;
}

Measured memory_bytes: 3632
n, m = map(int, input().split())
a = list(map(int, input().split()))
sum, c = 0, 0
for i in a:
	sum += i
for i in a:
	if sum / (m * 4) <= i:
		c += 1
if c >= m:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 9172
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef pair<int, int> P;

int main() {
  int N, M;
  while(cin >>N >>M && N){
    int ans = 0, t;
    vector<P> v(N);
    REP(i, N) cin >>v[i].second >>v[i].first;
    SORT(v);
    REVERSE(v);
    REP(i, v.size()){
      if(M >= v[i].second) t = v[i].second;
      else if(M != 0) t = M;
      else t = 0;
      ans += v[i].first * (v[i].second - t);
      M -= t;
    }
    cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 1280
n = int(input())
arr = []
for i in range(n):
    a = list(map(int,input().split()))
    a.reverse()
    arr.append(a)
arr.sort()
tot = 0
for ab in arr:
    tot += ab[1]
    if tot>ab[0]:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 51288