akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Mll = M<ll, ll>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin(),ie=(c).rend();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;
string s;

int main() {
    cin >> s;
    Vi m(26, 0);

    for (auto c: s) {
        m[c-'a']++;
    }

    REP(i, 26) {
        if (m[i]%2 != 0) {
            cout << "No" << '\n';
            return 0;
        }
    }
    cout << "Yes" << '\n';

    return 0;
}


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

template <typename T>
constexpr T my_gcd(T a, T b)
{
    if (a < b)
        my_gcd<T>(b, a);
    T r = 0;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

int N;
long long X;
int main()
{
    std::cin >> N >> X;
    long long temp;
    long long ans;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> temp;
        if (i == 0)
            ans = std::abs(X - temp);
        else
            ans = my_gcd(ans, std::abs(X - temp));
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

n = lines[0][0]
m = lines[0][1]

hights = lines[1]

connected = []
for i in 1..n do
  connected[i-1] = []
end

for i in 1..m do
  go_from = lines[i+1][0]
  go_to = lines[i+1][1]
  connected[go_from-1].push(go_to)
  connected[go_to-1].push(go_from)
end

answer = 0
for i in 1..n do
  good_spot = 1
  for j in connected[i-1] do
    if hights[i-1] <= hights[j-1] then
      good_spot = 0
      break
    end
  end
  answer += good_spot
end
  
print answer

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

int main() {
  string S;
  cin >> S;
  
  int N;
  N = S.size();

  string ans = "Yes";
  for (int i = 0; i < (N - 1) / 2; i ++) {
    if (S[i] != S[(N - 3) / 2 - i]) ans = "No";
    if (S[(N + 1) / 2 + i] != S[N - 1 - i]) ans = "No";
    if (S[i] != S[(N + 1) / 2 + i]) ans = "No";
    if (S[(N - 3) / 2 - i] != S[N - 1 - i]) ans = "No";
  }
  cout << ans << endl;
}


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

#define sf(n) scanf("%d",&n)
#define sfl(n) scanf("%lld",&n)
#define sfd(n) scanf("%lf",&n)
#define sfc(n) scanf(" %c",&n)
#define endll pf("\n")
#define pf printf
#define pi acos(-1.0)
#define eps 1e-10
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define xx first
#define yy second
#define pii pair<int,int >
#define pll pair<ll int,ll int >
#define ll long long
#define MP make_pair
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define cnd tree[idx]
#define lnd tree[idx<<1]
#define rnd tree[(idx<<1)+1]
#define lndp (idx<<1),(b),((b+e)>>1)
#define rndp ((idx<<1)+1),(((b+e)>>1)+1),(e)
#define inf 1999999999
#define MX 100005
#define mod 1000000007
#define var int i,j,k,l,m,n,z=0,c=0,x,y,t,r,mid
//int dx[8]={0,0,1,1,-1,-1,1,-1};
//int dy[8]={1,-1,1,-1,1,-1,0,0};
//int dx[4]={1,-1,0,0};
//int dy[4]={0,0,1,-1};

ll int bigmod(ll int x,ll int y,ll int m)
{
    if(y==0)return 1;
    ll n=bigmod(x,y/2,m);
    n=(n*n)%m;
    if(y & 1)n=((n%m)*(x%m))%m;
    return n;
}

void subset(int n)
{
    int i,j,sz=(1<<n);
    for(i=1;i<sz;i++)
    {
        for(j=0;j<n;j++)
        {
            if((1<<j)&i)
            {
                //cout<<j<<" ";
            }
        }
        //endll;
    }
}


int main()
{
    var;
    cin>>n>>m;
    z=n+m;
    z%=3;
    if(z==0 || n%3==0 || m%3==0)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
ll sum[51]={},p[51]={};
ll solve(ll n,ll x){
    if(n==0) return 1;
    if(x<=n) return 0;
    if(x<=sum[n]/2) return solve(n-1,x-1);
    if(x==sum[n]/2+1) return solve(n-1,x-1)+1;
    return p[n-1]+1+solve(n-1,x-sum[n]/2-1);
}
int main(void){
    ll n,x;
    cin>>n>>x;
    sum[0]=1,p[0]=1;
    for(int i=1;i<=50;i++){
        sum[i]=2*sum[i-1]+3;
        p[i]=2*p[i-1]+1;
    }
    cout<<solve(n,x)<<endl;
}

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

int main(){
  string s;
  cin >> s;
  rep(i,s.size()) s[i] = 'x';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 764
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    C = [[A[i], B[i]] for i in range(N)]
    C.sort()
    ans = 0
    i = 0
    while True:
        if C[i][1]<M:
            M -= C[i][1]
            ans += C[i][0]*C[i][1]
        else:
            ans += C[i][0]*M
            break
        i += 1
    print(ans)

    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 21652
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.nio.Buffer;
import java.util.*;

class Main {
    public static void main(String[] args){
        try {
            PrintWriter out=new PrintWriter(System.out,true);
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int t=Integer.parseInt(br.readLine());
            t=t%1000;
            t=1000-t;
            if(t==1000){
                t=0;
            }
            out.println(t);
            out.close();
        } catch (Exception e) {
            System.out.println("kkkk "+ e.getMessage());
        }

    }
}

Measured memory_bytes: 32816
#include <bits/stdc++.h>
using namespace std;
typedef int64_t LL;
const LL MOD=1e9+7;
LL bnm(int n,int k,LL mod)
{
  LL coef=1;
  vector<LL> sieve(n+1,0);
  if(n==k||k==0){coef=1;return coef;}
  k=min(k,n-k);
  for(LL p=2;p<=n;p++)
  {
    if(sieve.at(p)==0)
    {
      for(LL i=p*p;i<=n;i+=p)
      {
        sieve.at(i)=1;
      }
      for(LL r=p;r<=n;r*=p)
      {
        LL cnt=n/r-k/r-(n-k)/r;
        for(LL j=0;j<cnt;j++)
        {
          coef*=p;
          coef%=mod;
        }
      }
    }
  }
  return coef;
}
int main()
{
  int x,y,z;
  cin>>x>>y;
  if((x+y)%3>0){cout<<0<<endl;return 0;}
  z=(x+y)/3;
  x-=z;
  y-=z;
  if(x<0||y<0){cout<<0<<endl;return 0;}
  cout<<bnm(x+y,x,MOD)<<endl;
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    set<string> s;
    rep(i, n){
        string t;
        cin >> t;
        s.insert(t);
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 19260
h,w=map(int,input().split())
s=[input() for _ in range(h)]
infi=10**18
dp=[[infi]*w for _ in range(h)]
if s[0][0]=='#':
  dp[0][0]=1
else:
  dp[0][0]=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
    else:
      if i<h-1:
        if s[i+1][j]=='.':
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        else:
          dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      if j<w-1:
        if s[i][j+1]=='.':
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
        else:
          dp[i][j+1]=min(dp[i][j+1],dp[i][j])
print(dp[h-1][w-1])

Measured memory_bytes: 3188
#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() {
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
    return 0;
}

Measured memory_bytes: 256
def gcd(x,y):
    while not y == 0:
        x,y = y,x%y
    return x

def lcm(x,y):
    return (x*y)//gcd(x,y)

N = int(input())
T = list(int(input())for i in range(N))
tmp =1
for i in T:
    tmp =lcm(tmp,i)
print(tmp)

Measured memory_bytes: 3060
import sys
bbn=1000000007
	
#+++++

		
def main():
	a = int(input())
	s = input()
	ret=0
	for ci,cj,ck in zip(s,s[1:],s[2:]):
		if (ci,cj,ck)==('A','B','C'):
			ret+=1
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

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

    int a,b,c;
    cin>>a>>b>>c;
    int cost1 = abs(a-b)+abs(c-b);
    int cost2 = abs(b-a)+abs(c-a);
    int cost3 = abs(a-c)+abs(b-c);
    cout<<min(cost1,min(cost2,cost3));
    return 0;
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define INF 1000000000000
#define MOD 10000007
#define PI 3.14159265359
#define dij priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>
typedef long long ll;
//
vector<int> get_ans(int a,vector<vector<int>> tree,vector<int> vv){
    stack<pair<int,int>> st;
//    vector<int> ans(a);
    rep(i,tree[0].size()){
        st.push(make_pair(0,tree[0][i]));
    }
    vector<bool> flag(a,false);
    flag[0]=true;
    while(!st.empty()){
        auto p=st.top();st.pop();
        if(flag[p.S])continue;
        else{
        vv[p.S]+=vv[p.F]; 
        for(auto e:tree[p.S]){
            st.push(make_pair(p.S,e));
        }
        flag[p.S]=true;
        }
    }
    return vv;
}
int main(){
    int n,q;cin>>n>>q;
    vector<vector<int>> tree(n);
    rep(i,n-1){
        int a,b;cin>>a>>b;
        a--;b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    vector<int> vv(n,0);
    vector<pair<int,int>> v(q);
    rep(i,q){
        int a,b;cin>>a>>b;
        a--;
        v[i]=make_pair(a,b);
        vv[a]+=b;
    }
    vector<int> ans(n,0);
//    rep(i,q){
        ans=get_ans(n,tree,vv);
//        for(auto e:vvv)cout<<e;cout<<endl;
//    }
    for(auto e:ans)cout<<e<<" ";cout<<endl;
}


Measured memory_bytes: 32136
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int X; cin >> X;
    for(int i=9;i>=1;i--){
        if(X>=i*200){
            cout << 10-i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 3624
import sys

import numba as nb

input = sys.stdin.readline


@nb.njit("i8(List(i8, reflected=True),i8)", cache=True)
def binary_search(a, key):
    """Meguru type binary search"""
    ok = -1
    ng = len(a)

    def is_ok(a, key, idx):
        if a[idx] < key:
            return True
        else:
            return False

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(a, key, mid):
            ok = mid
        else:
            ng = mid

    return ok


@nb.njit("i8(i8,List(i8, reflected=True))", cache=True)
def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = binary_search(L, L[a] + L[b])
            ans += (x - b)
    return ans


def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = solve(N, L)

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 106908
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <inttypes.h>

int compare_int(const void *a, const void *b){//qsort 整数比較<
	return *(int*)a - *(int*)b;
}
int compare_int2(const void *a, const void *b){//qsort 整数比較>
	return *(int*)b - *(int*)a;
}

int main(void){
	int a;
	int answer;

	scanf("%d",&a);
	answer=a+a*a+a*a*a;
	printf("%d",answer);
	return 0;
}


Measured memory_bytes: 1732
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

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

Measured memory_bytes: 256
from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

count = 0
while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

Measured memory_bytes: 88028
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin>>s;
    if(s[0]==s[s.length()-1]){
        if(s.length()&1)cout<<"Second"<<endl;
        else cout<<"First"<<endl;
    }
    else{
        if(s.length()&1)cout<<"First"<<endl;
        else cout<<"Second"<<endl;
    }
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

using namespace std;

int computeSimple(int initial, int year, double rate,int change){
	int money = initial;//資金
	int interestSum = 0;//積み重ねた利子の和
	for(int i=0;i<year;i++){//O(year)
		int interest = money*rate;//この年の利子
		interestSum += interest;
		money -= change;//年の最後に手数料を取る
	}
	return money + interestSum;
}

int computeCompound(int initial, int year, double rate,int change){
	int money = initial;
	for(int i=0;i<year;i++){//O(year)
		int interest = money*rate;//この年の利子
		money += interest;
		money -= change;
	}
	return money;
}

int main(){
	int m;
	cin >> m;
	for(int i=0;i<m;i++){
		int initial;//初期資金
		int year;//運用年数
		int n;//運用方法の種類の数
		cin >> initial >> year >> n;
		int maxmoney = 0;//求める最大値
		for(int j=0;j<n;j++){
			bool isCompound;//1(true)が入力されると複利
			double rate;
			int charge;//手数料
			cin >> isCompound >> rate >> charge;
			int result;//最終的なお金
			if(isCompound){
				result = computeCompound(initial,year,rate,charge);
			}else{
				result = computeSimple(initial,year,rate,charge);
			}
			maxmoney = max(result,maxmoney);
		}
		cout << maxmoney << endl;
	}
	return 0;
}

/*
<メモ>
単利:simple interest
複利:compound interest
compoundは混ぜ合わせるという意味
*/

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll n;
	cin>>n;
	ll an=(n*(n-1))/2;
	cout<<an;
	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("-O3")
/*
				C++
				encoding: UTF-8
				Last Modified: 24/Nov/19 05:38:18 PM
*/

#include <bits/stdc++.h>
#ifdef H4wk3ye
#	include <prettypr.hpp>
#endif

using namespace std;

// clang-format off

#define		int                    long long
#define		ve                     vector
#define		pb                     push_back
#define		endl                   "\n"
#define		ff                     first
#define		ss                     second
#define		pii                    pair<int, int>
#define		len(v)                 (int)v.size()
#define		all(v)                 v.begin(), v.end()
#define		reset(a, b)            memset(a, b, sizeof(a));
#define		fr(i, s, n)            for (int i = s ; i < n ; ++i)
#define		dfr(i, s, n)           for (int i = s ; i > n ; --i)

template < typename T > void pr (const T& t) {
    cout << t << "\n";
}

template < typename T, typename U, typename... ARGS >
void pr (const T& t, const U& u, const ARGS&... args) {
    cout << t << " ";
    pr (u, args...);
}

// clang-format on


signed main () {
	ios_base::sync_with_stdio (false), cin.tie (nullptr);
	int n;
	string s;
	cin >> n >> s;
	fr (i, 0, len (s)) {
		s[i] = (s[i] + n - 'A') % 26 + 'A';
	}
	pr (s);
	return 0;
}

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

int main(){
    int H, W;
    cin >> H >> W;
    
    char bd[1010][1010];
    for (int i=0; i<1010; ++i) {
        for (int j=0; j<1010; ++j) {
            bd[i][j] = '_';
        }
    }

    queue<pair<pair<int, int>, int> > q;
    for (int i=1; i<=H; ++i) {
        for (int j=1; j<=W; ++j) {
            cin >> bd[i][j];
            if (bd[i][j] == '#') {
                q.push(make_pair(make_pair(i, j), 0));
            }
        }
    }

    int cnt = 0;
    while ( ! q.empty()) {
        auto t = q.front(); q.pop();
        int i = t.first.first;
        int j = t.first.second;
        int k = t.second;

        cnt = max(cnt, k);

        if (bd[i-1][j] == '.') {
            bd[i-1][j] = '#';
            q.push(make_pair(make_pair(i-1, j), k+1));
        }
        if (bd[i+1][j] == '.') {
            bd[i+1][j] = '#';
            q.push(make_pair(make_pair(i+1, j), k+1));
        }
        if (bd[i][j-1] == '.') {
            bd[i][j-1] = '#';
            q.push(make_pair(make_pair(i, j-1), k+1));
        }
        if (bd[i][j+1] == '.') {
            bd[i][j+1] = '#';
            q.push(make_pair(make_pair(i, j+1), k+1));
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 13328
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define res(i,n) for(int i=n;;i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define REV(i,n) for(int i=n-1;i>0;i--)
#define req(i,n,m) for(int i=n;i<m;i++)
#define REQ(i,n,m,l) for(int i=n;i<m;i+=l) 
#define _GLIBCXX_DEBUG
int INF = 1e9 + 7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
    unsigned day;
    if (dow < dow1) dow += 7;
    day = dow - dow1;
    day += 7 * n - 6;
    return day;
}
signed gcd(long long x, long long y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
signed lcm(long long x, long long y) {
    return x / gcd(x, y) * y;
}
unsigned DayToWeekNumber(unsigned day)
{
    return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
    return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main() {
    int H, W; cin >> H >> W;
    vector<vector<char>>D(H * 2, vector<char>(W));
    rep(i, H) {
        string S; cin >> S;
        rep(j, 2) {
            rep(k, W)cout << S.at(k);
            cout << endl;
        }
    }
}

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

typedef long long int ll;

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

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

int main(){
  ll a,b;
  cin >> a >>b;
  cout<<lcm(a,b)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf ll(10e15)
short int isL(ll n)
{
    ll last=n%10;
    n/=10;
    while(n)
    {
        if(abs(n%10-last)>1)
            return false;
        last=n%10;
        n/=10;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll t;
    t=1;
    while(t--)
    {
        ll n,count=0,i;
        cin>>n;
        queue<ll> q;
        for(int j=1;j<10;++j)
            q.push(j);

        while(count<n)
        {
            i=q.front();
            q.pop();
            if(i%10)
            q.push(10*i+i%10-1);

            q.push(10*i+i%10);

            if(i%10!=9)
            q.push(10*i+i%10+1);
            ++count;
        }
        cout<<i<<endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

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

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

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

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(ios_base::fixed);
    cout.precision(12);

    var(int, N, x, t);

    print((N + x - 1) / x * t);

    return 0;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

ll XOR(ll A) {
    ll ans = 0;
    rep(i, 50) {
        ll loop = 1LL << (i + 1);
        ll cnt = (A + 1) / loop * (loop / 2);
        cnt += max(0LL, ((A + 1) % loop) - (loop / 2));
        if (cnt % 2 == 1) {
            ans += 1LL << i;
        }
    }

    return ans;
}

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

    ll ans = XOR(B) ^ XOR(A - 1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

numbers = input().split(" ")
n = int(numbers[0])
m = int(numbers[1])

numbers = input().split(" ")
h = [int(x) for x in numbers]
h.insert(0, 0)

is_good = [1] * (n + 1)

for i in range(m):
  numbers = input().split(" ")
  a = int(numbers[0])
  b = int(numbers[1])
  if h[a] <= h[b]:
    is_good[a] = 0
  if h[a] >= h[b]:
    is_good[b] = 0

print(is_good.count(1) - 1)


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

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

    int i;
    bool clear = true;
    for(i=0; i<tap.length(); i++){
        if(tap[i]!='L' && tap[i]!='R' && tap[i]!='U' && tap[i]!='D'){
            break;
        }
        if(i%2 == 0){
            if(tap[i]!='R' && tap[i]!='U' && tap[i]!='D') clear = false;
        }else{
            if(tap[i]!='L' && tap[i]!='U' && tap[i]!='D') clear = false;
        }
    }

    if(clear) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
	vector<string> T{"Sunny", "Cloudy", "Rainy"};
	string s; cin>>s;
	cout<< (s==T[0]? T[1]: s==T[1]? T[2]: T[0]) <<endl;
}

Measured memory_bytes: 256
import bisect
def find_left(P,position):
    N=len(P)
    left1=[-1]*N
    left2=[-1]*N
    stack=[]
    popped=[[] for i in range(len(P))]
    stack=[P[0]]
    for i in range(1,len(P)):
        while stack:
            if stack[-1]<P[i]:
                
                popped[i]+=[stack.pop()]
            else:
                left1[i]=stack[-1]
                stack+=[P[i]]
                
                break
                
        if stack==[]:
            stack+=[P[i]]
            left1[i]=-1
        if left1[i]==-1:
            left2[i]==-1
        else:
            val=left1[i]
            pos=position[val]
            big_val_pos=len(popped[pos])
            if popped[pos]:
                big_val_pos=bisect.bisect_left(popped[pos],P[i])
                if big_val_pos<len(popped[pos]):
                    left2[i]=popped[pos][big_val_pos]
            #for x in popped[pos]:
            #    if x>P[i]:
            #        left2[i]=x
            #        break
                    
            
            
            if left2[i]==-1:
                if len(stack)>=3:
                    left2[i]=stack[-3]
    #print(popped)
    return left1,left2


def find_right(P,position):
    position=[len(P)-x-1 for x in position]
    right1,right2=find_left(P[::-1],position)
    return right1[::-1],right2[::-1]
input()
P=list(map(int,input().strip().split(" ")))



N=len(P)
P=[p-1 for p in P]
position=[0]*len(P)
for i in range(len(P)):
    position[P[i]]=i

left1,left2=find_left(P,position)
right1,right2=find_right(P,position)

for i in range(N):
    if left1[i]!=-1:
        left1[i]=position[left1[i]]
    if left2[i]!=-1:
        left2[i]=position[left2[i]]
    
    if right1[i]==-1:
        right1[i]=N
    else:
        right1[i]=position[right1[i]]
    
    if right2[i]==-1:
        right2[i]=N
    else:
        right2[i]=position[right2[i]]
        
#print(P)
#print(left1,left2)
#print(right1,right2)

ans=0
for i in range(N):
    L1,L2,R1,R2=left1[i],left2[i],right1[i],right2[i]
    val=P[i]+1
    if val==N:
        
        continue
    temp=0
    if L1==-1:
        temp+=(i+1)*(R2-R1)
    elif R1==N:
        temp+=(L1-L2)*(N-i)
    else:
        temp+=(L1-L2)*(R1-i)
        temp+=(i-L1)*(R2-R1)
    
    ans+=temp*val
    
print(ans)
        
    



Measured memory_bytes: 87020
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};


int main() {
    int a,b; cin>>a>>b;
    string S,T;
    for(int i=0;i<a;++i) S+=to_string(b);
    for(int i=0;i<b;++i) T+=to_string(a);
    cout<<min(S,T)<<endl;
    return 0;
}


Measured memory_bytes: 256
n = input()
hana = 0
taro = 0
while True:
  try:
    a, b = input().split()
    if a < b:
      hana += 3
    elif a == b:
      hana += 1
      taro += 1
    else:
      taro += 3
  except EOFError:
    break
print(taro, hana)


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

int main() {
  int a , b , R;
  cin >> a >> b;

  R = a * b;
  if ((R % 2) == 0) {
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }  
}


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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    bool ok = true;
    rep(i,n){
        if (i%2 == 0 && s[i] == 'L') ok = false ;
        if (i%2 == 1 && s[i] == 'R') ok = false ;
    }
    if (ok) puts("Yes"); else puts("No");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

vector <ll> a,b;

int main() {
   

    ll n;
    cin >> n;
    ll suma = 0;
    ll sumb = 0;
    for (ll i=0;i<n;i++){
        ll p;
        cin >> p;
        suma += p;
        a.push_back(p);
    }
    for (ll i=0;i<n;i++){
        ll p;
        cin >> p;
        sumb += p;
        b.push_back(p);
    }
    if(suma < sumb){
        cout << -1 << endl;
    }else{
        vector <ll> sub;
        for (ll i=0;i<n;i++){
            sub.push_back(a[i] - b[i]);
        }
        sort(sub.begin(), sub.end());
//        for (ll i=0;i<n;i++){
//            cout << sub[i] << endl;
//        }
//        cout << sub[0] + sub[1] + sub[2] << endl;
//        cout << sub[n-1] << endl;

        ll ans = 0;
        ll maxind = n;
        ll minind = 0;
        for (ll i=0;i<n;i++) {
            if (sub[i] >= 0) {
                minind = i;
                break;
            }
            if (maxind >= n) {
                maxind--;
            }
            while (sub[i] < 0) {
                if (sub[maxind] == 0) {
                    maxind--;
                }
                if (sub[maxind] >= abs(sub[i])) {
                    sub[maxind] += sub[i];
                    sub[i] = 0;
                } else {
                    sub[i] += sub[maxind];
                    sub[maxind] = 0;
//                maxind --;
                }
            }
//            cout << i << endl;
        }
//        cout << endl;
//        for (ll i=0;i<n;i++){
//            cout << sub[i] << endl;
//        }
//        cout << endl;
//        cout << sub[0] + sub[1] + sub[2] << endl;
//        cout << sub[n-1] << endl;

        cout << (n-maxind) + minind << endl;
    }

}




Measured memory_bytes: 3316
#include<iostream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define mp make_pair
#define pb push_back
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

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

const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int n,m;
char in[99];

int main()
{
  while(scanf("%d%d",&m,&n),m){
    int r=m,c=0; bool a[1000];
    rep(i,m)a[i]=1;

    for(int i=1;i<=n;i++){
      for(;!a[c];c=(c+1)%m);
      scanf("%s",in);
      if(r==1)continue;
      if(i%15==0){
	if(strcmp(in,"FizzBuzz"))a[c]=0,r--;
      }
      else if(i%5==0){
	if(strcmp(in,"Buzz"))a[c]=0,r--;
      }
      else if(i%3==0){
	if(strcmp(in,"Fizz"))a[c]=0,r--;
      }
      else{
	if(!isdigit(in[0])||atoi(in)!=i)a[c]=0,r--;
      }
      c=(c+1)%m;
    }
    bool f=1;
    rep(i,m)if(a[i]){
      if(!f)putchar(' '); else f=0;
      printf("%d",i+1);
    }
    puts("");
  }
  return 0;
}

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

struct SegTree
{
    int N;
    vector<int> seg;

    SegTree(int n)
    {
        N = 1;
        while(N<n) N<<=1;
        seg.assign(2*N-1,INT_MAX);
    }

    void update(int k,int x)
    {
        k += N-1;

        seg[k] = x;

        while(k>0)
        {
            k = (k-1)/2;
            seg[k] = min(seg[k*2+1],seg[k*2+2]);
        }
    }

    int query(int a,int b) { return query(a,b,0,0,N); }

    int query(int a,int b,int k,int l,int r)
    {
        if ( r <= a || b <= l ) return INT_MAX;
        if ( a <= l && r <= b ) return seg[k];

        return min(query(a,b,k*2+1,l,(l+r)/2), query(a,b,k*2+2,(l+r)/2,r));
    }
};

int main()
{
    int N,Q;

    cin >> N >> Q;

    SegTree seg(N);

    for(int i=0;i<Q;i++)
    {
        int c,x,y;
        cin >> c >> x >> y;

        if(c)
        {
            cout << seg.query(x,y+1) << endl;
        }
        else
        {
            seg.update(x,y);
        }
    }
}

Measured memory_bytes: 2060
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N,W=map(int,input().split())
G=[list() for i in range(10)]

for i in range(10):
    tmp=list(map(int,input().split()))
    for j in range(10):
        if(i!=j):
            G[i].append(edge(j,tmp[j]))
            #G[j].append(edge(i,tmp[j])) #無向グラフならこれも


ans=[0 for _ in range(10)]
for j in range(N):
    tmp=list(map(int,input().split()))
    for i in tmp:
        if(i!=-1):
            ans[i]+=1


def dijkstra(o):
    d=[float('inf') for i in range(10)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(10)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev

s=0
for i in range(len(ans)):
    if(ans[i]!=0):
        s+=dijkstra(i)[0][1]*ans[i]
print(s)

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>

int main(int argc, char const* argv[]) {
	int a,b;
	a = 12300;b = 99;
	a = 2, b=100000009;
	std::cin >> a >> b;
	std::cout << a/b << " " ;
	std::cout << a%b << " " ;
	std::cout.precision(50);
	std::cout << std::fixed << std::setprecision(8) <<  static_cast<double>(a)/b << std::endl;
	return 0;
}

Measured memory_bytes: 1248
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define yorn(f) puts((f)?"safe":"unsafe")
#define YORN(f) puts((f)?"ABC":"ARC")
//ll s,w;
//ld ;
string s;
// char c;

int main() {
  cin >> s;
  YORN(s[1] == 'R');
  return 0;
}

Measured memory_bytes: 3588
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm> // sort
#include <math.h>
#include <map>
#include <set>

#define DEBUG 0

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
                    //999999997000000003
                    //1000000000000000000

using namespace std;

int solve(){

    int H,W,K;
    cin >> H >> W >> K;

    vector <string> c(H);
    REP(i,H)
    {
        cin >> c[i];
    }

    //全探索でよさそう
    //該当行、該当列は計算しない
    //どこか1列、でなく全部選ぶやつだった
    int res = 0;
    //ターゲット設定
    for(int bit_i = 0; bit_i < (1 << H); ++bit_i)
    {
        for(int bit_j = 0; bit_j < (1 << W); ++bit_j)
        {
            int cnt = 0;
            REP(x,H)
            {
                REP(y,W)
                {
                    if((1<<x) & bit_i)continue;
                    if((1<<y) & bit_j)continue;
                    if(c[x][y] == '#')++cnt;
                }
            }
            if(cnt == K)++res;
        }
    }
    cout << res << endl;



    return 0;
}

int main()
{
    solve();
    return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 3005, mod = 1e9 + 7;
 
inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}
 
int n, m, f[maxn][maxn][2], fac[maxn << 1], ifac[maxn << 1];
 
int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
 
int C(int n, int m)
{
	return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
 
int main()
{
	n = gi(); m = gi();
 
	fac[0] = ifac[0] = ifac[1] = 1;
	for (int i = 1; i <= n + m; ++i) fac[i] = (ll)fac[i - 1] * i % mod;
	for (int i = 2; i <= n + m; ++i) ifac[i] = (ll)(mod - mod / i) * ifac[mod % i] % mod;
	for (int i = 1; i <= n + m; ++i) ifac[i] = (ll)ifac[i - 1] * ifac[i] % mod;
	
	for (int i = 0; i <= n; ++i) f[0][i][i == 0] = 1;
 
	for (int i = 0; i < m; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k < 2; ++k) {
				if (!f[i][j]) continue;
				if (j) f[i + 1][j - 1][k | (j == 1)] = add(f[i + 1][j - 1][k | (j == 1)], f[i][j][k]);
				if (j < n) f[i + 1][j + 1][k] = add(f[i + 1][j + 1][k], f[i][j][k]);
				if (j) f[i + 1][j][k | (j == 1)] = add(f[i + 1][j][k | (j == 1)], f[i][j][k]);
				if (j < n) f[i + 1][j][k] = add(f[i + 1][j][k], f[i][j][k]);
			}
	int ans = 0;
	for (int i = 0; i <= n; ++i) ans = add(ans, f[m][i][1]);
	printf("%d\n", ans);
	
	return 0;
}
 


Measured memory_bytes: 70784
n,m = map(int,input().split())
ab = [[-1] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if ab[a-1][-1] == -1:
        ab[a-1][-1] = b-1
    else:
        ab[a-1].append(b-1)
flg = False
for i, mid in enumerate(ab[0]):
    if n-1 in ab[mid]:
        flg = True
        break

if flg :print('POSSIBLE')
else:print('IMPOSSIBLE')


Measured memory_bytes: 31860
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // dequef
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower

#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> x(n), y(n);
  //vector<ll> defx(n), defy(n);
  map<pii, int> board;
  rep(i, n){
    cin >> x[i] >> y[i];
    board[make_pair(y[i], x[i])] = 1;
  }
  sort(all(x)); sort(all(y));
  ll ans = (x[n - 1] - x[0]) * (y[n - 1] - y[0]);
  vector<vector<ll>> rui(n + 1, vector<ll>(n + 1));
  rep(dx, n){
    rep(dy, n){
      rui[dy + 1][dx + 1] = rui[dy][dx + 1] + rui[dy + 1][dx] - rui[dy][dx] + board[make_pair(y[dy], x[dx])];
    }
  }
  rep(dx, n){
    for(ll ddx = dx; ddx < n; ddx++){
      rep(dy, n){
        for(ll ddy = dy; ddy < n; ddy++){
          ll num = rui[ddy + 1][ddx + 1] - rui[dy][ddx + 1] - rui[ddy + 1][dx] + rui[dy][dx];
          if(num >= k) ans = min(ans, (x[ddx] - x[dx]) * (y[ddy] - y[dy]));
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
# include <bits/stdc++.h>
# define pb push_back
# define ll long long
# define fi first
# define se second
# define all(vc) vc.begin(),vc.end()
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define DEBUG

using namespace std;

const int N = 100 + 7;
const int mod = 1e9 + 7;

int n, a[N], sum, m, x, y, ans;

int main()
{
    speed;
    /// Author: Dilshod--Imomov
    #ifdef DEBUGh
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif // DEBUG
    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> a[i];
        sum += a[i];
    }
    cin >> m;
    for ( int i = 0; i < m; i++ ) {
        cin >> x >> y;
        ans = sum;
        ans = ans - a[x - 1] + y;
        cout << ans << endl;
    }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,c;cin>>N;
  for(int i=1; i<=N;i++){
    int a;cin>>a;
    if(a!=i)c++;
  }
  cout << ( c==2||c==0 ? "YES":"NO")<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

int n, m, s, t;
VI e[100010];

void solve() {
  cin >> n >> m;
  REP(i, m) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    e[u].push_back(v);
  }
  cin >> s >> t;
  s--;
  t--;

  set<int> vis1;
  set<int> vis2;
  set<int> vis3;
  vis3.insert(s);
  queue<pair <int, int> > q;
  q.push(make_pair(s, 0));
  while(q.size() > 0) {
    pair <int, int> node = q.front();
    q.pop();
    int v = node.first;
    int cost = node.second;
    if (v == t) {
      cout << cost << endl;
      return;
    }

    VI v1s;
    REP(i, SZ(e[v])) {
      if (vis1.count(e[v][i]) == 0) {
        v1s.push_back(e[v][i]);
        vis1.insert(e[v][i]);
      }
    }
    VI v2s;
    REP(i, SZ(v1s)) REP(j, SZ(e[v1s[i]])){
      int next = e[v1s[i]][j];
      if (vis2.count(next) == 0) {
        v2s.push_back(next);
        vis2.insert(next);
      }
    }
    REP(i, SZ(v2s)) REP(j, SZ(e[v2s[i]])) {
      int next = e[v2s[i]][j];
      if (vis3.count(next) == 0) {
        q.push(make_pair(next, cost+1));
        vis3.insert(next);
      }
    }

  }
  cout << -1 << endl;

}

int main() {
	solve();
	return 0;
}


Measured memory_bytes: 19840
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, k;
  cin >> n >> k;
  vl a(n), f(n);
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> f[i];
  sort(all(a));
  sort(all(f), greater<ll>());
  vl c(n);
  rep(i, n) c[i] = a[i] * f[i];
  ll ng = -1, ok = a[n - 1] * f[0];
  while(ng + 1 < ok) {
    ll x = (ng + ok) / 2;
    ll cost = 0;
    rep(i, n) {
      ll now = (c[i] - x + f[i] - 1) / f[i];
      if(now > 0) cost += now;
    }
    if(cost > k)
      ng = x;
    else
      ok = x;
  }
  cout << ok << endl;
}

Measured memory_bytes: 4992
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
c = [a[i]-i-1 for i in range(n)]
c.sort()
mn = s = sum(c[1:])-(n-1)*c[0]
for i in range(n-1):
    s += (2*i+2-n)*(c[i+1]-c[i])
    mn = min(mn,s)
print(mn)


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

int main()
{
    int a,b,c; cin >> a >> b >> c;
    ll k; cin >> k; ll ans;

    //aだけでなんとかする
    if(a>=k) ans = k;
    else if(a+b>=k) ans = a;
    else ans = a - (k - a - b);

    cout << ans << endl;

    return 0;
}

/*
Ctrl+@
g++ a.cpp
./a.out
*/

Measured memory_bytes: 3596