akhauriyash/Code-Regression huggingface dataset:
import sys, math,os
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
sys.setrecursionlimit(100000)
from fractions import Fraction
INF = float('inf')
mod = 998244353


def main():

    n=int(data())
    A=mdata()
    act=[0]*(n+1)
    t=1
    if n==0 and A[0]!=1:
        out(-1)
        exit()
    for i in range(n):
        act[i]=t-A[i]
        if act[i]<0:
            out(-1)
            exit()
        t=act[i]*2
    for i in range(n,0,-1):
        if act[i-1]<(act[i]+A[i])//2+(act[i]+A[i])%2 :
            out(-1)
            exit()
        act[i-1]=min(act[i]+A[i],act[i-1])
    ans=0
    for i in range(n):
        if act[i]<(act[i+1]+A[i+1])//2+(act[i+1]+A[i+1])%2 or act[i]>(act[i+1]+A[i+1]):
            out(-1)
            exit()
    for i in range(n+1):
        ans+=act[i]+A[i]
    out(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 674720
Q = int(input())
lr_list = [list(map(int, input().split())) for _ in range(Q)]

max_val = max([lr[1] for lr in lr_list])

# エラトステネスの篩
num_list = list(range(max_val + 1))
for num in num_list[2:max_val // 2 + 1]:
    if num > 0:
        for i in range(num*2, max_val+1, num):
            num_list[i] = -1

prime_num_set = set([num for num in num_list if num>0][1:])

# 累積和
sum_list = [0, 0, 0]
for i in range(3, max_val+1):
    if i in prime_num_set and (i+1)//2 in prime_num_set:
        sum_list.append(sum_list[-1]+1)
    else:
        sum_list.append(sum_list[-1])

for l, r in lr_list:
    print(sum_list[r] - sum_list[l-1])


Measured memory_bytes: 33656
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()
#define ADD(a, b) a = (a + b) % MOD

ll pow(ll x, ll n)
{
  if (n == 0)
    return 1;
  ll res = pow(x * x % MOD, n / 2);
  if (n & 1)
    res = res * x % MOD;
  return res;
}

ll inv(ll n)
{
  return pow(n, MOD - 2);
}

int main()
{
  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N)
  cin >> A[i];
  vector<ll> fact(N + 1); // 1!, 2!, N!
  vector<ll> h(N + 1);    // 1/1 + 1/2 + ... + 1/N
  fact[0] = 1;
  h[0] = 0;
  REP(i, N)
  {
    fact[i + 1] = (i + 1) * fact[i] % MOD;
    ADD(h[i + 1], (inv(i + 1) + h[i]) % MOD);
  }
  ll ans = 0;
  REP(i, N)
  {
    ll tmp = A[i] * fact[N] % MOD;
    tmp *= ((h[i + 1] + h[N - i] - h[1]) % MOD) % MOD;
    ADD(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    int n, m; cin >> n >> m;
    map<int, vector<int>> jobs;
    while (m--) {
        int s, t; cin >> s >> t;
        jobs[s].emplace_back(t);
    }
    vector<int> dp(n + 1);
    for (int s = 1; s <= n; s++) {
        chmax(dp[s], dp[s - 1]);
        for (int t: jobs[s]) chmax(dp[t], dp[s] + 1);
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 11520
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  long long W, H;
  std::cin >> W >> H;
  long long x, y;
  std::cin >> x >> y;

  // Main
  // double xMin = std::min(x * H, (W - x) * H);
  // double yMin = std::min(y * W, (H - y) * W);
  // double res = std::max(xMin, yMin);
  double res = (double)H * W / 2;

  // Output
  std::printf("%.10f ", res);
  // std::cout << res << " ";

  if (x == (W / 2) and W % 2 == 0 and y == (H / 2) and H % 2 == 0)
    std::cout << 1 << std::endl;
  else
    std::cout << 0 << std::endl;

  return 0;
}


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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            string szLine = Console.ReadLine();
            
            long n = long.Parse(szLine);
            var dic = new Dictionary<long, int>();// key 数字、value 総数

            for (long i = 0;i<n;++i)
            {
                szLine = Console.ReadLine();
                long a = long.Parse(szLine);
                if( dic.ContainsKey(a))
                {
                    dic[a]++;
                }
                else
                {
                    dic.Add(a, 1);
                }
            }
            int total = 0;
            var keys = dic.Keys;
            foreach(long a in keys)
            {
                if( dic[a] % 2 != 0)
                {
                    total += 1;
                }
            }

            Console.WriteLine(total);
        }
    }
}


Measured memory_bytes: 23264
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int n;
    string name,board;
    cin>>n>>name;
 
    int ans=0;
    bool solve;
    for(int i=0;i<n;i++){
        cin>>board;
        solve=false;
        for(int j=0;j<board.size();j++){
        	for(int k=1;k<board.size();k++){
        		if(j>k){
        			continue;
        		}
                if(j+(k-j)*(name.size()-1)>=board.size() || solve==true){
                    break;
                }
                if(board[j]==name[0] && board[k]==name[1]){
                    for(int l=2;l<name.size();l++){
                        if(board[j+(k-j)*l]==name[l]){
                            solve=true;
                            if(name.size()-1==l){
                                break;
                            }
                        } else{
                        	solve=false;
                            break;
                        }
                    }
                }
            }
        }
        if(solve){
          ans++;
        }
    }
 
    cout<<ans<<endl;
 
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

typedef pair<pair<ll, ll>, ll> p;
typedef pair<ll, ll> pii;

ll n;
p ps1[100000], ps2[100000];

struct edge {
	ll to, cost;
};
vector<edge> es[100000];

int main(int argc, char **argv) {
	cin >> n;
	REP(i, n) {
		ps1[i].second = i;
		cin >> ps1[i].first.first >> ps1[i].first.second;
		ps2[i] = ps1[i];
		swap(ps2[i].first.first, ps2[i].first.second);
	}
	sort(ps1, ps1 + n);
	sort(ps2, ps2 + n);

	REP(i, n - 1) {
		ll x1 = ps1[i].first.first, y1 = ps1[i].first.second, n1 = ps1[i].second;
		ll x2 = ps1[i + 1].first.first, y2 = ps1[i + 1].first.second, n2 = ps1[i + 1].second;
		ll c = min(abs(x1 - x2), abs(y1 - y2));
		es[n1].push_back({ n2, c });
		es[n2].push_back({ n1,c });
		x1 = ps2[i].first.first, y1 = ps2[i].first.second, n1 = ps2[i].second;
		x2 = ps2[i + 1].first.first, y2 = ps2[i + 1].first.second, n2 = ps2[i + 1].second;
		c = min(abs(x1 - x2), abs(y1 - y2));
		es[n1].push_back({ n2, c });
		es[n2].push_back({ n1,c });
	}

	set<ll> ved;
	ved.insert(0);
	priority_queue<pii, vector<pii>, greater<pii>> q;
	REP(i, es[0].size()) q.push(MP(es[0][i].cost, es[0][i].to));
	ll res = 0;
	REP(i, n - 1) {
		pii t;
		while (true) {
			t = q.top(); q.pop();
			if (!ved.count(t.second)) break;
		}
		ved.insert(t.second);
		res += t.first;
		REP(j, es[t.second].size()) q.push(MP(es[t.second][j].cost, es[t.second][j].to));
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 24560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}




int main(){

  ll N;
  cin >> N;
  vector<ll> A(N),B(N);
  FOR(i,0,N) cin >> A[i] >> B[i];
  SORT(A);
  SORT(B);

  ll l,r;
  if(N%2 == 0){
    l = A[N/2] + A[N/2 - 1];
    r = B[N/2] + B[N/2 - 1];
  }else{
    l = A[N/2];
    r = B[N/2];
  }

  cout << r-l+1 << endl;

}




Measured memory_bytes: 6440
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

int BIT[ 500010 ][30],n,q,t,l,r,pos,ans;
char ch;
string s;

void updateBIT( int pos , int f , int val ){

    while( pos <= n ){
        BIT[ pos ][ f ]+=val;
        pos+=(pos&(-pos));
    }

    return;
}

int queryBIT( int pos , int f ){

    int myAns = 0;
    while( pos > 0 ){
        myAns+=BIT[ pos ][ f ];
        pos-=(pos&(-pos));
    }

    return myAns;
}

int main()
{

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

    cin >> n >> s >> q;
    for(int i=1; i<=n; i++) updateBIT( i , s[i-1]-'a' , 1 );

    while( q-- ){
        cin >> t;
        if( t == 1 ){
            cin >> pos >> ch;
            updateBIT( pos , s[pos-1]-'a' , -1 );
            s[pos-1] = ch;
            updateBIT( pos , s[pos-1]-'a' , 1 );
        }else{
            cin >> l >> r;
            ans = 0;
            for(int i=0; i<='z'-'a'; i++) ans+=min( queryBIT( r , i )-queryBIT( l-1 , i ) , 1 );
            cout << ans << "\n";
        }
    }

    return 0;
}


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

int main(){
  int a,b;
  cin >> a >> b;
  
  if (((a % 2) == 0) || ((b % 2) == 0)){
    cout << "Even" << endl;
  }else {
    cout << "Odd" << endl;
  }
}

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

int main() {
  int N,M,b;
  cin >> N >> M;
  priority_queue<int> a;
  for (int i=0; i < N; i++) {
    cin >> b;
    a.push(b);
  }
  for (int i=0; i < M; i++) {
    b = a.top();
    b /= 2;
    a.pop();
    a.push(b);
  }
  int64_t sum = 0;
  for (int i=0; i < N; i++) {
    sum += a.top();
    a.pop();
  }
  cout << sum << endl;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

void solve(long long N) {
    mint ans = mint(10).pow(N);
    ans = ans - mint(9).pow(N) * 2 + mint(8).pow(N);
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main() {
    long long N;
    scanf("%lld", &N);
    solve(N);
    return 0;
}


Measured memory_bytes: 3764
#include <iostream>
#include <cstdlib>
using namespace std;
int main(void){
  string w;
  int cnt[26] = {0};
  cin >> w;
  for(int i = 0; i < w.size(); i++) cnt[w[i]-'a']++;
  for(int i = 0; i < 26; i++){
    if(cnt[i]%2 == 1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream> 
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<sstream>
using namespace std;
 
#define sf scanf
#define pf printf
#define pfn printf("\n");
#define pfk printf(" ");
#define pf0 printf("0");
#define pf1 printf("1");
#define ll long long
#define sfd(n) scanf("%d",&n);
#define sfdd(n,m) scanf("%d%d",&n,&m);
#define sfld(n) scanf("%lld",&n);
#define sfldd(n,m) scanf("%lld%lld",&n,&m);
#define sflf(n) scanf("%lf",&n);
#define sflff(n,m) scanf("%lf%lf",&n,&m);
#define sfc(n) scanf("%c",n);
#define sfcc(n,m) scanf("%c%c",n,m);
#define sfs(n) scanf("%s",n);
#define sfss(n,m) scanf("%s%s",n,m);
#define pfd(n) printf("%d",n);
#define pfld(n) printf("%lld",n);
#define pflf(n) printf("%lf",n);
#define pfc(n) printf("%c",n);
#define pfs(n) printf("%s",n);
 
#define csh(a,n) memset(a,n,sizeof(a));
int main(){
	int n,m,t,a,b;
	cin>>n;
	string arr;
	cin>>arr;
	for(int i=0;i<arr.length();i++){
		cout<<char((arr[i]-'A'+n)%26+'A');
	}
	
}

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

#define MOD 1000000007

int N;
vector<vector<int>> a, memo;

long long solve(int i, int s) {
    // 男性 i 人（男性 0 〜 男性 i-1）が
    // 集合 s に含まれる女性とペアを作っている場合の
    // 残りの男女でペアを作る方法の数（memo[i][s]の値）を返す

    // i==N なら、全員ペアを作ったので、1通りを返す
    if (i == N) return 1;

    // すでに計算済みならメモの値を返す
    if (memo[i][s] != -1) return memo[i][s];

    long long ans = 0;

    // i < N なら、男性 i のペア相手を探す
    for (int j = 0; j < N; j++) {
        // 女性 j についてチェック
        if ((s & (1 << j)) != 0) {
            // 女性 j がすでにペアを組んでいるならパス
            continue;
        }
        if (a[i][j] == 1) {
            // 男性 i が女性 j とペアになれるなら
            // 二人をペアにして、残りのパターン数を足す
            ans += solve(i + 1, s ^ (1 << j));
            ans %= MOD;
        }
    }
    // メモに記録
    memo[i][s] = ans;
    return ans;
}

int main(void) {
    cin >> N;
    // N×N の配列を用意
    a = vector<vector<int>>(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
    }

    // (N+1)×2^N のDP用配列を用意
    memo = vector<vector<int>>(N + 1, vector<int>(1 << N, -1));
    // memo[i][s]:
    //   男性 i 人（男性 0 〜 男性 i-1）が
    //   集合 s に含まれる女性とペアを作っている場合の
    //   残りの男女でペアを作る方法の数を返す

    // memo[0][0] の値が答え
    cout << solve(0, 0) << endl;

    return 0;
}


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

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

  for (int i = 0; i < s.size() - 1; i++) {
    for (int j = i + 1; j < s.size(); j++) {
      if (s.at(i) == s.at(j)) {
        cout << "no" << endl;
        return 0;
      }
    }
  }
  cout << "yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N;
    vector<int> inv = {};
    cin >> N;
    for (int i = 0; i < N; i++) {
        int tempI;
        cin >> tempI;
        inv.push_back(tempI);
    }
    sort(inv.begin(), inv.end());
    
    int finSub = 0;
    int tempC = 0;
    int tempI = inv[0];
    for (int i = 1; i <= inv.size(); i++) {
        tempC++;
        if (tempI != inv[i]) {
            if (tempC >= tempI) {
                finSub += tempC - tempI;
                tempC = 0;
            } else {
                finSub += tempC;
                tempC = 0;
            }
        tempI = inv[i];
        }
    }
    if (inv[N] == inv[0]) {
        if (N > inv[0]) {
            finSub += N - inv[0];
        } else if (N == inv[0]) {
            finSub = 0;
        } else {
            finSub += N;
        }
    }
    cout << finSub;
}


Measured memory_bytes: 892
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    K = int(input())
    ans = 1
    for i in range(N):
        ans = min(ans*2,ans+K)
    print(ans)
    
if __name__ == '__main__':
    main()


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

namespace ABC096C
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            int h = input[0];
            int w = input[1];

            char[][] s = new char[h][];
            for(int i = 0; i < h; i++)
            {
                s[i] = Console.ReadLine().ToCharArray();
            }

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

            bool isYes = true;
            bool isFinished = false;
            for(int y = 0; y < h; y++)
            {
                for(int x = 0; x < w; x++)
                {
                    if (s[y][x] == '#')
                    {
                        bool isSharp = false;
                        for (int i = 0; i < 4; i++)
                        {
                            int nx = x + dx[i];
                            int ny = y + dy[i];

                            if (nx < 0 || w <= nx || ny < 0 || h <= ny)
                            {
                                continue;
                            }

                            if (s[ny][nx] == '#')
                            {
                                isSharp = true;
                                break;
                            }
                        }
                        if (!isSharp)
                        {
                            isYes = false;
                            isFinished = true;
                            break;
                        }
                    }
                }
                if (isFinished)
                {
                    break;
                }
            }

            if (isYes)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

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

ll ngcd(vector<ll> a) {
  ll res = a[0];
  for(ll i=1; i<a.size() && res!=1; i++) res = gcd(a[i], res);
  return res;
}
ll nlcm(vector<ll> a){
  ll res = a[0];
  for(ll i=1; i<a.size(); i++) res = lcm(a[i], res);
  return res;
}
bool is_prime(ll n) {
  if(n < 2) return false;
  for (ll i = 2; i * i <= n; i++) if (n % i == 0) return false;
  return true;
}
ll digsum(ll n) {
  ll res=0;
  while(n) res += n%10, n /= 10;
  return res;
}
ll digcnt(ll n){
  ll res=0;
  while(n) res++, n /= 10;
  return res;
}
vector<ll> divisor(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) res.push_back(n / i);
    }
  }
  sort(res.begin(), res.end());
  return res;
}
map<ll, ll> prime_factor(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) ++res[i], n /= i;
  }
  if (n != 1) res[n] = 1;
  return res;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  ll ans=0;
  for(auto e: divisor(n)){
    if(e==1) continue;
    ll tmp=n;
    while(tmp%e==0) tmp/=e;
    if(tmp%e==1) ans++;
  }
  cout<<ans+divisor(n-1).size()-1<<endl;
}

Measured memory_bytes: 384
/*
 *
 *   Author     : Amit Kumar
 *   Date    	: August 20 , 2019
 * 
 */

#include <climits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FAST_INPUT_OUTPUT
//#define MORE_THAN_ONE_TESTCASE // COMMENT IT

#define vi vector<int>
#define vl vector<long long>
#define mii map<int , int>
#define mll map<long long , long long>
#define msi map<string , i>
#define msl map<string , long long>
#define umii unordered_map<int,int>
#define umll unordered_map<long long ,long long>
#define umsi unordered_map<string , int>
#define umsl map<string , long long> 
#define si set<int>
#define sl set<long long>
#define pii pair<int , int >
#define psi pair<string,int>
#define psl pair<string , long > 
#define pll pair<long long , long long>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpsi vector<psi>
#define vpsl vector<psl>
#define pqi priority_queue<int>
#define pql priority_queue<long long>
#define ub upper_bound
#define lb lower_bound
#define bint long long int
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define iv(v) for(auto &i:v){cin>>i;}
#define ov(v) for(auto i:v){cout<<i<<" ";}cout<<endl;
#define ovn(v) for(auto i:v){cout<<i<<endl;}
#define euv(v) for(auto i:v){cerr<<i<<" ";}cerr<<endl;
#define eovn(v) for(auto i:v){cerr<<i<<endl;}
#define os(s) for(auto itr:s){cout<<itr<<" ";}cout<<endl;
#define osn(s) for(auto itr:s){cout<<itr<<endl;}
#define eos(s) for(auto itr:s){cerr<<itr<<" ";}cerr<<endl;
#define eosn(s) for(auto itr:s){cerr<<itr<<endl;}
#define rep(x) for(auto i=0 ; i<(x); ++i)
#define _rep(a,b) for(auto i=(a); i<(b); ++i)
#define ef else if
#define wh while
#define el else
#define ivv(x) int x; cin>>x
#define lv(x) bint x; cin>>x
#define sv(x) string x; cin>>x
#define cv(x) char x; cin>>x
#define fv(x) float x; cin>>x
#define dv(x) double x; cin>>x
#define endl '\n'
using namespace std;




auto SOLUTION_FUNCTION( void ) ->void {
    // your solution goes here 
    ivv(N);
    vi v(N);
    iv(v);
    bint sum = accumulate(all(v),0);
    ivv(M);
    while(M--){
        ivv(p);ivv(x);
        p--;
        sum-=v.at(p);
        sum+=x;
        cout<<sum<<endl;
        sum-=x;
        sum+=v.at(p);
    }
    return ;
}




int main(void){
#ifdef FAST_INPUT_OUTPUT
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout<<setprecision(10);
    cout<<fixed;
    cout<<boolalpha;
#endif
#ifdef MY_LOCAL_PROJECT
    freopen("input","r",stdin);
    freopen("output","w",stdout);
#endif
    int testcase = 1;


#ifdef MORE_THAN_ONE_TESTCASE
    cin>>testcase;
#endif
    
    while(testcase--){
        SOLUTION_FUNCTION();
    }

#ifdef MY_LOCAL_PROJECT
    cout<<"Time : "<<1.0*(double)clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

ll a,b,n;

ll check(ll x){return (a*x)/b-a*(x/b);}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>a>>b>>n;
	ll L=1,R=n;
	while(R-L>10){
		ll m1=L+(R-L)/3;
		ll m2=R-(R-L)/3;
		if(check(m1)>check(m2))
			R=m2-1;
		else
			L=m1+1;
	}
	ll mx=0;
	// cout<<"R="<<R<<" L="<<L<<'\n';
	for(ll i=L;i<=min(n,R);i++){
		// cout<<"check("<<i<<")="<<check(i)<<'\n';
		if(check(i)>mx){
			mx=check(i);
		}
	}
	cout<<mx<<'\n';
	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;

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

	vector<int> A(N);
	rep(i, N) cin >> A[i];
	sort(A.begin(), A.end());

	vector<int> B(N);
	rep(i, N) cin >> B[i];
	sort(B.begin(), B.end());

	vector<int> C(N);
	rep(i, N) cin >> C[i];
	sort(C.begin(), C.end());

	long long ans = 0;
	rep(i, N)
	{
		auto position = lower_bound(A.begin(),A.end(),B[i]);
		long long A_count = distance(A.begin(),position);

		position = upper_bound(C.begin(), C.end(), B[i]);
		long long C_count = distance(position, C.end());

		ans += A_count * C_count;
	}

	cout << ans << endl;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <iostream>
#include <cstring>
#include <bitset>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>

int n;
long long a[1000010], A[1000010];

int main()
{
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> a[i];
    }
    long long s = 0;
    for (long long i = 1, minus = 1; i < n; ++i)
    {
        s += minus * a[i];
        minus = -minus;
    }
    A[1] = a[n] + s;
    for (int i = 2; i <= n; ++i)
    {
        A[i] = 2 * a[i - 1] - A[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        std::cout << A[i] << " ";
    return 0;
}

Measured memory_bytes: 6272
from operator import itemgetter
N, X = map(int, input().split())
S = [list(map(int, input().split())) for i in range(N)]
A = []
aoki = 0
for i, (b, l, u) in enumerate(S):
    A.append([(X-b)*u + (b)*l, i])
    aoki += b*l
A.sort(reverse=True, key=itemgetter(0))
ans = 0
tak = 0
for iaaaa, (a, i) in enumerate(A):
    if aoki >= a:
        aoki -= a
        ans += X
        if aoki==0:
            print(ans)
            exit()
    else:
        break
mi = float("inf")
aoki_ = aoki
for j in range(iaaaa, N):
    a, i = A[j]
    b, l, u = S[i]
    aoki = aoki_
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)
ans_ = ans + mi

a, i = A[iaaaa]
aoki_ -= a
#aoki_ = -aoki
anss = (iaaaa)*X
mi = float("inf")
for a, i in A[:iaaaa]:
    b, l, u = S[i]
    aoki = aoki_ + a
    an, m = divmod(aoki, l)
    if m!=0:
        an += 1
    mi = min(mi, an)
    aoki += (u-l) * b
    an, m = divmod(aoki, u)
    if m!=0:
        an += 1
    mi = min(mi, an)

print(min(ans_, anss+mi))


Measured memory_bytes: 46444
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] sciences = new int[4];
		int[] socials = new int[2];
		int total = 0;
		for (int i = 0; i < sciences.length; i++) {
		    sciences[i] = sc.nextInt();
		    total += sciences[i];
		}
		Arrays.sort(sciences);
		for (int i = 0; i < socials.length; i++) {
		    socials[i] = sc.nextInt();
		    total += socials[i];
		}
		Arrays.sort(socials);
		System.out.println(total - sciences[0] - socials[0]);
	}
}



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

///for ordered set///
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
///for ordered set///

using namespace std;

///for ordered set///
//using namespace __gnu_pbds;
//typedef tree< long long int , null_type, less_equal<long long int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
///for ordered set///

///Compiler Optimizer///
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
///Compiler Optimizer///

typedef long long           ll;
typedef unsigned long long  ull;

#define sf                  scanf
#define pf                  printf
#define pb                  push_back
#define ppb                 pop_back
#define MP                  make_pair
#define PF                  first
#define PS                  second
#define si(n)               scanf("%d",&n)
#define sii(x,y)            scanf("%d %d",&x,&y)
#define siii(x,y,z)         scanf("%d %d %d",&x,&y,&z)
#define sl(n)               scanf("%lld",&n)
#define sll(x,y)            scanf("%lld %lld",&x,&y)
#define slll(x,y,z)         scanf("%lld %lld %lld",&x,&y,&z)
#define FOR(i,x,y)          for(int i=x;i<y;i++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define CLR(arr,val)        memset(arr,val,sizeof arr);
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define TCL(test,t)         for(test=1;test<=t;test++)
#define READ()              freopen("input.txt", "r", stdin)
#define WRITE()             freopen("output.txt", "w", stdout)
#define fastIO()            {ios_base::sync_with_stdio(false); cin.tie(NULL);}
#define MAXN                1000006
#define MAXP                1000006
#define MOD                 1000000007
#define PI                  acos(-1)

int main(){
    #ifdef ELDUIVEL
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5]){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    #ifdef ELDUIVEL
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
string b[8];
int main() {
    for (int i=0; i<8; i++) cin>>b[i];
    cout<<90<<endl;
    for (int i=0; i<8; i++) {
        for (int j=7; j>=0; j--) {
            cout<<b[j][i];
        }
        cout<<endl;
    }
    cout<<180<<endl;
    for (int i=7; i>=0; i--) {
        for (int j=7; j>=0; j--) {
            cout<<b[i][j];
        }
        cout<<endl;
    }
    cout<<270<<endl;
    for (int i=7; i>=0; i--) {
        for (int j=0; j<8; j++) {
            cout<<b[j][i];
        }
        cout<<endl;
    }
}

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

int main() {
  int n,k;
  cin >> n >> k;
  for (int i = 0; i < k+2; i++) {
    cout << "#";
  }
  cout << endl;
  string s;
  for (int i = 0; i < n; i++) {
    cin >> s;
    cout << "#" << s << "#" << endl;
  }
  for (int i = 0; i < k+2; i++) {
    cout << "#";
  }
}


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

int main(void) {
    int a, b;
    cin >> a >> b;
    a = (a + 11) % 13;
    b = (b + 11) % 13;
    if (a > b) cout << "Alice" << endl;
    else if (a < b) cout << "Bob" << endl;
    else if (a == b) cout << "Draw" << endl;
}


Measured memory_bytes: 256
import numpy as np
N = input()
K = int(input())
L = len(N)
dp0 = [[0]*(K+1) for i in range(L+1)]
dp1 = [[0]*(K+1) for i in range(L+1)]
dp0[0][0] = 1
for i in range(1,L+1):#i桁目
  c = int(N[i-1])
  for j in range(K+1):#k個0を使っているとする
    if j==0:
      if c>0:
        dp1[i][j] = dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = 0
      else:
        dp1[i][j] = dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
    else:
      if c>0:
        dp1[i][j] = dp0[i-1][j-1]*(c-1)+dp1[i-1][j-1]*9+dp1[i-1][j]+dp0[i-1][j]
        dp0[i][j] = dp0[i-1][j-1]
      else:
        dp1[i][j] = dp1[i-1][j-1]*9+dp1[i-1][j]
        dp0[i][j] = dp0[i-1][j]
print(dp0[-1][-1]+dp1[-1][-1])


Measured memory_bytes: 12872
//#include<bits/stdc++.h>
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double db;
typedef long double ldb;
#define rep(i,a,b) for(i=a;i<b;i++)
#define repu(i,a,b) for(i=a;i<=b;i++)
#define repd(i,a,b) for(i=a;i>=b;i--)
#define repc(i,a,b,c) for(i=a;i<b;i+=c)
#define repcu(i,a,b,c) for(i=a;i<=b;i+=c)
#define repcd(i,a,b,c) for(i=a;i>=b;i-=c)
#define FIN freopen("input.in","r",stdin)
#define FOUT freopen("output.out","w",stdout)
#define CC(a) memset(a,0,sizeof(a))
#define MST(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define VI vector<int>
#define VL vector<long long>
#define VII vector<PII>
#define VLL vector<PLL>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
 
template<typename T>inline void gn(T &x){
	x=0;T f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
template<typename T>inline void gt(T x){
	if(!x)return;
	gt(x/10);putchar(x%10+'0');
}
 
const LL MAXN=2e6+10;
LL t,n,m,ans,cnt;
LL MOD=1e9+7,inf=1e10;
db eps=1e-5;

string a,b;

int main()
{
	//ios_base::sync_with_stdio(false);cin.tie(0);
	LL i,j,k,l,ca=0;
	cin>>a;l=a.size();
	repu(i,0,3)cout<<a[i];
	cout<<" ";
	rep(i,4,l)cout<<a[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.lang.*;
import java.io.*;
import java.util.*;

class Main{
	public static void main(String args[]) throws Exception{
		FScanner sc=new FScanner();
		int[] num=sc.readIntL();
		System.out.println(num[0]+(num[1]/2));
	}

	static void disp(int[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%d ",data[i]);
		}
			System.out.println();
	}
	
	static void disp(String[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%s ",data[i]);
		}
			System.out.println();
	}
	
	static void disp(long[] data){
		for(int i=0; i<data.length; i++){
				System.out.printf("%d ",data[i]);
		}
			System.out.println();
	}
	
	static class FScanner{
		BufferedReader read=null;
		StringTokenizer tok=null;
		Scanner sc;
		FScanner() throws FileNotFoundException{
			sc=new Scanner(System.in);
		}
		boolean hasNextLine(){
			boolean has=true;
			if(!sc.hasNextLine()){
				has=false;
			}
			return has;
		}
		int readInt(){
			String buf=sc.nextLine();
			return Integer.parseInt(buf);
		}
		long readLong(){
			long i=Long.parseLong(sc.nextLine());
			return i;
		}
		int[] readIntL(){
			String[] buf=sc.nextLine().split(" ");
			int[] num=new int[buf.length];
			for(int i=0; i<buf.length; i++){
				num[i]=Integer.parseInt(buf[i]);
			}
			return num;
		}
		
		String readString(){
			return sc.nextLine();
		}
		String[] readStringL(String dlm){
			String[] s=sc.nextLine().split(dlm);
			return s;
		}
	}
}


Measured memory_bytes: 21844
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 make_tree(cur_idx: usize, parent_idx: usize, edges: &Vec<Vec<usize>>,
             tree: &mut Vec<Vec<usize>>) {

    for child_idx in edges[cur_idx].iter() {
        if *child_idx == parent_idx {
            continue;
        }
        tree[cur_idx].push(*child_idx);
        make_tree(*child_idx, cur_idx, edges, tree);
    }
}

fn topological_dfs(cur_idx: usize, tree: &Vec<Vec<usize>>, result: &mut Vec<usize>) {
    for child_idx in tree[cur_idx].iter() {
        result.push(*child_idx);
        topological_dfs(*child_idx, tree, result);
    }
}

fn main() {
    let n = read::<usize>();
    if n == 1 {
        println!("2");
        return;
    }
    let mut edges: Vec<Vec<usize>> = vec![Vec::new(); 2 * (n - 1)];
    for _ in 0..n - 1 {
        let v = read_vec::<usize>();
        let (a, b) = (v[0] - 1, v[1] - 1);
        edges[a].push(b);
        edges[b].push(a);
    }

    let mut tree: Vec<Vec<usize>> = vec![Vec::new(); n];
    make_tree(0, n, &edges, &mut tree);
    // println!("tree {:?}", tree);
    let mut topological_sorted_indexes = vec![0];
    topological_dfs(0, &tree, &mut topological_sorted_indexes);
    // println!("t sorted {:?}", topological_sorted_indexes);

    let mut dp_b = vec![1u64; n];
    let mut dp_w = vec![1u64; n];

    let big_int = 1000_000_000 + 7;

    for ti in topological_sorted_indexes.iter().rev() {
        if !tree[*ti].is_empty() {
            for idx in tree[*ti].iter() {
                dp_b[*ti] *= dp_w[*idx];
                dp_b[*ti] %= big_int;
                dp_w[*ti] *= dp_b[*idx] + dp_w[*idx];
                dp_w[*ti] %= big_int;
            }
        }
    }
    // println!("{:?}", dp_b);
    // println!("{:?}", dp_w);
    println!("{:?}", (dp_b[0] + dp_w[0]) % big_int);
}


Measured memory_bytes: 29692
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (1e+18) + 7;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-6;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

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

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 2000500;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}

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

void solve() {
	int lx, ly, rx, ry;
	cin >> lx >> ly >> rx >> ry;
	modint ans = 0;
	for (int x = lx; x <= rx; x++) {
		modint rsum = comb(ry + x + 1, ry);
		modint lsum = comb(ly - 1 + x + 1, ly - 1);
		ans += rsum;
		ans -= lsum;
	}
	cout << ans << endl;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	init_f(); //init();
	//int t; cin >> t; rep(i, t)solve();
	//while(cin>>n,n)solve();
	solve();
	stop
		return 0;
}

Measured memory_bytes: 31488
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

signed main(void) {
	string s;
	cin >> s;
	int index = s.size();
	while (true) {
		if (index <= 0) {
			print("YES");
			return 0;
		}
		else if (s.substr(index - 5, 5) == "dream" || s.substr(index - 5, 5) == "erase") {
			index -= 5;
		}
		else if (s.substr(index - 6, 6) == "eraser") {
			index -= 6;
		}
		else if (s.substr(index - 7, 7) == "dreamer") {
			index -= 7;
		}
		else {
			print("NO");
			return 0;
		}
	}
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)

int main(){
  ll n,m;
  cin >> n >>m;
  bool a=false;
  if(n==1)a=true;
  bool b=false;
  if(n==2)b=true;
  bool c=false;
  if(m==1)c=true;
  bool d=false;
  if(m==2)d=true;
  ll ans;
  if(a&&c)ans=1;
  else if((a&&d) ||(b&&c))ans=0;
  else if(b&&d)ans=0;
  else if(a || c)ans=n*m-2;
  else if(b || d)ans=0;
  else ans=(n-2)*(m-2);
  cout << ans << endl;
}

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

int main() {
	int n, k, x, y;
	cin >> n >> k >> x >> y;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (i <= k) {
			ans += x;
		}
		else {
			ans += y;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int p[10000],n=2,i,j;
int main(){
  *p=2;
  for(;i<10000;)
    for(;;){
    a:  n++;
      for(j=0;p[j]*p[j]<=n;j++)
	if(n%p[j]==0) goto a;
      p[++i]=n;
      break;
    }
  for(i=1;i<10000;i++)
    p[i]+=p[i-1];
  for(;;){
    scanf("%d",&n);
    if(!n) break;
    printf("%d\n",p[n-1]);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include<string>
#include<ctype.h>
using namespace std;
int main(void){
    // Your code here!
    string w,t;  //tはsentence ,zは変換用
    int a = 0,b;  //ｗが何回出たかカウントするやつ,bは小文字に変換用
    cin >> w;  // wはwordなんで、最初に読み込んでそれを使い続ける
    
    //cout << "z : " <<w << endl;
    
    while(1){
        cin >> t;   //ワード移行の文章の人単語ごとに読み取っていく
        if(t == "END_OF_TEXT") break;
        b = t.size();
        string z = "";
        
        for(int i = 0; i < b;i++){
            z += tolower(t[i]);
        }
        //cout << z << endl;
        if(w == z)  a++;  //ワードと一致しているかどうか判断して、カウントしていく
        
     }
     cout << a << endl;
     
    
}




Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> S_l(Q), S_r(Q);
    for (int i = 0; i < Q; i++)
    {
        cin >> S_l[i] >> S_r[i];
        // S_l[i]--;
        // S_r[i]--;
    }
    vector<int> S_ind(1, 0);
    int i = 1;
    while (i < N + 1)
    {
        string S_part = S.substr(i - 1, 2);
        // cout << "str" << S_part << endl;
        if (S_part == "AC")
        {
            S_ind.push_back(S_ind[i - 1]);
            S_ind.push_back(S_ind[i] + 1);
            i += 2;
        }
        else
        {
            S_ind.push_back(S_ind[i - 1]);
            i++;
        }
    }
    //for (int i = 0; i < N + 1; i++)
    //{
    //    cout << i << "th" << S_ind[i] << endl;
    //}
    for (int i = 0; i < Q; i++)
    {
        int ans = 0;
        // cout << "S_r" << S_r[i] << endl;
        //cout << "S_l" << S_l[i] << endl;
        ans += S_ind[S_r[i]] - S_ind[S_l[i]];
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 2296