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

using namespace std;

int main(){

	int w,h;


	while (1){
		cin >> h >> w;
		if (w == 0 && h == 0) break;

		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				if ((i + j) % 2 == 0){
					cout << "#";
				}
				else{
					cout << ".";
				}
			}
			cout << endl;
		}
		cout << endl;
	}


	return 0;
}

Measured memory_bytes: 1156
S = list(input())
import copy
S1 = copy.copy(S)
S1[0] = '0' if S1[0] == '1' else '1'
ans = 0
ans1 = 1
for i in range(1, len(S)):
    if S[i] == S[i-1]:
        S[i] = '0' if S[i-1] == '1' else '1'
        ans+=1
    # print(''.join(map(str, S)))

for i in range(1, len(S1)):
    if S1[i] == S1[i-1]:
        S1[i] = '0' if S1[i-1] == '1' else '1'
        ans1+=1
    # print(''.join(map(str, S1)))

print(min(ans, ans1))


Measured memory_bytes: 50288
#include<bits/stdc++.h>
#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define MIN3(a,b,c) (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c))
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN2(a,b) (a)<(b)?(a):(b)
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
#define ull unsigned long long
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;
#define deb(x )     cerr << #x << " here "<< x << endl;
#define endl    "\n"
#define printCase() "Case #" << caseNum << ": "
inline bool is_palindrome(const string& s){ return std::equal(s.begin(), s.end(), s.rbegin()); }
const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
#define ff first
#define ss second
/*----------------------------------------------------------------------*/

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    ll x = (s[0] == t[0]) ? 1 : 2;
    ll ans = 3 * x;
	FOR(i, x, n){
		if(s[i] == t[i]){
			if(s[i-1] == t[i-1]){
				(ans *= 2) %= MOD;	
			}
		}else{
			if(s[i-1] == t[i-1]){
				(ans *= 2) %= MOD;
			}else{
				(ans *= 3) %= MOD;
			}
			i++;
		}
	}
    cout<<ans;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<stack>
#include<unordered_map>
#include<bitset>
#include<limits>
#include<complex>
#include<array>
#include<numeric>
#include<functional>

using namespace std;
#define ll long long
#define ull unsigned long long
#define rrep(i,m,n) for(ll (i)=(ll)(m);(i)>=(ll)(n);(i)--)
#define rep(i,m,n) for(ll (i)=(ll)(m);i<(ll)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
constexpr long double m_pi = 3.1415926535897932L;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 62;
constexpr long double EPS = 1e-10;
template<typename T> using vector2 = vector<vector<T>>;
template<typename T> using vector3 = vector<vector2<T>>;
typedef vector<ll> Array;

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

	ll n, k;
	cin >> n >> k;
	Array a(n);
	REP(i, n)cin >> a[i];
	sort(all(a), greater<ll>());
	ll ans = 1;
	ll l = 0, r = n - 1;
	if (k % 2 == 1)ans *= a[0], l = 1;
	REP(i, k / 2) {
		if (a[l] * a[l + 1] >= a[r] * a[r - 1])(ans *= a[l] * a[l + 1] % MOD) %= MOD, l += 2;
		else (ans *= a[r] * a[r - 1] % MOD) %= MOD, r -= 2;
	}
	if (ans < 0) ans = accumulate(a.begin(), a.begin() + k, 1LL, [](ll a, ll b) {return a * b % MOD; });
	cout << (ans + MOD) % MOD << "\n";

	return 0;
}


Measured memory_bytes: 4756
/*alurquiza*/
#include <bits/stdc++.h>

using namespace::std;

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

	// freopen("milkvisits.in","r",stdin);
	// freopen("milkvisits.out","w",stdout);

	int N;
	cin >> N;

	bool flag = true;
	for(int i = 1;i <= N;i++){
		int ent;
		cin >> ent;


		if(ent % 2 == 0 && ent % 3 && ent % 5)
			flag = false;
	}

	if(flag)
		cout << "APPROVED\n";
	else
		cout << "DENIED\n";

	return 0;
}

//g++ -std=c++11 -Wall DS.cpp -o main

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
typedef long long int ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef pair<ll, ll>P;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

ll par[100000], depth[100000];
static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}
#define yo 100001
//------------------変数-----------------------//
//-------------------関数----------------------//
int main() {
	ll n,cnt=0;
	cin >> n;
	ll a[yo] = {};
	REP(i, n) { cin >> a[i]; }
	ll num[yo] = {};
	REP(i, n) {
		num[a[i]]++;
	}
	ll izryt = 0;
	REP(i, yo) {
		if (num[i]) {
			num[i]--;
		}
	}
	REP(i, yo) {
		if (num[i] % 2) {
			izryt++;
			num[i]--;
		}
	}
	if (izryt % 2) {
		izryt /= 2 ;
		izryt++;
		cnt += izryt*2;
	}
	else { izryt /= 2; cnt += izryt * 2; }
	REP(i, yo) {
		if (num[i]) {
			izryt += num[i] / 2;
			cnt += num[i] ;
		}
	}
	cout <<n- cnt << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> x(n);
	vector<int> x1(n);

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

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

	for (int i = 0; i < n; i++){
		if (x[i] != x1[n - 1]) cout << x1[n - 1] << endl;
		else cout << x1[n - 2] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3200
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[fastout]
fn main() {
    input! {mut a:isize,b:isize,mut c:isize,d:isize}
    let mut flag = true;
    while a > 0 && c > 0 {
        if flag {
            c -= b;
        } else {
            a -= d;
        }
        flag = !flag;
    }
    if !flag {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2172
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b)
{
    return *(long long int*)a - *(long long int*)b;
}


int main(void)
{	
	char s[4];
	scanf("%s",s);
	
	printf("ABC%s\n",s);
	return 0;
}


Measured memory_bytes: 128
n = int(input())
s = list(map(int, input().strip().split(' ')))

count = 0

for i in range(n):
    minj = i
    for j in range(i + 1, n):
        if s[j] < s[minj]:
            minj = j
    
    if minj != i:
        count += 1
    
    s[i], s[minj] = s[minj], s[i]

for i in range(n):
    if i != n - 1:
        print(s[i], end = ' ')
    else:
        print(s[i])

print(count)


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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  
  int count = 0;
  int pos = 0;
  while(true){
    pos = s.find("ABC",pos);
    if(pos==string::npos) break;
    pos += 3;
    count++;
  }

  cout << count << endl;
  return 0;
}




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

int main() {
  long long n,y;
  cin>>n;
  long long sum = 0;
  for(long long i = 1; i <= n; i++){
    y = (long long)(n / i);
    sum += (y * (y + 1) * i) / 2;
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 3648
N = int(input())
x = []
sigma_yen = 0
sigma_btc = 0.0

for i in range(N):
    x.append(input().split())



for i in range(N):
    if x[i][1] == 'JPY':
        sigma_yen += int(x[i][0])
    else:
        sigma_btc += float(x[i][0])


sigma = float(sigma_yen) + (sigma_btc * 380000.0)

print(sigma)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
using ll = long long;

int main()
{
	ll N, K, a, b;
	cin >> N >> K;
	vector<ll> cnt(MAX + 1);
	while (N--) {
		cin >> a >> b;
		cnt[a] += b;
	}
	ll c = 0;
	for (int i = 1; i <= MAX; i++) {
		c += cnt[i];
		if (c >= K) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}


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

using namespace std;

int main() {

    int m;

    cin >> m;

    while(m--) {

        int len;
        string train, temp1, temp2;
        map<string, bool> pat;

        cin >> train;

        len = train.size();

        for(int i = 1; i < len; ++i) {
            temp1 = train.substr(0, i);
            temp2 = train.substr(i);

            pat[temp1 + temp2] = true;
            pat[temp2 + temp1] = true;

            reverse(temp1.begin(), temp1.end());
            pat[temp1 + temp2] = true;
            pat[temp2 + temp1] = true;

            reverse(temp1.begin(), temp1.end());
            reverse(temp2.begin(), temp2.end());
            pat[temp1 + temp2] = true;
            pat[temp2 + temp1] = true;

            reverse(temp1.begin(), temp1.end());
            pat[temp1 + temp2] = true;
            pat[temp2 + temp1] = true;
        }

        cout << pat.size() << endl;

    }

}

Measured memory_bytes: 1300
def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

N, M = map(int, input().split(" "))
X=[]
Y=[]
c=-1
K = 10 ** 9 + 7
i=2
while True:
    if M % i == 0:
        X.append(i)
        Y.append(0)
        c += 1
        while M % i == 0:
            M /= i
            Y[c] += 1

    if i==2:
        i += 1
    else:
        i += 2

    if i>M:
        break

    if i**2>M:
        X.append(M)
        Y.append(1)
        break

ret = 1
for i in Y:
    ret *= mod_combination(i+N-1, i, K)
    ret %= K

print (ret)

Measured memory_bytes: 3064
#include <stdio.h>
int main(){
	long n;
	long a[10000];
	scanf("%li",&n);
	a[0]=-1;
	long ans=0;
	for (int i=1;i<=n;i++){
		scanf("%li",&a[i]);	
		if (a[i]==a[i-1]){
			ans++;
			a[i]=-i;
		}
	}
	printf("%li",ans);
}

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

using namespace std;

const int INF = 1001001001;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dist[50][50];       // (0, 0)からの最短距離

typedef pair<int, int> P;

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    int w_cnt = 0;
    for(int i = 0; i < H; ++i){
        cin >> s[i];
        for(int j = 0; j < s[i].length(); ++j){
            if(s[i][j] == '.')      w_cnt++;
        }
    }
    
    for(int i = 0; i < H; ++i){
        for(int j = 0; j < W; ++j){
            dist[i][j] = INF;
        }
    }
    dist[0][0] = 0;
    
    // 座標(x, y)
    queue<P> que;
    que.push(P(0, 0));
    dist[0][0] = 0;
    
    // (0, 0)から(H - 1, W - 1)への最短コストを求める
    while(!que.empty()){
        P p = que.front();
        que.pop();
        int x = p.first;
        int y = p.second;
        
        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= H || ny < 0 || ny >= W)      continue;
            if(s[nx][ny] == '#')                            continue;
            if(dist[x][y] + 1 >= dist[nx][ny])              continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            que.push(P(nx, ny));
        }
    }
    
    if(dist[H - 1][W - 1] == INF){
        cout << -1 << endl;
        return 0;
    }
    
    cout << w_cnt - 1 - dist[H - 1][W - 1] << endl;
}

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

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

    // dp[i][j] : i文字目からとj文字目からでの最長一致文字列の長さ
    vector<vector<int>> dp(5010, vector<int>(5010, 0));
    
    for(int i=N-1; i>=0; i--){
        for(int j=N-1; j>=0; j--){
            if(S[i] != S[j]) dp[i][j] = 0;
            else dp[i][j] = dp[i+1][j+1] + 1;
        }
    }

    int ans = 0;
    rep(i, N) rep(j, N){
            if(i >= j) continue;
            ans = max(ans, min(dp[i][j], j-i));
    }

    cout << ans << endl;
}


Measured memory_bytes: 98432
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dx[]={-3,-2,-1,0,0,0,1,2,3,0,0,0};
int dy[]={0,0,0,1,2,3,0,0,0,-1,-2,-3};
char mas[8][8];
void solve(int,int);
int main(){
  int n,x,y,HM=1;
  cin >> n;
  while(n--){
    for(int i=0;i<8;i++){
      for(int j=0;j<8;j++){
	cin >> mas[i][j];
      }
    }
    cin >> y >> x;
    solve(x-1,y-1);
    cout << "Data " << HM << ":" << endl;
    for(int i=0;i<8;i++){
      for(int j=0;j<8;j++){
	cout << mas[i][j];
      }
      cout << endl;
    }
    HM++;
  }
}
void solve(int x,int y){
  mas[x][y]='0';
  for(int i=0;i<12;i++){
    int nx=dx[i]+x,ny=dy[i]+y;
    if(nx>=0&&nx<8&&ny>=0&&ny<8&&mas[nx][ny]=='1'){
      solve(nx,ny);
    }
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;

ll n,m,v,p;
vector<ll> a;

bool ok( ll mid ){
    
    if( n-p <= mid ) return true;

    ll my = a[ mid ] + m;
    ll vv = v - ( p-1 );
   /* if( mid >= vv-1  ){
	if( a[n-p] <= my ) return true;
	else return false;
    }else{
*/
	if( my < a[n-p] ) return false;
	
	ll cnt = ( vv )*m;
	ll cc = 0;
	for(ll i= 0 ;i <= n-p ;i++){
	    cc += min( m , max( my - a[i]  , 0ll ) );
	}

	if( cnt <= cc ) return true;
	else return false;

  //  }

}

int main(){
    cin>>n>>m>>v>>p;
    a = vector<ll> (n);
    for(ll i=0;i<n;i++) cin>>a[i];
    ll cnt = p;

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

    ll l = 0, u = n;

    while( u - l > 1 ){
	ll mid = (u+l)/2;
	if( ok( mid ) ){
	    u = mid;
	}else{
	    l = mid;
	}
    }

    if( ok(l) ) cout<<n-l<<endl;
    else cout<<n-l-1<<endl;

    //cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 1024
N = int(raw_input())
a = [int(x) for x in raw_input().split(" ")]

lookup = {}
for val in a:
    lookup[val] = 1 + (lookup[val] if lookup.has_key(val) else 0)

remove_num = 0
for val, count in lookup.items():
    remove_num += count if count < val else (count - val)

print remove_num


Measured memory_bytes: 20044
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

int x[100010],xx[100010],w[100010];
int l,r,s,t,n,m;
ll c;

inline int rd()
{
	int x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

int main()
{
	n=rd();l=rd();t=rd();
	for (int i=1;i<=n;i++) x[i]=rd(),w[i]=rd();
	for (int i=1;i<=n;i++)
	{
		if (w[i]==2) w[i]=-1;
		r=x[i]+w[i]*t;
		if (r>0) (c+=r/l)%=n;
		else if (r<0) (c+=(r+1)/l-1)%=n;
		xx[i]=(r%l+l)%l;
	}
	sort(xx+1,xx+n+1);
	c=(c+n)%n;
	for (int i=c+1;i<=n;i++) printf("%d\n",xx[i]);
	for (int i=1;i<=c;i++) printf("%d\n",xx[i]);
	return 0;
}

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

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

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

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

constexpr int extgcd(int a, int b, int &x, int &y) {
  int d = a;
  if (b != 0) {
    d = extgcd(b, a%b, y, x);
    y -= (a/b)*x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

// m is a large prime integer. Usually 1000000007 is used.
constexpr int mod_inverse(int a, int m) {
  int x=0, y=0;
  extgcd(a, m, x, y);
  return (m + x%m)%m;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, x; cin >> n >> x;
  vector<int> s(n);
  rep(i, n) cin >> s[i];
  sort(s.begin(), s.end());

  ll fact = 1;
  for(int i=2; i<=n; i++) {
    fact *= i;
    fact %= mod;
  }
  vector<ll> modinv(n+1);
  for(int i=1; i<=n; i++) {
    modinv[i] = mod_inverse(i, mod);
  }

  unordered_map<int, ll> mp;
  unordered_map<int, ll> mp2;
  mp[x] = fact;

  bool flag = true;
  while(flag) {
    flag = false;
    for(auto e: mp) {
      auto r = e.first;
      auto it = upper_bound(s.begin(), s.end(), r);
      auto k = distance(s.begin(), it);
      if (k==0) {
        mp2[e.first] += mp[e.first];
        mp2[e.first] %= mod;
      }
      for(int i=0; i<k; i++) {
        flag = true;
        auto pos = r%s[i];
        mp2[pos] += e.second * modinv[k];
        mp2[pos] %= mod;
      }
    }
    swap(mp, mp2);
    mp2.clear();
  }

  ll ans = 0;
  for(auto e: mp) {
    ans += e.second*e.first;
    ans %= mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T> T in(){
	T res;
	cin >> res;
	return res;
}
template<typename T> vector<T> in(int n){
	vector<T> res(n);
	rep(i,n) cin >> res[i];
	return res;
}

template<typename T> void out(bool a, T F, T S){
	cout << (a ? F : S) << endl;
}

void solve(vector<int> a){
	out(a[0] % 500 <= a[1], "Yes", "No");
}

int main(){
	solve(in<int>(2));
}


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


int main() {
    int n;
    cin>>n;
    int a[n];
    rep(i,n) cin>>a[i];

    double b = 0;
    rep(i,n) b += 1.0/a[i];

    cout<<setprecision(18);
    cout<<1/b<<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;
const int INF = 2147483647;
using ll = long long;

int main() {
    ll x;
    cin >> x;
    ll a=0;
    ll ans;
    if(x %11>0 && x%11<=6)  a=1;
    if(x % 11 == 0)
        ans = (x/11)*2-a;
    else
        ans = (x/11)*2+2-a;

    cout << ans << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
#define LL long long
#define INF 1e18
#define Gmin(x,y) (x>(y)&&(x=(y)))
using namespace std;
int n,a[N+5][N+5];LL f[N+5][N+5],s1[N+5][N+5],s2[N+5][N+5],t1[N+5][N+5],t2[N+5][N+5];
int main()
{
	RI i,j,k;LL ans=INF;for(scanf("%d",&n),i=1;i<=n;++i) for(j=1;j<=n;++j) i^j&&scanf("%d",&a[i][j]);
	for(i=1;i<=n+1;++i) for(j=1;j<=n+1;++j) s1[i][j]=s1[i][j-1]+a[i][j],s2[i][j]=s2[i-1][j]+a[i][j];
	for(i=1;i<=n;++i) for(j=n+1;j>=i+1;--j) t1[i][j]=t1[i][j+1]+s1[j][i];
	for(i=1;i<=n;++i) for(j=i+1;j<=n+1;++j) t2[i][j]=t2[i][j-1]+s2[j-1][j]-s2[i-1][j];
	for(i=0;i<=n+1;++i) for(j=0;j<=n+1;++j) f[i][j]=INF;f[0][0]=0;
	for(i=0;i<=n;++i) for(j=i;j<=n;++j) if(f[i][j]!=INF)
		for(k=j+1;k<=n+1;++k) Gmin(f[j][k],f[i][j]+t1[j][k+1]-t1[i][k+1]+t2[j+1][k]);
	for(i=0;i<=n;++i) Gmin(ans,f[i][n+1]);return printf("%lld",ans),0;
}

Measured memory_bytes: 11136
N=int(input())
DD=[]
t=0

for _ in range(N):
    D=list(map(int,input().split()))
    DD.append(D)

for i in range(N-2):
    if (DD[i][0]-DD[i][1])**2+(DD[i+1][0]-DD[i+1][1])**2+(DD[i+2][0]-DD[i+2][1])**2==0:
        t=1
        break
    i+=1
if t==1:
    print('Yes')
else:
    print('No')

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

using namespace std;

int main(void){

    int n;
    cin >> n;
    vector<int> a(n*3);
    for(int i=0; i<3*n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    long long result = 0;
    for(int i=0; i<n; i++) {
//        cout << (3*n-2)-(i*2) << endl;
        result += a[(n*3-2)-(i*2)];
    }
    
    cout << result << endl;

    return 0;
    
}


Measured memory_bytes: 1408
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(H: int, W: int, a: "List[List[int]]"):
    ans = []  # type: List[List[int]]
    p = 0
    for i in range(H):
        if i % 2 == 0:
            js = range(W)
        else:
            js = reversed(range(W))
        for j in js:
            if a[i][j] % 2 == 1:
                p ^= 1
            nexti = i
            nextj = j + (1 if i % 2 == 0 else -1)
            if nextj == -1:
                nexti += 1
                nextj = 0
            elif nextj == W:
                nexti += 1
                nextj = W - 1
            if p:
                ans.append([i, j, nexti, nextj])
    if p:
        del ans[-1]
    print(len(ans))
    for i, j, nexti, nextj in ans:
        print(i + 1, j + 1, nexti + 1, nextj + 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, a)


if __name__ == '__main__':
    main()


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  cin >> n;
  vint a(n);
  rep(i, n) cin >> a[i];
  deque<int> b;
  rep(i, n) {
    if(i%2) b.push_front(a[i]);
    else b.push_back(a[i]);
  }
  rep(i, n) {
    if(i) cout << " ";
    cout << (n%2 ? b[n-1-i] : b[i]);
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 5376
import sys
def input():
    return sys.stdin.readline().strip()

def calc(x,n):
    ans = 0
    for i,a in enumerate(x):
        ans += (2*i-n+1)*a
    return ans

n,m = map(int,input().split())
x = tuple(map(int,input().split()))
y = tuple(map(int,input().split()))

print(calc(x,n)*calc(y,m)%(int(1e9+7)))


Measured memory_bytes: 18624
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()
/* libraries */

struct UnionFind
{
  int n;
  std::vector<int> par,size;
  UnionFind(int sz) : n(sz), par(sz,0), size(sz,1) {
    std::iota(par.begin(),par.end(),0);
  }
  int find(int x) {
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x=find(x);y=find(y);
    if(x==y) return;
    if(size[x]<size[y]) std::swap(x,y);
    size[x]+=size[y];
    par[y]=x;
  }
};


signed main() {
	int n,k;
	std::cin >> n >> k;
	std::vector<int> p(n);
	rep(i,n) std::cin >> p[i];
	std::set<int> current;
	rep(i,k) current.emplace(p[i]);

	std::vector<int> sorted(n,0);

	int icount = 0;
	{
		int curr = 1;
		rep(i,n-1) {
			if(p[i+1]>p[i]) {
				curr++;
				if(curr>=k) {
					sorted[i+1]=1;
				}
			} else {
				icount+=std::max(0ll,curr-k+1);
				curr=1;
			}
		}
		icount+=std::max(0ll,curr-k+1);
	}

	UnionFind uf(n);

	if(icount>1) {
		int first = -1;
		rep(i,n) if(sorted[i]==1) { first = i; sorted[first] = 0; break; }
		rep(i,n) if(sorted[i]==1) uf.unite(first,i);
	}

	int count = 1;
	int front = p[0];
	int fronti = 0;
	for(int i=k;i<n;i++) {
		fronti++;
		int back = p[i];
		current.emplace(back);
		if(*current.begin()==front && *current.rbegin()==back) {
			uf.unite(i,i-1);
			current.erase(front);
			front = p[fronti];
			continue;
		}
		current.erase(front);
		front = p[fronti];
		count++;
	}
	int cnt = 0;
	for(int i=k-1;i<n;i++) {
		if(uf.find(i)==i) cnt++;
	}
	print(cnt);

	return 0;
}


Measured memory_bytes: 15872
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////

int main() {
	
	ll N;
	cin >> N;
	map<ll,ll> mpd;
	repn(i, N) {
		ll d;
		cin >> d;
		mpd[d]++;
	}

	ll M;
	cin >> M;
	map<ll, ll> mpt;
	repn(i, M) {
		ll t;
		cin >> t;
		mpt[t]++;
	}

	string ans = "YES";

	for (auto p : mpt) {
		//cout << p.first << mpd[p.first] << p.second << endl;
		if (mpd[p.first] < p.second) { ans = "NO"; }
	}

	cout << ans;
	

	system("PAUSE");
}


Measured memory_bytes: 25464
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
//template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}


int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    vector<string> a{"Sunny", "Cloudy", "Rainy", "Sunny"};
    string s;
    cin>>s;
    cout<<*(find(all(a), s)+1)<<endl;
}


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



using namespace std;

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

int n;
long long int ans=0;

int main(){
    cin >> n;
    ans = 1;
    for(int i=2;i<=n;i++){
        ans += i*2;
        for(int j=2*i;j<=n;j+=i){
            ans+=j;
        }
    } 
    // rep(i,n+1){
    //     // cout << i << " " << mm[i] << endl;
    //     ans += i*mm[i];
    // }
    cout << ans << endl;


return 0;
}

Measured memory_bytes: 3632
package main

import "fmt"

func Reverse(s string) string {
  runes := []rune(s)
  for i, j := 0, len(runes) - 1; i < j; i, j = i + 1, j - 1 {
    runes[i], runes[j] = runes[j] , runes[i]
  }
  return string(runes)
}

func main() {
  var s string
  ss := []string{"maerd", "remaerd", "esare", "resare"}
  fmt.Scan(&s)
  s = Reverse(s)
  for i := 0; i < len(s); {
    b := false
    for j := 0; j < 4; j++ {
      if i + len(ss[j]) > len(s) {
        continue
      }
      if s[i : i + len(ss[j])] == ss[j] {
        b = true
        i += len(ss[j])
      }
    }
    if b == false {
      fmt.Println("NO")
      return
    }
  }
  fmt.Println("YES")
}

Measured memory_bytes: 1792
// CGL_1_C
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N    0.00001
using namespace std;

struct vec{
	double x;
	double y;
};

struct point{
	double x;
	double y;
};

double norm(struct vec a){
	return sqrt(pow(a.x, 2) + pow(a.y, 2));
}

double inner_p(struct vec a, struct vec b){
	return (a.x*b.x + a.y*b.y);
}

double cross_p(struct vec a, struct vec b){
	return (a.x*b.y - a.y*b.x);
}

int main(){
	point p[3];
	vec v[2];
	int q, flag;

	cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y;
	v[0].x = p[1].x - p[0].x;
	v[0].y = p[1].y - p[0].y;

	cin>>q;
	for(int i=0;i<q;i++){
		cin>>p[2].x>>p[2].y;

		v[1].x = p[2].x - p[0].x;
		v[1].y = p[2].y - p[0].y;
		
		flag = 0;
		if(fabs(cross_p(v[0], v[1])) < N)
			if(inner_p(v[0], v[1]) < 0)
				flag = 3;
			else if(norm(v[0]) < norm(v[1]))
				flag = 4;
			else
				flag = 5;
		else if(cross_p(v[0], v[1]) > 0)
			flag = 1; 
		else
			flag =  2;

		switch(flag){
		case 1:
			cout<<"COUNTER_CLOCKWISE"<<endl;
			break;
		case 2:
			cout<<"CLOCKWISE"<<endl;
			break;
		case 3:
			cout<<"ONLINE_BACK"<<endl;
			break;
		case 4:
			cout<<"ONLINE_FRONT"<<endl;
			break;
		case 5:
			cout<<"ON_SEGMENT"<<endl;
			break;
		default:
			cout<<"ERROR"<<endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 1224
#include <stdio.h>
int main(void){
    int r,d,x;
    int num;
    int i;
    
    scanf("%d %d %d",&r,&d,&x);
    num=x;
    
    for(i=0;i<10;i++){
        num=r*num-d;
        printf("%d\n",num);
    }
    return 0;
}

Measured memory_bytes: 128
import scala.math.min

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val c = sc.next

  val r = c.count(_ == 'R')
  val w = c.count(_ == 'W')

  val lr = c.take(r).count(_ == 'R')
  val rw = c.takeRight(w).count(_ == 'W')

  val result = min(r - lr, min(w - rw, min(r, w)))

  println(result)
}


Measured memory_bytes: 55724
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
using namespace std;

#define ll int64_t
const long MOD = 1e9 + 7;


int main()
{
 int a,b,c;
  cin >> a >> b;
  if ( a+b <10){
    cout <<a+b;
  }else{
	cout <<"error";
  }
}

Measured memory_bytes: 256
N, M, Q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(Q):
    a_, b_, c_, d_ = map(int, input().split())
    a += [a_-1]
    b += [b_-1]
    c += [c_]
    d += [d_]

def score(A):
    ret = 0
    for i in range(Q):
        if A[b[i]] - A[a[i]] == c[i]:
            ret += d[i]
    return ret


def dfs(li):
    if len(li) == N:
        global ans
        ans = max(ans, score(li))
    else:
        if li == []:
            st = 1
        else:
            st = li[-1]
        for i in range(st, M+1):
            li.append(i)
            dfs(li)
            li.pop()

ans = 0
dfs([])
print(ans)

Measured memory_bytes: 9304
import numpy as np

N, W = map(int, input().split())
knap = []
for i in range(N):
    knap.append(tuple(map(int, input().split())))

s_val = sum([v for w, v in knap])
    
INF = float("inf")
dp = np.full(s_val+1, INF)
dp[0] = 0

for i, (w, v) in enumerate(knap):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
    
print(max([i for i in range(s_val+1) if dp[i] <= W]))

Measured memory_bytes: 29480
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

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

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 998244353 ; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	
	constexpr int MAX = 3100;
	int ans = 0;
	int N, S;
	vector<int> A;
	vector<vector<int>> dp;
	
	cin>>N>>S;
	
	A.resize(N);
	dp.resize(MAX, vector<int>(MAX));
	
	for(int i = 0; i < N; i++){
		cin>>A[i];
	}
	
	dp[0][0] = 1;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < MAX; j++){
			dp[i+1][j] += dp[i][j] * 2;
			dp[i+1][j] %= MOD;
			
			if(A[i] + j < MAX) {
				dp[i+1][j + A[i]] += dp[i][j];
				dp[i+1][j + A[i]] %= MOD;
			}
		}
	}
	
	ans = dp[N][S];
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 78448
#include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for (int i = 0;i<(n);i++)
typedef long long ll;
using namespace std;

const int inf = 0x3f3f3f3f;
int N,M;

int main(){
	// freopen("test.in","r",stdin);
	cin>>N>>M;
	vector<vector<int> > jobs(M);
	rep(i,N){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a>M) continue;
		jobs[M-a].push_back(b);
	}
	priority_queue<int> q;
	ll ans = 0;
	for(int i = M-1;i>=0;--i){
		for(int b:jobs[i]){
			q.push(b);
		}
		if(!q.empty()){
			ans += q.top();
			q.pop();
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
    int n;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    long long result = 0;
    for (int i = n - 1; i >= 0; i--) {
        long long current = a[i] + result;
        if (current != 0) {
            result += ((current - 1) / b[i] + 1) * b[i] - current;
        }
    }
    cout << result;
    return 0;
}

Measured memory_bytes: 1024
n,k=map(int, input().split())
r,s,p=map(int, input().split())
t = input()
le = len(t)//k
his = []
ans=0
for i in range(k):
    if t[i]=="r":
        ans+=p
        his.append("r")
    if t[i]=="s":
        ans+=r
        his.append("s")
    if t[i]=="p":
        ans+=s
        his.append("p")

for i in range(k, n):
    if his[i-k]==t[i]:
        if i<n-k:
            his.append(" ")
    else:
        if t[i]=="r":
            ans+=p
            his.append("r")
        if t[i]=="s":
            ans+=r
            his.append("s")
        if t[i]=="p":
            ans+=s
            his.append("p")
print(ans)


Measured memory_bytes: 4212
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  ll N,W;
  cin >> N >> W;
  vector<ll> w(110);
  vector<ll> v(110);
  rep(i,N) cin >> w[i] >> v[i];

  vector<vector<ll>> dp(110,vector<ll>(100010,0));
  rep(i,N){
    rep(sumv,W+1){
      if(sumv >= w[i])dp[i+1][sumv] = max(dp[i][sumv],dp[i][sumv-w[i]]+v[i]);
      dp[i+1][sumv] = max(dp[i][sumv],dp[i+1][sumv]);
    }
  }


  cout << dp[N][W] << endl;
}


Measured memory_bytes: 87296
n = int(input())
v = list(map(int, input().split()))
even = dict()
odd = dict()
even[0] = 0
odd[0] = 0
for i in range(n//2):
  a = v[2*i]
  if a in even:
    even[a] += 1
  else:
    even[a] = 1
  a = v[2*i + 1]
  if a in odd:
    odd[a] += 1
  else:
    odd[a] = 1

even_sorted = sorted(even.items(), key=lambda x:x[1], reverse=True)
odd_sorted = sorted(odd.items(), key=lambda x:x[1], reverse=True)

if even_sorted[0][0] == odd_sorted[0][0]:
  print(n - max(even_sorted[0][1]+odd_sorted[1][1], even_sorted[1][1]+odd_sorted[0][1]))
else:
  print(n - even_sorted[0][1] - odd_sorted[0][1])

Measured memory_bytes: 63084
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
   
int main(){
  int n,id=1,nv,ch,index,syuryo=1;
     
  scanf("%d\n",&n);
 
  int *A = new int[100040];
  bool *B = new bool[100040];
  int *C = new int[100040];
  string *D = new string[100040];
  int st,ed;
  for(int i=0;i<=100040;i++){
    A[i]=0; // hukasa
    C[i]=-1; // oya
    B[i]=false; //false nara ko wo motte inai
  }
  for(int i=0;i<n;i++){
    scanf("%d",&id);
    
    getline(cin,D[id]);
 
    syuryo=1;
    for(int r=1;r<=D[id].length();r++){
      if(D[id][r] == ' '){
	syuryo = r-1; // String no iti gime
	break;
      }
    }
   
    index = atoi(D[id].substr(1,syuryo).c_str()); // val wo motomeru 
    //cout << "index = " << index << ", syuryo = " << syuryo << endl;

    if(index != 0)B[id]=true;
       
   

    if(index != 0){
      st = syuryo+2;    
      for(int d = syuryo+2;d<=D[id].length();d++){ 
	if(D[id][d] == ' ' || d == D[id].length()){
	  A[atoi(D[id].substr(st,d-st).c_str())]=A[id]+1;
	  C[atoi(D[id].substr(st,d-st).c_str())]=id;
	  if(B[atoi(D[id].substr(st,d-st).c_str())]){
	    int st2=3;
	    
	    for(int j = syuryo+2;j<=D[atoi(D[id].substr(st,d-st).c_str())].length();j++){
	      
	      if(D[atoi(D[id].substr(st,d-st).c_str())][j] == ' ' || j == D[atoi(D[id].substr(st,d-st).c_str())].length()){
		A[atoi(D[atoi(D[id].substr(st,d-st).c_str())].substr(st2,j-st2).c_str())]=A[atoi(D[id].substr(st,d-st).c_str())]+1;
		st2=j+1;
	      }
	    }
	  }
	  st = d+1;
      }
      }
      
    }
    
  }
     
 
     
  for(int i=0;i<n;i++){
    printf("node %d: parent = %d, depth = %d, ",i,C[i],A[i]);
    int cou=0;
    if(C[i] == -1){printf("root, [");}
    else if(!B[i])printf("leaf, [");
    else printf("internal node, [");
    

    syuryo=1;
    for(int r=1;r<=D[i].length();r++){
      if(D[i][r] == ' '){
	syuryo = r-1;
	break;
      }
    }
    index = atoi(D[i].substr(1,syuryo).c_str());
    //cout  << endl << index << endl;
    
    st=syuryo+2;
    if(index != 0){      
      for(int j=syuryo+2;j<=D[i].length();j++){
	if(D[i][j] == ' ' || D[i].length() == j ){
	  //cout << "i = " << i << ",j = " << j << endl;qqq
	  printf("%d",atoi(D[i].substr(st,j-st).c_str()));
	  if(j != D[i].length())printf(", ");
	  st=j+1;
	}
      }
    }
    printf("]\n");
  }
     
  delete [] A;
  delete [] B;
  delete [] C;
  delete [] D;
  return 0;
}

Measured memory_bytes: 5212
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <cstdint>
#include <cmath>
using namespace std;

void solve() {
	int r;
	cin >> r;
	cout << r * r << endl;
}

int main() {
	solve();
	return 0;
}


Measured memory_bytes: 256
from collections import deque

n, q = map(int, input().split())

queue = deque()
for i in range(n):
    N, T = input().split()
    queue.append([N, int(T)])

t = 0
while queue:
    x = queue.popleft()
    if x[1] <= q:
        t += x[1]
        print(x[0], t)
        
    else:
        queue.append([x[0], x[1]-q])
        t += q


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

int main(void) 
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    sort(p.begin(), p.end());
    int ans = 0;
    rep(i,k) ans += p[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<string.h>
 
int main()
{
 
  int i,j,minj,num,flag=1,hantei=0;
  char b[36][3],s[36][3],sw[36][3];
   

  scanf("%d",&num);
 
  for(i=0;i<num;i++){
 
    scanf("%s",b[i]);
 
    strcpy(s[i],b[i]);
     
      }
   
  i=0;
  while(flag){
    flag = 0;
for (j = num - 1; j >= i+1; j--) {
      if (b[j - 1][1] > b[j][1]) { 
    strcpy(sw[j],b[j]);        
    strcpy( b[j],b[j - 1]);
    strcpy( b[j - 1],sw[j]);
    flag = 1;
      }
 }
    i++;
  }
   
 
  for(i=0;i<num;i++){
 
    minj = i;
 
    for(j=i;j<num;j++){
      if(s[j][1] < s[minj][1]){
    minj = j;
      }
    }
    if(i != minj){
    
    strcpy(sw[i] ,s[i]);
    strcpy(s[i],s[minj]);
    strcpy(s[minj],sw[i]);
    }
  }
 
  for(i=0;i<num-1;i++){
 
    printf("%s ",b[i]);
  }
    printf("%s",b[i]);
   
 
  printf("\n");
  printf("Stable\n");
 
  for(j=0;j<num-1;j++){
 
    printf("%s ",s[j]);
 
  }
  printf("%s",s[j]);
  printf("\n");
  flag = 1;
  for(i=0;i<num;i++){
 
 
    if(strcmp(&b[i][0],&s[i][0])!=0 && hantei==0){
      printf("Not stable\n");
      flag=0;
      hantei++;
    }
  }
  if(flag==1){
    printf("Stable\n");
  }
 return 0;
}


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

int main(){
	int n;	cin>>n;
	int b1=0, b2=0, b4=0;
	for(int i=0;i<n;i++){
		int a;	cin>>a;
		if(a%4==0)b4++;
		else if(a%2==0)b2++;
		else b1++;
	}

	if(b2) b1++;

	if(b4+1>=b1) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;



	return 0;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);


int main()
{
    int i = 0, j = 0, cs = 0, in;
    int n; cin>>n;
    int cnt = 0, ans = 0;
    for(int i = 0; i < n; i++){
        int a, b; cin>>a>>b;
        if(a == b) cnt++;
        else cnt = 0;
        if(cnt >= 3) ans = 1;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3612