akhauriyash/Code-Regression huggingface dataset:
def dfs(i, a, b, c, t):
    global ans
    if a*b*c > 0:
        ans = min( ans, abs(A-a)+abs(B-b)+abs(C-c)+10*(t-3) )
    if i > N - 1: return 0
    dfs(i+1,a,b,c,t)
    dfs(i+1, a + L[i], b, c, t+1)
    dfs(i+1, a, b + L[i], c, t+1)
    dfs(i+1, a, b, c + L[i], t+1)
    return ans
N, A, B, C = map(int,input().split())
L = [int(input()) for i in range(N)]
ans = 10**9
print(dfs(0,0,0,0,0))

Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <fstream>

using namespace std;

int main(){
    string s, t;
    cin >> s >> t;
    int ans = 0;
    for(int i = 0; i < 3; i++){
        if (s[i]==t[i]){
            ans++;
        }
    }
    cout << ans <<  endl;
}

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

int main()
{
  int N, M, C, ans=0;
  int B[20], A[20][20];
  cin >> N >> M >> C;
  for(int i=0; i<M; ++i) cin>>B[i];
  for(int j=0; j<N; ++j) for(int i=0; i<M; ++i) cin>>A[j][i];
  for(int j=0; j<N; ++j) {
    int sum=0;
    for(int i=0; i<M; ++i)
      sum+=A[j][i]*B[i];
    if(sum+C>0) ++ans;
  }
  cout << ans << endl;
  return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x, y) CPP_CAT_I(x, y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x, y) x##y

#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;
// }}}

constexpr i64 INF = 1'010'000'000'000'000'017LL;

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

#define M5 100007
#define M9 1000000000

// util {{{
#define FOR(i, start, end) for (i64 i = (start), CPP_CAT(i, xxxx_end) = (end); i < CPP_CAT(i, xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f, c, ...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); })(c))
#define ll long long int
#define VI vector<int>
template <typename C>
i64 SIZE(const C &c)
{
    return static_cast<i64>(c.size());
}

template <typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

template <typename T, typename U, typename Comp = less<>>
bool chmax(T &xmax, const U &x, Comp comp = {})
{
    if (comp(xmax, x))
    {
        xmax = x;
        return true;
    }
    return false;
}

template <typename T, typename U, typename Comp = less<>>
bool chmin(T &xmin, const U &x, Comp comp = {})
{
    if (comp(x, xmin))
    {
        xmin = x;
        return true;
    }
    return false;
}
// }}}

// init {{{
struct ProconInit
{
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit()
    {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

//--------------------------------------------------------------------

bool isOK(int mid, double key)
{
}

int binary_search(double key)
{
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = 2000000000;
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;

        if (isOK(mid, key))
            right = mid;
        else
            left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

bool isKaibun(string st)
{
    bool ans = true;
    int n = st.length();
    REP(i, n / 2)
    {
        if (st[i] != st[n - i - 1])
        {
            return false;
        }
    }
    return true;
}

int toInt(char a)
{
    return a - '0';
}

int gcd(int a, int b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

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

void solve()
{
    int N;
    cin >> N;
    while (N - 1000 > 0)
    {
        N -= 1000;
    }
    cout << 1000 - N;
    //    cout << ;
}

signed main()
{

    solve();

    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main() {
  for (;;) {
    int n;
    cin >> n;
    if (!n) return 0;
    string result;
    cin >> result;
    result.push_back(0);
    for (int i = 0; i < n; i++) {
      stringstream s;
      for (int i = 1, length = 1; i < result.size()+1; i++)
        if (result[i] == result[i-1])
          length++;
        else {
          s << length << result[i-1];
          length = 1;
        }
      result = s.str();
    }
    cout << result << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;

int n, k;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	int cur = 1;
	FOR(i, n) {
		if (cur <= k) cur *= 2;
		else cur += k;
	}
	cout << cur << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    int a, b;
    cin >> a >> b;
    if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0)
        cout << "Possible\n";
    else
        cout << "Impossible\n";
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f(a, b) for (ll i = a; i <= b; i++)
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
#define N 200005
const ll INF = 1000000000000000001;
const ll MOD = 1000000007;
#define lim 1000000



void solve(){
    ll n; cin >> n;
    n--;
    ll ans= 0;
    f(1, n){
        ans += n/i;
    }
    cout << ans << '\n';
;}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
   //ll t;cin >> t;for(ll index=1; index<=t; index++){
        //cout << "Case #" << index << ": " ;
        solve();
   // }
    return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define RI(x) x = rit()
#define RII(a,b) a = rit(), b = rit()
#define RIII(a,b,c) a = rit(), b = rit(), c = rit()
#define REP(I, N) for(int I=0;I<int(N);I++)
#define REPP(I, N) for(int I=1;I<=int(N);I++)
#define ll long long
#define SZ(x) (int)(x).size()
#define F first
#define S second
#define PB(x) push_back(x)
#define N 100000
inline int rit(){
    int f=0,key=1;
    char ch;
    do{
        ch = getchar();
        if(ch=='-') key=-1;;
    }while(ch<'0'||ch>'9');
    do{
        f = f*10+ch-'0';
        ch = getchar();
    }while(ch>='0'&&ch<='9');
    return f*key;
}
using namespace std;
typedef pair<int,int> P;
int n,m,a,b,v,d,c,Q;
vector<int> vct[N+5];
int clr[N+5];
bool fn[N+5][15];
struct st_{
	int pt, dis, cl;
}st[N+5];
void BFS(int x, int mxd, int mdcl){
        fn[x][mxd] = true;
	queue<P> que;
	que.push(P(x,mxd));
	while(!que.empty()){
		P tmp = que.front();
		que.pop();
		if(!clr[tmp.F])	clr[tmp.F] = mdcl;
		if(tmp.S){
			for(auto to:vct[tmp.F]) if(!fn[to][tmp.S-1]){
                                fn[to][tmp.S-1] = true;
				que.push(P(to,tmp.S-1));
			}
		}
	}
}
int main(void){
	RII(n,m);
	REP(i,m){
		RII(a,b);
		vct[a].PB(b);
		vct[b].PB(a);
	}
	RI(Q);
	REPP(i,Q){
		RIII(v,d,c);
		st[i].pt = v, st[i].dis = d, st[i].cl = c;
	}
	for(int i=Q;i;--i){
		if(!fn[st[i].pt][st[i].dis])
			BFS(st[i].pt, st[i].dis, st[i].cl);
	}
	REPP(i,n) printf("%d\n",clr[i]);
}

Measured memory_bytes: 10024
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M = map(int, readline().split())

adj = [[] for _ in range(N)]
for i in range(M):
    x, y, z = map(int, readline().split())
    x -= 1
    y -= 1
    adj[x].append(y)
    adj[y].append(x)

visited = [False for _ in range(N)]
def dfs(v):
    if visited[v]:
        return False
    visited[v] = True
    for u in adj[v]:
        dfs(u)
    return True


ans = 0
for i in range(N):
    if dfs(i):
        ans += 1
print(ans)

Measured memory_bytes: 105104
use proconio::input;

fn main() {
    input! {
        x: i128,
    }

    let mut a: i128 = 1;
    let mut b: i128 = 0;

    loop {
        if a.pow(5) < x {
            a += 1;
        } else {
            break;
        }
    }

    loop {
        if (a - b.pow(5)) > x {
            b += 1;
        } else {
            break;
        }
    }

    if check(a, b, x) {
        println!("{} {}", a, b);
        return;
    }

    let mut w = 1;

    loop {
        for w1 in 0..(w + 1) {
            for w2 in 0..(w + 1) {
                if check(a + w1, b + w2, x) {
                    println!("{} {}", a + w1, b + w2);
                    return;
                }

                if check(a + w1, b - w2, x) {
                    println!("{} {}", a + w1, b - w2);
                    return;
                }

                if check(a - w1, b - w2, x) {
                    println!("{} {}", a - w1, b - w2);
                    return;
                }
            }
        }

        w += 1;
    }
}

fn check(a: i128, b: i128, x: i128) -> bool {
    if (a.pow(5) - b.pow(5)) == x {
        return true;
    } else {
        return false;
    }
}


Measured memory_bytes: 2168
import sys
import cmath
input = sys.stdin.buffer.readline
pi = cmath.pi
exp = cmath.exp

""" https://tjkendev.github.io/procon-library/python/fft/fft.html
"""

def make_exp_t(fn, base):
    exp_t = {0: 1}
    temp = fn
    while temp:
        exp_t[temp] = exp(base / temp)
        temp >>= 1
    return exp_t

def fft_dfs(f, s, fn, st, exp_t):
    if fn==2:
        a = f[s]; b = f[s+st]
        return [a+b, a-b]
    fn2 = fn//2; st2 = st*2
    F0 = fft_dfs(f, s   , fn2, st2, exp_t)
    F1 = fft_dfs(f, s+st, fn2, st2, exp_t)
    w = exp_t[fn]; wk = 1.0
    for k in range(fn2):
        U = F0[k]; V = wk * F1[k]
        F0[k] = U + V
        F1[k] = U - V
        wk *= w
    F0.extend(F1)
    return F0

def fft_init(n: int):
    fn = 2**(n-1).bit_length()
    fft_exp_t = make_exp_t(fn, -2j*pi)
    ifft_exp_t = make_exp_t(fn, 2j*pi)

    def fft(f):
        if fn==1: return f
        F = fft_dfs(f, 0, fn, 1, fft_exp_t)
        return F

    def ifft(F):
        if fn==1: return F
        f = fft_dfs(F, 0, fn, 1, ifft_exp_t)
        f = [x/fn for x in f]
        return f

    return fn, fft, ifft

def pad(f, fn):
    return f + [0,]*max(0, fn-len(f))

def roll(f, shift):
    return f[-shift:] + f[:-shift]

def main():
    N, M = map(int, input().split())
    vA = list(map(int, input().split()))
    nH = 10**5 + 1
    vH = [0,]*nH
    for a in vA:
        vH[a] += 1

    fn, fft, ifft = fft_init(nH*2)
    vH = pad(vH, fn)
    #vB = pad(vB, fn)
    vB = roll(vH, 1)

    fA = fft(vH)
    fB = fft(vB)
    fC = [a*b for a,b in zip(fA,fB)]
    vC = ifft(fC)
    rC = [int(x.real+.5) for x in vC]
    print(*rC[50:70], sep=" ", file=sys.stderr)

    res = 0
    for i,c in zip(reversed(range(len(rC))),rC[::-1]):
        if M>=c:
            res += (i-1)*c
            M -= c
        else:
            res += (i-1)*M
            break
    print(res)

if __name__ == "__main__":
    main()


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

int main() {
  cout << fixed << setprecision(15);
  double a, b, x; cin >>a >>b >>x;
  // 縦b, 横y, 面積x/aの三角形の角度cを考える
  // b * y / 2 = x/aよりy = 2x/ab
  // tan(c) = b/y = abb/2x
  // c = arctan(abb/2x)
  // x/a > a*b/2 == 2x > a*a*b
  if (x > a*a*b/2){
    cout <<atan((2*b-2*x/(a*a))/a)*180/M_PI <<endl;
  }else{
    cout <<atan(a*b*b/(2*x))*180/M_PI <<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 1e5+5;

int main()

{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n;

    cin >> n;

    for (int i = 1; i*i <= n; i++) {

        if (n%i == 0 && i <= 9 && n/i <= 9) {

            cout << "Yes";
            return 0;
        }
    }

    cout << "No";

    return 0;
}


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

void trace(int A[],int  N) {
	int i;
	for (i = 0; i < N; i++) {
		if (i > 0) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}

void insertionSort(int A[], int N) {
	int i, j, v;
	for (i = 1; i < N; i++) {
		v = A[i];
	
		for (j = i - 1; j >= 0 && A[j] > v;j--) {
			A[j + 1] = A[j];
			
		}
		A[j + 1] = v;
		trace(A, N);
	}
	
}

int main()
{
	int A[100];
	int N, i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &A[i]);

	trace(A, N);
	insertionSort(A, N);



	return 0;
}




Measured memory_bytes: 3216
#include<iostream>
using namespace std;
int main() {
	int a, b, c, d, f;
	double e;
	cin >> a >> b >> c >> d >> e >> f;
	a *= 100;
	b *= 100;
	e = e / (e + 100) * 100;
	int x = 0, y = 0;
	double sugar, sugar_water;
	double nodo;
	double nodomax = -1;
	double anssugar, anssugar_water;
	for (int ai = 0;ai*a <= f;ai++) {
		for (int bi = 0;ai*a + bi*b <= f;bi++) {
			for (int ci = 0;ai*a + bi*b + ci*c <= f;ci++) {
				for (int di = 0;ai*a + bi*b + ci*c + di*d <= f;di++) {
					sugar = ci*c + di*d;
					sugar_water = sugar + ai*a + bi*b;
					nodo = sugar / sugar_water * 100;
					if (e < nodo) {
						break;
					}
					if (e == nodo) {
						cout << sugar_water << " " << sugar << endl;
						return 0;
					}
					else {
						if (nodomax < nodo) {
							anssugar = sugar;
							anssugar_water = sugar_water;
							nodomax = nodo;
						}
					}
				}
			}
		}
	}
	cout << anssugar_water << " " << anssugar << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
if N%2==0:
  B = [A[i] for i in range(N) if i%2==0]
  C = [A[(N-i-1)] for i in range(N) if (N-i-1)%2==1]
  print(*C+B)
else:
  B = [A[i] for i in range(N) if i%2==1]
  C = [A[(N-i-1)] for i in range(N) if (N-i-1)%2==0]
  print(*C+B)

Measured memory_bytes: 30868
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define M 1000000007
#define all(a) (a).begin(),(a).end()
#define rep(i,n) reps(i,0,n)
#define reps(i,m,n) for(int i=(m);i<(n);i++)
int main(){
  int n,m,k;cin>>n>>m>>k;
  vector<int> a(n),b(m);
  int ma=M,mb=M;
  rep(i,n){
    cin>>a[i];
    chmin(ma,a[i]);
  }
  rep(i,m){
    cin>>b[i];
    chmin(mb,b[i]);
  }
  int mc=ma+mb;
  rep(i,k){
    int x,y,z;
    cin>>x>>y>>z;
    chmin(mc,a[x-1]+b[y-1]-z);
  }
  cout<<mc;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        long a = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        long c = Long.parseLong(sc.next());
        long d = Long.parseLong(sc.next());
        sc.close();

        // 主処理
        long mlta = Math.max(a * c, a * d);
        long mltb = Math.max(b * c, b * d);
        long result = Math.max(mlta, mltb);

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


Measured memory_bytes: 35632
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>

using namespace std;

const int MAX=1e5+10;

struct {
	int t,x,y;
}point[MAX];

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&point[i].t,&point[i].x,&point[i].y);
	}
	int a=point[0].t;
	int b=abs(point[0].x);
	int c=abs(point[0].y);
	bool flag=true;
	for(int i=0;i<n;i++){
		int u;	
		if(b+c!=0){
			u=a%(b+c);
			if(u%2==0&&a>=(c+b)){
				a=point[i+1].t-point[i].t;
				b=abs(point[i+1].x-point[i].x);
				c=abs(point[i+1].y-point[i].y);
			}
			else{
				flag=0;
				cout<<"No"<<endl;
				break;
			}
		}
		else
		{
			if(a%2==0&&a>=0)
			{
				a=point[i].t-a;
				b=abs(point[i].x-point[i-1].x);
				c=abs(point[i].y-point[i-1].y);
			}
			else{
				flag=0;
				cout<<"No"<<endl;
				break;
			}
		}
	}
	if(flag)
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <cstdlib>
#include <sstream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define sz size()

const double EPS = 1e-10;
const int INF = 100000000;

bool is(int n){
    if(n==1)return false;
    if(n==2)return true;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)return false;
    }
    return true;
}

int main(){
    int n;
    int c=0;
    while(cin>>n){
        c=0;
        for(int i=1;i<n;i++){
            if(is(i) && is(n-i+1)){
                c++;

            }
        }
        cout<<c<<endl;
    }

    
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

int bitcount( const int b )
{
	int res = 0;
	REP( i, 0, 10 )
	{
		res += b & 1 << i ? 1 : 0;
	}
	return res;
}

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

	for ( string line; getline( cin, line ); )
	{
		int n, s;
		{
			ISS iss( line );
			iss >> n >> s;
		}

		VVI dp( 1 << 10, VI( s + 1, 0 ) );
		dp[0][0] = 1;

		int res = 0;
		REP( bits, 0, 1 << 10 )
		{
			const int num_bits = bitcount( bits );
			if ( n < num_bits )
			{
				continue;
			}

			REP( i, 0, s + 1 )
			{
				if ( num_bits == n && i == s )
				{
					res += dp[ bits ][i];
				}

				REP( j, 0, 10 )
				{
					if ( bits & 1 << j || s < i + j * ( num_bits + 1 ) )
					{
						continue;
					}
					dp[ bits | 1 << j ][ i + j * ( num_bits + 1 ) ] += dp[ bits ][i];
				}
			}
		}

		cout << res << endl;
	}

	return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> d(N);
  for(auto i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    ++d[a];
    ++d[b];
  }
  cout << (any_of(begin(d), end(d), [](auto i) {return i&1;}) ? "NO" : "YES") << endl;
}


Measured memory_bytes: 640
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
import Data.Array.Unboxed
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete

maximumOrDefault d xs = if null xs then d else maximum xs
pairs [] = []
pairs (x:xs) = [(x,y) | y <- xs] ++ pairs xs

main = do
    n <- getInt
    when (n/=0) $ do
        ds <- map (apply2 (,)) <$> replicateM n getInts
        let set = Set.fromList ds
        print $ maximumOrDefault 0 [dx ^ 2 + dy ^ 2| ((x1,y1),(x2,y2)) <- pairs ds, (x1/=x2 || y1/=y2), let dx = x2 - x1, let dy = y2 - y1, Set.member (x1-dy,y1+dx) set, Set.member (x2-dy,y2+dx) set]
        main

Measured memory_bytes: 36956
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL)
#define INF LONG_MAX
#define io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

int32_t main()
{
    //io;
    boost;
    int n;
    cin>>n;
    int a[n],f=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==1)
            f=1;
    }
    if(!f)
    {
        cout<<-1<<endl;
        return 0;
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]==ans+1)
            ans++;
    }
    cout<<n-ans<<endl;
}



Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(inti=a;i<=b;i++)

#define MOD 1000000007
typedef long long int ll;
typedef vector<int>vi;
typedef pair<int,int>pi;


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

string s ,t;
cin>>s>>t;

bool ans = true;

int sum=0;
for(char c : s)
{
    for(char l:t)
        if(c<l)
    {
        cout<<"Yes"<<endl;
        return 0;
    }else if(c==l)
    sum++;
}
if(sum==t.size()*s.size()&&s.size()<t.size())
    cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
 return 0;
}


Measured memory_bytes: 3616
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll d[33][33];
ll dd[1001][1001];

int main() {
  ll n, c;
  cin >> n >> c;
  rep(y, 0, c) {
    rep(x, 0, c) {
      ll a;
      cin >> a;
      d[y][x] = a;
    }
  }
  rep(y, 0, n) {
    rep(x, 0, n) {
      ll a;
      cin >> a;
      dd[y][x] = a;
    }
  }
  ll mn[3][30];
  rep(i,0,3)rep(j,0,30)mn[i][j] = 1000000000;
  rep(t, 0, 3) {
    rep(i, 0, c) {
      ll b = 0;
      rep(y, 0, n) {
        rep(x, 0, n) {
          if ((x + y) % 3 == t) {
            b += d[dd[y][x] - 1][i];
          }
        }
      }
      mn[t][i] = b;
    }
  }
  ll ans = 1000000000;
  rep(i,0,30){
    rep(j,0,30){
      rep(k,0,30){
        if(i==j)continue;
        if(i==k)continue;
        if(j==k)continue;
        ans = min(ans,mn[0][i]+mn[1][j]+mn[2][k]);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4352
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def prime_factorization(n, res):
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        ex = 0
        while n % i == 0:
            n = n // i
            ex += 1
        res[i] = res.get(i, 0) + ex
    if n != 1:
        res[n] = res.get(n, 0) + 1
    return res

def solve():
    N = II()

    # print(make_divisors(120))
    memo = {}
    for i in range(1, N+1):
        memo = prime_factorization(i, memo)

    # print(memo)

    def e(num):
        res = 0
        for v in memo.values():
            if v >= num:
               res += 1
        return res

    ans = 0
    # 2 * 4 * 4
    ans += e(4) * (e(4) - 1) * (e(2) - 2) // 2


    # 4 * 14
    ans += (e(4) - 1) * e(14)

    # 2 * 24
    ans += (e(2) - 1) * e(24)

    # 74
    ans += e(74)

    print(ans)



if __name__ == '__main__':
    solve()


Measured memory_bytes: 3188
#[allow(dead_code)]
fn rd() -> String {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    input.trim().to_owned()
}

/// 1行の文字を空白で分割してVec<T>にする。
#[allow(dead_code)]
fn rd_vec<T : std::str::FromStr>() -> Vec<T> {
    rd().split_whitespace().map(|x| x.parse().ok().unwrap()).collect()
}

/// 1つの要素を入力で受け取る
#[allow(dead_code)]
fn rd_one<T : std::str::FromStr>() -> T {
    rd().parse().ok().unwrap()
}

/// 複数回read_splitを行う
#[allow(dead_code)]
fn rd_vec_mul<T : std::str::FromStr>(count : i32) -> Vec<Vec<T>> {
    (0..count).map(|_| rd_vec()).collect()
}

/// Vecを1列で出力する
#[allow(dead_code)]
fn op_vec<T : std::fmt::Display>(item : Vec<T>, splitter : char) {
    let cnt = item.len();
    let mut c = 0;
    for i in item.iter() {
        c+=1;
        if cnt > c {print!("{}{}", i, splitter);} else {println!("{}", i);}
    }
}

fn main() {
    let input : Vec<i32> = rd_vec();
    let n : Vec<i32> = rd_vec();
    let mut answer = 0;
    for i in n {
        if input[1] <= i {answer += 1};
    }
    println!("{}", answer);
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main()
{
  int h,w,k;
  cin >> h >> w >> k;
  vector<string> s(h);
  rep(i,h){
    cin >> s[i];
  }

  vector<vector<int>> res(h,vector<int>(w,0));
  int cnt=0;
  int kk=1;
  rep(i,h){
    bool f=true;
    rep(j,w){
      if(s[i][j]=='#'){
	if(f){
	  rep(l,j+1){
	    res[i][l]=kk;
	  }
	  f=false;	  
	}
	else{
	  kk++;
	  res[i][j]=kk;
	}
      }
      else{
	if(!f){
	  res[i][j]=kk;
	}
      }
    }
    if(f){
      cnt++;
    }
    else{
      rep1(l,cnt){
    	rep(j,w){
    	  res[i-l][j]=res[i][j];
    	}
      }
      cnt=0;
      kk++;
    }
  }
  if(cnt!=0){
    rep1(i,cnt){
      rep(j,w){
	res[h-1-cnt+i][j]=res[h-1-cnt][j];
      }
    }

  }

  
  rep(i,h){
    rep(j,w){
      cout <<  res[i][j] << " ";
    }
    cout  << "\n";
  }
  
  
  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<N;i++)
#define INF 1e9
typedef long long LL;
const LL MOD = 1e9+7;

int main() {
  LL N, K;
  cin >> N >> K;
  
  vector<vector<LL>> dp(2001, vector<LL>(2001));
  
  for (int i = 0; i <= N; i++) {
    dp[i][0] = 1;
    dp[i][i] = 1;
  }
  
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j < i; j++) {
      dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
      dp[i][j] %= MOD;
    }
  }
  
  for (int i = 1; i <= K; i++) {
    cout << (dp[N-K+1][i] * dp[K-1][i-1]) % MOD << endl;
  }
  
  return 0;
}

Measured memory_bytes: 31616
N = int(input())
A=[]
B=[]

for i in range(N):
  cyc = int(input())
  A.append(cyc)
  B.append([])
  for t in range(cyc):
    Ar = list(map(int,input().split()))
    B[i].append(Ar)

rep_10 = 2**N
Ans=0
for i in range(rep_10):
  rep_2 = bin(i)
  mem_list = list(rep_2)
  del mem_list[0:2]
  mem_list = list(map(int,mem_list))
  while len(mem_list)<N:
    mem_list = [0]+mem_list

  for t in range(N):
    cnt=0
    if mem_list[t]==1:
      for s in range(A[t]):
        u = B[t][s][0] - 1
        if (mem_list[u])!=(B[t][s][1]):
          cnt+=1
    if cnt!=0:
      break
  if (cnt==0)and(Ans<sum(mem_list)):
    Ans=sum(mem_list)

print(Ans)
      



Measured memory_bytes: 3064
require 'set'; require 'prime'
INF=Float::INFINITY; MOD=10**9+7
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

a.sort!
a.reverse!
rui = Array.new(n,0)
rui[-1] = a.last
(n-1).downto(1) do |i|
  rui[i-1] = rui[i] + a[i-1]
end

ans = 1
(n-1).times do |i|
  break if a[i] > rui[i+1] * 2
  ans += 1
end

puts ans


Measured memory_bytes: 10804
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l;
    cin >> n >> l;
    vll a(n);
    REP(i,n) cin >> a[i];
    REP(i,n-1){
        if(a[i]+a[i+1]>=l){
            cout << "Possible\n";
            for(int j=0;j<i;j++){
                cout << j+1 << endl;
            }
            for(int j=n-2;j>i;j--){
                cout << j+1 << endl;
            }
            cout << i+1 << endl;
            return 0;
        }
    }
    cout << "Impossible\n";
    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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

vector<int> to[1010];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        to[a].push_back(b);
    }

    int mi = N + 1;
    vector<int> ans;
    REP(i,N){
        vector<int> dist(N, -1);
        vector<int> prev(N, -1);
        queue<int> q;
        q.push(i);
        dist[i] = 0;
        while(!q.empty()){
            auto v = q.front(); q.pop();
            for(auto nv : to[v]){
                if(dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                prev[nv] = v;
                q.push(nv);
            }
        }
        REP(t, N){
            if(t == i || dist[t] == -1) continue;
            for(auto nt : to[t]){
                if(nt == i){
                    vector<int> tmp({i});
                    int cur = t;
                    while(cur != i) tmp.push_back(cur), cur = prev[cur];
                    if(mi > tmp.size()){
                        mi = tmp.size();
                        ans = tmp;
                    }
                }
            }
        }
    }
    if(mi == N + 1) cout << -1 << endl;
    else{
        cout << ans.size() << endl;
        for(auto v : ans) cout << v + 1 << endl;
    }
}

Measured memory_bytes: 384
H, W = map(int, input().split())

b = []
b.append('.' * (W + 2))

for i in range(H):
    s = input()
    b.append('.' + s + '.')

b.append('.' * (W + 2))

r = True

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if b[i][j] == '#':
            # print(i, j)
            if b[i][j-1] == '#':
                pass
            elif b[i][j+1] == '#':
                pass
            elif b[i-1][j] == '#':
                pass
            elif b[i+1][j] == '#':
                pass
            else:
                r = False

if r:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main() {
	int a, b,x[30][30],y[30],p=0,o=0;
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> y[i];
		for (int j = 0; j < y[i]; j++) {
			cin >> x[i][j];
		}
	}
	for (int i = 1; i <= b; i++) {
		for (int j = 0; j < a; j++) {
			for (int l = 0; l < y[j]; l++) {
				if (x[j][l] == i)p++;
			}
		}
		if (p == a)o++;
		p = 0;
	}
	cout << o << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;


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

  int ans = 0;
  for(int i = 0;i<4;i++){
    if(S.at(i) == '+'){
      ans++;
    }
    else{
      ans--;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
template
<   
    typename TYPE,
    std::size_t SIZE
>
std::size_t array_length(const TYPE (&)[SIZE])
{   
    return SIZE;
}

int main() {
    int N,W;
  
    vector<string> vec;  // 座標を受け取る配列
    cin >> N >> W;
    
    vec.resize(N); for (int i = 0; i < N; ++i) cin >> vec[i];
  
 int a[N];
 int b[W];
  
for(int i = 0;i<N;i++){
  int ans = 0;
  
  for(int j = 0;j<W;j++){
   
    if(vec[i][j]=='.'){
       
      ans++;
    }
    
  }
   
  if(W == ans){
   a[i] = 9999;
  }
   
}
  
  int bnum = 0;
  
  for(int i = 0;i<W;i++){
  int ans = 0;
    
   for(int j = 0;j<N;j++){
    if(vec[j][i]=='.'){
       
      ans++;
    }
        
     }
    if(N == ans){
   b[i] = 9999;
      bnum++;
  }
   //if(vec[0][i]==vec[1][i]&&vec[1][i]==vec[2][i]&&vec[2][i]==vec[3][i]){
  
   //   b[i] = 100;
  //    bnum++;
  // }

   
}
  
 
  for(int i = 0;i<N;i++){
    
    if(a[i]==9999){
    
      continue;
    }
    
    for(int j = 0;j<W;j++){
      
      if(b[j]==9999){
    
      continue;
     }
      
     
        cout << vec[i][j];
      
    }
    
     
       
        cout << endl;
      
  }
   
  
  return 0;
}

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

int main() { 
	int N, M, X;
	int less=0;
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		
		if (x < X) {
			less++;
		}
	}

	cout << min(less, M - less);
	cin >> N;
	return 0; 
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c) {
  stack<int> S;
  S.push(r);
  color[r] = c;
  while ( !S.empty() ) {
    int u = S.top();
    S.pop();
    for (int i = 0; i < G[u].size(); i++) {
      int v = G[u][i];
      if (color[v] == NIL) {
        color[v] = c;
        S.push(v);
      }
    }
  }
}

void assignColor() {
  int id = 1;
  for (int i = 0; i < n; i++) color[i] = NIL;
  for (int u = 0; u < n; u++) {
    if (color[u] == NIL) dfs(u, id++);
  }
}

int main() {
  int s, t, m, q;

  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    cin >> s >> t;
    G[s].push_back(t);
    G[t].push_back(s);
  }

  assignColor();

  cin >> q;

  for (int i = 0; i < q; i++) {
    cin >> s >> t;
    if (color[s] == color[t]) {
      cout << "yes" << endl;
    } else {
      cout << "no" << endl;
    }
  }

  return 0;

}


Measured memory_bytes: 8984
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for(int i= 0; i < n ; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  int ta, tb;
  ta =0;
  tb =0;
  for(int i=0;i <n; i++){
    ta = ta+ vec.at(i);
    i++;
    if(i < n){
    tb = tb + vec.at(i);
    }
  }
  cout << ta -tb << endl;
}
    

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int main(){
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    if(A == B && A != C){
        printf("Yes");
    }else if(B == C && A != B){
        printf("Yes");
    }else if(A == C && A != B){
        printf("Yes");
    }else{
        printf("No");
    }
    return 0;

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const ll mod = 998244353;
char a[maxn];
ll b[maxn];
int main()
{
    int n,k;
    while(cin>>n>>k)
    {
        scanf("%s",a);
        a[k-1] = a[k-1] - 'A' + 'a';
        printf("%s\n",a);
    }
}




















Measured memory_bytes: 2304
#include <iostream>
#define ull unsigned long long
using namespace std;
const int N = 1005;
const int mod = 1e9 + 7;
char grid[N][N];
ull dp[N][N];
int r, c;
ull countPath(int i, int j) {
	if ( i < 1 || i > r || j < 1 || j > c || grid[i][j] == '#') {
		return 0;
	}
	if (dp[i][j] != 0) {
		return dp[i][j];
	}
	if ( i == r && j == c) {
		return 1;
	}
	dp[i][j] += countPath(i + 1, j) % mod;
	dp[i][j] += countPath(i, j + 1) % mod;
	return dp[i][j] % mod;
}
void buttomUp() {
	int i = 1;
	while ( i <= r && grid[i][1] == '.') dp[i][1] = 1, i++;
	int j = 1;
	while ( j <= c && grid[1][j] == '.') dp[1][j] = 1, j++;
	for (int i = 2; i <= r; i++) {
		for (int j = 2; j <= c; j++) {
			if (grid[i][j] != '#') {
				dp[i][j] = (dp[i][j -1] + dp[i - 1][j]) % mod;
			}
		}
	}
	cout << dp[r][c] % mod;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> grid[i][j];
		}
	
	}
	buttomUp();
	//cout << countPath(1, 1);
	return 0;
}


Measured memory_bytes: 9088
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

template <class Weight>
constexpr Weight inf=(Weight(1)<<(8*sizeof (Weight)-3));

template <class Weight>
class WeightedUnionFind {
  std::vector<intmax_t> tree;
  std::vector<Weight> cost;

public:
  WeightedUnionFind(size_t n): tree(n, -1), cost(n) {}

  size_t find(size_t v) {
    if (tree[v] < 0)
      return v;

    size_t r=find(tree[v]);
    cost[v] += cost[tree[v]];
    return (tree[v] = r);
  }

  bool unite(size_t u, size_t v, Weight w) {
    size_t ru=find(u), rv=find(v);
    if (ru == rv)
      return false;  // FIXME assuming no multi-edges

    w -= cost[u]-cost[v];
    if (-tree[ru] >= -tree[rv]) {
      std::swap(ru, rv);
      std::swap(u, v);
      w = -w;
    }
    tree[rv] += tree[ru];
    tree[ru] = rv;
    cost[ru] = w;
    return true;
  }

  bool connected(size_t u, size_t v) {
    return (find(u) == find(v));
  }

  Weight diff(size_t u, size_t v) {
    return connected(u, v)? (cost[u]-cost[v]):inf<Weight>;
  }

  size_t size(size_t v) {
    return -tree[find(v)];
  }
};

int main() {
  size_t N;
  int M;
  scanf("%zu %d", &N, &M);

  WeightedUnionFind<intmax_t> uf(N);

  for (int i=0; i<M; ++i) {
    size_t L, R;
    intmax_t D;
    scanf("%zu %zu %jd", &L, &R, &D);

    --L;
    --R;
    if (!uf.connected(L, R)) {
      uf.unite(L, R, D);
    } else if (uf.diff(L, R) != D) {
      printf("No\n");
      return 0;
    }
  }

  printf("Yes\n");
}


Measured memory_bytes: 1920
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 21/01/2018 12:21:41
	flamers will **** you
*/
#include<bits/stdc++.h>
//#include<flamers.h>
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define POB pop_back
#define dist(a, b) sqrt(a*a + b*b)
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vipi;
bool compare(pi p1, pi p2){
	 if(1) return true;
	 return false;
}

int main(){
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	long long n, t1, t2, x1, x2, y1, y2;
	cin>>n;
	t1 = 0; x1 = 0; y1 = 0;
	bool flag = true;
	for(int i = 0; i < n; i++){
		cin>>t2>>x2>>y2;
		if(abs(x2 - x1) + abs(y2 - y1) > t2 - t1) flag = false;
		else if((t2 - t1 - abs(x2 - x1) - abs(y2 - y1)) % 2 != 0) flag = false;
		t1 = t2; x1 = x2; y1 = y2;
	}
	if(flag) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
//
// Created by yamunaku on 2019/11/05.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int main(){
    int n;
    cin >> n;
    vi ans(n);
    int a;
    rep(i,n){
        cin >> a;
        ans[a-1]=i+1;
    }
    rep(i,n){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N;
  cin>>N;
  vector<ll>A(N+1);
  vector<ll>B(N);
  for(ll i=0;i<N+1;i++)cin>>A[i];
  for(ll i=0;i<N;i++)cin>>B[i];
  ll ans=0;
  for(ll i=0;i<N;i++){
    if(A[i]<=B[i]){
      ans+=A[i];
      B[i]-=A[i];
    }else{
      ans+=B[i];
      B[i]=0;
    }
    if(A[i+1]<=B[i]){
      ans+=A[i+1];
      A[i+1]=0;
    }else{
      ans+=B[i];
      A[i+1]-=B[i];
      B[i]=0;
    }
    //cout<<ans<<endl;
  }
  cout<<ans<<endl;

  
}

Measured memory_bytes: 4756
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if (l[i]!=l[j]) and (l[j]!=l[k]) and (l[k]!=l[i]):
                if l[j]-l[i] < l[k] < l[i]+l[j]:
                    ans += 1

print(ans)

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

int s[200002];
map<int,int> mp;

int main(){
	int n;
	cin>>n;
	for (int i=0;i<n;i++){
		cin>>s[i];
		mp[s[i]]++;
	}
	for (int i=0;i<n;i++)
		if (mp[s[i]]>1){
			cout<<"NO"<<endl;
			return 0;
		}
	cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 10368
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
using namespace std;
long long int n, q, m, p[20000] = {}, a[300000] = {}, b, lef[200000], h, w, tab[500][500] = {}, same = 0, qu[300000], rui[300000] = {}, giza[300000] = {}, res[300000] = {};
int nibutan(long long int check,int left,int right) {
	
	int nibu = (left + right) / 2;
	if (right-left==1&& check < lef[nibu]) {
		return nibu+1;
	}

	if (check >= lef[nibu]&&check<lef[nibu-1]) {
		return nibu;
	}
	else if (check >= lef[nibu]) {

		return nibutan(check, left, nibu);
	}
	else {
		return nibutan(check, nibu, right);
	}
}

int main() {
	
	string str[600];
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		rui[i] = rui[i - 1] + a[i];
		
	}
	for (int i = 1; i <= q; i++) {
		cin >> qu[i];
	}
	giza[1] = a[1];
	for (int i = 2; i <= n; i++) {
		
		giza[i] = giza[i - 2] + a[i];

	}
	res[0] = giza[n];
	res[1] = giza[n];

	for (int i =2; i <= n/2; i++) {

		res[i] = rui[n] - rui[n - i] + giza[n - 2 * i];
		
	}
	res[n / 2 + 1] = rui[n] - rui[n / 2];

	for (int i = 0; i <= n/2; i++) {
		lef[i] = (a[n - i] + a[n - 2 * i]) / 2 + 1;
		

	}
	lef[n / 2 + 1] = 0;

	for (int i = 1; i <= q; i++) {
		if (qu[i] > a[n]) { cout << res[0] << endl; }
		else {
			cout << res[nibutan(qu[i], 0, n / 2 + 1)] << endl;
		}
	}
}

Measured memory_bytes: 12288