akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
typedef pair<int, int> pii;
struct segtree{
	struct node{
		int cnt, sum;
		node *ch[2];
	}pl[20*MAXN + 5], *NIL, *ncnt;
	segtree(){NIL = ncnt = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL;}
	node *add(node *pre, int l, int r, int pos, int del) {
		node *nw = (++ncnt); (*nw) = (*pre);
		if( l == r ) {
			nw->cnt++, nw->sum += del;
			return nw;
		}
		int mid = (l + r) >> 1;
		if( pos <= mid ) nw->ch[0] = add(pre->ch[0], l, mid, pos, del);
		else nw->ch[1] = add(pre->ch[1], mid + 1, r, pos, del);
		return nw;
	}
	pii query(node *nw, int l, int r, int pos) {
		if( l == r )
			return make_pair(nw->cnt, nw->sum);
		int mid = (l + r) >> 1;
		if( pos <= mid ) return query(nw->ch[0], l, mid, pos);
		else return query(nw->ch[1], mid + 1, r, pos);
	}
}T;
segtree::node *rt[MAXN + 5];
struct edge{
	int dis, clr, to;
	edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v, int c, int d) {
	edge *p = (++ecnt);
	p->to = v, p->clr = c, p->dis = d;
	p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->clr = c, p->dis = d;
	p->nxt = adj[v], adj[v] = p;
}
int N, Q;
int fa[20][MAXN + 5], dep[MAXN + 5];
int dis[MAXN + 5];
void dfs(int x, int f) {
	fa[0][x] = f;
	for(int i=1;i<20;i++)
		fa[i][x] = fa[i-1][fa[i-1][x]];
	dep[x] = dep[f] + 1;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		rt[p->to] = T.add(rt[x], 1, N-1, p->clr, p->dis);
		dis[p->to] = dis[x] + p->dis;
		dfs(p->to, x);
	}
}
int lca(int u, int v) {
	if( dep[u] < dep[v] ) swap(u, v);
	for(int i=19;i>=0;i--)
		if( dep[fa[i][u]] >= dep[v] )
			u = fa[i][u];
	if( u == v ) return u;
	for(int i=19;i>=0;i--)
		if( fa[i][u] != fa[i][v] )
			u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}
int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<N;i++) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
		addedge(a, b, c, d);
	}
	rt[1] = T.NIL, dfs(1, 0);
	for(int i=1;i<=Q;i++) {
		int x, y, u, v; scanf("%d%d%d%d", &x, &y, &u, &v);
		int p = lca(u, v);
		pii a = T.query(rt[u], 1, N-1, x), b = T.query(rt[v], 1, N-1, x), c = T.query(rt[p], 1, N-1, x);
		printf("%d\n", (dis[u]+dis[v]-2*dis[p]) - (a.second+b.second-2*c.second) + (a.first+b.first-2*c.first)*y);
	}
}

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

int main() {
	int n, a;
	cin >> n;

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

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

Measured memory_bytes: 4012
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
# 必ずB1の方を大きくする必要がある
if A1 > B1:
    B1, A1 = A1, B1
    B2, A2 = A2, B2
P = T1*(A1-B1)  # Pは負の値
Q = T2*(A2-B2)
if P + Q == 0:
    print("infinity")
    exit()
elif P + Q < 0:  # 出会う位置まで戻ってこれなかった
    print(0)
    exit()
elif P + Q > 0:  # 限られた数だけあえる
    if (-P % (P + Q)) == 0:
        print(2*(-P // (P+Q)))
    else:
        print(2*(-P // (P+Q))+1)


Measured memory_bytes: 3064
import itertools
if __name__=='__main__':
    N = int(input())
    x = []
    y = []
    pq = []
    max_pq = 0
    for i in range(N):
        xi, yi = map(int, input().split())
        x.append(xi)
        y.append(yi)
    for i,j in itertools.combinations(range(N),2):
        p = x[i]-x[j]
        q = y[i]-y[j]
        if p < 0:
            p = -p
            q = -q
        elif p == 0 and q < 0:
            q = -q
        pq.append((p,q))
    for k in pq:
        max_pq = max(max_pq,pq.count(k))
    print(N-max_pq)

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

struct edge {
    ll to, cost;
    edge() {
        to = 0;
        cost = 0;
    }
    edge(ll t, ll c) {
        to = t;
        cost = c;
    }
};

const ll coin_max = 3000;
ll make_num(ll v_num, ll coin_num) {
    coin_num = min(coin_num, coin_max - 1);
    return v_num * coin_max + coin_num;
}

// cost,num
using p = pair<ll, ll>;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m, s;
    cin >> n >> m >> s;
    vector<vector<edge>> g(n * coin_max);
    rep(i, m) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        repd(coin, a, coin_max) {
            ll from = make_num(u, coin), to = make_num(v, coin - a);
            g[from].push_back(edge(to, b));
            from = make_num(v, coin), to = make_num(u, coin - a);
            g[from].push_back(edge(to, b));
        }
    }
    rep(i, n) {
        ll c, d;
        cin >> c >> d;
        rep(coin, coin_max) {
            ll from = make_num(i, coin), to = make_num(i, coin + c);
            g[from].push_back(edge(to, d));
        }
    }

    ll inf = 1LL << 60;
    vector<ll> d(n * coin_max);
    fill(d.begin(), d.end(), inf);
    d[make_num(0, s)] = 0;

    priority_queue<p, vector<p>, greater<p>> q;
    q.push(p(0, make_num(0, s)));
    while (!q.empty()) {
        p now = q.top();
        q.pop();
        ll now_position = now.second;
        if (d[now_position] < now.first)
            continue;
        for (edge e : g[now_position]) {
            if (d[e.to] > d[now_position] + e.cost) {
                d[e.to] = d[now_position] + e.cost;
                q.push(p(d[e.to], e.to));
            }
        }
    }

    repd(t, 1, n) {
        ll ans = inf;
        rep(i, coin_max) {
            ll num = make_num(t, i);
            ans = min(ans, d[num]);
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 27536
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T &a){int t = 0;for(auto itr :a){if(t++)cout << " "; cout << itr;} cout <<endl; }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
template<class T, class Func = function<T(T, T)>>
class segtree {
    vector<T> obj;
    int offset;
    Func updater;
    T e;
    int bufsize(int num) {
        int i = 1;
        for (; num + 1 >i; i <<= 1);
        offset = i - 1;
        return (i << 1) - 1;
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)return e;
        if (a <= l && r <= b)return obj[k];
        else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
    }
public:
    T query(int a, int b) {//[a,b)
        return query(a, b, 0, 0, offset + 1);
    }
    void updateall(int l = 0, int r = -1) {
        if (r < 0)r = offset + 1;
        l += offset, r += offset;
        do {
            l = (l - 1) >> 1, r = (r - 1) >> 1;
            for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
        } while (l);
    }
    void update(int k, T &a) {
        k += offset;
        obj[k] = a;
        while (k) {
            k = (k - 1) >> 1;
            obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
        }
    }
    segtree(int n, T e, const Func &updater = Func()) :obj(bufsize(n), e), e(e), updater(updater) {}
    segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
        copy(vec.begin(), vec.end(), obj.begin() + offset);
        updateall();
    }
    typename vector<T>::reference operator[](int n) {
        return obj[n + offset];
    }
};
template<class T> T gcd(T a,  T b) {return b ? gcd(b, a % b) : a;}
template<class U> U lcm( U m, U n ){if((0 == m )||( 0 == n ))return 0; return ((m / gcd(m, n)) * n); }
signed main(){
    //    std::ios_base::sync_with_stdio(false);
    //    cin.tie(NULL);
    int n; cin >> n;
    vector<int>v(n);
    for(auto & e : v) cin >> e;
    auto sgt = segtree<int>(v,/*accumulate(all(v),1LL,[](int a, int b){return a*b;})*/0LL,[](int a, int b){return gcd(a,b);});
    int ans = -INF;
    for(int i = 0; i < n; ++i){
        cmax(ans,gcd(sgt.query(0,i),sgt.query(i+1,n)));
    }
    cout << ans << endl;
}




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

int kosu(int n){
    vector<int> v;
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            v.push_back(i);
            if(i*i != n){
                v.push_back(n/i);
            }
        }
    }
    return v.size();
}

int main(){
    vector<int> A(200,0);
    for(int i=1;i<=200;i++){
        A[i-1] = kosu(i);
    }
    int n;
    cin >> n;
    int ans = 0;
    for(int i=1;i<=n;){
        if(A[i-1] == 8) ans++;
        i+=2;
    }
    cout << ans << endl;
    
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define ld long double
#define li long long int
li A[1000006];
int main()
{
    li N; cin >> N;
    for(int i = 0; i < 1000006; i++)
    A[i] = 0;
    for (int i = 0; i < N; i++)
    {
        li x; cin >> x;
        A[x]++;
    }

    for (int i = 1; i < 1000006; i++)
    {
        if (A[i] == 0)
            continue;
        for (int j = 2 * i; j <= 1000006; j = j + i)
        {
            A[j] = 0;
        }
        if (A[i] != 1)
            A[i] = 0;
    }
    li ans = 0;
    for (int i = 1; i < 1000006; i++)
    {
        ans += A[i];
    }
    cout << ans;
}

Measured memory_bytes: 11448
import java.util.*;

class Main {
	  static long mod=1_000_000_007;
  public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
      String S = sc.next();
      if(S.equals("Sunny")) {
    	  System.out.println("Cloudy");    	  
      } else if (S.equals("Cloudy")) {
    	  System.out.println("Rainy"); 
      } else {
    	  System.out.println("Sunny"); 
      }
      
  }
  
 
}

Measured memory_bytes: 21716
#include <stdio.h>
#include <algorithm>

int main(){
  int num;
  scanf("%d",&num);
  int address[num];
  for(int i = 0;i != num;i++){
    scanf("%d",&address[i]);
  }
  std::sort(address, address+num);
  int result = address[num-1] - address[0];
  printf("%d\n",result);
  return 0;
}

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

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var N = long.Parse(Console.ReadLine());
            var answer = this.Calc(N).Min();
            Console.WriteLine(answer);
        }

        private IEnumerable<long> Calc(long N)
        {
            for (long a = 1; a * a <= N; a++)
            {
                if (N % a == 0)
                {
                    yield return a + (N / a) - 2;
                }
            }
        }
    }
}


Measured memory_bytes: 13268
import std.stdio;
import std.algorithm;
import std.range;
import std.conv;
import std.format;
import std.array;
import std.math;
import std.string;
import std.container;

void main() {
  int N; readlnTo(N);
  if (N == 1) "Hello World".writeln;
  else {
    int A, B;
    readlnTo(A);
    readlnTo(B);
    (A + B).writeln;
  }
}

// helpers
void readlnTo(T...)(ref T t) {
  auto s = readln.split;
  assert(s.length == t.length);
  foreach(ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1..$];
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,mod=1000000000+7,ans=0,val=1,a=0,b=0,m_=0;cin>>n;
  lvector v(n,0),p(n-1,0),f(n-1,0),d(n-1,0);
  rep(i,n) cin>>v[i];
  rep(i,n-1) d[i]=v[i+1]-v[i];
  p[0]=1;
  for(ll i=1;i<n-1;++i) {val=(val*i)%mod; p[i]=((i+1)*p[i-1]+val)%mod;}
  f[0]=(val*(n-1))%mod;
  for(ll i=1;i<n-1;++i) {
    a=1;b=(i+1)%mod;m_=mod-2;
    while(m_ != 0) {
      if(m_&1) a=(a*b)%mod;
      b=b*b%mod;
      m_=m_>>1;
    }
    f[i]+=(f[i-1]*a)%mod;
  }
  for(ll i=0;i<n-1;++i) ans+=(((d[i]*p[i])%mod)*f[i])%mod;
  ans%=mod;
  print(ans);
  return 0;
}

Measured memory_bytes: 3456
import java.io.*;


public class Main{
	public static void main(String args[]) throws IOException{
		InputStreamReader in = new InputStreamReader(System.in);
		BufferedReader bf = new BufferedReader(in);
		String str = bf.readLine();
		char[] ch = str.toCharArray();
		for(int i=0; i<ch.length/2; i++){
			output(Integer.parseInt(""+ch[i*2]),ch[i*2+1]);
		}
		System.out.println();
	}

	static void output(int i, char c){
		switch(i){
		case 0:
			if(c == 'T'){
				System.out.print("wa");
			}else if(c == 'U'){
				System.out.print("nn");
			}else if(c == 'D'){
				System.out.print("wo");
			}
			return;
		case 1:
			break;
		case 2:
			System.out.print("k");
			break;
		case 3:
			System.out.print("s");
			break;
		case 4:
			System.out.print("t");
			break;
		case 5:
			System.out.print("n");
			break;
		case 6:
			System.out.print("h");
			break;
		case 7:
			System.out.print("m");
			break;
		case 8:
			System.out.print("y");
			break;
		case 9:
			System.out.print("r");
			break;
		}
		switch(c){
		case 'T':
			System.out.print("a");
			return;
		case 'L':
			System.out.print("i");
			return;
		case 'U':
			System.out.print("u");
			return;
		case 'R':
			System.out.print("e");
			return;
		case 'D':
			System.out.print("o");
			return;
		}
	}
}

Measured memory_bytes: 17172
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repl(i, l, r) for (ll i = (l); i < (r); i++)
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CST(x) cout << fixed << setprecision(x)
using ll = long long;
const ll MOD = 1000000007;
const int inf = 1e9 + 10;
const ll INF = 4e18;
const int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
const int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	int a[n], b[n];
	pair<int, int> p[n];
	rep(i, n) {
		cin >> a[i] >> b[i];
		p[i] = {a[i] + b[i], i};
	}
	sort(p, p + n, greater<pair<int, int>>());
	ll ans = 0;
	rep(i, n) {
		if (i % 2)
			ans -= b[p[i].second];
		else
			ans += a[p[i].second];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
from sys import stdin, setrecursionlimit


def main():

    setrecursionlimit(2000001)

    current, q = [int(x) for x in stdin.readline().split()]

    tree = [[] for _ in range(current + 1)]
    for _ in range(current - 1):
        a, b = [int(x) for x in stdin.readline().split()]
        tree[a].append(b)
        tree[b].append(a)

    cnt = [0] * (current + 1)
    for _ in range(q):
        parent, x = [int(x) for x in stdin.readline().split()]
        cnt[parent] += x

    stack = []
    visited = [False] * (current + 1)

    stack.append((0, 1))

    while len(stack) > 0:
        parent, current = stack.pop()
        visited[current] = True
        cnt[current] += cnt[parent]
        for child in tree[current]:
            if not visited[child]:
                stack.append((current, child))

    print(*cnt[1:])


main()


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

int64_t mod = 998244353 ;

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


vector<int> getprime(int n){
    vector<int> p(0) ;
    vector<bool> table(n+1,0) ;
    for (int i = 2; i <= n; i++)
    {
        if (table.at(i) == 0)
        {
            p.push_back(i) ;
            for (size_t j = 2; j < n/i ; j++)
            {
                table.at(i*j) = 1 ;
            }
            
        }
        
    }
    return p ;
}


int main(){
    int n,h ;
    cin >> n >> h ;
    vector<pair<int,int> > s(n,pair<int,int>()) ;
    for (int i = 0; i < n; i++)
    {
        cin >> s.at(i).first >> s.at(i).second ;
    }
    sort(s.begin(),s.end()) ;
    pair<int,int> keep = s.at(n-1) ;
    s.pop_back() ;
    for (int i = 0; i < n-1; i++)
    {
        swap(s.at(i).first, s.at(i).second) ;
    }
    sort(s.begin(),s.end(),greater<pair<int,int> >()) ;
    int ans = 0 ;
    bool end = 0 ;
    for (int i = 0; i < s.size(); i++)
    {
        if (s.at(i).first > keep.first)
        {
            h -= s.at(i).first ;
            ans ++ ;
            if (h <= 0)
            {
                end = 1 ;
                break ;
            }else if (h <= keep.second)
            {
                h -= keep.second ;
                ans ++ ;
                end = 1 ;
                break ;
            }
            
        }else
        {
            break ;
        }
        
        
        
        
        
    }
    if (end == 0)
    {
        h -= keep.second ;
        ans ++ ;
        ans += (h+keep.first-1)/keep.first ;
    }
    cout << ans << endl ;
    
}

Measured memory_bytes: 4060
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <random>
#include <tuple>
#include <iomanip>
#include <cstring>

using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
//typedef pair<ll, ll> P;
//typedef pair<ll, pair<ll, ll>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)
#define pb push_back
#define f first
#define s second
//const ll INFL = 1LL << 60;//10^18 = 2^60
const ll INFL = 1LL << 60;
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD  = 998244353;
vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}
ll inverse(ll x){return pow_mod(x, MOD - 2);};

//最大公約数
ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

ll N;
string S;
int main(){
  cin >> N >> S;
  ll x = 0;
  ll ans = 1;
  for(ll i = 1; i <= N; i++){
    ans *= i;
    ans %= MOD;
  }
  rep(i, 2 * N){
    if(S[i] == 'B'){
      if(x % 2 == 0){
        x++;
      }else{
        ans *= x;
        ans %= MOD;
        x--;
      }
    }else{
      if(x % 2 == 0){
        ans *= x;
        ans %= MOD;
        x--;
      }else{
        x++;
      }
    }
    if(x < 0) ans = 0;
  }
  if(x != 0) ans = 0;
  cout << ans << endl;
}


Measured memory_bytes: 644
fun main(args: Array<String>) {
    val (n, m) = run {
        val (n, m) = readLine()!!.split(' ')
        Pair(n.toLong(), m.toInt())
    }

    val bridges = (0 until m).map {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        Pair(a, b)
    }.reversed()

    val unionFind = UnionFind(n.toInt())

    val res = LongArray(m) { 0L }
    res[0] = n * (n - 1) / 2

    bridges.take(m - 1).forEachIndexed { i, bridge ->
        val x = bridge.first - 1
        val y = bridge.second - 1

        if (unionFind.same(x, y)) {
            res[i + 1] = res[i]
            return@forEachIndexed
        }

        res[i + 1] = res[i] - unionFind.size(x).toLong() * unionFind.size(y).toLong()

        unionFind.unite(x, y)
    }

    res.reversed().forEach {
        println(it)
    }
}

private class UnionFind(n: Int) {

    private val par = IntArray(n) { it }

    private val rank = IntArray(n) { 0 }

    private val size = IntArray(n) { 1 }

    fun find(x: Int): Int {
        if (par[x] == x) {
            return x
        }
        par[x] = find(par[x])
        return par[x]
    }

    fun unite(x1: Int, y1: Int) {
        val x = find(x1)
        val y = find(y1)

        if (x == y) return

        if (rank[x] < rank[y]) {
            par[x] = y
            size[y] += size[x]
        } else {
            par[y] = x
            size[x] += size[y]
            if (rank[x] == rank[y]) {
                rank[x]++
            }
        }
    }

    fun same(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

    fun size(x: Int): Int {
        return size[find(x)]
    }

}


Measured memory_bytes: 79184
package main

import "fmt"

func main() {
	var H, W int
	for {
		fmt.Scan(&H, &W)
		if H == 0 && W == 0 {
			break
		}
		for i := 0; i < H; i++ {
			for j := 0; j < W; j++ {
				if i == 0 || i == H-1 || j == 0 || j == W-1 {
					fmt.Print("#")
				} else {
					fmt.Print(".")
				}
			}
			fmt.Println("")
		}
		fmt.Println("")
	}
	return
}



Measured memory_bytes: 1176
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 1e18;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

using Pair = pair<ll, ll>;


signed main() {
  ios::sync_with_stdio(false);
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n), f(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> f[i];
  sort(all(a), greater<>());
  sort(all(f));
  ll lft = 0;
  ll rgt = 1e12;
  if(sum(all(a)) <= k) rgt = 0;
  while(rgt - lft > 1) {
    ll mid = (lft + rgt) / 2;
    ll c = 0;
    REP(i, n) {
      if (mid > a[i] * f[i]) continue;
      c += (a[i] * f[i] - mid + f[i] - 1) / f[i];
    }
    if(c > k) {
      lft = mid;
    }
    else {
      rgt = mid;
    }
  }
  cout << rgt << endl;
  return 0;
}

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

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,a[maxn],inv[maxn];

int main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++) inv[i]=(inv[i]+inv[i-1])%mod;
    int ans=0;
    for(int i=1;i<=n;i++) {
        int x=(inv[i]-1+inv[n-i+1]-2)%mod;
        ans=(ans+1ll*x*a[i]%mod)%mod;
    }
    for(int i=1;i<=n;i++) ans=1ll*ans*i%mod;
    write(ans);
    return 0;
}


Measured memory_bytes: 4736
#include<stdio.h>

int main(){
	int w,h,x,y,r;
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	
	if(x+r<=w && x-r>=0 && y+r<=h && y-r>=0){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
}


Measured memory_bytes: 1992
#include<iostream>
#include<vector>

using namespace std;
const int inf=1e8;

int main(){

    while(1){
        int n, m;
        cin>> n>> m;
        if(n==0&&m==0) break;
        int a[m], b[m];
        for(int i=0; i<m; i++){
            cin>> a[i]>> b[i];
            a[i]--; b[i]--;
        }

        int mtrx[n][n];
        fill(mtrx[0], mtrx[n], inf);
        for(int i=0; i<m; i++){
            mtrx[a[i]][b[i]]=mtrx[b[i]][a[i]]=1;
        }


        for(int k=0; k<n; k++)
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                    mtrx[i][j]=min(mtrx[i][j], mtrx[i][k]+mtrx[k][j]);

        int ans=0;
        for(int i=1; i<n; i++){
            if(mtrx[0][i]==2||mtrx[0][i]==1) ans++;
        }

        cout<< ans<< endl;

    }

    return 0;
}

Measured memory_bytes: 4136
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <bitset>

using namespace std;

//#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

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

//static const ll MOD = 1000000007;
//static const ll INF = 100000000;

int main() {
    // input
    ll A, B, K;
    cin >> A >> B >> K;

    // process
    if (A >= K) {
        cout << A - K << " " << B << endl;
    } else if ((A + B) <= K) {
        cout << 0 << " " << 0 << endl;
    } else {
        cout << 0 << " " << B - (K - A) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
using namespace std;

double v;

int main() {
  while (1) {
    if (scanf("%lf", &v) != 1) return 0;
    
    int n = 1;
    while (1) {
      double h = 5*n-5;
      if (sqrt(h/4.9)*9.8 >= v) break;
      ++n;
    }

    printf("%d\n", n);
  }
}

Measured memory_bytes: 2568
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	string S,T;cin>>S>>T;
	int n=S.size(),i,j;
	int  a[26][26]={0};
	for(i=0;i<n;i++){a[S[i]-'a'][T[i]-'a']=1;}
	for(i=0;i<26;i++){
		int b=0,c=0;
		for(j=0;j<26;j++){
			b+=a[i][j];c+=a[j][i];
		}
		if(1<b||1<c){cout<<"No"<<endl;return 0;}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 776
int_list = [int(input()) for _ in range(4)]
res = 0
for n_500 in range(int_list[0] + 1):
  for n_100 in range(int_list[1] + 1):
    for n_50 in range(int_list[2] + 1):
      if n_500 * 500 + n_100 * 100 + n_50 * 50 == int_list[3]:
        res += 1

print(res)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; ++i){
        if(i % 3 == 0 || i % 5 == 0)    continue;
        sum += i;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3648
#include <iostream>

using namespace std;

string S, T;

void solve() {
  for (int i = 0; i < S.size(); i++) {
    if (S[i] != T[i]) {
      printf("No\n");
      return;
    }
  }
  printf("Yes\n");
}

int main() {
  cin >> S >> T;
  solve();
}


Measured memory_bytes: 3620
// #define LOCAL
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll k; cin >> k;
    vector<ll> v;
    ll n = 1;
    auto snuke = [&](ll n){
        ll t = 0;
        ll nt = n;
        while(nt){
            t += nt % 10;
            nt /= 10;
        }

        return ld(n) / ld(t);
    };

    vector<ll> tens(17);
    tens[0] = 1;
    rep(i,16)tens[i+1] = tens[i] * 10;
    while(k--){
        debug(n, snuke(n));
        if(snuke(n) == 1){
            v.emplace_back(n);
            n++;
            continue;
        }

        // if(n % 10 == 0)n += 9;
        rep(i,15){
            debug(n, snuke(n));
            if(snuke(n) > tens[i]){
                debug(tens[i]);
                n += tens[i] * 9;
            }
        }

        v.emplace_back(n);
        n++;
    }

    for(auto &i : v)cout << i << "\n";
    return 0;
}

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

const int K = 18, N = 1<<K, M = 1e9+7;
int prod[N][K];
int a[N];

vector<pair<int, int>> vp[N];

void add(int x, int z, int mul) {
    assert(vp[x].empty() || vp[x].back().first <= z);
    if (vp[x].empty() || vp[x].back().first < z)      vp[x].push_back({z, mul});
    else {
        vp[x].back().second += mul;
        if (vp[x].back().second >= M) vp[x].back().second -= M;
    }
}

int rgt[N];

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

    int k;
    cin>>k;

    int L = 1<<(k-1), R = 2*L-1;

    for (int i=L; i<=R; i++) {
        prod[i][0] = i;
        for (int j=1; j<k; j++) {
            prod[i][j] = (1LL*prod[i][j-1]*(i>>j))%M;
        }
    }


    for (int i=L; i<2*L; i++) {
        int x;
        cin>>x;
        a[i] = x+L-1;
    }

     for (int k1=k-1; k1>=0; k1--) {
        for (int k2=k-1; k2>=0; k2--) {
            for (int i=L; i<2*L; i++) {
                int x = a[i];
                int pr = (1LL*prod[i][k1]*prod[x][k2])%M;

                int a1 = (i>>k1), a2 = (x>>k2);
                add(a2, a1, pr);
            }
        }
    }

    long long ans = 0;
    for (int i=1; i<=L; i++) {
        int ll = 2*i, rr = 2*i+1;

        for (auto pr: vp[rr])       rgt[pr.first] = pr.second;

        for (auto pr: vp[ll]) {
            int x = pr.first;
            if (x == 1) continue;
            unsigned long long con = (1LL*pr.second*rgt[x^1])%M;
            con = (con*i*(x>>1))%M;
            ans += con;
        }

        for (auto pr: vp[rr])       rgt[pr.first] = 0;
    }
    cout<<ans%M<<endl;
}


Measured memory_bytes: 270724
#include<iostream>
#include<algorithm>
using namespace std;
int A,B,C,K;

int main(){
	ios::sync_with_stdio(0);
	cin>>A>>B>>C>>K;
	cout<<A+B+C+max({A,B,C})*((1<<K)-1)<<'\n';
	return 0;
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

int main(){
    int n, m;
    cin >> n >> m;
    vector<P> v;
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        v.push_back({max(a, b), min(a, b)});
    }
    SORT(v);
    int ans = 0, t = -1, j = 0;
    rep(i, n){
        while(v[j].first == i){
            if(v[j].second >= t){
                ++ans;
                t = v[j].first;
            }
            ++j;
            if(j == m){
                break;
            }
        }
        if(j == m){
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1400
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
	int n,i;
	
	cin >> n;
	
	cout << n << ":";
	
	for(i=2;n!=1;i++)
	{
		if(i>sqrt(n))
		{
			cout << " " << n;
			n=1;
			continue;
		}
		while(n%i==0)
		{
			cout << " " << i;
			n/=i;
		}
	}
	cout << endl;
	
	return 0;
}

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

using namespace std;

int main()
{

  // freopen("atcoderdiv.txt", "r", stdin);
   //freopen("atcoderdivout.txt", "w", stdout);

    int n;



    cin >> n;

    string s[n+1];

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

   int cnt = 0;

   for(int i = 0; i < n; i++)
   {
       int sz = s[i].size();
        for(int j = 0; j < sz - 1; j++)
        {
            if(s[i][j] == 'A' && s[i][j+1] == 'B')
            {
                cnt++;
                s[i][j] = 'Z';
                s[i][j+1] = 'Z';
            }
        }

   }

  // cout << cnt << endl;

    int a = 0 , b = 0, ch = 0;

   for(int i = 0; i < n; i++)
   {

      int sz = s[i].size();

      if(s[i][0] == 'B' && s[i][sz-1] == 'A')
      {
          ch++;
      }

      else if(s[i][0] == 'B')
       {
         // s[i][0] = 'Z';
          b++;
       }
         // b++;

     else if(s[i][sz-1] == 'A')
        {
            // s[i][sz-1] = 'Z';
              a++;
       }

   }


    int result = 0;

   //cout << "a " << a << b << endl;

   if(a+b == 0)
   {
      //cout << "nahid" << endl;
      if(ch > 0)
      {
            result = ch + cnt - 1;
      }
      else
         result = cnt;
   }

   else
   {
        int ans = min(a, b);

        //cout << ans << cnt << ch << endl;

        result = ans + cnt + ch;
   }


   cout << result << endl;





    return 0;
}


Measured memory_bytes: 768
N = int(input())
H = list(map(int, input().split()))

if N == 1:
    print("Yes")

if N == 2:
    if H[0]-H[1] <= -1:
        print("Yes")
    else:
        print("No")

if N >= 3:
    for i in range(1, N):
        if H[0]-H[1] <= -1:
            H[1] -= 1
        elif H[0]-H[1] == 0:
            H[0] -= 1
            H[1] -= 1
        elif H[0]-H[1] == 1:
            H[0] -= 1

        if i == N-1:
            print("Yes")
            break
        elif H[i]-H[i+1] <= -1:
            H[i+1] -= 1
            continue
        elif H[i]-H[i+1] == 0:
            continue
        else:
            print("No")
            break


Measured memory_bytes: 14480
import java.util.*;
public class Main {
  public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
      long N = sc.nextLong();
      long M = sc.nextLong();
      long result = 0;
      //if (M >= 2) {
        if (N*2 <= M) {
          if ((M - N*2) >= 4) {
            result = ((M - N*2) / 4) + N;
          } else {
            result = N;
          }
        } else {
          result = M/2;
        }
        //} else {
        //result = 0;
        //}
      System.out.println(result);
  }
}

Measured memory_bytes: 21972
#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;
const long int mod = (int)(1e9+7);

int main() {

    int h,w;
    cin>>h>>w;

    vector<vector<char> > mat(h,vector<char>(w));
    for(int i = 0;i<h;i++) {
        for(int j = 0;j<w;j++) {
            cin>>mat[i][j];
        }
    }
          
    vector<vector<int> > dp(h,vector<int>(w,0));
    dp[0][0] = 1;

    for(int i = 0;i<h;i++) {
        for(int j = 0;j<w;j++) {
            if(i==0 || j==0) {
                if(i==0 && j==0)
                    dp[0][0] = 1;
                else if(j==0 && i>0) {
                    if(mat[i][j]=='#')
                        dp[i][j] = 0;
                    else
                        dp[i][j] = dp[i-1][j];
                } else {
                    if(mat[i][j]=='#')
                        dp[i][j] = 0;
                    else
                        dp[i][j] = dp[i][j-1];
                }
            }
            else if(mat[i][j]!='#') {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            } else
                dp[i][j] = 0;
            
           dp[i][j]=dp[i][j]%mod;
        }
    }

    cout<<dp[h-1][w-1]<<endl;

    return 0;
}


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

int main() {
    long double a, b;
    cin >> a >> b;
    cout << ll(a * b) << endl;

    return 0;
}

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

#define mod 1000000007

void add(long long &a, long long b)
{
	a += b;
	if(a>=mod)
		a -= mod;
}

long long power(long long x, long long y) 
{ 
    int res = 1;     
    x = x % mod;  
    
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % mod; 
  		 y = y>>1;
        x = (x*x) % mod;   
    } 
    return res; 
} 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
   
	long n;
	cin>>n;
	unsigned long long a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];

	long long zero[63]={0},one[63]={0};
	long long p = 1;

	for(int i=0;i<63;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(a[j] & (p<<i))
				one[i]++;
			else
				zero[i]++;
		}
	}
	long long ans = 0;   
	for(int i=0;i<63;i++)
	{
		//cout<<one[i]<<" "<<zero[i]<<'\n';
		add(ans,((((one[i]*zero[i])%mod))*power(2,i))%mod);
	}
	cout<<ans;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long
const int MOD = 1e9 + 7;

struct Combination{
  vector<int> fact; //　fact[i] = iの階乗
  Combination(int n) : fact(n+1){
    fact[0] = fact[1] = 1;
    for(int i = 2; i <= n; i++){
      fact[i] = fact[i-1] * i % MOD;
    }
  }

  int nCr(int n, int r){ // nCr = n!/r!(n-r)!
    if(n < r) return 0;
    return fact[n] * inv(fact[r]*fact[n-r]%MOD) % MOD;
  }

  int inv(int n, int p = MOD-2){ // a/n ≡ a*n^(p-2) nとpは互いに素
    int r = 1;
    for(; p > 0; p >>= 1){
      if(p & 1LL) r = (r * n) % MOD;
      n = (n * n) % MOD;
    }
    return r; // r = n^p % MOD
  }
};

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

  Combination c(n+1);
  vector<int> num(n, 0), dp(n, 1);
  auto dfs1 = [&](auto&& dfs1, int u, int p)->void{
    for(int v : G[u]){
      if(v == p) continue;
      dfs1(dfs1, v, u);
      num[u] += num[v];
      dp[u] = dp[u] * dp[v]%MOD * c.nCr(num[u], num[v]) % MOD;
    }
    num[u]++;
  };
  dfs1(dfs1, 0, -1);

  vector<int> ans(n);
  auto dfs2 = [&](auto&& dfs2, int u, int p, int res)->void{
    ans[u] = dp[u] * res%MOD * c.nCr(n-1, n-num[u]) % MOD;
    for(int v : G[u]){
      if(v == p) continue;
      res = ans[u] * c.inv(dp[v])%MOD * c.inv(c.nCr(n-1, num[v])) % MOD;
      dfs2(dfs2, v, u, res);
    }
  };
  dfs2(dfs2, 0, -1, 1);

  for(int p : ans){
    cout << p << endl;
  }

  return 0;
}


Measured memory_bytes: 21848
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
a,b,t = readInts()
ans = 0
time = 0
while True:
    ans += b
    #print(time,t+0.5)
    if time + a > t + 0.5:
        break
    else:
        time += a
print(ans - b)


Measured memory_bytes: 3444
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#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> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

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

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

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 &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x): x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

bool f(string s) {
    dump(s);
    int l = 0;
    int r = int(s.length()) - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l;
        --r;
    }
    return true;
}

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

    var(string, s);
    const int N = s.length();

    if (f(s) && f(s.substr(0, (N - 1) / 2)) && f(s.substr((N + 3) / 2 - 1, 10000))) {
        print("Yes");
    } else {
        print("No");
    }

    return 0;
}


Measured memory_bytes: 256