akhauriyash/Code-Regression huggingface dataset:
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
XY = [(-1, 0), (1, 0), (0, 1), (0, -1)]

t_max = 0
for i in range(H):
    for j in range(W):
        step = [[0]*W for _ in range(H)]
        visited = [[False]*W for _ in range(H)]
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            if maze[x][y] == "#":
                continue
            if visited[x][y]:
                continue
            for dx, dy in XY:
                nx = x + dx
                ny = y + dy
                if 0 <= nx <= H-1 and 0 <= ny <= W-1:
                    step[nx][ny] = step[x][y] + 1
                    queue.append((nx, ny))
                    t_max = max(t_max, step[nx][ny])
            visited[x][y] = True

print(t_max-1)





Measured memory_bytes: 9228
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <limits.h>
#include <bitset>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBUG = true;

bool check( vector<int> &cnt ){
    for(int i = 0; i < cnt.size(); i++){
        if(cnt[i] > 1) return false;
    }
    return true;
}

void add( vector<int> &cnt, bitset<20> &bs ){
    for(int i = 0; i < 20; i++){
        cnt[i] += bs[i];
    } 
}

void sub( vector<int> &cnt, bitset<20> &bs ){
    for(int i = 0; i < 20; i++){
        cnt[i] -= bs[i];
    } 
}


int main(){

    int n;
    cin >> n;

    vector < bitset<20> > v(n);
    for(int i = 0; i < n; i++){
        unsigned long s;
        cin >> s;
        bitset<20> bs(s);
        v[i] = bs;
    }

    vector<int> cnt(20);

    int left = 0;
    int right = -1;
    ll ans = 0;

    while(true){

        if( check(cnt) && right < n ){
            right ++;
            //ans += (right - left);
            if(right != n) add( cnt, v[right] );
        }
        else{
            ans += (right - left);
            sub( cnt, v[left] );
            left ++;
        }

        if(right == n && left == n) break;

    }
    
    cout << ans  << endl;


}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        int[] nums = new int[S.length()];

        int count=0;
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if(c=='R'){
                count++;
            }else if(count>0){// L ,set values
                nums[i-1] += (int)Math.ceil(count/2.0);
                nums[i] += count - nums[i-1];
                count=0;
            }
        }

        for (int i = S.length()-1 ; i >=0; i--) {
            char c = S.charAt(i);
            if(c=='L'){
                count++;
            }else if(count>0){// at R ,set values
                int countL = (int)Math.ceil(count/2.0);
                nums[i+1] += countL;
                nums[i] += count - countL;
                count=0;
            }
        }


        for (int i = 0; i < S.length(); i++) {
            System.out.print(nums[i]+((i==S.length()-1)?"\n":" "));
        }

    }
}


Measured memory_bytes: 46964
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  int n;
  cin >> n;
  vector<char> s(n);
  REP(i, n) {
    cin >> s[i];
  }
  int x = 0;
  REP(i, n) {
    if (s[i] == 'Y') x = 1;
  }
  if (x == 1) dump("Four");
  else dump("Three");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

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


	ll n;
	cin >> n;
	Array a(n, 0);

	ll min=INF;
	ll max = -INF;
	REP(i, n) {
		cin >> a[i];
		chmin(min, a[i]);
		chmax(max, a[i]);
	}

	ll ans = INF;
	for (ll i = min; i <= max; i++) {
		ll sum = 0;
		REP(j, n) {
			sum += (i - a[j]) * (i - a[j]);
		}
		chmin(ans, sum);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    
    int n;
    scanf("%d",&n);

    int h[n];

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

    int max, count;
    max = h[0];
    count = 0;

    for(int j = 0; j < n; j++){
        if(max <= h[j]){
            count++;
            max = h[j];
        }
    }    

    printf("%d",count);

    return 0;

}

Measured memory_bytes: 128
s=input().rstrip()
if int(s[0]+s[1])>=1 and int(s[0]+s[1])<=12  and int(s[2]+s[3])>=1 and int(s[2]+s[3])<=12:
    print('AMBIGUOUS')
elif  int(s[0]+s[1])>=1 and int(s[0]+s[1])<=12 and (int(s[2]+s[3])>12 or int(s[2]+s[3])<1):
    print('MMYY')
elif (int(s[0]+s[1])>12 or int(s[0]+s[1])<1) and int(s[2]+s[3])>=1 and int(s[2]+s[3])<=12:
    print('YYMM')
else:
    #print(int(s[0]+s[1]))
    
    #print(int(s[2]))
    print('NA')

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


int main(){
  int n;cin >> n;
  set<string> S;
  rep(i,n){
    string a;
    cin >> a;
    S.insert(a);
  }

  cout << S.size() << endl;

}




Measured memory_bytes: 19228
from fractions import Fraction
from operator import add, mul

MOD = 10 ** 9 + 7


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


def mod_add(x, y):
    return add(x, y) % MOD


def cmb(n, r):
    return mod_mul(
        mod_mul(fact[n], inv(fact[r])),
        inv(fact[n - r]))


N, A, B, C = map(int, input().split())

r = mod_mul(100, inv(A + B))
a = mod_mul(A, inv(A + B))
b = mod_mul(B, inv(A + B))

pow_a = [1]
pow_b = [1]
for n in range(N + 1):
    pow_a.append(mod_mul(pow_a[-1], a))
    pow_b.append(mod_mul(pow_b[-1], b))

fact = [1]
for n in range(1, N * 2):
    fact.append(mod_mul(fact[-1], n))

p = 0
for m in range(N, N * 2):
    pa = pow_a[N] * pow_b[m - N]
    pb = pow_a[m - N] * pow_b[N]
    c = cmb(m - 1, N - 1)

    em = mod_mul(mod_mul(mod_mul(c, mod_add(pa, pb)), m), r)
    p = mod_add(p, em)
    # print(m, c, pa, pb, em, p)

f = Fraction(p, 1)
ans = mod_mul(f.numerator, inv(f.denominator))
print(ans)


Measured memory_bytes: 80716
#include <bits/stdc++.h>
using namespace std;
int main()
{/// Standing in The hall of Fame
    ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL);
    int a[5] , k;
    for(int i = 0 ; i < 5 ; i++)
        cin >> a[i];
    cin >> k;
    for(int i = 4 ; i > 0 ; i--)
        for(int j = i-1 ; j >= 0 ; j--)
            if(a[i]-a[j] > k)
                return cout << ":(\n" , 0;
    cout << "Yay!\n";
    return 0;
}

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


int main(){


    int n, i, x;

    int k = 0;

    vector<int> a;


    cin >> n;


    a.push_back(0);


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

         cin >> x;

         a.push_back(x);

         }


    for( i = 1 ; k < n ; ){

         i = a.at(i);

         k += 1;

         if( i == 2 ) break;

         }


    if( k == n ) k = -1;


    cout << k << endl;


    return 0;

    }


Measured memory_bytes: 892
#include<stdio.h>
int main(){
int i;
int height[10];
int temp, flag;
for(i = 0; i < 10; i++){
scanf("%d", &height[i]);
}
do{
flag = 0;
for(i = 0; i < 9; i++){
if(height[i] > height[i + 1]){
flag = 1;
temp = height[i + 1];
height[i + 1] = height[i];
height[i] = temp;
}
}
}while(flag);
printf("%d\n%d\n%d\n", height[9], height[8], height[7]);
return 0;
}

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

int main(){
	int h,w;
	cin >> h >> w;
	char m[105][105];
	int count = 0;
	map<int,int> mp;
	rep(i,h)rep(j,w) {
		cin >> m[i][j];
		mp[m[i][j] - 'a']++;
	}
	rep(i,26){
		if(mp[i] % 2 == 1) count++;
	}
	if(h % 2 == 0 && w % 2 == 0){
		bool ok = true;
		if(count >= 1) ok = false;
		rep(i,26){
			if(mp[i] != 0 && mp[i] % 4 != 0) ok = false;
		}
		if(ok){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}else if(h % 2 == 0 && w % 2 == 1){
		bool ok = true;
		if(count >= 1) ok = false;
		int yon = 0;
		int ni = 0;
		rep(i,26){
			if(mp[i] % 4 == 0){
				yon++;
			} else if (mp[i] % 2 == 0){
				ni++;
			}else{
				ok = false;
			}
		}
		if(ni > h/2) ok = false;
		if(ok){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	} else if (h % 2 == 1 && w % 2 == 0){
		bool ok = true;
		if(count >= 1) ok = false;
		int yon = 0;
		int ni = 0;
		rep(i,26){
			if(mp[i] % 4 == 0){
				yon++;
			} else if (mp[i] % 2 == 0){
				ni++;
			}
		}
		if(ni > w/2) ok = false;
		if(ok){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}else{
		bool ok = true;
		if(count >= 2) ok = false;
		int yon = 0;
		int ni = 0;
		rep(i,26){
			if(mp[i] % 2 == 1) continue;
			if(mp[i] % 4 == 0){
				yon++;
			}else if (mp[i] % 2 == 0){
				ni++;
			}
		}
		if(ni > h/2 + w/2) ok = false;
		if(ok){
			cout << "Yes" << endl;
		}else{
			cout << "No" << endl;
		}
	}
	
    return 0;
}



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

const int MAX_N=5e5+10;
vector<int> primes,is_prime(MAX_N,1);

void sieve(){
    is_prime[0]=is_prime[1]=0;
    for (int i=2;i<MAX_N;++i){
        if (is_prime[i]){
            primes.emplace_back(i);
            for (int j=2*i;j<MAX_N;j+=i) is_prime[j]=0;
        }
    }
}

int N,P;
vector<int> ps,sums;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    sieve();
    while(cin >> N >> P,N!=-1){
        ps.clear(); sums.clear();
        auto itr=upper_bound(primes.begin(),primes.end(),N);
        for (int i=0;i<P;++i) ps.emplace_back(*(itr+i));
        for (int i=0;i<P;++i)
            for (int j=i;j<P;++j)
                sums.emplace_back(ps[i]+ps[j]);
        sort(sums.begin(),sums.end());
        cout << sums[P-1] << '\n';
    }
}


Measured memory_bytes: 5116
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  int n;
  cin >> n;
  vector<string> s(2);
  cin >> s[0] >> s[1];

  ll ans = 1;
  for (int i = 0; i < n; ++i)
  {
    if (i == 0)
    {
      ans = (ans * 3) % MOD;
      if (s[0][i] != s[1][i])
      {
        ans = (ans * 2) % MOD;
        i++;
      }
    }
    else
    {
      if (s[0][i] != s[1][i])
      {
        if (s[0][i - 1] != s[1][i - 1])
          ans = (ans * 3) % MOD;
        else
          ans = (ans * 2) % MOD;
        i++;
      }
      else if (s[0][i - 1] == s[1][i - 1])
        ans = (ans * 2) % MOD;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define pi 3.141592653589
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long
#define MOD (int)(1e9+7)
#define pii pair<int,int>
using namespace std;


int main() {

	string s;
	int cnt = 0;

	cin >> s;
	rep(i, 0, 3) {
		if (s[i] == '1')cnt++;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int n,i;
    scanf("%d",&n);
    int k[n],p[n];
    for(i = 0;i < n;i++)
        scanf("%d %d",&k[i],&p[i]);
    for(i = 0;i < n;i++){
        if(k[i]%p[i] == 0){
            printf("%d\n",p[i]);
            continue;
        }
        printf("%d\n",k[i] % p[i]);
    }
    return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int main(void){
	int a,b;
	cin >> a >> b;
	if(a == b){
		cout << "a == b" << endl;
	}else if(a < b){
		cout << "a < b" << endl;
	}else{
		cout << "a > b" << endl;
	}
	return 0;
}

Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int
ll gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

ll lcm(int a, int b)
{
   return a * b / gcd(a, b);
}
struct Union{
  vector<ll> par;
  Union(ll a){
  par=vector<ll>(a,-1);
  }
  ll find(ll a){
    if(par[a]<0){
      return a;
    }
    else{
      return par[a]=find(par[a]);
    }
  }
  bool same(ll a,ll b){
    return (find(a)==find(b));
  }
  ll size(ll a){
    return -par[find(a)];
  }
  void unite(ll a,ll b){
    ll c=find(a),d=find(b);
    if(c==d)
      return;
    if(size(c)<size(d)){
      swap(c,d);
    }
    par[c]+=par[d];
    par[d]=c;
  }
};
int main(){
  char s[8];
  cin >> s;
  if(s[2]==s[3]&&s[4]==s[5])cout << "Yes";
  else cout << "No";
}


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

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

int main() {
	int n, i,max,c;
	cin >> n;
	vector<int> d(n);

	vector<int>::iterator iter;
	size_t index;
	rep(i, n) {
		cin >> d.at(i);
	}
	c = 1;
	rep(i, n) {
		iter = max_element(d.begin(), d.end());
		index = distance(d.begin(), iter);
		//cout << *iter << endl;
		if (i == 0) {
			max = *iter;
			d[index] = -1;
		}
		else {
			if (max > * iter) {
				max = *iter;
				d[index] = -1;
				c++;
			}
			else {
				d[index] = -1;
			}
		}
	}
	cout << c << endl;
	return 0;
}

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

typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;


//===

const ll mod = static_cast<ll>(1e9 + 7);



int main() {
	int N, K;
	cin >> N >> K;
	Vi VV(N);
	for (int i = 0; i < N; ++i) {
		cin >> VV[i];
	}

	int a = min(N, K);
	Vi nega;
	int ans = 0;
	for (int i = 0; i <= a; ++i) {
		for (int j = 0; j <= a - i; ++j) {
			int sum = 0;
			for (int k = 0; k < i; ++k) {
				sum += VV[k];
				if (VV[k] < 0) nega.push_back(VV[k]);
			}
			for (int k = N - 1; k > N - j - 1; --k) {
				sum += VV[k];
				if (VV[k] < 0) nega.push_back(VV[k]);
			}
			sort(nega.begin(), nega.end());
			for (int k = 0; k < min(K - (i + j), static_cast<int>(nega.size())); ++k) {
				sum += -nega[k];
			}
			ans = max(ans, sum);
			nega.clear();
		}

	}
	cout << ans << endl;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)
ll N,K;
ll mk[101010],mk2[101010];
ll mk3[101010];
ll i, j, k,ans;


void ck(ll n){
    if(n==0){
        return;
    }
    ll i, j;

    if(n&1){
        fornum(i,0,K){
            mk2[i + 1] = mk3[i + 1];
            mk3[i + 1] = 0;
        }
        for (i = K; i >= 1;--i)
        {
            ll a = 0, b = 0;
            for (j = i; j <= K; j += i)
            {
                (a += mk2[j]) %= MOD;
                (b += mk[j]) %= MOD;
                (mk3[i] += MOD - mk3[j]) %= MOD;
            }
            (mk3[i] += a * b) %= MOD;
        }
    }

    fornum(i,0,K){
        mk2[i + 1] = mk[i + 1];
        mk[i + 1] = 0;
    }
    for (i = K; i >= 1;--i)
    {
        ll a = 0;
        for (j = i; j <= K; j += i)
        {
            (a += mk2[j]) %= MOD;
            (mk[i] += MOD - mk[j]) %= MOD;
        }
        (mk[i] += a * a) %= MOD;
    }

    ck(n / 2);
}

int main(){
    scanf("%lld%lld", &N,&K);
    fornum(i,0,K){
        mk2[i + 1] = 1;
    }

    fornum(i,0,K){
        mk[i+1]=mk3[i + 1] = 1;
    }
    ck(N - 1);
    fornum(i,0,K){
        (ans += mk3[i + 1] * (i + 1)) %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 6064
#include<iostream>
using namespace std;
int fee[] = {0, 125, 140, 160};

int calc(int w){
  int res = 1150;
  if(10 < w && w <= 20){
    return res + (w - 10)*125;
  }else if(20 < w && w <= 30){
    return res + 1250 + (w - 20)*140;
  }else if(30 < w){
    return res + 1250 + 1400 + (w - 30)*160;
  }else{
    return res;
  }
}

int main(int argc, char *argv[]){
  int fee = 0, w;
  while(cin >> w){
    if(w == -1)break;
    std::cout << 4280 - calc(w) << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

char s[105][105];
int row[105]={0},col[105]={0};

main() {
    int h,w,i,j;
    scanf("%d %d", &h, &w);
    for(i=0;i<h;i++) {
        scanf("%s", s[i]);
    }
    for(i=0;i<h;i++) {
        for(j=0;j<w;j++) {
            if(s[i][j]=='#') break;
        }
        if(j!=w) row[i]=1;
    }

    for(j=0;j<w;j++) {
        for(i=0;i<h;i++) {
            if(s[i][j]=='#') break;
        }
        if(i!=h) col[j]=1;
    }

    for(i=0;i<h;i++) {
        int flag=0;
        for(j=0;j<w;j++) {
            if(col[j] && row[i]) {
                printf("%c", s[i][j]);
                flag=1;
            }
        }
        if(flag) puts("");
    }
}

Measured memory_bytes: 128
import numpy as np

a,b = map(int, input().split())
s_max = b + a -1
s_min = b 
ans = 0 

if s_min >= 0 and s_max >= 0:
    for i in range(s_min + 1,s_max+1):
        ans += i
           
    print (ans)
elif s_min < 0 and s_max > 0:
    for i in range(s_min,s_max+1):
        ans += i
           
    print (ans)
else:
    for i in range(s_min,s_max):
        ans += i
           
    print (ans)


Measured memory_bytes: 14264
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    k = int(input())
    dp = [[[] for _ in range(10)] for _ in range(11)]
    
    num = ['0','1','2','3','4','5','6','7','8','9']
    for i in range(10):
        dp[1][i] = [num[i]]

    if k <= 9:
        print(*dp[1][k])
        return 
    
    cnt = 9
    for i in range(2,11):
        for l in range(len(dp[i - 1][0])):
            dp[i][0].append('0' + dp[i - 1][0][l])
        for l in range(len(dp[i - 1][1])):
            dp[i][0].append('0' + dp[i - 1][1][l])   

        for j in range(1,10):
            for l in range(len(dp[i - 1][j - 1])):
                dp[i][j].append(num[j] + dp[i - 1][j - 1][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    #print(dp)
                    #print(num)
                    return

            for l in range(len(dp[i - 1][j])):
                dp[i][j].append(num[j] + dp[i - 1][j][l])
                cnt += 1
                if cnt == k:
                    print(dp[i][j][-1])
                    #print(dp)
                    #print(num)
                    return

            if j < 9:
                for l in range(len(dp[i - 1][j + 1])):
                    dp[i][j].append(num[j] + dp[i - 1][j + 1][l])
                    cnt += 1
                    if cnt == k:
                        print(dp[i][j][-1])
                        #print(dp)
                        #print(num)
                        #print(dp[2][1])
                        return
        

 
if __name__ =='__main__':
    main()  

Measured memory_bytes: 10740
#include <iostream>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define IN(v) int v;cin>>v;
#define OUT(v) cout<<v<<endl

int main() {
  IN(M); IN(D);

  int ans = 0;
  FOR(m, 1, M+1) {
    FOR(d, 22, D+1) {
      if (d % 10 < 2)
        continue;
      if ((d % 10) * (d / 10) == m)
        ++ans;
    }
  }
  OUT(ans);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<long long>w;
vector<long long>v;
long long n,wt;
long long mem[101][100001];
long long dp(long long pos,long long val)
{
    if(val==0)
    return 0;
    if(pos==n)
    return 100000000000000;
    if(mem[pos][val]!=-1)
        return mem[pos][val];
    long long ans;
    if(val>=v[pos])
    ans=min(dp(pos+1,val),w[pos]+dp(pos+1,val-v[pos]));
    else
    ans=dp(pos+1,val);
    mem[pos][val]=ans;
    return ans;
}
int main()
{
    long long i;
    memset(mem,-1,sizeof(mem));
    cin>>n>>wt;
    w.resize(n);
    v.resize(n);
    for(i=0;i<n;i++)
        cin>>w[i]>>v[i];
    for(i=100000;i>0;i--)
    {
        if(dp(0,i)<=wt)
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}


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

int n, y;
bool isFind = false;
void f(int a, int b, int c , int d) {
    
    if (isFind == true)
        return;
    
    if (a + b + c == n) {
        if (d == 0) {
            cout << a << " " << b << " " << c << '\n';
            isFind = true;
        }
        return;
    }
    
    
    f(a+1,  b,  c,  d-10000);
    f(a,    b+1,c,  d-5000);
    f(a,    b,  c+1,d-1000);
}


int main()
{
    ios::sync_with_stdio(false);
    
    cin >> n >> y;
    
    //f(0, 0, 0, y);
    //if (isFind == false)
    //    cout << "-1 -1 -1" << '\n';
    
    for (int i = 0; i <= 2000; i++) {
        for (int j = 0; j <= 2000; j++) {
            int z = n - i - j;
            if (z >= 0) {
                if (i*10000 + j*5000 + z*1000 == y) {
                    cout << i << " " << j << " " << z << '\n';
                    return 0;
                }
            }
        }
    }
    cout << "-1 -1 -1\n";
    
    return 0;
}


Measured memory_bytes: 256
S,T=input(),input()
s,t=len(S),len(T)
l=[]
for i in range(s-t+1):
  for j in range(t):
    if S[i+j] not in (T[j],'?'): break
  else: l.append((S[:i]+T+S[i+t:]).replace('?','a'))
print(min(l) if l else 'UNRESTORABLE')

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<tuple>
#include<string>
typedef unsigned long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define F first
#define S second
using namespace std;
const ll INF = 1e12;
const int i_INF = 2147483647;

int main() {
	int d;
	cin >> d;
	cout << "Christmas";
	rep(i, 0, -d + 25)cout << " Eve";
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const ll INF=1000000000000001;
const double PI=3.141592653589;


int main(){
  int d,n; cin>>d>>n;
  if(d==0){
    if(n==100)
    n+=1;
    cout<<n<<endl;
  }else if(d==1){
    int ans=n*100;
    if(n==100)
    ans+=100;
    cout<<ans<<endl;
  }else{
    int ans=n*10000;
    if(n==100)
    ans+=10000;
    cout<<ans<<endl;
  }

  return 0;
}


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

int main(){
    int h,w,k; cin >> h >> w >> k;
    vector<vector<char>> m(h,vector<char>(w)),mtmp(h,vector<char>(w));
    for(int ix=0;ix<h;ix++){
        for(int ixx=0;ixx<w;ixx++){
            cin >> m.at(ix).at(ixx);
        }
    }
    bitset<12> bb;
    int ans = 0;
    for(int ix=0;ix<(1<<(h+w));ix++){
        bb = ix;
        mtmp = m;
//        vector<vector<char>> mtmp = m;
        int cnt=0;
        for(int ix2=0;ix2<h;ix2++){
            if(bb.test(ix2)){
                for(int ix3=0;ix3<w;ix3++) mtmp.at(ix2).at(ix3) = 'r';
            }
        }
        for(int ix2=h;ix2<h+w;ix2++){
            if(bb.test(ix2)){
                for(int ix3=0;ix3<h;ix3++) mtmp.at(ix3).at(ix2-h) = 'r';
            }
        }
        for(int ix3=0;ix3<h;ix3++){
            for(int ix4=0;ix4<w;ix4++){
                if(mtmp.at(ix3).at(ix4) == '#') cnt++;
            }
        }
        if(cnt == k) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int a,b,c,d; cin >> a >> b >> c >> d;
	while(1){
		c-=b;
		if(c<=0){
			printf("Yes\n");
			break;
		}
		a-=d;
		if(a<=0){
			printf("No\n");
			break;
		}
	}
}

Measured memory_bytes: 3652
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
#include <list>
using namespace std;
#define INF 1000000000
typedef long long int lli;
typedef pair<int,int> P;

int main(){
	int n,m;
	cin >> n >> m;
	vector<int> a;
	vector<int> b;
	for(int i=0; i<n; ++i){
		int tmp;
		cin >> tmp;
		a.push_back(tmp);
	}
	for(int i=0; i<m; ++i){
		int tmp;
		cin >> tmp;
		b.push_back(tmp);
	}
	vector<int> c(n);
	for(int i=0; i<m; ++i){
		for(int j=0; j<n; ++j){
			if(b[i]>=a[j]){
				++c[j];
				break;
			}
		}
	}
	P ans(0,0);
	for(int i=0; i<n; ++i){
		if(ans.first<c[i]){
			ans.first=c[i];
			ans.second=i+1;
		}
	}
	cout << ans.second << "\n";
	return 0;
}

Measured memory_bytes: 1232
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

n,m = inputIL()

print((n-1)*(m-1))

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n, m, c;
    cin >> n >> m >> c;
    vi b(m);
    rep(i, m) cin >> b[i];
    int ans = 0;
    rep(i, n) {
        int sum = 0;
        rep(j, m) {
            int aij;
            cin >> aij;
            sum += aij * b[j];
        }
        sum += c;
        if (sum > 0) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    int N, M; cin >> N >> M;
    if (N >= M) {
        cout << 0 << "\n";
        return 0;
    }

    vector<int> X(M);
    rep(i, 0, M) cin >> X[i];
    sort(X.begin(), X.end());

    vector<int> intervals(M-1);
    rep(i, 0, M-1) intervals[i] = X[i+1] - X[i];
    sort(intervals.begin(), intervals.end(), greater<int>());

    int res = X.back() - X.front();
    rep(i, 0, N-1) res -= intervals[i];

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

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=i;
        }
        printf("%d\n",ans);
    }
    return 0;
}


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

#define ll long long
#define pll pair<ll,ll> 

ll M[3003][3003];

	
int main() {

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

	string s, w;
	cin>>s>>w;
	ll n=s.size();
	ll m=w.size();
	memset(M,0,sizeof M);
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			if(s[i-1]==w[j-1])
				M[i][j]=1+M[i-1][j-1];
			else M[i][j]=max(M[i-1][j], M[i][j-1]);
		}
	}

	string ans;
	ll i=n, j=m;
	while(i>0 && j>0){
		if(s[i-1]==w[j-1]){
			ans.push_back(s[i-1]);
			i--,j--;
		}
		else{
			if(M[i][j]==M[i-1][j])
				i--;
			else j--;
		}
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<endl;
}


Measured memory_bytes: 74092
n, m =gets.split(" ").map(&:to_i)

list = []
n.times do 
 a, *b = gets.split(" ").map(&:to_i)
 list.push(b)
end
list = list.flatten

sum = 0
(1..m).map{ |t| sum += 1 if list.count(t) == n}
p sum

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

int MAX = 1000001;
int prime[1000001] = {};

void make_prime(){
  int i, j;

  for (i = 2; i < MAX; i++) {
    prime[i] = 1;
  }

  for (i = 2; i * i < MAX; i++) {
    if (prime[i]){
      for (j = i * 2; j < MAX; j += i) {
        prime[j] = 0;
      }
    }
  }
}

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

  make_prime();
  int i, input, count;

  while (cin >> input) {
    count = 0;
    for (i = 0; i <= input; i++) {
      if (prime[i] == 1) { count += 1; }
    }
    cout << count << endl;
  }

  return 0;
}

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

int main()
{
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) cout << "Bad" << endl;
    else cout << "Good" << endl;
    return 0;
}

Measured memory_bytes: 256
arr = []
n = gets.chomp.to_i
n.times do
	arr << gets.chomp.to_i
end
if arr.first==2
	a = 1
else
	a = -1
	for i in 1..arr.length-1
		h = arr.first if i==1
		h = arr[h-1]
		if h == 2
			a = i+1; break
		end
  end
end
puts a

Measured memory_bytes: 4732
#include<stdio.h>
#include<math.h>

int main(void)
{
int w,h,x,y,z;
double s;
scanf("%d %d %d %d",&w,&h,&x,&y);

if((double)x==((double)w/2)&&(double)y==((double)h/2))
{
z=1;
}else{
z=0;
}

s=((double)w*(double)h)/2;

printf("%f %d",s,z);

return 0;
}

Measured memory_bytes: 128
n = int(input())
c = list(input().split())
c1, c2 = c[:], c[:]

def bubbleSort():
  for i in range(n):
    for j in range(n-1, i, -1):
      if c1[j][-1]<c1[j-1][-1]:
        c1[j], c1[j-1] = c1[j-1], c1[j]

def selectionSort():
  for i in range(n):
    minj = i
    for j in range(i, n):
      if c2[j][-1]<c2[minj][-1]:
        minj = j
    c2[i], c2[minj] = c2[minj], c2[i]

bubbleSort()
selectionSort()
print(" ".join(map(str, c1)))
print("Stable")
print(" ".join(map(str, c2)))
if c1==c2:
  print("Stable")
else:
  print("Not stable")


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

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

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int H, W;
string S[25];

int bfs(int sy, int sx) {
    int res = 0;

    queue<pair<P, int>> q;
    q.push(make_pair(P(sy, sx), 0));

    bool used[25][25];
    rep(i, 25) {
        rep(j, 25) used[i][j] = false;
    }
    used[sy][sx] = true;

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

    while (!q.empty()) {
        auto a = q.front(); q.pop();
        P pos = a.first;
        int y = pos.first, x = pos.second;
        int cost = a.second;
        
        rep(d, 4) {
            int ny = y + dy[d], nx = x + dx[d];

            if (0 <= ny && ny < H && 0 <= nx && nx < W && S[ny][nx] == '.' && !used[ny][nx]) {
                used[ny][nx] = true;
                q.push(make_pair(P(ny, nx), cost + 1));
            }
        }

        res = max(res, cost);
    }

    return res;
}

int main(){
    cin >> H >> W;

    rep(i, H) cin >> S[i];

    int ans = 0;
    rep(y, H) {
        rep(x, W) {
            if (S[y][x] == '.') ans = max(ans, bfs(y, x));
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;
template <typename T1, typename T2>
inline void chmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int N, M, K;
vector<int> A, B;
void input() {
  int i, j, k, x, y;
  string s;
  cin >> N >> K;
}
void solve() {
  int ans = K;
  rep(i, 1, N - 1) { ans *= K - 1; }
  cout << ans << endl;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
// D - Recording
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

int main(){
	int N,C; cin>>N>>C;
	vector<vi> tv(100000, vi(C, 0));
	int mx_t = 0;
	while(N--){
		int s,t,c; cin>>s>>t>>c; --c;
		for(int i=s-1; i<t; ++i) tv[i][c] = 1;
		mx_t = max(mx_t, t);
	}
	int ans = 0;
	for(int t=0; t<mx_t; ++t){
		int s = 0; for(auto c:tv[t]) s += c;
		ans = max(ans, s);
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 18004
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;

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

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

int main(){
    ll N, K;
    cin>>N>>K;
    vector<ll> Sum(K+1, 0); //Sum[i]がgcdi以上
    for(ll i=1; i<=K; i++){
        ll V=K/i;
        Sum[i]=myPow(V, N, MOD);
      	//cout<<Sum[i]<<" ";
    }
    ll Ans=0;
    for(ll i=K; i>=1; i--){
        ll J=i;
        ll F=2;
        while(J*F<=K){
            Sum[i]-=Sum[J*F];
          	F++;
        }
      	Sum[i]%=MOD;
      	if(Sum[i]<0)Sum[i]+=MOD;
      	//cout<<Sum[i]<<" ";
        Ans+=i*Sum[i];
      	
        Ans%=MOD;
    }
    cout<<Ans<<endl;
}



Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

ll dp[3001][3001][2];

int main()
{
	ll n, m;
	cin >> n >> m;
	for (int j = 0; j <= n; ++j) {
		dp[0][j][0] = 1;
	}
	for (int i = 1; i <= m; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (j > 1) {
				dp[i][j][0] += dp[i - 1][j - 1][0];
				dp[i][j][0] += dp[i - 1][j][0];
			}
			if (j > 0 && j < n) {
				dp[i][j][0] += dp[i - 1][j + 1][0];
				dp[i][j][0] += dp[i - 1][j][0];
			}
			if (j == 0) {
				dp[i][j][1] += dp[i - 1][j + 1][0];
				dp[i][j][1] += dp[i - 1][j][0];
			} else if (j == 1) {
				dp[i][j][1] += dp[i - 1][j - 1][0];
				dp[i][j][1] += dp[i - 1][j][0];
			}
			if (j > 0) {
				dp[i][j][1] += dp[i - 1][j - 1][1];
				dp[i][j][1] += dp[i - 1][j][1];
			}
			if (j < n) {
				dp[i][j][1] += dp[i - 1][j + 1][1];
				dp[i][j][1] += dp[i - 1][j][1];
			}
			dp[i][j][0] %= MOD;
			dp[i][j][1] %= MOD;
		}
	}
	ll ans = 0;
	for (int j = 0; j <= n; ++j) {
		ans = (ans + dp[m][j][1]) % MOD;
	}
	cout << ans << endl;
	return 0;
}



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

const int MAX_N = 200005;
int N;
struct rang {
  int st, en;
} rs[MAX_N];

int main() {
  scanf("%d", &N);
  std::vector<int> mm, dd;
  for (int i = 0; i < N; ++i) {
    scanf("%d %d", &rs[i].st, &rs[i].en);
    mm.push_back(rs[i].st);
    dd.push_back(rs[i].en);
  }
  std::sort(mm.begin(), mm.end());
  std::sort(dd.begin(), dd.end());
  if (N % 2) {
    int left_lower = mm[mm.size()/2];
    int right_higher = dd[dd.size()/2];
    printf("%d\n", right_higher - left_lower + 1);
  } else {
    int left_lower = (mm[mm.size()/2] + mm[mm.size()/2-1]);
    int right_higher = (dd[dd.size()/2] + dd[dd.size()/2-1]);
    printf("%d\n", right_higher - left_lower + 1);
  }

}


Measured memory_bytes: 6628
#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;
using   ll=long long;
using   ld=long double;

#define fast        	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ordered_set 	tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>

#define endl        	"\n"
#define pb          	push_back
#define mp          	make_pair
#define F           	first
#define S           	second
#define int             long long int

#define ALL(v)      	v.begin(),v.end()
#define ALLR(v)     	v.rbegin(),v.rend()
#define pii         	3.14159265358979323
#define inf     		LLONG_MAX
#define ones(x)     	__builtin_popcount(x)
#define fill(a,b)   	memset(a,b,sizeof(a))
#define mod 			1000000007

ll mod_pow(ll a,ll b) {
    ll res = 1;
    while(b)	
    {
        if(b&1) 	
        {
        	res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}

ll mod_inverse(ll a) {
	return mod_pow(a , mod-2);
}

void solve() {
	
	int n , m, k;
	
	cin >> n >> m >> k;
	
	int a[n];
	int b[m];
	
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	for(int i = 0; i < m; ++i) {
		cin >> b[i];
		
		if(i != 0) {
			b[i] += b[i-1];
		}
	}
	
	int mx = 0;
	int sm = 0;
	
	for(int i = 0; i <= n; ++i) {
		
		if(i != 0)  {
			sm += a[i-1];
		}
		
		if(sm > k) {
			break;
		}
		
		auto u = upper_bound(b,b+m, k - sm) - b;
		
		mx = max(mx , i + u);
	}
	
	cout<< mx;
}

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

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5+23;

int a[N], parent[N], SIZE[N];

int find_set(int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (SIZE[a] < SIZE[b]) swap(a, b);
    parent[b] = a;
    SIZE[a] += SIZE[b];
  }
}

void solve() {
  int n, m; scanf("%d%d", &n, &m);
  for (int p, i = 0; i < n; ++i) {
    scanf("%d", &p);
    a[p-1] = i;
    parent[i] = i;
    SIZE[i] = 1;
  }
  for (int x, y, i = 0; i < m; ++i) {
    scanf("%d %d", &x, &y);
    --x; --y;
    union_sets(x, y);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (find_set(i) == find_set(a[i])) ++ans;
  }
  printf("%d", ans);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4944
s = gets.split

stk = []

s.each{|t|
    case t
    when '+'
        snd = stk.pop
        fst = stk.pop
        stk.push(fst + snd)
    when '-'
        snd = stk.pop
        fst = stk.pop
        stk.push(fst - snd)
    when '*'
        snd = stk.pop
        fst = stk.pop
        stk.push(fst * snd)
    else
        stk.push(t.to_i)
    end
}

p stk[-1]


Measured memory_bytes: 6872
n,k=map(int,input().split())
d=[0]*k
A=[]

for i in range(k):
    d=int(input())
    A+=list(map(int,input().split()))
    list(set(A))
cnt=0
for i in range(n):
    if i+1 not in A:
        cnt+=1
print(cnt)


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

typedef pair<long long, long long> P;
int main(){
    int n;
    cin>>n;
    vector<long long> v;
    rep(i,n){
        long long a;
        cin>>a;
        v.push_back(a);
    }
    long long ans=__gcd(v[0],v[1]);
    for(int i=2; i<n; i++){
       ans=__gcd(ans,v[i]);
    }
    cout<<ans<<endl;
}

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

int main() {
    ll N,T;
    cin >> N>>T;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin >>A[i];
    }
    vector<ll> B(N);
    ll m = 0;
    ll mostDif =0;
    for(int i=N-1;i>=0;--i){
        m = max(m,A[i]);
        B[i] = m;
        mostDif = max(mostDif,B[i]-A[i]);
    }
    // cerr << mostDif<< endl;
    ll ans =0;
    for(int i=0;i<N;i++){
        if(A[i] + mostDif== B[i]){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
  int A,B,T;
  int ans = 0;
  cin >> A >> B >> T;
  for (int i=1;i<T+0.5;i++){
    if(i%A == 0){
      ans += B;
    }
  } 
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
    string O, E;

    cin >> O >> E;

    for (int i = 0; i < O.length(); i++) {
        cout << O[i];
        if (i < O.length() - 1 || O.length() == E.length()) cout << E[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n;
    cin>>n;
    long int a[n],b[n];
    for(long int i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    int temp=0;
    sort(b,b+n);
    for(long int i=0;i<n;i++)
    {
        if(a[i]!=b[i])
        temp++;
    }
    if(temp==0||temp==2)
    cout<<"YES";
    else
    cout<<"NO";
}

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

#define MAXN (15)

int n;
int p[MAXN];

int main() {
    scanf("%d", &n);
    int max = 0;
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", p + i);
        max = std::max(max, p[i]);
        sum += p[i];
    }
    printf("%d\n", sum - (max >> 1));
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int K = 42;
const int N = K * (K - 1) + 1;
int ans[N][K];
int main() {
    for (int i = 0; i < K; i++) {
        ans[0][i] = i + 1;
    }
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j < K; j++) {
            ans[(i - 1) * (K - 1) + j][0] = i;
        }
    }
    for (int i = 1; i < K; i++) {
        for (int j = 1; j < K; j++) {
            ans[i][j] = K + (i - 1) * (K - 1) + j;
        }
    }
    for (int i = 0; i < K - 1; i++) {
        for (int k = 1; k < K; k++) {
            for (int j = 1; j < K; j++) {
                ans[(i + 1) * (K - 1) + k][j] =
                    ans[j][(k + i * (j - 1) - 1) % (K - 1) + 1];
            }
        }
    }
    printf("%d %d\n", N, K);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            printf("%d%c", ans[i][j], " \n"[j == K - 1]);
        }
    }
    return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;




int main(){
    string s;cin >> s;
    int n = s.length();
    if(s[n-1] == '1'||s[0] != '1'){
        puts("-1");
        return 0;
    }
    int sz = (n + 1) / 2;
    for (int i = 0; i < sz; i++) {
        if(s[i] != s[n-2-i]){
            puts("-1");
            return 0;
        }
    }
    vector<P> ans(n-1);
    int u=1,v=2;
    for (int i = 0; i < n-1; i++) {
        if(i > sz){
            ans[i] = make_pair(u,v);
            v++;
        }
        else{
            if(s[i] == '1'){
                ans[i] = make_pair(u,v);
                u = v;
                v++;
            }
            else{
                ans[i] = make_pair(u,v);
                v++;
            }
        }
    }
    for (int i = 0; i < n-1; i++) {
        cout << ans[i].fs << " " << ans[i].sc << endl;
    }
    return 0;
}


Measured memory_bytes: 3200