akhauriyash/Code-Regression huggingface dataset:
/*input
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	const int mod = 1e9+7;
	int n;cin>>n;
 
	vector<long long int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
 
	vector<long long int> pf(n);
	pf[0]=a[0];
	for(int i=1;i<n;i++) pf[i]=pf[i-1]+a[i];
	
	vector<vector<long long int>> dp(n,vector<long long int> (n,0));
	vector<vector<long long int>> sum(n,vector<long long int> (n,0));
 
	for(int i=0;i<n;i++) for(int j=i;j<n;j++) sum[i][j] = pf[j]-(i-1>=0?pf[i-1]:0);
	for(int len=1;len<=n;len++)
	{
		for(int i=0;i<=n-len;i++)
		{
			int j = i+len-1;
			if(len==1) dp[i][j] = a[i];
			else dp[i][j] = max( sum[i][j]-dp[i+1][j],sum[i][j]-dp[i][j-1]);
		}
	}
 
	cout<<2*dp[0][n-1]-sum[0][n-1];
 
	return 0;
}


Measured memory_bytes: 144232
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define pb push_back
#define f first
#define s second
#define double long double
#define p push
const int MAX=2e5+5;
const int MAX2=2e6+4;
const int MAAX=2e18;
const int MOD=1e9+7;

in main()
{
int n,k;
cin>>n>>k;
int ans=min(k-(n%k),n%k);
cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 3
hats = [1, 0, 0]

if n == 1:
    if A[0] == 0:
        print(3)
    else:
        print(0)
    exit()


if A[0] != 0:
    print(0)
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print(0)
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

Measured memory_bytes: 14396
H, W, N = [int(_) for _ in input().split()]
R, C = [int(_) for _ in input().split()]
S = input()
T = input()

#drop by up
r = R
for i in range(N):
    if S[i] == 'U':
        r -= 1
        if r == 0:
            print('NO')
            exit()
    if T[i] == 'D' and r < H:
        r += 1

#drop by down
r = R
for i in range(N):
    if S[i] == 'D':
        r += 1
        if r == H + 1:
            print('NO')
            exit()
    if T[i] == 'U' and r > 1:
        r -= 1

#drop by left
c = C
for i in range(N):
    if S[i] == 'L':
        c -= 1
        if c == 0:
            print('NO')
            exit()
    if T[i] == 'R' and c < W:
        c += 1

#drop by right
c = C
for i in range(N):
    if S[i] == 'R':
        c += 1
        if c == W + 1:
            print('NO')
            exit()
    if T[i] == 'L' and c > 1:
        c -= 1

print('YES')


Measured memory_bytes: 3888
#include <iostream>

using namespace std;

typedef long long ll;

int n;
string s[202020];
int l[202020];
int b[1222333];

int tr[1222333][26];
int tc;
int th[1222333][26];

void add(int i, int k) {
    int u = 0;
    for (int j = k; j >= 1; j--) {
        for (int h = 0; h < 26; h++) {
            if (b[j]&(1<<h)) th[u][h]++;
        }
        int c = s[i][j]-'a';
        if (tr[u][c] == 0) tr[u][c] = ++tc;
        u = tr[u][c];
    }
}

int calc(int i, int k) {
    int u = 0;
    for (int j = k; j >= 2; j--) {
        int c = s[i][j]-'a';
        u = tr[u][c];
    }
    return th[u][s[i][1]-'a'];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        l[i] = s[i].size();
        s[i] = "#"+s[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= l[i]; j++) {
            b[j] = b[j-1]|(1<<(s[i][j]-'a'));
        }
        add(i,l[i]);
    }
    ll c = 0;
    for (int i = 1; i <= n; i++) {
        //cout << i << " " << s[i] << " " << calc(i,l[i]) << "\n";
        c += calc(i,l[i])-1;
    }
    cout << c << "\n";
}


Measured memory_bytes: 215064
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long A[][] = new long[N][N];
		long B[][] = new long[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				A[i][j]=B[i][j]=sc.nextLong();
			}
		}
		sc.close();
 		
		for(int k=0;k<N;k++) {
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					if(A[i][j]==A[i][k]+A[k][j]) {
						if(i==j||j==k||k==i)continue;
						B[i][j]=0;
					}
					if(A[i][j]>A[i][k]+A[k][j]) {
						System.out.println(-1);
						return;
					}
				}
			}
		}
		long sum = 0;
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				sum += B[i][j];
			}
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 61272
def solve():
    N = int(input())

    ans = N // 11

    if (N - 11 * ans) == 0:
        print(ans * 2)
    elif (N - 11 * ans) > 6:
        print(ans * 2 + 2)
    elif 0 < (N - 11 * ans) <= 6:
        print(ans * 2 + 1)

solve()

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, W;
  cin >> H >> W;
  vector<vector<char>> s(H, vector<char>(W));
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      cin >> s[i][j];
    }
  }
  vector<vector<int>> dp(H, vector<int>(W, INT_INF));
  dp[0][0] = (s[0][0] == '#') ? 1 : 0;
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      for (int k = 0; k < 2; k++)
      {
        int ni = i + dy[k], nj = j + dx[k];
        if (ni >= H || nj >= W)
          continue;
        int add = 0;
        if (s[ni][nj] == '#' && s[i][j] == '.')
          add++;
        chmin(dp[ni][nj], dp[i][j] + add);
      }
    }
  }
  cout << dp[H - 1][W - 1] << endl;
  return 0;
}

// まずは経路を一つ固定してみる．その経路が条件を満たすようにするための最小操作回数を求めてみる．dp[i][j]:=マス(i, j)に到達するまでに魔法を唱える最小回数　(i, j)から(ni, nj)への移動に関するDPは(ni, nj)が通路のときchmin(dp[ni][nj], dp[i][j]), (ni, ni)が壁で(i, j)が通路の時，chmin(dp[ni][nj], dp[i][j] + 1), (ni, nj)が壁で(i, j)が壁の時，chmin(dp[ni][nj], dp[i][j])(魔力が継続中)


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

int main() {
  int a,b;
  cin >> a >> b;
  
  if(a>=b){
    for(int i=0; i<a; i++){
      if(i==(a-1)){
        cout << b << endl;
      }
      else{
        cout << b;
      }
    }
  }
  else{
    for (int i=0; i<b; i++){
      if(i==(b-1)){
        cout << a << endl;
      }
      else{
        cout << a;
      }
    }
  }
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,i,p=0;
    cin>>n;
    string s;
    cin>>s;
    for(i=0;i<n-2;i++){
        if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C')
        p++;
    }cout<<p;
    return 0;
}


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

public class Main {
    static long mod = (long) 1e9 + 7;
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        long [] x = new long[n + 1];
        for (int i = 1; i <= n; i++) x[i] = sc.nextInt();
        long [] pref = new long[n];
        pref[1] = 1;
        for (int i = 2; i < n; i++) pref[i] = (pref[i - 1] + inv(i)) % mod;
        long ans = 0;
        for (int i = 1; i < n; i++) {
            ans = (ans + pref[i] * (x[i + 1] - x[i]) % mod) % mod;
        }
        fac = new long[n + 3];
        initFac(n + 1);
        ans = (ans * fac[n - 1]) % mod;
        out.println(ans);
        out.close();
    }

    static long[] fac;

    static void initFac(long n) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = (fac[i - 1]  * i) % mod;
        }
    }

    static long exponentiation(long base, long exp)
    {
        long t = 1L;
        while (exp > 0) {

            // for cases where exponent
            // is not an even value
            if (exp % 2 != 0)
                t = (t * base) % mod;

            base = (base * base) % mod;
            exp /= 2;
        }
        return t % mod;
    }

    static long nck(int n, int k) {
        if (n < k)
            return 0;
        long den = inv((int) (fac[k] * fac[n - k] % mod));
        return fac[n] * den % mod;
    }

    static long pow(long b, long e) {
        long ans = 1;
        while (e > 0) {
            if (e % 2 == 1)
                ans = ans * b % mod;
            e >>= 1;
            b = b * b % mod;
        }
        return ans;
    }

    static long inv(long x) {
        return pow(x, mod - 2);
    }



    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}

Measured memory_bytes: 47052
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	n := getInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = getInt()
	}

	b := make([]int, n*2)
	l := n - 1
	r := n
	rot := false
	for i := 0; i < n; i++ {
		if !rot {
			b[r] = a[i]
			r++
		} else {
			b[l] = a[i]
			l--
		}
		rot = !rot
	}

	// out(b)
	// out(l, r)

	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	l++
	r--
	for i := 0; i < n; i++ {
		if !rot {
			fmt.Fprint(w, b[l], " ")
			l++
		} else {
			fmt.Fprint(w, b[r], " ")
			r--
		}
	}
	fmt.Fprintln(w)
}


Measured memory_bytes: 10496
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string S;
  cin >> S;
  int s = stoi(S.substr(0, 4)) * 10000 + stoi(S.substr(5, 2)) * 100 +
          stoi(S.substr(8, 2));

  if (s <= 20190430) {
    cout << "Heisei" << endl;
  } else {
    cout << "TBD" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> p(n);
	for(int i = 0; i < n; i++) scanf("%d", &p[i]);

	int cnt = 0, mi = 1 << 30;
	for(int i = 0; i < n; i++) {
		if(mi >= p[i]) {
			mi = p[i];
			cnt++;
		}
	}
	
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 1024
from collections import defaultdict

def solve(n, S, m, T):
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    for t in T:
        d[t] -= 1
    return max(0, max(d.values()))

_n = int(input())
_S = [input() for _ in range(_n)]
_m = int(input())
_T = [input() for _ in range(_m)]
print(solve(_n, _S, _m, _T))

Measured memory_bytes: 3316
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define fst first
#define snd second

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);

  int n, m;
  cin >> n >> m;
  vector<set<pair<int,int>>> pref(n+1);
  for(int i = 0; i < m; i++){
    int p, t;
    cin >> p >> t;
    pref[p].insert({t, i});
  }
  vector<string> ids(m);
  for(int i = 1; i <= n; i++){
    int pos = 1;
    for(auto j : pref[i]){
      string first = to_string(i);
      int x = 6 -  first.size();
      first = string(x, '0') + first;
      string second = to_string(pos);
      x = 6 - second.size();
      second = string(x, '0') + second;
      ids[j.second] = first + second;
      pos++;
    }
  }
  for(int i = 0; i < m; i++){
    cout << ids[i] << "\n";
  }
  return 0;
}



Measured memory_bytes: 16384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
int main()
{
	ld d,t,s;
	cin>>d>>t>>s;
	ld x=t*s;
	if(t*s>=d){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
const int N = 0x3f3f3f3f;
int ans , n , m , mivn = N;
int main(){
	cin >> n >> m;
	ans = 0 ;
	for (int i=1;i<=n;i++){
		int x;
		cin >> x;
		ans ++;
		m -= x; 
		mivn = min(x,mivn);
	}
	while ( m >= mivn ){
		ans ++ ;
		m -= mivn;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3544
#include <iostream>
using namespace std;
int main(){
    int a;
    cin>>a;
    int f=a/100;
    int b=a%100;
    bool ym=0,my=0;
    if(f>0 && f<13)my=1;
    if(b>0 && b<13)ym=1;
    if(ym && my)cout<<"AMBIGUOUS"<<endl;
    else if(ym)cout<<"YYMM"<<endl;
    else if(my)cout<<"MMYY"<<endl;
    else cout<<"NA"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n;
    ll d, a;
    cin >> n >> d >> a;
    vector<pair<int, int>> p(n);
    rep(i, n) cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end());
    ll ans = 0;
    d = d * 2;
    ll tot = 0;
    queue<pair<int, int>> q;
    rep(i, n) {
        int x = p[i].first;
        int h = p[i].second;
        while (q.size() && q.front().first < x) {
            tot -= q.front().second;
            q.pop();
        }
        h -= tot;
        if (h > 0) {
            ll num = (h + a - 1) / a;
            ll damage = num * a;
            ans += num;
            tot += damage;
            q.push(make_pair(x + d, damage));
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2688
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

struct edge{
    int to, cap, rev;
};

#define MAX_V 300
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].push_back((edge){to, cap, (int)G[to].size()});
    G[to].push_back((edge){from, 0, (int)G[from].size()-1});
}

// v...target vertex, t...end vertex, f...maximum flow 
int dfs(int v, int t, int f){
    if(v == t)  return f;

    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(!used[e.to] && e.cap > 0){
            int d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }

    return 0;
}

const int INF = 1<<29;

// maxflow from s to t
int max_flow(int s, int t){
    int flow = 0;
    while(1){
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if(f == 0)  return flow;
        flow += f;
    }
}

int di[8] = {0,0,1,-1,1,1,-1,-1};
int dj[8] = {1,-1,0,0,1,-1,1,-1};
#define inRange(x,a,b) (a <= x && x < b)

// 解説AC
int main(){
    int h, w;
    cin >> h >> w;
    auto f = [=](int i, int j)->int{
        return i*w+j;
    };
    int si, sj, gi, gj;
    char mat[h][w];
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> mat[i][j];
            if(mat[i][j] == 'S'){
                si = i, sj = j;
                mat[i][j] = 'o';
            }else if(mat[i][j] == 'T'){
                gi = i, gj = j;
                mat[i][j] = 'o';
            }
        }
    }
    if(si == gi || sj == gj){
        cout << -1 << endl;
        return 0;
    }
    int SOURCE = 298, SINK = 299;
    // 始点・終点につながっている辺の容量を極端に大きくすることで
    // 最小カットによって蓮S, Tがカットされないようにする
    add_edge(SOURCE, si, INF);
    add_edge(SOURCE, h+sj, INF);
    add_edge(gi, SINK, INF);
    add_edge(h+gj, SINK, INF);
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(mat[i][j] != 'o')    continue;
            add_edge(i, h+j, 1);
            add_edge(h+j, i, 1);
        }
    }
    cout << max_flow(SOURCE, SINK) << endl;
    return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cctype>
#include<queue>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<map>
#include<utility>
#include<iomanip>
#include<set>
using namespace std;
typedef long long ll;
const int INF=1e9+7;
vector<int> bfs(int n,vector<vector<int> >&G,int s)
{
	vector<int> d(n,INF);
	d[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int v:G[u])
			if(d[v]>d[u]+1)
			{
				d[v]=d[u]+1;
				q.push(v);
			}
	}
	return d;
}
int main()
{
	int n;
	cin>>n;
	vector<vector<int> >G(n);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int> d1=bfs(n,G,0);
	vector<int> d2=bfs(n,G,n-1);
	int n1=0,n2=0;
	for(int u=0;u<n;u++)
		if(d1[u]<=d2[u])
			n1++;
		else n2++;
	cout<<(n1>n2?"Fennec":"Snuke")<<endl;
	return 0;
}

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

using namespace std;
using ll = long long;

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

    vector<ll> A(N);
    for (auto&& Ai : A) {
        cin >> Ai;
    }

    while(true) {
        if (A.size() == 1) {
            break;
        }

        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A.size(); ++j) {
                if (i != j) {
                    A[j] %= A[i];
                }
            }
            A.erase(remove(A.begin(), A.end(), 0), A.end());
        }
    }

    std::cout << A[0] << std::endl;

    return 0;
}


Measured memory_bytes: 1024
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

int main() {
	string s;
	cin >> s;
	int cnt = 0;
	string ss = "CODEFESTIVAL2016";
	FOR(i, 0, s.size()) {
		if (s[i] != ss[i])
			cnt++;
	}
	cout << cnt << endl;
	return 0;

}

Measured memory_bytes: 764
#include<stdio.h>
int main(){
  int n,l[10],i,max,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&l[i]);
    sum+=l[i];
  }
  max=l[0];
  for(i=1;i<n;i++){
    if(max<l[i]){
      max=l[i];
    }
  }
  puts(max*2<sum?"Yes":"No");
}
 

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rint register int
#define gc() getchar()
inline int read(){int r=0,s=0,c=gc();for(;!isdigit(c);s=c,c=gc());for(;isdigit(c);(r*=10)+=c-48,c=gc());return s^45?r:-r;}
int f[16][32768], g[32768], w[16][16], n, E;
int main()
{
	n = read(), E = 1<<n; for(rint m = read(), a, b; m--; a = read()-1, b = read()-1, w[a][b] = w[b][a] = read()); for(rint i = 0; i < n; fill(f[i],f[i]+E,-INF), i++);
	for(rint S = 1, T, i, j; S < E; S&1 ? f[0][S] = g[S] : 0, S++) for(g[S] = g[T=S-(S&-S)], i = ilogb(S&-S), j = 0; j < n; j++) if(T&1<<j) g[S] += w[i][j];
	for(rint S = 1, T, i, j; S < E; S++) for(T = ~-S&S; T; --T&=S) for(i = 0; i < n-1; i++) if((S^T)&1<<i&&f[i][S^T]>=0)
		for(j = 1; j < n; T&1<<j&&w[i][j] ? f[j][S] = max(f[j][S],f[i][S^T]+g[T]+w[i][j]) : 0, j++); printf("%d\n",g[~-E]-f[~-n][~-E]); return 0;
}

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

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

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define bk back()
#define pb push_back

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(x,a) for (auto& x: a)

const int MX  = 2e5+5;
const int MOD = 1e9+7;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
    // cin.exceptions(cin.failbit);
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

int32_t main() {

    setIO();

    int x,n; cin >> x >> n;

    vi arr(n); trav(x,arr) cin >> x;

    bitset<MX> vis; vis.reset();
    trav(x,arr) vis[x] = true;

    pi res = {INF,0};
    FOR(i,0,102) {
        if (!vis[i]) {
            if (res.f > abs(x-i)) {
                res = {abs(x-i),i};
            } else if (res.f == abs(x-i)) {
                res.s = min(res.s,i);
            }
        } 
    }

    cout << res.s << "\n";
}   



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

using namespace std;

typedef long long ll;

int max(int a, int b)
{ return (a > b) ? a : b; }

const int MAXN = 200031;

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

    string s;
    cin >> s;
    ll ans = 0;
    ll cnt = 0;
    for (char c : s)
    {
        if (c == 'B') cnt++; else ans += cnt;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 720
# coding: utf-8

def getInput():
    N = int(input())
    in_row = [ int(x) for x in input().split(" ") ]
    return N, in_row

def checkNext(tail):
    cnt = 1
    for val in tail[1:]:
        if tail[0] == val:
            cnt += 1
        else:
            break
    return cnt

def countMagic(in_row):
    m_sum = 0
    i = 0
    while len(in_row) >= i-1:
        tmp = checkNext(in_row[i:])
        i += tmp
        m_sum += tmp // 2
    
    return m_sum

if __name__ == "__main__":
    N, in_row = getInput()
    print(countMagic(in_row))


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

int main() {
  int n; cin >> n;
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) cin >> c[i];
  sort(a.begin(), a.end(), greater<int>());
  sort(b.begin(), b.end(), greater<int>());
  sort(c.begin(), c.end(), greater<int>());

  long long ans = 0;
  int i = 0, j = 0, k = 0;
  while (i < n) {
    while (j < n && a[i] < b[j]) {
      while (k < n && b[j] < c[k]) k++;
      ans += 1LL * (n - i) * k;
      j++;
    }
    i++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	cout << ((a+d-1)/d>=(c+b-1)/b ? "Yes" : "No") << endl;




}

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

int n;
const int MAXN = 100005;

struct Node{
	int L;
	int R;
}node[MAXN];

bool cmp(Node a, Node b){
	return a.L < b.L;
}

int main(){
	cin >> n;
	int x, l;
	for (int i = 1; i <= n; i++){
		cin >> x >> l;
		node[i].L = x - l;
		node[i].R = x + l - 1;
	}
	sort(node + 1, node + n + 1, cmp);
	int sum = 0;
	for (int i = 1; i <= n - 1; i++){
		if (node[i].R >= node[i + 1].L) {
			sum++;
			node[i + 1].R = min(node[i].R, node[i + 1].R);
		}
	}
	cout << n - sum << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
  for(;;){
    int n;
    cin >> n;
    if(n==0) break;
    map<int,vector<int> > add,sub;
    for(int i=0; i<n; i++){
      int m,a,b;
      cin >> m >> a >> b;
      add[a].push_back(m);
      sub[b].push_back(m);
    }
    map<int,vector<int> >::iterator ap,sp;
    ap = add.begin();
    sp = sub.begin();
    long long weight = 0;
    bool bOK = true;
    while(ap != add.end()){
      if((*ap).first < (*sp).first){
        vector<int>& v = (*ap).second;
        for(int i=0; i<v.size(); i++){
          weight += v[i];
        }
        if(weight > 150){
          bOK = false;
          break;
        }
        ap++;
      }else{
        vector<int>& v = (*sp).second;
        for(int i=0; i<v.size(); i++){
          weight -= v[i];
        }
        sp++;
      }
    }
    if(bOK) cout << "OK" << endl;
    else cout << "NG" << endl;
  }
  return 0;
}

Measured memory_bytes: 1228
while True:
    H,W = [int(x) for x in input().split()]
    if(H,W) == (0,0):break
    
    for i in range(H):
        for j in range(W):
            if (i+j) % 2 ==0: 
                print('#',end='')
            else:
                print('.', end='')
        print('')
        
    print('')


Measured memory_bytes: 7024
N, M, C = gets.chomp!.split(" ").map(&:to_i)
B_m = gets.chomp!.split(" ").map(&:to_i)

count = 0
N.times do |i|
    a_m = gets.chomp!.split(" ").map(&:to_i)
    sum = 0
    a_m.zip(B_m).each do |a, b|
        sum += a * b
    end

    if sum + C > 0
        count+=1
    end
end

puts count


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 2e5 + 50;
const int mod = 1e9 + 7;
const int inf = 1e17;
int dx[] = {0, 1, -1, 0, -1, 1, 1, -1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  int tot = H * W - h * W - (H - h) * w;
  cout << tot;
}

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

int vec[10001];
int func(int x,int y,int z) {
	return x*x+y*y+z*z+x*y+y*z+z*x;
}
int main() {
	int n;cin >> n;
	vint ans(n+1,0);
	int ma=sqrt(double(n))+1;
	for(int i=1;i<=ma;i++)for(int j=1;j<=ma;j++)for(int k=1;k<=ma;k++) {
		if(func(i,j,k)<=n) ans[func(i,j,k)]++;
	}
	rep(i,n) cout << ans[i+1] << endl;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   int t;
   cin>>t;
   int n;
   cin>>n;
   vector<string> v;
   while(t--)
   {
      string str;
      cin>>str;
      v.push_back(str);
   }
   sort(v.begin(),v.end());
   for(auto x:v)
    cout<<x;
   
    return 0;
}








Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
int n,now,a[N],v[M],b[N],nex[M],head[N];
void addedges(int x,int y){
	nex[++now]=head[x];
	head[x]=now,v[now]=y;
}
int dfs(int x,int fa){
	int res=0,mx=0;
	if(b[x]==1)	return a[x];
	for(int i=head[x];i;i=nex[i])
		if(v[i]!=fa){
			int k=dfs(v[i],x);
			if(k==-1)	return -1;
			res+=k,mx=max(mx,k);
		}
	int up=(a[x]*2-res);
	if(res<up||up<0||2*mx-res>up||res<up)	return -1;
	return up;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	if(n==2){
		if(a[1]==a[2])	puts("YES");
		else	puts("NO");
		return 0;
	}
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		addedges(x,y),++b[x];
		addedges(y,x),++b[y];
	}
	for(int i=1;i<=n;i++)
		if(b[i]!=1){
			addedges(0,i);
			if(dfs(0,0)!=-1)	puts("YES");
			else	puts("NO");
			break;
		}
	return 0;
}


Measured memory_bytes: 8320
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b){return *(int*)a-*(int*)b;}
int main(){
    int n[4];
    for(int i = 0; i < 4; i++)
        scanf("%d",&n[i]);
    qsort(n,4,4,cmp);
    if(n[0] == 1 && n[1] == 4 && n[2] == 7 && n[3] == 9)
        puts("YES");
    else puts("NO");
    return 0;
}

Measured memory_bytes: 128
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nya_n "(=^･ω･^=)"
typedef long long ll;
using namespace std;


/*
ll gcd(ll x, ll y) {
if (y == 0) return x;
return gcd(y, x%y);
}
/*
ll lcm(ll x, ll y) {
ll g = gcd(x, y);
return x / g * y;
}
ll pw(int x, int n) {
	ll y = 1;
	ll p = x;
	while (n != 0) {
		if (n % 2) {
			y = y*p%mod;
			n = n - 1;
		}
		else {
			p = p*p%mod;
			n = n / 2;
		}
	}
	return y;
}

ll modinv(ll x) {
	return pw(x, mod - 2);
}*/

int n, cnt, cnt2;

int main() {
	cin >> n;
	cnt = 0;
	lp(n) {
		cnt2 = 0;
		if ((i+1) % 2) {
			LP(n, j) {
				if ((i + 1) % (j + 1) == 0)
					cnt2++;
			}
			if (cnt2 == 8)
				cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
#include<algorithm>
#include <queue>
#include <cmath>
#include <limits>
#include <map>
#include <iomanip>
using namespace std;
long long int n;

int main(){
  cin >> n;
  long long int A[n+1];
  long long int num_count[n+1];
  long long int same_count = 0;
  for (long long int i = 0; i <= n + 1; i++)
  {
    num_count[i] = 0;
  }
  for (long long int i = 1; i <= n; i++){
    cin >> A[i];
    num_count[A[i]]++;
  }
 
  for (long long int i = 1; i <= n; i++){
    same_count += num_count[i] * (num_count[i] - 1) / 2;
  }
  for (long long int i = 1; i <= n; i++)
  {
   cout << same_count - (num_count[A[i]] - 1)  << endl;
  }

  return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define MOD 1000000007
using namespace std;
typedef long long ll;

int pm(int a, int e){
	int r=1;
	while(e){
		if(e&1)r=(1LL*r*a)%MOD;
		e>>=1;
		a=(1LL*a*a)%MOD;
	}
	return r;
}

int uf[200005];

int find(int x){
	if(uf[x]<0)return x;
	return uf[x]=find(uf[x]);
}

void join(int x, int y){
	x=find(x);y=find(y);
	if(x==y)return;
	if(uf[x]>uf[y])swap(x,y);
	uf[x]+=uf[y];
	uf[y]=x;
}

int f[200005];
vector<pair<int,int> > g[200005];
pair<pair<int,int>,int> z[200005];
int n,x,y;

int main(){
	int r=1;
	memset(uf,-1,sizeof(uf));
	f[0]=1;
	fore(i,1,200005)f[i]=(1LL*f[i-1]*i)%MOD;
	scanf("%d%d%d",&n,&x,&y);
	fore(i,0,n){
		int c,w;
		scanf("%d%d",&c,&w);c--;
		z[i]=mp(mp(w,c),i);
		g[c].pb(mp(w,i));
	}
	sort(z,z+n);
	fore(i,0,n){
		if(!g[i].size())continue;
		sort(g[i].begin(),g[i].end());
		fore(j,1,g[i].size()){
			if(g[i][0].fst+g[i][j].fst<=x)join(g[i][0].snd,g[i][j].snd);
		}
	}
	int a=-1;
	fore(i,0,n){
		if(z[i].fst.snd!=a){
			fore(j,0,n){
				if(z[j].fst.snd==z[i].fst.snd)continue;
				if(z[i].fst.fst+z[j].fst.fst<=y)join(z[i].snd,z[j].snd);
			}
			if(a>=0)break;
			a=z[i].fst.snd;
		}
	}
	fore(i,0,n)if(uf[i]<0)r=(1LL*r*f[-uf[i]])%MOD;
	fore(i,0,n){
		map<int,int> s;
		for(auto p:g[i]){
			s[find(p.snd)]++;
		}
		for(auto p:s)r=(1LL*r*pm(f[p.snd],MOD-2))%MOD;
	}
	printf("%d\n",r);
	return 0;
}






Measured memory_bytes: 16368
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 1000;

int n,m,par[MAX],rank[MAX];

void init(int n){
  for(int i = 0 ; i < n ; i++){
    par[i] = i;
    rank[i] = 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(rank[x] < rank[y]){
    par[x] = y;
  } 
  else {
    par[y] = x;
    if(rank[x] == rank[y]) rank[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}

int kruskal(pair<int,pair<int,int> > es[MAX]){
  sort(es,es+m);
  init(n);
  int res = 0;
  for(int i = 0 ; i < m ; i++){
    int a = es[i].second.first;
    int b = es[i].second.second;
    if(!same(a,b)){
      unite(a,b);
      res += es[i].first;
    }
  }
  return res;
}

int main(){
  while(cin >> n >> m ,n +m){
    pair<int,pair<int,int> > es[MAX];
    for(int i = 0 ; i < m ; i++){
      cin >> es[i].second.first >> es[i].second.second >> es[i].first;
    }
    cout << kruskal(es) << endl;
  }

  return 0;
}

Measured memory_bytes: 1180
/*****************************************************
 				*	Logged in : HABIBUR RAHMAN						 *
				*	Dept	  : COMPUTER SCIENCE AND ENGINEERING	 *
				*													 *
				*	KHULNA UNIVERSITY OF ENGINEERING AND TECHNOLOGY  *
				******************************************************/


#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<string> vs;
typedef pair<ll,ll> pll;
#define fast_io 			ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) 				v.begin(),v.end()
#define allr(v) 			v.rbegin(),v.rend()
#define rep(i,a,b) 			for(ll i=a;i<=b;i++)
#define rep0(i,n)			for(ll i=0;i<n;i++)
#define rrep0(i, n) 		for(ll i=(ll)(n);i>0;--i)
#define rrep(i, a, b) 		for(ll i=(ll)(a);i>=(ll)(b);--i)
#define pb(z) 				push_back(z)
#define ff					/first
#define ss 					second
#define caset 				int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define sz(X) 				((ll)(X).size())
#define scan(X) 			scanf("%s", (X))
#define ms(v,val)			memset((v),(val),sizeof((v)))
#define ms0(X) 				memset((X), 0, sizeof((X)))
#define ms1(X) 				memset((X), -1, sizeof((X)))
#define m_p(a,b)            make_pair(a,b)
#define get_pos(c,x) 		(lower_bound(c.begin(),c.end(),x)-c.begin())
#define lcm(a,b)            (a*b)/__gcd(a,b)
#define INF9                1000000010
#define INF18               4000000000000000010
#define bpll(a)             __builtin_popcountll(a)
#define sqr(a)              ((a)*(a))
#define nl					"\n"
//#define mod					1e9+7;
#define mx_el(v)			*max_element(all(v));
#define mn_el(v)			*min_element(all(v));
#define pcase(z,x)    		cout<<"Case "<<z<<": "<<x<<"\n"
const double pi = 2*acos(0) ;
#define display(v)			vi :: iterator it;for(it=(v).begin();it!=(v).end();it++){cout << *it << " " ;}cout << endl;
#define taking(n,v) 		for(ll i=0;i<(n);i++){ll inp;cin>>inp;(v).push_back(inp);}

void start(){
      #ifndef ONLINE_JUDGE 
      freopen("input.txt" , "r" , stdin) ;
      freopen("output.txt" , "w" , stdout) ;
      #endif
}

void solve()
{
 	 char b;cin>>b;
 	 if(b=='A')cout << 'T' << nl;
 	 else if(b=='T')cout << 'A'<< nl;
 	 else if(b=='C')cout << 'G'<<nl;
 	 else if(b=='G') cout << 'C'<<nl;
}

int main() {
	fast_io
	//start();
    //caset{
    	//cout << "Case " << tt << ": ";

		  solve();
	//}
	
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  ll ans=1;
  vector<int> v(n);
  rep(i,n){
    cin >> v[i]; 
    ans*=3;
  }
  ll cnt=1;
  for (int i=0;i < n;i++){
    int tmp=0;
    for (int j=-1;j <2;j++){
      if ((v[i]+j)%2==1) tmp++; 
    }
    cnt*=tmp;
  }
  cout << ans-cnt << endl;
  
  
  return 0;
}



Measured memory_bytes: 256
n = int(input())
s1 = input()
s2 = input()

idea = '''
ABB
ACC
任意の A の選び方に対して B の選び方 2 通り * C の選び方 1 通り

AB
AB
任意の A の選び方に対して B の選び方 2 通り

AABB
CCDD
任意の A,B の選び方に対して、 C,D の選び方 3 通り
1122 1122 1133
2211 2233 2211

AAC
BBC
任意の A,B の選び方に対して、 C の選び方 1 通り

開幕だけちょっと気をつける
'''

ind = 0
ans = 1
is_vertical = s1[0] == s2[0]
if is_vertical:
  ans = 3
  ind += 1
else:
  ans = 6
  ind += 2
while ind < n:
  prev_vertical = is_vertical
  is_vertical = s1[ind] == s2[ind]
  if prev_vertical:
    ans *= 2 
  elif not is_vertical:
    ans *= 3
  ind = ind + 1 + (not is_vertical)
print(ans%(10**9+7))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define F first
#define S second
#define M 998244353
ll n,a,b,k,ans;
ll o[300005];
ll pw(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y&1)res=res*x%M;
        x=x*x%M;
        y>>=1;
    }
    return res;
}
ll cm(ll x,ll y){
    if(y==0)return 1;
    return o[x]*pw(o[y],M-2)%M*pw(o[x-y],M-2)%M;
}
int main(void){
    cin>>n>>a>>b>>k;
    o[0]=1;
    for(ll i=1;i<=n;i++)o[i]=o[i-1]*i%M;
    for(ll i=0;i<=n;i++){
        if(a*i<=k&&(k-a*i)%b==0){
            ll j=(k-a*i)/b;
            if(j<=n)ans=(ans+cm(n,i)*cm(n,j)%M)%M;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define inf          INT_MAX
#define zer          INT_MIN
#define nl cout<<'\n' ; 
void speed() { ios_base::sync_with_stdio(false);cin.tie(NULL);}

void max_self(ll &a , ll b)
{
	a= max(a,b);
}

void solve()
{
	
	int n , w ; cin>>n>>w ; 
	vector<ll> dp(w+1); 
	
	for(int i=0 ; i<n ; i++)
	{
		int wgt , val ; cin>>wgt>>val ;
		
		for(int left_w =w ; left_w>=0 ; left_w--)
		{
			if(left_w+wgt<=w)
			{
				max_self(dp[left_w+wgt] , dp[left_w]+val );
			}
		}
	}
	
	ll answer =0 ; 
	for(int i=0 ; i<=w ; i++) max_self(answer , dp[i]); 
	cout<<answer ; 
	
	
}

int main()
{
	speed(); 
    int T = 1;
   // cin >> T;
    while (T--){
    solve();
}
}




Measured memory_bytes: 3960
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int q = sc.nextInt();
    List<Map<String, Integer>> queue = new ArrayList<>();
    int second = 0;
    for(int i = 0; i < n; i++) {
        queue.add(new HashMap<>());
        queue.get(queue.size() - 1).put(sc.next(), sc.nextInt());
    }
    while(queue.size() > 0) {
      String s = "";
      for(String e : queue.get(0).keySet()) {
        s = e;
      }
      int a = queue.get(0).get(s);
      queue.remove(0);
      if(a <= q) {
        second += a;
        System.out.println(s + " " + second);
      } else {
        second += q;
        queue.add(new HashMap<>());
        queue.get(queue.size() - 1).put(s, a - q);
      }
    }
  }
}



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

typedef long long ll;

#define rep0(i, n) for(ll i=0; i<(ll)(n); i++)
#define rep1(i, n) for(ll i=1; i<=(ll)(n); i++)
#define rep(i, a, b) for(ll i=(ll)a; i<=(ll)(b); i++)
#define rep0r(i, n) for(ll i=(ll)(n)-1; i>=0; i--)
#define rep1r(i, n) for(ll i=(ll)(n); i>0; i--)
#define repr(i, a, b) for(ll i=(ll)b; i>=(ll)(a); i--)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) a * b / __gcd(a, b)


void solve() {
    ll n;
    ll cnt[200010];
    cin >> n;

    for(ll i=0; i<200010; i++) {
        cnt[i] = 0;
    }

    for(ll i=2; i<=n; i++) {
        ll x = 0;
        cin >> x;
        cnt[x]++;
    }

    for(ll i=1; i<=n; i++) {
        cout << cnt[i] << '\n';
    }
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 5220
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<unordered_map>
#include<queue>

using namespace std;
class CompareFirst
{
public:
  bool operator()(pair<int,int> n1,pair<int,int> n2) {
    return n1.first>n2.first; //>:desc <:asc
  }
};


int main(){

  string s;
  int a,b,c,i,j,k,n,ans;
  vector<string> lst;
  vector<int> cnt;

  //unordered_map<string,int> mp;

  //priority_queue<int> pq; // default ‘å‚«‚¢‡
  //priority_queue<pair<int,int>,vector<pair<int,int>>,CompareFirst pq;

  cin >> a;
  cin >> s;
  
  if(a >= 3200)cout << s << endl;
  else cout << "red" << endl;



  

  return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 2000000

int H,A[MAX+1];
void swap(int* a,int* b){
  int tempx=*a;
  int tempy=*b;
  *a=tempy;
  *b=tempx;
  return;
}
void maxheap(int i){
  int l,r,largest;
  l=2*i;
  r=2*i+1;

  if(l<=H && A[l]>A[i])largest=l;
  else largest=i;
  if(r<=H&&A[r]>A[largest])largest=r;
  if(largest !=i){
    swap(&A[i],&A[largest]);
    maxheap(largest);
  }
}

int main(){
  scanf("%d",&H);
  for(int i=1;i<=H;i++)scanf("%d",&A[i]);

  for(int i=H/2;i>=1;i--)maxheap(i);

  for(int i=1;i<=H;i++)printf(" %d",A[i]);
  printf("\n");
  return 0;
}



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

int main(){
    string zero_one;
    cin >> zero_one;
    long long size = zero_one.size();

    int ans = 0;
    long long mohan[size];
    long long Zero_one[size];

    for (int i = 0; i < size; i++){
        if ( zero_one[i] == '0' ) {
            Zero_one[i] = 0;
        } else {
            Zero_one[i] = 1;
        }
    }

    if ( Zero_one[0] == 0 ) {
        for (int i = 0; i < size; i++){
            if ( i % 2 == 0 ) {
                mohan[i] = 0;
            } else {
                mohan[i] = 1;
            }
        }
    } else {
        for (int i = 0; i < size; i++){
            if ( i % 2 == 0 ) {
                mohan[i] = 1;
            } else {
                mohan[i] = 0;
            }
        }
    }

    for (int i = 0; i < size; i++){
        if ( Zero_one[i] != mohan[i] ) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };
#define all(u) begin(u),end(u)
#define mp make_pair
#define pb push_back
#define WMAX 30
#define HMAX 60

int W,H;
char S[HMAX][WMAX];
int B[HMAX][WMAX][2];

int main()
{
  while(true)
    {
      scanf("%d%d",&W,&H);
      if(W==0&&H==0)break;
      memset(B, -1, sizeof(B));
      queue<pi> Q;
      queue<bool> R;
    
      rep(i,H)
	{
	  rep(j,W)
	    {
	      scanf(" %c",&S[i][j]);
	      if(S[i][j]=='S')
		{
		  B[i][j][0]=0;
		  B[i][j][1]=0;
		  Q.push(pi(i,j));
		  Q.push(pi(i,j));
		  R.push(0);
		  R.push(1);
		}	      
	    }
	}
      
      int M = 114514;
      while(!Q.empty())
	{
	  int h=Q.front().first;
	  int w=Q.front().second;
	  Q.pop();
	  bool r=R.front();
	  R.pop();

	  if(S[h][w]=='T')
	    {
	      M=min(B[h][w][r], M);
	      continue;
	    }
	  repi(i,h-2,h+3)
	    {
	      
	      repi(j,w-3,w+4)
		{
		  if(i<0||i>=H||j<0||j>=W)continue;
		  if(r && j<=w)continue;
		  if(!r && w<=j)continue;
		  if(abs(h-i)+abs(w-j)>3)continue;
		  if(S[i][j]=='X' || S[i][j]=='S')continue;
		  int dis;
		  if(S[i][j]=='T')dis=0;
		  else dis = S[i][j] -'0';
		  if(B[i][j][!r]!=-1 && B[i][j][!r]<=B[h][w][r]+dis)continue;
		  B[i][j][!r]=B[h][w][r]+dis;
		  Q.push(pi(i,j));
		  R.push(!r);
		}
	    }
	    
	  
	}
      /* rep(i,H)
	{
	  rep(j,W)
	    {
	      printf("%d ",min(B[i][j][0],B[i][j][1]));
	    }
	  printf("\n");
	  }*/
      if(M==114514)M=-1;
      printf("%d\n",M);
    }
  return 0;
}

Measured memory_bytes: 3256
#include <iostream>
#include <unordered_set>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <stack>

using namespace std;

template<class T> inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false;}

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

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

void checkRoute(int step, int start, VI& route, map<int, unordered_set<int>> AB) {
  for (const auto elem: AB[start]) {
    if (elem < 2 || step >= route[elem-2]) {
      continue;
    }
    route[elem-2] = start;
    checkRoute(step+1, elem, route, AB);
  }
  return;
}

int main(void){
  int N, M;
  cin >> N >> M;
  map<int, unordered_set<int>> AB;
  VI route(N, -1);

  rep(i, M) {
    int j, k;
    cin >> j >> k;
    j--;k--;
    AB[j].insert(k);
    AB[k].insert(j);
  }

  cout << "Yes" << endl;
  queue<pair<int, int>> que;
  que.emplace(0, -2);
  while(!que.empty()) {
    auto [v, p] = que.front();
    que.pop();
    if(route[v] != -1) continue;
    route[v] = p;
    for(auto to : AB[v]) {
      if(to==p) continue;
      if(route[to] != -1) continue;
      que.emplace(to, v);
    }
  }

  for(int i=1; i < N; i++) {
    cout<< route[i]+1 << endl;
  }

  return 0;
};

Measured memory_bytes: 33308