akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int parent ,left ,right;};

struct Node T[MAX];
int n , D[MAX] , H[MAX];

void setDepth(int u , int d)
{
	if( u == NIL) return;
	D[u] = d;
	setDepth(T[u].left,d+1);
	setDepth(T[u].right,d+1);
}

int setHeight(int u)
{
	int h1 = 0 , h2 = 0;
	if(T[u].left != NIL)
	h1 = setHeight(T[u].left)+1;
	if(T[u].right != NIL)
	h2 = setHeight(T[u].right)+1;
	return H[u] = (h1 > h2 ? h1 : h2);
}

//節点uの兄弟を返す
int getSibling(int u)
{
	if( T[u].parent == NIL) return NIL;
	if(T[T[u].parent].left != u && T[T[u].parent].left != NIL)
	return T[T[u].parent].left;
	if(T[T[u].parent].right!=u && T[T[u].parent].right!= NIL)
	return T[T[u].parent].right;
	return NIL;
}

void print(int u)
{
	printf("node %d: ",u);
	printf("parent = %d, ",T[u].parent);
	printf("sibling = %d, ",getSibling(u));
	int deg = 0;
	if(T[u].left != NIL) deg++;
	if(T[u].right != NIL) deg++;
	printf("degree = %d, ",deg);
	printf("depth = %d, ",D[u]);
	printf("height = %d, ",H[u]);
	
	if(T[u].parent == NIL)
	{
		printf("root\n");
	}
	else if(T[u].left == NIL && T[u].right == NIL)
	{
		printf("leaf\n");
	}
	else{
		printf("internal node\n");
	}
}

int main()
{
	int v , l , r , root = 0;
	scanf("%d",&n);
	
	for( int i = 0;i < n; i++) T[i].parent = NIL;
	
	for( int i = 0; i < n; i++)
	{
		scanf("%d %d %d",&v,&l,&r);
		T[v].left = l;
		T[v].right = r;
		if(l != NIL) T[l].parent = v;
		if(r != NIL) T[r].parent = v;
	}
	
	for( int i = 0; i < n; i++) if(T[i].parent == NIL) root = i;
	
	setDepth(root,0);
	setHeight(root);
	
	for(int i = 0; i < n; i++) print(i);

	return 0;
}




Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
#define AB_BHI_NI_DEGI                \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
int mod = 1e9 + 7;
//int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double
#define endl "\n"

void solve()
{
    int x, k, d;
    cin >> x >> k >> d;
    int y = abs(x) / d;
    if (y < k)
    {
        k -= y;
        int dd = y * d;
        if (x < 0)
            x += dd;
        else if (x > 0)
            x -= dd;
        else
        {
            k += y;
            if (k % 2)
                cout << d << "\n";
            else
                cout << 0 << "\n";
            return;
        }
        int ans = abs(x);
        if (k % 2)
        {
            int temp = inf;
            temp = min(abs(x - d), abs(x + d));
            ans = temp;
        }
        x = ans;
        cout << abs(x) << "\n";
    }
    else
    {
        if (x < 0)
            x += k * d;
        else if (x > 0)
            x -= k * d;
        else
        {
            if (k % 2)
                cout << d << "\n";
            else
                cout << 0 << "\n";
            return;
        }
        cout << abs(x) << "\n";
    }
}
int32_t main()
{
    AB_BHI_NI_DEGI
    int Test = 1;
    //cin >> Test;
    //init();
    while (Test--)
        solve();
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <map>
#include <ctime>
#include <cstdlib>
#include <random>
using namespace std;

int n;
int x[200];
int ans = 1e9;

int main(){
	cin >> n;
	for(int i = 0; i < n; i++)cin >> x[i];
	for(int i = 0; i <= 100; i++){
		int val = 0;
		for(int j = 0; j < n; j++){
			val += (x[j] - i)*(x[j] - i);
		}
		if(val < ans)ans = val;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = 26
d = int(input())
c = list(map(int,input().split()))
s = [[] for i in range(d)]
for i in range(d):
    s[i] = list(map(int,input().split()))

last = [0]*n
import copy
for i in range(d):
    m = -float('inf')
    ind = 0
    for k in range(n):
        x = s[i][k]
        buf = copy.copy(last)
        buf[k] = i+1
        for j in range(n):
            x -= c[j]*(i-buf[j]+1)
        if m<x:
            ind = k
            m = x
    last[ind] = i  
    print(ind+1)


Measured memory_bytes: 69912
//TODO:あとで直す
import java.util.*;
import java.io.*; 
 
class Main { 
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
      	PrintWriter out = new PrintWriter(System.out);
        out.println(Math.max(sc.nextInt() - sc.nextInt(), 0));
      	out.flush();
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    private boolean hasNext() { skipUnprintable(); return hasNextByte();}

    public int nextInt() {
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
}


Measured memory_bytes: 21204
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, s;
};

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

	string str;

	cin >> str;

	map<pair<string,string>,ll> l,r;
	
	int mask = 0;

	REP(i, n) mask |=( 1 << i );

	for (int c = 0; bitcheck(c, n) != 1; c++) {

		if ((c ^ mask) < c) continue;

		{
			string a1, b1, a2, b2;

			REP(i, n) {
				if (bitcheck(c, i)) {
					a1 += str[i];
				}
				else b1 += str[i];
			}

			a2 = b1;
			reverse(ALL(b1));

			b2 = a1;
			reverse(ALL(b2));

			l[MP(a1, b1)]++;
			l[MP(a2, b2)]++;
		}
		{
			string a1, b1, a2, b2;
			rep(i,n, n*2) {
				if (bitcheck(c, (i-n))) {
					a1 += str[i];
				}
				else b1 += str[i];
			}

			a2 = b1;
			reverse(ALL(b1));

			b2 = a1;
			reverse(ALL(b2));

			r[MP(b1, a1)]++;
			r[MP(b2, a2)]++;
		}
	}

	ll ans = 0;
	for (auto itr : l) {
		if (r[itr.first] != 0)
			printf("");
		ans += itr.second * r[itr.first];
	}

	cout << ans << endl;
	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int n = s.size();

  string s2 = "";
  for(int i=n-1;i>=0;i--) {
    if(s[i] == 'x')
      continue;
    s2 += s[i];
  }
  string s3 = "";
  for(int i=0;i<n;i++) {
    if(s[i] == 'x')
      continue;
    s3 += s[i];
  }
  int sz = (s3.size()+1)/2;
  if(s3 != s2) {
    cout << - 1 << endl;
    return 0;
  }
  int f = 0, b = n-1;
  int ans = 0;
  int num = 0;
  while(true) {
    if(num >= sz)
      break;
    int f_cnt = 0, b_cnt = 0;
    if(s[f] == 'x') {
      while(f < n && s[f] == 'x') {
        f_cnt++;
        f++;
      }
    }
    if(s[b] == 'x') {
      while(b >= 0 && s[b] == 'x') {
        b_cnt++;
        b--;
      }
    }
    ans += abs(f_cnt - b_cnt);
    f++;
    b--;

    num++;
    if(f >= b) {
      break;
    }
  }
  cout << ans << endl;

}


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

struct st{
	st *linkk[27];
	st *up;
	int cnt;
	int belong;
	int att;
	int val;
	int en;
	st(){
		for (int i = 0; i < 27; i++){
			linkk[i] = NULL;
		}
		cnt = 0;
		en = 0;
	}
};


int n;
int q;

#define MAX 400002

char buf[MAX];

vector<string> v;




st linkk2[MAX];
int ord = 0;
st *neww(){
	ord++;
	return &linkk2[ord - 1];
}


st *root;
vector<st*> lis;

void ins(string a){
	st *b = root;
	for (int i = 0; i < a.size(); i++){
		if (b->linkk[a[i] - 'a'] == NULL){
			b->linkk[a[i] - 'a'] = neww();
			b->linkk[a[i] - 'a']->up = b;
		}
		b = b->linkk[a[i] - 'a'];
	}
	b->en++;
	lis.push_back(b);
}

inline void dfs(st *b){
	bool f = false;
	b->cnt = b->en;
	for (int i = 0; i < 26; i++){
		if (b->linkk[i] != NULL){
			f = true;
			b->linkk[i]->val = i;
			dfs(b->linkk[i]);
			b->cnt += b->linkk[i]->cnt;
		}
	}
}

map < st*, vector<pair<string, int> > > mp;

int store[27][27];
int outt[MAX];
int F = 0;
inline void dfs2(st *b){
	F += b->en;
	for (int i = 0; i < 26; i++){
		if (b->linkk[i] != NULL){
			for (int j = 0; j < 26; j++){
				if (i != j){
					if (b->linkk[j] != NULL){
						store[i][j] += b->linkk[j]->cnt;
					}
				}
			}
			dfs2(b->linkk[i]);
			for (int j = 0; j < 26; j++){
				if (i != j){
					if (b->linkk[j] != NULL){
						store[i][j] -= b->linkk[j]->cnt;
					}
				}
			}
		}
	}
	F-=b->en;
	if (mp.count(b)){
		vector<pair<string, int> > &V = mp[b];
		for (int i = 0; i < V.size(); i++){
			int ans = 0;
			for (int j = 0; j < 26; j++){
				for (int k = 0; k < j; k++){
					ans += store[V[i].first[j]-'a'][V[i].first[k]-'a'];
				}
			}
			outt[V[i].second] = ans+F;
		}
	}
}

int main(){
	root = neww();
	root->up = NULL;
	cin >> n;
	for (int i = 0; i < n; i++){
		scanf("%s", buf);
		v.push_back(buf);
		ins(v.back());
	}
	dfs(root);
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++){
		int id;
		scanf("%d", &id);
		id--;
		scanf("%s", buf);
		mp[lis[id]].push_back(make_pair(buf,i) );
	}
	dfs2(root);
	for (int i = 0; i < q; i++){
		printf("%d\n", outt[i] + 1);
	}
	return 0;
}


Measured memory_bytes: 129264
def gcb(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        gcb_table[a][b] = a
    else:
        if gcb_table[a][b] == -1:
            gcb_table[a][b] = gcb(b, a%b)
    return gcb_table[a][b]

k = int(input())
gcb_table = [[-1 for _ in range(k+1)] for _ in range(k+1)]

for i in range(1, k+1):
    for j in range(1, k+1):
        temp = gcb(i, j)
        gcb_table[i][j] = temp
        gcb_table[j][i] = temp
        
res = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        gcb_first = gcb_table[a][b]
        for c in range(1, k+1):
            res += gcb_table[gcb_first][c]
print(res)

Measured memory_bytes: 9384
A, B = map(int, input().split())
if A > B:
  tmp = A
  A = B
  B = tmp
_A = A
num = 2
while True:
  if A % num == 0:
    A = A / num
    if B % num == 0:
      B = B / num
  else:
    num = num + 1
    
  if A == 1:
    break
print(int(_A * B))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  ll n;
  cin >> n;
ll ans = 0;
ll a[10000005] = {0};
for(ll i = 1; i<=n ; i++){
   for(ll j = i; j<=n; j += i){
          a[j]++;
    }
 ans += i*a[i];
}
cout << ans << endl;
}



Measured memory_bytes: 81720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    stack<int> st1;
    stack<pair<int,int>> st2;

    int sum = 0;
    for(int i=0; i<s.size(); i++){
        if(s[i] == '\\'){
            st1.push(i);
        }
        else if(s[i] == '/' && st1.size()>0){
            int j = st1.top(); st1.pop();
            sum += i-j;
            int a = i-j;
            while(st2.size()>0 && st2.top().first > j){
                a += st2.top().second; st2.pop();
            }
            st2.push({j, a});
        }
    }

    // 出力
    vector<int> ans;
    while(st2.size() > 0){
        ans.push_back(st2.top().second);
        st2.pop();
    }
    reverse(ans.begin(), ans.end());

    cout << sum << endl;
    cout << ans.size();
    for(int i=0; i<ans.size(); i++) cout << " " << ans[i];

    cout << endl;
    return 0;
}


Measured memory_bytes: 3332
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#UnionFindのクラス,0-indexed
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m = map(int,ipt().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        uf.union(a-1,b-1)

    rt = uf.roots()
    ma = 0
    for i in rt:
        sz = uf.size(i)
        if ma < sz:
            ma = sz

    print(ma)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 84324
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <numeric>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const int mod = 1000000007;
const ll MOD = 1000000007;
const ll INF = 1LL << 60;


int solve()
{
   ll n;
   string s;
   cin >> n;
   cin >> s;
   map<ll, ll> m;

   for(int i=0; i < 1000; i++){
      string ss = "";
      if(i == 0){
        ss+="000";
      }else{
      if(i < 10){
         ss += "00";
      }else if(i >=10 && i < 100){
         ss += "0";
      }
      ss += to_string(i);
      }
      ll cnt = 0;
      //cout << ss << endl;
 
      for(int j=0; j < n; j++){
         //cout << ss[cnt] <<" "<< s[j];
         if (ss[cnt] == s[j])
         {
            cnt++;
         }
         if(cnt == 3){
            //cout << atoi(ss.c_str());
            m[atoi(ss.c_str())] = 1;
            break;
         }
      }
   }
   ll ans = 0;
     for(int i=0; i < 1000; i++){
      string ss = "";
      if(i == 0){
        ss +="000";
      }else if(i < 10){
         ss += "00";
      }else if(i >=10 && i < 100){
         ss += "0";
     }
      ss += to_string(i);
      ans += m[atoi(ss.c_str())];
   }
   cout << ans << endl;

   return 0;
}

int main()
{
   //cout.precision(10)
   ios::sync_with_stdio(false);
   cin.tie(0);

   solve();
}

Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define debug(x) cout<<x<<endl
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const int MAXN=1e5+50;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
//::iterator it;
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int k;
    cin>>k;k--;
    queue<ll>q;
    for(int i=1;i<=9;i++)q.push(i);
    while(k--){
        ll x=q.front();
        q.pop();
        if(x%10!=0)q.push(10*x+x%10-1);
        q.push(10*x+x%10);
        if(x%10!=9)q.push(10*x+x%10+1);
    }
    cout<<q.front()<<endl;
    return 0;
}
/*

*/

 
 

Measured memory_bytes: 1792
use std::collections::HashMap;
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let n = read::<i64>();
    let an = read_vec::<i64>();
    let ans = an.iter().fold(HashMap::new(),|mut map,x|{
        let y = map.get(&x).map(|i| i+1).unwrap_or(1);
        map.insert(x,y);
        map
    }).into_iter().collect::<Vec<(_,_)>>()
    .into_iter()
    .map(|(k,v)|{
        if v  < *k {
            v 
        } else{
            v - k
        }
    })
    .fold(0,|y,x| y + x);
    println!("{}",ans);
}

Measured memory_bytes: 13560
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define ll long long int
#define ld unsigned long long int
#define pi pair<ll,ll>
#define pb push_back
#define pf push_front
#define pu push
#define po pop
#define fi first
#define se second
#define mk make_pair
#define ve vector
#define lr(n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define be begin
#define sz(a) (ll)a.size()
#define INF 1e18
 
typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
 
ll mod=1e9+7;
// ll gcd(ll a, ll b){
//     if(a<b) swap(a,b);
//     if(b==0) return a;
//     return gcd(b,a%b);
// }
 
// ll fun(ll x, ll y){
//     ll rem=1;
//     while(y!=0){
//         if(y%2==1){
//             rem=(rem*x)%mod;
//         }
//         x=(x*x)%mod;
//         y/=2;
//     }
//     return rem;
// }

ll dp[1001][1001];
char ar[1001][1002];

ll fun(ll i,ll j,ll n,ll m){
	if(dp[i][j]!=-1) return dp[i][j];
	dp[i][j]=0;
	if(j<m && ar[i][j+1]=='.'){
		if(dp[i][j+1]==-1)fun(i,j+1,n,m);
		dp[i][j]+=dp[i][j+1];
		dp[i][j]%=mod;
	}
	if(i<n && ar[i+1][j]=='.'){
		if(dp[i+1][j]==-1)fun(i+1,j,n,m);
		dp[i][j]+=dp[i+1][j];
		dp[i][j]%=mod;
	}
	return dp[i][j];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll h,w;
	cin>>h>>w;
	for(ll i=1;i<=h;i++){
		cin>>&ar[i][1];
	}
	for(ll i=1;i<=h;i++){
		for(ll j=1;j<=w;j++){
			dp[i][j]=-1;
		}
	}
	dp[h][w]=1;
	cout << fun(1,1,h,w) << "\n";
	return 0;
}

Measured memory_bytes: 9216
use std::io;


fn main() {
    let o = read_one::<String>().chars().collect::<Vec<char>>();
    let e = read_one::<String>().chars().collect::<Vec<char>>();
    let mut pass = Vec::new();
    for i in 0..(o.len() + e.len()) {
        if i % 2 == 0 { pass.push(o[i/2]); }
        else { pass.push(e[(i-1)/2]); }
    }
    for c in pass {
        print!("{}", c);
    }
    println!();
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
N = gets.chomp.to_i
V = gets.chomp.split(" ").map(&:to_i)
C = gets.chomp.split(" ").map(&:to_i)
sum = 0
N.times do |i|
  diff = V[i] - C[i]
  if diff > 0
    sum += diff
  end 
end
puts sum


Measured memory_bytes: 1788
n = STDIN.gets
arr = STDIN.gets.split.map(&:to_i)
Min = 1000000
Max = -1000000
min = arr.inject(Min){|min,dum|  if dum > min then
                           min
                           else
                           dum
                           end}

max = arr.inject(Max){|max,dum| if dum < max then
                          max
                          else
                          dum
                          end}
print min,' ',max,' ',arr.inject(:+),"\n"

Measured memory_bytes: 9132
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

int main() {
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll lcm_cd = lcm(c,d);
    ll ans = b-a+1;
    ans -= b/c + b/d - b/lcm_cd;
    ans += (a-1)/c + (a-1)/d - (a-1)/lcm_cd;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  char i,s[30],b[300]={};
  scanf("%s",s);
  for(i=0;s[i];i++){
    if(b[s[i]]){
      printf("no\n");
      return 0;
    }
    b[s[i]]=1;
  }
  printf("yes\n");
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

using real = double;
real EPS = 1e-10;
struct Point {
    real x, y;
    Point& operator+=(const Point a) { x += a.x; y += a.y;  return *this; }
    Point& operator-=(const Point a) { x -= a.x; y -= a.y;  return *this; }
    Point& operator*=(const real k) { x *= k; y *= k;  return *this; }
    Point& operator/=(const real k) { x /= k; y /= k;  return *this; }
    Point operator+(const Point a) const {return Point(*this) += a; }
    Point operator-(const Point a) const {return Point(*this) -= a; }
    Point operator*(const real k) const {return Point(*this) *= k; }
    Point operator/(const real k) const {return Point(*this) /= k; }
    bool operator<(const Point &a) const { return (x != a.x ? x < a.x : y < a.y); }
    explicit Point(real a = 0, real b = 0) : x(a), y(b) {};
};

istream& operator>> (istream& s, Point& P){
    s >> P.x >> P.y;
    return s;
}

inline real dot(Point a, Point b){ return a.x*b.x + a.y*b.y; }
inline real cross(Point a, Point b){ return a.x*b.y - a.y*b.x; }
inline real abs(Point a){ return sqrt(dot(a, a)); }

static constexpr int COUNTER_CLOCKWISE = 1;
static constexpr int CLOCKWISE = -1;
static constexpr int ONLINE_BACK = 2;
static constexpr int ONLINE_FRONT = -2;
static constexpr int ON_SEGMENT = 0;

int ccw(Point a, Point b, Point c){
    b -= a; c -= a;
    if(cross(b, c) > EPS) return COUNTER_CLOCKWISE;
    if(cross(b, c) < -EPS) return CLOCKWISE;
    if(dot(b, c) < 0) return ONLINE_BACK;
    if(abs(b) < abs(c)) return ONLINE_FRONT;
    return ON_SEGMENT;
}
struct Segment {
    Point a, b;
    Segment(Point x, Point y) : a(x), b(y) {};
};

double distance(Segment l, Point c){
    if(dot(l.b-l.a, c-l.a) < EPS) return abs(c-l.a);
    if(dot(l.a-l.b, c-l.b) < EPS) return abs(c-l.b);
    return abs(cross(l.b-l.a, c-l.a)) / abs(l.a-l.b);
}

bool intersect(Segment l1, Segment l2){
    return (ccw(l1.a, l1.b, l2.a)*ccw(l1.a, l1.b, l2.b) <= 0 &&
            ccw(l2.a, l2.b, l1.a)*ccw(l2.a, l2.b, l1.b) <= 0);
}

Point crossPoint(Segment l1, Segment l2){
    real d1 = abs(cross(l1.b-l1.a, l2.b-l2.a));
    real d2 = abs(cross(l1.b-l1.a, l1.b-l2.a));
    if(d1 < EPS && d2 < EPS) return l2.a;
    return l2.a+(l2.b-l2.a)*d2/d1;
}

Point project(Segment s, Point p){
    Point Q = s.b-s.a;
    return s.a + Q*(dot(p-s.a, Q) / dot(Q, Q));
}

int main(){
    Point a, b;
    cin >> a >> b;
    Segment s(a, b);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        Point P;
        cin >> P;
        Point ans = project(s, P);
        printf("%.10lf %.10lf\n", ans.x, ans.y);
    }
    return 0;
}


Measured memory_bytes: 3296
# -*- coding: utf-8 -*-
"""
Created on Tue May 12 01:19:32 2020

@author: shinba
"""
import collections

n = int(input())

A = list(map(int,input().split()))

data = collections.Counter(A)

I = sorted(data.items(),reverse = True)
#print(I)
s1 = 0
s2 = 1
cnt1 = 0
cnt2 = 0 

for i,j in I:
    if cnt1 == 0 and j >= 4:
        s1 = i**2
        cnt1 = 1
    if j >= 2:
        s2 *= i
        cnt2 += 1
    if cnt2 == 2:
        print(max(s1,s2))
        break
else:
    if s1 != 0:
        print(s1)
    else:
        print(0)

    
    



Measured memory_bytes: 69912
# https://atcoder.jp/contests/abc108/tasks/abc108_b


x1, y1, x2, y2 = gets.split.map(&:to_i)

v = [x2 - x1, y2 - y1]
x3 = x2 - v[1]
y3 = y2 + v[0]
x4 = x1 - v[1]
y4 = y1 + v[0]

puts "#{x3} #{y3} #{x4} #{y4}"


Measured memory_bytes: 1788
def actual(X, N, P):
    for i in range(X, -1 - 1, -1):
        if i not in P:
            left = i
            break

    for i in range(X, 101 + 1):
        if i not in P:
            right = i
            break

    if abs(left - X) <= abs(right - X):
        answer = left
    else:
        answer = right

    return answer


X, N = map(int, input().split())

if N == 0:
    P = []
    print(actual(X, N, P))
else:
    P = list(map(int, input().split()))
    print(actual(X, N, P))


Measured memory_bytes: 9208
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}


fn bis<F>(ok: i64, ng: i64, p: F) -> i64
    where F : Fn(i64) -> bool {

    let mid = (ok + ng) / 2;
    if (ok - ng).abs() == 1 {
        ok
    } else if p(mid) {
        bis(mid, ng, p)
    } else {
        bis(ok, mid, p)
    }
}

fn main() {
    let N = get!(usize);
    let A = get!(i64; N);

    // 解は最長非増加部分列の長さ
    let mut dp: Vec<i64> = vec!(-1; N + 1);
    for a in A {
        let i = bis(N as i64, -1, |j| dp[j as usize] < a) as usize;
        dp[i] = a;
    }
    let ans = dp.into_iter().filter(|&x| x >= 0).count();

    println!("{}", ans);
}


Measured memory_bytes: 6396
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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

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


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T1, class T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "[";
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        if (it != mp.begin()) {
            os << ", ";
        }
        os << *it;
    }
    return os << "]";
}

// edit

void solve() {
    int N;
    cin >> N;

    vector<int> ans(N + 1);

    for (ll a = 2; a * a <= 2 * N; ++a) {
        for (ll b = 2; a * a + b * b <= 2 * N; ++b) {
            for (ll c = 2; a * a + b * b + c * c <= 2 * N; ++c) {
                ll s = a * a + b * b + c * c;
                if (s % 2 == 0) {
                    ll x = (a + b + c) / 2 - a;
                    ll y = (a + b + c) / 2 - b;
                    ll z = (a + b + c) / 2 - c;

                    if (x >= 1 && y >= 1 && z >= 1) {
                        ans[s / 2]++;
                    }
                }


            }
        }
    }

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


}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			cout<<i<<"x"<<j<<"="<<i*j<<endl;
		}
	}
}

Measured memory_bytes: 3080
///
// File:  a.go
// Author: ymiyamoto
//
// Created on Mon Apr  2 21:09:46 2018
//
package main

import (
	"fmt"
)

var H, W int

func main() {
	fmt.Scan(&H, &W)

	var count int
	for i := 0; i < H; i++ {
		var s string
		fmt.Scan(&s)
		for j := range s {
			if s[j] == '#' {
				count++
			}
		}
	}

	if count == H+W-1 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000009
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define rollcall cout<<"I'm Sucu."<<endl
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define int ll


signed main(void){
    int N,C,K;
    int Ans=0;
    int T[114514];
    cin >> N >> C >> K;
    REP(i,N){cin >> T[i];}
    sort(T,T+N);
    T[N]=T[N-1]+3*C;
    int j=0,k=0;//jは乗ってない最初の客、kは現在の乗客の数
    REP(i,N){
        if(k==0){
            k++;j=i;
        }else{
            k++;
        }
        if(k==C || T[i+1]-T[j]>K){
            Ans++;k=0;
            //cout << j << " " << i << endl;
        }
    }
    if(k!=0)Ans++;
    cout << Ans << endl;
  return 0;
}


Measured memory_bytes: 1024
from itertools import permutations


def main():
    n = int(input())
    l = ["M", "A", "R", "C", "H"]
    count = {x: 0 for x in l}
    for _ in range(n):
        s = input()[0]
        if s in count:
            count[s] += 1
    answer = 0
    for p in permutations(l, 3):
        answer += count[p[0]] * count[p[1]] * count[p[2]]
    print(answer // 6)


if __name__ == '__main__':
    main()



Measured memory_bytes: 3064
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int H = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int aMax = 0;
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            aMax = Math.max(aMax, a);
            pq.offer(b);
        }

        int ans = 0;
        while (!pq.isEmpty() && H > 0) {
            int b = pq.poll();
            if (aMax > b) {
                break;
            }
            H -= b;
            ans++;
        }
        if (H > 0) {
            ans += H/aMax + (H%aMax == 0 ? 0 : 1);
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 64236
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  int r,d,x;

  cin >> r >> d >> x;

  rep(i,10)
  {
    int xx = r * x - d;

    cout << xx << endl;

    x = xx;
  }
  return 0;
}
// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = "";
            while (!string.IsNullOrEmpty(read = Console.ReadLine()))
            {
                var data = read.Split().Select(s => int.Parse(s)).ToArray();

                if (data[0] == 0 && data[1] == 0) break;

                for (var i = 0; i < data[0]; i++)
                {
                    for (var j = 0; j < data[1]; j++)
                    {
                        if ((i % 2 == 0 && j % 2 == 0)
                            || (i % 2 != 0 && j % 2 != 0))
                        {
                            Console.Write("#");
                        }
                        else
                        {
                            Console.Write(".");
                        }
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }
    }
}



Measured memory_bytes: 18348
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include<iostream>
#include<cmath>

long long int min_op(const int current, const int prev_height_pos, const int k, const std::vector<int>& heights, std::vector<std::vector<std::vector<long long int>>> memo) {
	if (current == heights.size()) return 0;
	if (memo[current][prev_height_pos][k] >= 0) return memo[current][prev_height_pos][k];
	if (heights[current] >= heights[prev_height_pos]) {
		long long int min = min_op(current + 1, current, k, heights, memo) + heights[current] - heights[prev_height_pos];
		if (k > 0) {
			min = std::min(min, min_op(current + 1, prev_height_pos, k - 1, heights, memo));
		}
		return memo[current][prev_height_pos][k] = min;
	}
	else {
		long long int min = min_op(current + 1, current, k, heights, memo);
		if (k > 0) {
			min = std::min(min, min_op(current + 1, prev_height_pos, k - 1, heights, memo));
		}
		return memo[current][prev_height_pos][k] = min;
	}
}
int main() {
	int n, k; std::cin >> n >> k;
	std::vector<int> heights(n + 1, 0); for (auto i = 1; i <= n; ++i) std::cin >> heights[i];
	std::vector<std::vector<std::vector<long long int>>> memo(n + 2, std::vector<std::vector<long long int>>(n + 1, std::vector<long long int>(k + 1, 0)));
	for (int current = n; current > 0; --current) {
		for (int prev = 0; prev < current; ++prev) {
			for (auto k_rest = 0; k_rest <= k; ++k_rest) {
				if (heights[current] >= heights[prev]) {
					memo[current][prev][k_rest] = memo[current + 1][current][k_rest] + heights[current] - heights[prev];
					if (k_rest > 0) {
						if (memo[current][prev][k_rest] > memo[current + 1][prev][k_rest - 1]) {
							memo[current][prev][k_rest] = memo[current + 1][prev][k_rest - 1];
						}
					}
				}
				else {
					memo[current][prev][k_rest] = memo[current + 1][current][k_rest];
					if (k_rest > 0) {
						if (memo[current][prev][k_rest] > memo[current + 1][prev][k_rest - 1]) {
							memo[current][prev][k_rest] = memo[current + 1][prev][k_rest - 1];
						}
					}
				}
			}
		}
	}
	std::cout << memo[1][0][k] << '\n';
}


Measured memory_bytes: 217600
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 998244353;
 
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> l(k), r(k);
  rep(j,k) cin >> l[j] >> r[j];

  vector<ll> dp(n+1,0);
  vector<ll> dpsum(n+1,0);
  dp[1] = 1;
  dpsum[1] = 1;
  for (int i = 2; i <= n; i++)
  {
    rep(j,k) {
      int li = i - r[j];
      int ri = i - l[j];
      if (ri < 0) continue;
      li = max(1,li);
      dp[i] += dpsum[ri] - dpsum[li-1];
      //dp[i] = (dp[i]+MOD) % MOD;
      dp[i] %= MOD;
    }
    dpsum[i] = dpsum[i-1] + dp[i];
    dpsum[i] %= MOD;
    //dpsum[i] = (dpsum[i]+MOD) % MOD;
  }
  cout << (dp[n]+MOD)%MOD << endl;
  return 0;
}

Measured memory_bytes: 6408
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>

signed main()
{
int x=0,y=0,z=0,w=0,n=0,m=0,a=0,b=0;
double db=0;
std::cin >> x>>y;
int v[x][y];
rep(i,x){
  Rep(j,y){
    std::cin >> v[i][j];
  }
}
for (int i = 0; i < x; i++) {
  for(int j = i+1;j<x;j++){
    for(int k = 0;k<y;k++){
      db+=(v[i][k]-v[j][k])*(v[i][k]-v[j][k]);
    }
    db = sqrt(db);
    if((double)((int)db)==db)n++;
    db = 0;
  }
}
std::cout << n << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define ll long long
#define MAXN 100010
#define MAXM
using namespace std;
inline void read(int &x){
    char ch;
    bool flag=false;
    for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
}

inline void read(long long &x){
    char ch;
    bool flag=false;
    for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
}


int n;

int main(){
    read( n );
    int x,y,z;
    x=y=z=0;
    int cnt=0;
    for (int i=1;i<=n;i++)
        {
            int a, b, c;
            read(a); read(b ); read(c);
            if ( ( a-z ) >= ( abs( x-b ) + abs( z-c )) )
                if (( ( a-z )%2)== (( abs( x-b ) + abs( z-c ))%2 ) )
                    cnt++;
        }
    if (cnt!=n)
        puts("No");
    else
        puts("Yes");
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
 int n,m[10000],i,j,ans=0;

 scanf("%d",&n);

 for(i=0;i<n;i++){
  scanf("%d",&m[i]);
 }

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

  while(1){

   if( m[i] == 2 ){
     ans++;
     break;
   }

   if( m[i]<2 || m[i]%2 == 0 ) break;

   j=3;
   while( j*j <= m[i] ){
    if( m[i]%j == 0 ) break;
    j=j+2;
   }
   if( m[i]%j != 0 || m[i] == 3) ans++;
   
   break;
  }
 }

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

 return 0;
 
}
 

Measured memory_bytes: 1808
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int c[5][5];

int main(void){
	          int i,j,k;

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

	      	  for(i=1;i<=3;i++){
	      		  for(j=1;j<=3;j++){
	      			  cin >> c[i][j];
	      		  }
	      	  }

	      	  for(i=0;i<=100;i++){
	      		  for(j=0;j<=100;j++){
	      			  for(k=0;k<=100;k++){
	      				  if(c[1][1]-i==c[1][2]-j && c[1][1]-i==c[1][3]-k){
	      					  if(c[2][1]-i==c[2][2]-j && c[2][1]-i==c[2][3]-k){
	      						  if(c[3][1]-i==c[3][2]-j && c[3][1]-i==c[3][3]-k){
	      							  cout << "Yes" << endl;
	      							  return 0;
	      						  }
	      					  }
	      				  }
	      			  }
	      		  }
	      	  }

	      	  cout << "No" << endl;


	          return 0;
}


Measured memory_bytes: 256
n,a,b,c,d=map(int,input().split())
s=list(input())
if c<d:
  f=0
  for i in range(b,d-1):
    if s[i]=='#' and s[i+1]=='#':
      f=1
      break
  if f==0:
    for i in range(a,c-1):
      if s[i]=='#' and s[i+1]=='#':
        f=1
        break
  if f==1:print('No')
  else:print('Yes')
else:
  f=0
  for i in range(b,d-1):
    if s[i]=='#' and s[i+1]=='#':
      f=1
      break
  if f==0:
    for i in range(a,c-1):
      if s[i]=='#' and s[i+1]=='#':
        f=1
        break
  if f==0:
    if (s[d-2]=='#' or s[d]=='#') and (s[b-2]=='#' or s[b]=='#'):
      ct=0
      for i in range(b-1,d-2):
        if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
          ct+=1
          break
      if ct==0:
        f=1
  if f==1:print('No')
  else:print('Yes')

Measured memory_bytes: 4868
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;
const int MOD = 1000000009;
const double pi = acos(-1);

int disit_sum(int a) {
    int ans = 0;
    while(a) {
        ans += a%10;
        a /= 10;
    }
    return ans;
}

int main() {
    int N; cin >> N;
    int ans = 1e9;
    for(int A = 1; A < N; A++) {
        int B = N-A;
        chmin(ans,disit_sum(A)+disit_sum(B));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3556
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    map<int, int> m;
    rep(i, 0, N) {
        int K;
        cin >> K;
        rep(i, 0, K) {
            int a;
            cin >> a;
            a--;
            m[a]++;
        }
    }

    int rsl = 0;
    for(auto it = m.begin(); it != m.end(); it++) {
        if(it->second == N) rsl++;
    }
    cout << rsl << endl;


}


Measured memory_bytes: 256