akhauriyash/Code-Regression huggingface dataset:
n = int(input())
given_a = list(map(int, input().split()))

# money = 1000
# kabu = 0

# a = []
# for kabuka in given_a:
#     if len(a) > 0 and a[-1] == kabuka:
#         continue
#     else:
#         a.append(kabuka)

# n = len(a)
# if n == 1:
#     print(money)
#     exit()

# for i in range(n):
#     if i == 0:
#         if a[i+1] < a[i]:
#             continue
#         else:
#             kabu += money // a[i]
#             money %= a[i]
#     elif i == n-1:
#         money += kabu * a[i]
#         kabu = 0
#     else:
#         if a[i-1] < a[i] and a[i] > a[i+1]:
#             money += kabu * a[i]
#             kabu = 0
#         if a[i-1] > a[i] and a[i] < a[i+1]:
#             kabu += money // a[i]
#             money %= a[i]
# print(money)

money = 1000
kabu = 0
a = []
for kabuka in given_a:
    if len(a) > 0 and a[-1] == kabuka:
        continue
    else:
        a.append(kabuka)

n = len(a)
if n ==1:
    print(money)
    exit()

for i in range(n):
    if i == 0:
        if a[i+1] < a[i]:
            continue
        else:
            kabu += money // a[i]
            money %= a[i]
    elif i == n-1: #最後の日のとき
        money += kabu * a[i]
        kabu = 0
    else:
        if a[i-1] < a[i] and a[i] > a[i+1]:
            money += kabu * a[i]
            kabu = 0
        if a[i-1] > a[i] and a[i] < a[i+1]:
            kabu += money // a[i]
            money %= a[i]

print(money)



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

int main(void){
  string s, temp;
  cin >> s;
  temp = s;
  temp.pop_back();
  temp.erase(0,0);
  int n;
  n = temp.size()-1;
  cout << s[0] << n << s[n+1] << endl;

  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i:=0;i<n;i++{
		fmt.Scan(&a[i])
	}
	fmt.Println(sub(a, 0))
}

func sub(ints []int, res int) int {
	if isAllEven(ints) {
		for i:=0;i<len(ints);i++ {
			ints[i] /= 2
		}
		return sub(ints, res + 1)
	}
	return res
}

func isAllEven(ints []int) bool {
	for i := 0; i < len(ints); i++{
		if ints[i] % 2 != 0 {
			return false
		}
	}
	return true
}


Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
 
int main(int argc, char const* argv[])
{
    unsigned n;
    std::cin >> n;
    while (n!=0) {
        double sum{};
        double sigma{};
        double m{};
        std::vector<int> ss;
        for (int i = 0; i < n; i++) {
            int s;
            std::cin >> s;
            ss.push_back(s);
        }
        sum = 0.;
        for (auto&& s : ss) {
            sum += s;
        }
        m = sum / n;
        for (auto&& s : ss) {
            sigma += (s - m) * (s - m);
        }
        std::cout << std::fixed <<std::setprecision(8) << std::sqrt(sigma/n) << std::endl;
        std::cin >> n;
    }
 
    return 0;
}

Measured memory_bytes: 3284
// AOJ 0056: Goldbach's Conjecture
// 2017.10.28 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

#define MAX  50000
#define SQRT 223     // sqrt(MAX)

char table[MAX+1], *pmax = table+MAX;
int combi[MAX+MAX] = {0,0,0,0,1,0};
int prime[5200], sz;

int main()
{
	int i, j;
	char buf[10];
	char *p, *p2;
	int *q;

	for (p = table+3, i = 3; i <= SQRT; p += 2, i += 2) if (!*p) {
		for (p2 = p + i; p2 <= pmax; p2 += i) *p2 = 1;
	}

	for (p = table+3, q = prime, i = 3; i <= MAX; p += 2, i += 2)
		if (!*p) *q++ = i;
	sz = q - prime;

	for (i = 0; i < sz; i++) for (j = i; j < sz; j++)
		combi[prime[i] + prime[j]]++;

	while (fgets(buf, 8, stdin) && *buf != '0') {
		i = atoi(buf);
		if (i & 1) { putchar('1'-table[i-2]), putchar('\n'); }
		else printf("%d\n", combi[i]);
	}
	return 0;
}

Measured memory_bytes: 2112
defmodule Main do
  def main do
    [n, _m, x] =
      IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)

    list =
      Enum.reduce(1..n, [], fn _, acc ->
        [IO.gets("") |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)] ++
          acc
      end)

    Enum.reduce(1..n, [], fn i, acc ->
      combination(list, i) ++ acc
    end)
    |> Enum.filter(&pass?(&1, x))
    |> Enum.map(&bill/1)
    |> Enum.min(fn -> -1 end)
    |> IO.puts()
  end

  defp pass?(list_of_lists, x) do
    List.zip(list_of_lists)
    |> tl()
    |> Enum.map(&(Tuple.to_list(&1) |> Enum.sum()))
    |> Enum.all?(&(&1 >= x))
  end

  defp bill(list_of_lists) do
    List.zip(list_of_lists) |> hd() |> Tuple.to_list() |> Enum.sum()
  end

  defp combination(_, 0), do: [[]]
  defp combination([], _), do: []

  defp combination([x | xs], n) do
    for(y <- combination(xs, n - 1), do: [x | y]) ++ combination(xs, n)
  end
end

Measured memory_bytes: 32760
s = input()
p = input()
s_len = len(s)
p_len = len(p)
for i in range(s_len):
    for j in range(p_len):
        same = True
        if s[(i+j)%s_len] != p[j]:
            same = False
            break
    if same:
        print("Yes")
        exit(0)
print("No")



Measured memory_bytes: 5560
#include<iostream>
using namespace std;
typedef long long ll;

/*
int main() {
    int T;
    ll A, B, C, D, E, F, G;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> A >> B >> C >> D;
        if (A < B || B > D) cout << "No" << endl;
        if (A > C) {
            G = A - C;
            A -= B * (G / B);
        }
        if (D == B && A >= B) cout << "Yes" << endl;
        else {
            if (D == B) cout << "No" << endl;
            else {
                E = A - B * (A / B);
                F = ((C - E + D - B - 1) / (D - B)) * (D - B) + E;
                if (F == C) F += D - B;
                if (F < B) cout << "No" << endl;
                else cout << "Yes" << endl;
            }
        }
    }
    return 0;
}
*/

ll _gcd(ll a, ll b) {
    if (b == 0) return a;
    else return _gcd(b, a % b);
}

int main() {
    int T;
    ll A, B, C, D;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> A >> B >> C >> D;
        if (A < B || B > D) cout << "No" << endl;
        else if (B <= C) cout << "Yes" << endl;
        else {
            ll g = _gcd(D, B);
            ll max_mod = B - g + (A % g);
            if (max_mod > C) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>


using namespace std;
int main()
{
    int N, M;
    cin>>N>>M;
    int L_prev=0;
    int R_prev=1e5+1;
    for(int i=0; i<M; i++){
        int L, R;
        cin >> L >> R;
        L_prev = max(L, L_prev);
        R_prev = min(R, R_prev);
        if(L_prev>R_prev){
            cout<<0<<endl;
            return 0;
        }
    }
    cout<<R_prev-L_prev+1<<endl;

    return 0;
}

Measured memory_bytes: 256
def main():
    from collections import deque
    h,w = map(int,input().split())
    l = [list(input()) for i in range(h)]

    dp = [[[-1]*(h*w) for i in range(w)] for i in range(h)]
    q = deque([])
    if l[0][0] == ".":
        q.append((0,0,0,"."))
    else:
        q.append((0,0,1,"#"))
    dx = [0,1]
    dy = [1,0]
    while q:
        
        bx,by,num,bef = q.popleft()
        for j in range(2):
            nx = bx+dx[j]
            ny = by+dy[j]
            if nx < h and ny < w:
                if bef == "." and l[nx][ny] == "#":
                    if dp[nx][ny][num+1] == -1:
                    
                        dp[nx][ny][num+1] = 1
                        q.append((nx,ny,num+1,l[nx][ny]))
                elif dp[nx][ny][num] == -1:
                    dp[nx][ny][num] = 1
                    q.append((nx,ny,num,l[nx][ny]))

    print(dp[-1][-1].index(1))
if __name__ == "__main__":
    main()



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

int main(){
	int m, f, r;
	while (1){
		cin >> m >> f >> r;
		if (m == -1 && f == -1 && r == -1)
			break;
		if (m == -1 || f == -1)
			cout << 'F' << endl;
		else if (m+f>=80)
			cout << 'A' << endl;
		else if (m + f >= 65)
			cout << 'B' << endl;
		else if (m+f>=50)
			cout << 'C' << endl;
		else if (m + f >= 30){
			if (r>=50)
				cout << 'C' << endl;
			else
				cout << 'D' << endl;
		}
		else
			cout << 'F' << endl;
	}
	return 0;
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> cnt( 13 );
	cnt[0] = 1;
	int ma = 0;
	for( int i = 0; i < N; i++ ) {
		int D;
		cin >> D;
		cnt[D]++;
		ma = max( ma, cnt[D] );
	}

	if( cnt[0] > 1 || cnt[12] > 1 || ma > 2 ) {
		cout << 0 << endl;
		return 0;
	}
	vector<int> f;
	vector<int> v;
	for( int i = 1; i < 12; i++ ) {
		if( cnt[i] == 1 ) v.push_back( i );
		else if( cnt[i] == 2 ) {
			f.push_back( i );
			f.push_back( 24 - i );
		}
	}
	f.push_back( 0 );
	if( cnt[12] ) f.push_back( 12 );
	int fmi = 24 + 1;
	for( int i = 0; i < f.size(); i++ ) {
		for( int j = i + 1; j < f.size(); j++ ) {
			int d = abs( f[i] - f[j] );
			d = min( d, 24 - d );
			fmi = min( fmi, d );
		}
	}
	int n = v.size();
	int ans = 0;
	for( int mask = 0; mask < 1 << n; mask++ ) {
		int mi = fmi;
		for( int i = 0; i < f.size(); i++ ) {
			for( int j = 0; j < n; j++ ) {
				int d1 = v[j];
				if( mask >> j & 1 ) d1 = 24 - d1;
				int d = abs( f[i] - d1 );
				d = min( d, 24 - d );
				mi = min( mi, d );
			}
		}
		for( int i = 0; i < n; i++ ) {
			int d1 = v[i];
			if( mask >> i & 1 ) d1 = 24 - d1;
			for( int j = i + 1; j < n; j++ ) {
				int d2 = v[j];
				if( mask >> j & 1 ) d2 = 24 - d2;
				int d = abs( d2 - d1 );
				d = min( d, 24 - d );
				mi = min( mi, d );
			}
		}
		ans = max( ans, mi );
	}

	cout << ans << endl;
}


Measured memory_bytes: 3612
#!/usr/bin/env python3
import sys
import itertools

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    result = 0
    for iter in itertools.combinations_with_replacement(range(1,M+1),N):
        l = sorted(list(iter))
        sum = 0
        for i in range(Q):
            if l[b[i]-1] - l[a[i]-1] == c[i]:
                sum += d[i]
        result = max(result,sum)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()


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

constexpr int MAX_N = 100100;
constexpr long long INF = 1e18;

int main() {
    int n;
    cin >> n;
    vector<long long> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    
    long long dp[MAX_N];
    fill(dp, dp + MAX_N, INF);
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    
    for (int i = 2; i < n; i++) {
        dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }
    
    cout << dp[n-1] << '\n';
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int n;

struct Edge{
  int from, to, cost;
  Edge(int from, int to, int cost) : from(from), to(to), cost(cost){}
};

vector<vector<int>> to;
vector<vector<int>> rev_to;
vector<bool> reach1; 
vector<bool> reach2; 

void dfs(int v){
  if(reach1[v])return;
  reach1[v] = true;
  for(auto nv : to[v])dfs(nv);
}

void dfs2(int v){
  if(reach2[v])return;
  reach2[v] = true;
  for(auto nv : rev_to[v])dfs2(nv);
}


int ng = 0;

vector<Edge> es;
vector<int> dist;
int cnt = 0;
void bellman_ford(int s){ 
  dist.assign(n, INF);
  dist[s] = 0;
  bool update = true;
  while(update){
    update = false;
    for(auto e : es){
      if(e.from == INF)continue;
      if(!reach1[e.from] || !reach2[e.from])continue;
      if(!reach1[e.to] || !reach2[e.to])continue;
      if(dist[e.from] + e.cost < dist[e.to]){
        update = true;
        dist[e.to] = dist[e.from] + e.cost;
      }
    }
    ++cnt;
    if(cnt > n){
      ng = 1;
      break;
    }
  }
}

int main(){
  int m, p;
  cin >> n >> m >> p;
  to.resize(n);
  rev_to.resize(n);
  for(int i = 0; i < m; ++i){
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    c -= p;
    c *= -1;
    es.push_back(Edge(a, b, c));
    to[a].push_back(b);
    rev_to[b].push_back(a);
  }

  reach1.assign(n, false);
  reach2.assign(n, false);
  dfs(0);
  dfs2(n - 1);
  bellman_ford(0);
  if(ng)cout << -1 << endl;
  else cout << max(0, -dist[n - 1]) << endl;
  return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
const ll INF = 1e9;

bool M[5001][5001];
int x[3001], y[3001];

int main() {
    int N;
    while(cin >> N, N) {
        for (int i = 0; i < N; i++) for (int k = 0; k < N; k++) M[k][i] = false;
        for (int i = 0; i < N; i++) {
            cin >> x[i] >> y[i];
            M[x[i]][y[i]] = true;
        }

        ll ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if (i == j) continue;
                if (x[i] > x[j]) continue;

                int dx = x[j] - x[i], dy = y[j] - y[i];
                int kx = x[j] - dy;
                int ky = y[j] + dx;
//                cout << x[i] << " " << y[i] << " ";
//                cout << x[j] << " " << y[j] << " ";
//                cout << kx << " " << ky << endl;
                if (kx < 0 || ky < 0 || kx > 5000 || ky > 5000) continue;
                if (M[kx][ky]) { // k
                    int lx = kx - dx;
                    int ly = ky - dy;
                    if (lx < 0 || ly < 0 || lx > 5000 || ly > 5000) continue;
                    if (M[lx][ly]) { // l
//                        cout << x[i] << " " << y[i] << endl;
//                        cout << x[j] << " " << y[j] << endl;
//                        cout << kx << " " << ky << endl;
//                        cout << lx << " " << ly << endl;
                        ll w = max(kx - x[i], ky - y[i]);
//                        cout << w << endl;
                        ll area = w * w - 2 * abs(dx) * abs(dy);
                        ans = max(ans, area);
                    }
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 24784
#include <bits/stdc++.h>
using namespace std;
string s;
long n,i;
int main() {
    cin >> s;
    n = 0;
    for(i = 0; i < 3; i++) if(s[i] == 'R') n++;
    if(n != 2) cout << n;
    else {
        if(s[1] == 'R') cout << 2;
        else cout << 1;
    }
    return 0;
}

Measured memory_bytes: 3636
#pragma GCC optimize("O3")
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdlib>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#include <iomanip>
#include<unordered_set>
constexpr auto INF = 9223372036854775807;
typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned long int ul;
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i+=1)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i-=1)
#define endl '\n'
#define N 1000000007 // prime modulo value 
#define all(x) x.begin(),x.end()
using namespace std;
inline int mex(unordered_set<int> st)
{
	int m = 0;
	while (st.find(m) != st.end())
	{
		m += 1;
	}
	return m;
}
inline int calculateGrundy(int n)
{
	if (n == 1)
		return 0;
	unordered_set<int> mexi;
	for (int i = 1; i <= sqrt(n); i += 1)
	{
		if (n % i == 0)
		{
			if (n / i != n)
				mexi.insert(calculateGrundy(n / i));
			mexi.insert(calculateGrundy(i));
		}
	}
	return mex(mexi);
}
inline ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
inline ll exponentiation(ll base, ll exp)
{
	ll t = 1;
	while (exp > 0)
	{

		
		if (exp % 2 != 0)
			t = (t * base) % N;

		base = (base * base) % N;
		exp /= 2;
	}
	return t % N;
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0),cin.tie(0);
	string s, t;
	cin >> s >> t;
	ll a, b;
	cin >> a >> b;
	string u;
	cin >> u;
	if (u == s)
	{
		a -= 1;
	}
	else if(u==t)
	{
		b -= 1;
	}
	cout << max((ll)0, a) << " " << max((ll)0, b);
	return 0;
}

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

namespace diverta_B
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] a = Console.ReadLine().Split(' ');
            var r = long.Parse(a[0]);
            var g = long.Parse(a[1]);
            var b = long.Parse(a[2]);
            var n = long.Parse(a[3]);
            var count = 0;
            for (long i = 0; i <= n; i = i + g)
            {
                for (long j = 0; j <= n-i; j = j + b)
                {
                    if ((n-i-j) % r == 0 )
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(Convert.ToString(count));
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define per(a, b, c) for(int a = (b); a >= (c); -- a)
using namespace std;
template <class T> void rd(T &x){
  x = 0; int f = 1; char ch = getchar();
  while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  x *= f;
}

const int maxn = 105;
int n, ans;
char s[maxn];
int c[3];

int main(){
  rd(n);
  rep(i, 1, n){
	scanf("%s", s + 1);
	int len = strlen(s + 1);
	rep(j, 1, len - 1) if(s[j] == 'A' && s[j + 1] == 'B') ans ++;
	if(s[1] == 'B' && s[len] == 'A') c[2] ++;
	else if(s[1] == 'B') c[1] ++;
	else if(s[len] == 'A') c[0] ++;
  }
  if(!c[2]){
	ans += min(c[0], c[1]);
  }
  else{
	ans += c[2] - 1;
	if(c[0]) c[0] --, ans ++;
	if(c[1]) c[1] --, ans ++;
	ans += min(c[0], c[1]);
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
var s:String = readLine()!
let q:Int = Int(readLine()!)!
var c1:Int = 1
var s1:String = ""
var s2:String = ""
for _ in 0..<q {
  let query = readLine()!
  if query.contains(" ") {
    let l = query.split(separator:" ")
    let c2 = (l[1] == "1" ? 1:-1)
    if c1*c2 == 1 {
      s1 += l[2]
    } else {
      s2 += l[2]
    }
  } else {
    c1 = -c1
  }
}
s = String(s1.reversed()) + s + s2
print(c1 == 1 ? s:String(s.reversed()))

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

int main() {
	int w, h;
	do {
		cin >> h >> w;
		if (h == 0 && w == 0)
			break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	} while (true);
	return 0;
}


Measured memory_bytes: 3104
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }

int main() {
    int n; cin >> n;
    vector<int> number;
    number.push_back(1);
    for(int i=6; i<=n; i *= 6) number.push_back(i);
    for(int i=9; i<=n; i *= 9) number.push_back(i);
    sort(all(number));

    vector<int> dp(n+1, INF);
    dp[0] = 0;
    for(int i=0; i<=n; i++){
        rep(j, number.size()){
            if(i + number[j] > n) break;
            chmin(dp[i+number[j]], dp[i] + 1);
        }
    }
    cout << dp[n] << ln;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
double dp[301][301][301];

double solve(int x,int y,int z,int &n) //expected no.of operations
{
    if(x<0 || y<0 || z<0)  // to stop infinite recursion
        return 0;

    if(x==0 && y==0 && z==0)
        return 0;

    if(dp[x][y][z]>-0.9)
        return dp[x][y][z];

        double exp = n + x*solve(x-1,y,z,n) + y*solve(x+1,y-1,z,n) + z*solve(x,y+1,z-1,n);

        return dp[x][y][z] = exp/(x+y+z);

}

int main()
{
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
    int n,x;
    cin>>n;
    memset(dp,-1,sizeof dp);
    int one=0,two=0,three=0;
    for(int i=1;i<=n;i++)
    {

        cin>>x;

        if(x==1)
            one++;

        else if(x==2)
            two++;

        else
            three++;
    }

    cout<<fixed<<setprecision(10)<<solve(one,two,three,n)<<"\n";
    return 0;
}


Measured memory_bytes: 213376
#include <stdio.h>
#include <string.h>

  int i,j,k,l,m;
  int n,e,s,w,un,up;
  int a[7];
int t;


void input() {
 for(i=0;i<6;i++){
  
    scanf("%d",&a[i+1]);
  
  }
}

 void N() {
   t = a[1];
   a[1] = a[2];
   a[2] = a[6];
   a[6] = a[5];
   a[5] = t;
 }

 void S() {
   t = a[1];
   a[1] = a[5];
   a[5] = a[6];
   a[6] = a[2];
   a[2] = t;
}

 void E() {
   t = a[1];
   a[1] = a[4];
   a[4] = a[6];
   a[6] = a[3];
   a[3] = t;
 }

 void W() {
   t = a[1];
   a[1] = a[3];
   a[3] = a[6];
   a[6] = a[4];
   a[4] = t;
 }

int main() {

  input();
  //  strlen(?) 文字の長さ(数)を表示
 char str[110];  
 scanf("%s",str);

 for(i=0;i<strlen(str);i++) {

   if(str[i] == 'N') {
     N();
   } else if(str[i] == 'S') {
     S();
   } else if(str[i] == 'W') {
     W();
   } else if(str[i] == 'E') {
     E();
   }
 }

 printf("%d\n",a[1]);

 return 0;
}


Measured memory_bytes: 2148
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		stdin.nextLine();
		for (int i = 0; i < n; i++) {
			String train = stdin.nextLine();
			System.out.println(calculatePatterns(train));
		}
		System.exit(0);
	}
	public static int calculatePatterns(String train) {
		Set<String> patterns = new HashSet<String>();
		for (int i = 0; i < train.length() - 1; i++) {
			StringBuffer subtrainf = new StringBuffer(train.substring(0, i + 1));
			StringBuffer subtrainb = new StringBuffer(train.substring(i + 1, train.length()));

			patterns.add(subtrainf.toString() + subtrainb.toString());
			patterns.add(subtrainb.toString() + subtrainf.toString());
			subtrainf.reverse();
			patterns.add(subtrainf.toString() + subtrainb.toString());
			patterns.add(subtrainb.toString() + subtrainf.toString());
			subtrainb.reverse();
			patterns.add(subtrainf.toString() + subtrainb.toString());
			patterns.add(subtrainb.toString() + subtrainf.toString());
			subtrainf.reverse();
			patterns.add(subtrainf.toString() + subtrainb.toString());
			patterns.add(subtrainb.toString() + subtrainf.toString());
		}
		return patterns.size();
	}
}

Measured memory_bytes: 54792
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 3000;
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int f[MAXN + 5][MAXN + 5], b[MAXN + 5][MAXN + 5];
char s[MAXN + 5], t[MAXN + 5];
inline void prt_LCS(const int &x, const int &y) {
	if (x == 0 || y == 0) {
		return;
	}
	if (b[x][y] ^ 3) {
		prt_LCS(x - ((b[x][y] & 2) >> 1), y - (b[x][y] & 1));
	}
	else {
		prt_LCS(x - 1, y - 1);
		putchar(s[x]);
	}
}
int main() {
	int n, m;
	scanf("%s%s", s + 1, t + 1);
	n = strlen(s + 1);
	m = strlen(t + 1);
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			if (s[i] == t[j]) {
				f[i][j] = f[i - 1][j - 1] + 1;
				b[i][j] = 3;
			}
			else if (f[i - 1][j] >= f[i][j - 1]) {
				f[i][j] = f[i - 1][j];
				b[i][j] = 2;
			}
			else {
				f[i][j] = f[i][j - 1];
				b[i][j] = 1;
			}
		}
	}
	prt_LCS(n, m);
	return 0;
}

Measured memory_bytes: 70784
#include <iostream>


using namespace std;


void eating_symbols_easy()
{
  string s;
  cin >> s;

  int cnt = 0;
  for (int i = 0; i < 4; ++i)
  {
    if (s[i] == '+') ++cnt;
    else --cnt;
  }
  cout << cnt << "\n";
}

int main()
{
  eating_symbols_easy();
}

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

int f = -1;
int findMax(vector <int> x){
    int mx = 0, j = -1;
    for(int i=0; i<3; ++i){
        if(f != i){
            
            if(mx < x[i]){
                mx = x[i];
                j = i;
            }
        }
    }
    f = j;
    return mx;
}

int main(){
    vector <int> dp(3, 0);
    int n;  //days
    cin>>n;
    
    for(int i=0; i<n; ++i){
        vector <int> x(3);    //swim, catch, hw
        vector <int> temp(3, 0);

        cin>>x[0]>>x[1]>>x[2];   //same act cant be done >= 2 consec. days
        
        for(int j=0; j<3; ++j){
            for(int k=0; k<3; ++k){
                if(j != k){
                    temp[k] = max(temp[k], x[k] + dp[j]);
                }
            }
        }
        dp = temp;
    }
    cout<<max({dp[0], dp[1], dp[2]})<<endl;
    //to find - max possible total points

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  int i,j;
  int x;
  cin>>x;
  for(i=1;i<=100000;i++){
    int d=x-i*100;
    if(d>=0&&d<=5*i){
      cout<<1<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <set>
#include <stdio.h>
using namespace std;
int main()
{
  int i,M,N,f=1;
  set<string> U;
  char str[15];
  std::cin >> N;
  for (i=0;i<N;i++){
    std::cin >> str;
    U.insert(str);
  }
  std::cin >> M;
  for (i=0;i<M;i++){
    std::cin >> str;
    set<string>::iterator t=U.find(str);
      if (t==U.end())
        printf("Unknown %s\n",str);
      else{
        if (f==1){
          printf("Opened by %s\n",str);
          f=0;
        }else{
          printf("Closed by %s\n",str);
          f=1;
        }
      }
  }

  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define endl '\n'


signed main()
{
     int a, b, c;
     cin >> a >> b >> c;
     int k;
     cin >> k;
     if (k % 2 == 0) {
          cout << a-  b;
     } else {
          cout << b - a;
     }
     return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>

int main()
{
    int n;
    std::cin >> n;
    int nums[n];
    bool first = true;
    int sum = 0;
    for(int i = 0; i < n; i++){
        std::cin >> nums[i];
    }
    
    for(int i = 0; i < n; i++){
        if(!(nums[i] % 4)){
            sum += 2;
        }else if(!(nums[i] % 2)){
            if(first){
                sum--;
                first = false;
            }
            sum += 1;
        }
    }
    
    if(sum >= n - 1){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    
    return 0;
}


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

int main(){
    int N;  cin >> N;
    vector<ll> A(N+1, 0);
    map<ll, ll> mp;
    for(int i=1; i<=N; i++){
        cin >> A[i];
        A[i] += A[i-1];
    }
    for(int i=0; i<=N; i++){
        mp[A[i]]++;
    }

    ll ans = 0;
    for(auto p : mp){
        ans += p.second*(p.second-1)/2;
    }
    cout << ans << endl;
}   

Measured memory_bytes: 14336
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

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

    i64 a, b, c, d;
    read(a, b, c, d);
    if (a != c) {
        print(1);
    } else {
        print(0);
    }

    return 0;
}


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

int dfs(int node, vector<vector<int>> &g, vector<pair<int, int>> &ans) {
    vector<int> unpaired;

    for(auto v : g[node]) {
        int rem = dfs(v, g, ans);
        if(rem >= 0) {
            unpaired.push_back(rem);
        }
    }   

    int us_par = g[node].size();
    if(us_par % 2 == 0) {
        unpaired.push_back(node);
    }

    while(unpaired.size() >= 2) {
        auto a = unpaired.back();
        unpaired.pop_back();
        auto b = unpaired.back();
        unpaired.pop_back();
        ans.push_back(make_pair(a, b));
    }

    if(unpaired.empty())
        return -1;
    return unpaired.back();
}

vector<pair<int, int>> getPairs(vector<int> f) {
    int n = f.size();
    vector<vector<int>> g(n, vector<int> ());
    int root = 0;

    for(int i = 0; i < n; ++i) {
        if(f[i] < 0) {
            root = i;
            continue;
        }
        g[f[i]].push_back(i);
    }
    
    vector<pair<int, int>> ans;
    dfs(root, g, ans);

    return ans;
}

int main() {
   //ifstream cin("f.in");

   int n; cin >> n;

   vector<vector<int>> f(2, vector<int> (n, 0));
   vector<vector<int>> par(2, vector<int> (n, 0));

   for(int t = 0; t < 2; ++t) {
        for(int i = 0; i < n; ++i) {
            cin >> f[t][i];
            f[t][i] -= 1;
            if(f[t][i] >= 0) {
                par[t][f[t][i]] ^= 1;
            }
        }
   }

   for(int i = 0; i < n; ++i) {
        if(par[0][i] != par[1][i]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
   }
    
   vector<vector<int>> g(n);

   for(int t = 0; t < 2; ++t) {
        vector<pair<int, int>> matching = getPairs(f[t]);
        for(auto pr : matching) {
            g[pr.first].push_back(pr.second);
            g[pr.second].push_back(pr.first);
        }
   }

   vector<int> seen(n, 0);

   for(int i = 0; i < n; ++i) {
        if(seen[i])
            continue;
        if(par[0][i] == 1)
            continue;

        seen[i] = -1;
        queue<int> q;
        q.push(i);

        while(not q.empty()) {
            int node = q.front();
            q.pop();

            for(auto v : g[node]) {
                if(seen[v])
                    continue;
                seen[v] = (-1) * seen[node];
                q.push(v);
            }
        }
   }
   
   cout << "POSSIBLE\n";

   for(int i = 0; i < n; ++i)
       cout << seen[i] << " ";
}

Measured memory_bytes: 15576
#include <bits/stdc++.h>
#define read(arr,n)	for(int i=0;i<n;i++) cin>>arr[i];
#define print(arr,n) for(int i=0;i<n;i++) cout << arr[i]<<' ';cout << endl;
typedef int int32;
#define int ll

using namespace std;

typedef long long ll;

void solve() {
	ll n;
	cin >> n;
	int cost[100005] = {};
	int dp[100005] = {};
	dp[n] = 0;

	for (int i =1; i <= n; i++)	cin >> cost[i];
	
	dp[n-1] = abs(cost[n]-cost[n-1]) + dp[n];
	
	for (int i = n-2; i >= 1; i--) {
		dp[i] = min(abs(cost[i+1]-cost[i])+dp[i+1], 
				abs(cost[i+2]-cost[i])+dp[i+2]);
	}
	
	cout << dp[1] << endl;	
}

int32 main() {
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();	
	}
	return 0;
}


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

int main()
{
    vector<vector<int>> bingo(3, vector<int>(3));
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> bingo.at(i).at(j);
        }
    }

    int N;
    cin >> N;
    vector<int> selection(N);
    for (int i = 0; i < N; i++)
    {
        cin >> selection.at(i);
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                if (selection.at(i) == bingo.at(j).at(k))
                    bingo.at(j).at(k) = -1;
            }
        }
    }

    // for (int i = 0; i < 3; i++)
    // {
    //     for (int j = 0; j < 3; j++)
    //     {
    //         cout << bingo.at(i).at(j) << " ";
    //     }
    //     cout << endl;
    // }

    if ((bingo.at(0).at(0) == -1 && bingo.at(0).at(1) == -1 && bingo.at(0).at(2) == -1) ||
        (bingo.at(1).at(0) == -1 && bingo.at(1).at(1) == -1 && bingo.at(1).at(2) == -1) ||
        (bingo.at(2).at(0) == -1 && bingo.at(2).at(1) == -1 && bingo.at(2).at(2) == -1) ||
        (bingo.at(0).at(0) == -1 && bingo.at(1).at(0) == -1 && bingo.at(2).at(0) == -1) ||
        (bingo.at(0).at(1) == -1 && bingo.at(1).at(1) == -1 && bingo.at(2).at(1) == -1) ||
        (bingo.at(0).at(2) == -1 && bingo.at(1).at(2) == -1 && bingo.at(2).at(2) == -1) ||
        (bingo.at(0).at(0) == -1 && bingo.at(1).at(1) == -1 && bingo.at(2).at(2) == -1) ||
        (bingo.at(0).at(2) == -1 && bingo.at(1).at(1) == -1 && bingo.at(2).at(0) == -1))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
/**
 * Author : Deep Raval
 * There are no two words in the English language more harmful than "good job".
 * 1729 0_0
**/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <numeric>
using namespace std;
using ll = long long;
#define endl '\n'
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) 
{
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define FAST_IO ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
#define bp(x) __builtin_popcount(x)
#define zf(x) __builtin_clz(x)
#define zl(x) __builtin_ctz(x)
#define par(x) __bultin_parity(x)
#define all(x) (x).begin(), (x).end()
/* **************************************************************************************** */

void test_case()
{
    ll x, k, d;
    cin >> x >> k >> d;


    if(x == 0)
    {
        if(k & 1)
            cout << min(abs(x + d), abs(x- d)) << endl;
        else 
            cout << '0' << endl;
        return;
    }
    ll ans = min(abs(x + k * d), abs(x - k * d));

    ll need = ceil(abs(x) / double(d));

    if(k <= need)
    {
        if(x < 0)
            x += k * d;
        else 
            x -= k * d;
        ans = min(ans, abs(x));
    }
    else 
    {
        if(x < 0)
            x += need * d;
        else 
            x -= need * d;

        k -= need;

        if(k & 1)
            ans = min({ans, abs(x + d), abs(x - d)});
        else 
            ans = min(ans, abs(x));
    }


    cout << ans << endl;
	return ;
}
int main()
{
	FAST_IO
    int t = 1;
    //cin >> t;
    while(t--)
        test_case();
	return 0;
}

Measured memory_bytes: 3728
mod = 10 ** 9 + 7

n = int(input())
mp = {}
memo = [0 for i in range(n+1)]
# 2~Nの素因数の数を数えている
for i in range(2, n+1):
    x = i
    for j in range(2, x+1):
        while x % j == 0:
            x /= j
            if memo[j] == 0:
                mp[j] = 0
                memo[j] = 1
            mp[j] += 1

ans = 1
for v in mp.values():
    ans = ans * (v+1)

print(ans % mod)

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

const int N=2010;
int A[N<<2],B[N<<2];
int sa[N<<2],sb[N<<2];
int nxl[N<<2],nxr[N<<2];
char ss1[N],ss2[N];
int len,ans=INT_MAX;
int R[N<<2];

void xi_jin_ping_is_good()
{
    nxl[0]=-1;nxr[3*len-1]=3*len;
    for(int i=1;i<3*len;i++) nxl[i]=B[i]?i:nxl[i-1];
    for(int i=3*len-2;i>=0;i--) nxr[i]=B[i]?i:nxr[i+1];
    for(int k=0;k<len;k++)
    {
        int cnt=0,dafa=INT_MAX,mxr=0;
        memset(R,0,sizeof(R));
        for(int i=len;i<2*len;i++)
        {
            if(A[i]==B[i+k]) continue;
            cnt++;R[i-nxl[i]]=max(R[i-nxl[i]],nxr[i]-i-k);
        }
        if(cnt==0){ans=min(ans,k);continue;}
        for(int i=len-1;i>=0;i--)
            dafa=min(dafa,mxr+i),mxr=max(mxr,R[i]);
        ans=min(ans,cnt+k+dafa*2);
    }
}

int main()
{
    scanf("%s",ss1);len=strlen(ss1);scanf("%s",ss2);
    for(int i=0;i<len;i++) A[i]=A[i+len]=A[i+2*len]=ss1[i]-'0';
    for(int i=0;i<len;i++) B[i]=B[i+len]=B[i+2*len]=ss2[i]-'0';
    sa[0]=A[0];sb[0]=B[0];
    for(int i=1;i<3*len;i++) sa[i]=sa[i-1]+A[i],sb[i]=sb[i-1]+B[i];
    if(!sb[len-1]&&sa[len-1]) return puts("-1"),0;
    xi_jin_ping_is_good();
    reverse(A,A+3*len);
    reverse(B,B+3*len);
    xi_jin_ping_is_good();
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <cctype>
#include<math.h>
using namespace std;
int main() {
	int n, w[100], m = 10000000, t = 0, tt = 0;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> w[i];
		t = t + w[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i + 1; ++j) {
			tt = tt + w[j];
			
		}

		m = min(abs((t - tt) - tt), m);
		tt = 0;
	}
	cout << m << endl;
}

Measured memory_bytes: 256
# 2020/06/21
# AtCoder Beginner Contest 171 - C

# Input
n = int(input())

# Calc
wkval = n

str = ''
while(wkval > 0):
    div = wkval // 26
    rem = wkval % 26
    if rem == 0:
        str = 'z' + str
        div = (wkval - 1) // 26
    else:
        str = chr(96 + rem) + str
    wkval = div

# Output
print(str)


Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
vector <int> num;
vector <int> cmp;
vector <char> erg2;
int main () {
	bool erg=true;
string s;
int cmp;
cin>>s;
cmp=s.size();
for(int i=0;i<s.size();i++){
	if(s[i]!=s[cmp-1-i]){
		erg=false;
	}
}
if(erg==false){
	cout<<"No";
	return 0;
}
cmp--;
cmp/=2;
for(int i=0;i<cmp;i++){
	if(s[i]!=s[cmp-1-i]){
		erg=false;
	}
}
if(erg==false){
	cout<<"No";
}
else{
	cout<<"Yes";
}

   return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> H(n);
    rep(i,n) cin >> H.at(i);
    int MAX = H.at(0);
    bool flag = true;
    for (int i = 1; i < n; ++i) {
        if (MAX < H.at(i)) MAX = H.at(i);
        else if (MAX - H.at(i) > 1) flag = false;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
 
int get()
{
    char c;
    while (!isdigit(c=getchar()));
    int k=c-'0';
    for (; isdigit(c=getchar()); k=k*10+c-'0');
    return k;
}
 
using namespace std;
const int N=3010,mod=1e9+7;
char s[N];
int n,m,ans,fac[N],ifac[N],l[N],r[N],lb[N],rb[N],f[2][N],a[N];

int inv(int x)
{
    return x>1? 1ll*(mod-mod/x)*inv(mod%x)%mod:1;
}

int c(int n,int m)
{
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
 
int main()
{
    n=get(),m=get();
    fac[0]=1;
    rep(i,1,n)
        fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=inv(fac[n]);
    repd(i,n,1)
        ifac[i-1]=1ll*ifac[i]*i%mod;
    scanf("%s",s+1);
    rep(i,1,n)
        a[i]=a[i-1]+s[i]-48;
    int t=0;
    rep(i,1,m)
    {
        int x=get(),y=get();
        if (x==l[t])
            r[t]=max(r[t],y);
        else if (y>r[t])
            ++t,l[t]=x,r[t]=y;
    }
    m=t,l[m+1]=n+1,f[0][0]=1;
    rep(i,1,m)
    {
        static int *f=::f[0],*g=::f[1];
        swap(f,g);
        int w=a[r[i]]-a[max(l[i]-1,r[i-1])];
        int s=min(r[i],l[i+1]-1)-l[i]+1;
        int mx=r[i]-l[i]+1-s;
        lb[i]=max(0,lb[i-1]+w-s),rb[i]=min(mx,rb[i-1]+w);
        rep(j,lb[i],rb[i])
            rep(k,max(j-w,lb[i-1]),min(s+j-w,rb[i-1]))
                f[j]=(f[j]+1ll*g[k]*c(s,k+w-j))%mod;
        memset(g+lb[i-1],0,sizeof(int)*(rb[i-1]-lb[i-1]+1));
    }
    rep(i,lb[m],rb[m])
        ans=(ans+f[m&1][i])%mod;
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;

string s;
ll ans;
int a[N], ps[N];

void solve() {
    cin >> s;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == 'B') a[i + 1] = 1;
        else a[i + 1] = 0;
    }
    for(int i = 1; i <= s.size(); i++) {
        ps[i] = ps[i - 1] + a[i];
    }
    ans = 0;
    for(int i = 1; i <= s.size(); i++) {
        if(!a[i]) ans += ps[i];
    }
    cout << ans << "\n";
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();

}

Measured memory_bytes: 5344
n = int(input())
rooms = [[[0 for r in range(10)] for f in range(3)] for b in range(4)] 

for i in range(n):
  b, f, r, v = map(int,input().split())
  rooms[b-1][f-1][r-1] += v
for b in range(4):
  for f in rooms[b]:
    print('',*f)    
  if b != 3:
    print('#' *20)


Measured memory_bytes: 5628
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;

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

int main()
{
  string str_s, str_t; cin >> str_s >> str_t;
  int count = 0;
  REP(i, 3){
    if(str_s[i] == str_t[i]){count++;}
  }
  cout << count << endl;
  return 0;
}

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

using namespace std;

const int maxn = 1e5 + 10;
int n,a[maxn],dp[maxn];

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


Measured memory_bytes: 1024
#include <iostream>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>

#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(int x=from;x<to;x++)

using namespace std;


int main(void){

int n;


	while(cin >> n ){
		if(n==0 || cin.eof()) break;
		vector<int> nb(n,0);
		rep(i,n) cin >> nb[i];
		vector<int> sv(n,0);
		int cc=0;
		while(1){
			rep(i,n) sv[i]=0;
			rep(i,n) rep(j,n) if( nb[i]==nb[j]) sv[i]++;
			bool bksw=true;
			rep(i,n) if(nb[i]!=sv[i]) {bksw=false; break;}
			if(bksw) break;
			swap(sv,nb);
			cc++;
//			rep(i,n) printf("%d ",nb[i]); printf(" ::%d\n",cc);
		}
		cout << cc <<endl;
		rep(i,n) cout << nb[i] << (i<n-1? " ": "\n");
	}
	return 0;
}

Measured memory_bytes: 1192
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int count = 1;
        int i = 0;
        while (b > count) {
            count--;
            count += a;
            i++;
        }
        System.out.println(i);
    }
}


Measured memory_bytes: 21844
#include<iostream>
using namespace std;
int main()
{
  int a ,b,c,d,m1,m2;
  cin >> a>>b>>c>>d;
  m1=a*b;
  m2=c*d;
  if (m1>=m2)cout <<m1;
    else cout << m2;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int H,M,i,j;
	scanf("%d %d",&H,&M);
	while(1)
	{
	 if(H == 0 && M == 0)
	 {
		 break;
	 }
	 for(i = 0;i < H;i++)
	 {
		 for(j = 0;j < M;j++)
		 {
			 printf("#");
		 }
		 printf("\n");
	 }
	 printf("\n");
	 scanf("%d %d",&H,&M);
	}
	return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007LL;

int N, K;
vector<int> G[100005];
ll ret;

ll kai[100005];

void init(){
  kai[0] = 1;
  ll b = 1;
  REP(i,1,100005){
    b *= i;
    b %= MOD;
    kai[i] = b;
  }
}
ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d = a;
  if(b!=0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }else{
    x = 1; y = 0;
  }
  return d;
}

ll mod_inverse(ll a, ll m){
  ll x, y;
  extgcd(a, m, x, y);
  return (m+x%m)%m;
}
ll mod_perm(ll n, ll k, ll m){
   if(n<0) return 0;
  if(n-k<0) return 0;
  if(k == 0) return 1;
  return (kai[n] * mod_inverse(kai[n-k], MOD))%MOD;
}

void dfs(int v, int p){
  ll M = 1;
  if(p!=-1) M++;
  //cout << v << " " <<  mod_perm(K-M, G[v].size() - ((p==-1)?0:1), MOD) << endl;
  ret *= mod_perm(K-M, G[v].size() - ((p==-1)?0:1), MOD);
  ret %= MOD;
  rep(i,G[v].size()){
    if(G[v][i] == p) continue;
    dfs(G[v][i], v);
  }
}


int main(){
  init();
  cin >> N >> K;
  rep(i,N-1){
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  int mx = 0;
  int mx_i = 0;
  rep(i,N){
    if(mx < G[i].size()){
      mx = G[i].size();
      mx_i = i;
    }
  }

  if(mx+1 > K){
    cout << 0 << endl;
    return 0;
  }

  ret = 1;
  dfs(mx_i, -1);
  ret *= K;
  ret %= MOD;
  
  cout << ret << endl;
  
  return 0;
}


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

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

  vector<int> vec(N);
  long long sum = 0;
  for(int i = 0;i < N;i++) {
    cin >> vec.at(i);
    sum += vec.at(i);
  }

  long long x = 0,y = sum,ans = 10000000000;
  for(int i = 0;i < N - 1;i++) {
    x += vec.at(i);
    y -= vec.at(i);
    ans = min(ans,abs(x - y));
  }

  cout << ans << endl;

}

Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int n,q;

    int a[100001];

    cin>>n;

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

    sort(a,a+n);

    cin>>q;

    int cnt=0,b;
    for(int i=0;i<q;i++)
    {
        cin>>b;

        if(*lower_bound(a,a+n,b)==b)
        {
            cnt++;
        }
    }

    cout<<cnt<<endl;

    return 0;
}




Measured memory_bytes: 3452
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >>N;
    vector<int>vec(3*N);
    for(int i=0;i<3*N;i++){
        cin>>vec.at(i);
    }
    long long count=0;
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    for(int i=1;i<2*N+1;i+=2){
        count+=vec.at(i);
    }
    cout <<count<<endl;

}

Measured memory_bytes: 4540
#include<cstdio>
int N,K,c[10];
int f(int x){
    while(x){
        if(c[x%10])return 1;
        x/=10;
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0,x;i<K;i++){
        scanf("%d",&x);
        c[x]=1;
    }
    for(int x=N;;x++){
        if(f(x))continue;
        return !printf("%d\n",x);
    }
}

Measured memory_bytes: 128