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

#define select(_1, _2, x, ...) x

#define repn(i, n) for (int i = 0; i < (n); i++)
#define repr(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, ...) select(__VA_ARGS__, repr, repn)(i, __VA_ARGS__)

#define rrepn(i, n) for (int i = (n - 1); i >= 0; i--)
#define rrepr(i, a, b) for (int i = (b - 1); i >= (a); i--)
#define rrep(i, ...) select(__VA_ARGS__, rrepr, rrepn)(i, __VA_ARGS__)

#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

const int INF = 1e9;
const ll LINF = 1e18;


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

    if (a == b && a == c) {
        printf("No\n");
        return 0;
    }

    if (a != b && a != c && b != c) {
        printf("No\n");
        return 0;
    }

    if (a == b && a != c) {
        printf("Yes\n");
        return 0;
    }

    if (a == c && a != b) {
        printf("Yes\n");
        return 0;
    }

    if (c == b && a != c) {
        printf("Yes\n");
        return 0;
    }

    return 0;
}


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;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    vector<P> ab(n);
    rep(i, n) cin >> ab[i].first >> ab[i].second;
    sort(ab.begin(), ab.end());
    cout << ab[n - 1].first + ab[n - 1].second << endl; 
    return 0;
}

Measured memory_bytes: 1024
K,A,B=map(int,raw_input().split())

if B<=A+2:
    Ans=K+1
elif K<=A:
    Ans=K+1
elif (K-A)%2==1:
    Ans=B*(K-A+1)/2-A*(K-A-1)/2
else:
    Ans=B*(K-A)/2-A*(K-A-2)/2+1
print Ans

Measured memory_bytes: 2568
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int main(){

    int a[4], b, h, bl;
    while(scanf("%d %d %d %d", &a[0], &a[1], &a[2], &a[3]) != EOF) {
        set<int> s;
        h = bl = 0;
        for (int i = 0; i < 4; i++) s.insert(a[i]);
        for (int i = 0; i < 4; i++) {
            scanf("%d", &b);
            if (a[i] == b) h++;
            else if (s.find(b) != s.end()) bl++;
        }
        printf("%d %d\n", h, bl);
    }
    return 0;
}


Measured memory_bytes: 2636
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

int main() {
    int a, b;
    cin >> a >> b;
    int ans = max(a, b);
    if (a < b) {
        b--;
    } else {
        a--;
    }
    ans += max(a, b);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[input() for _ in range(h)] #マップ
vi=[ [-1 for _ in range(w)] for _ in range(h)]#visit
st=deque()
st2=deque()
st.append([ch-1,cw-1])
vi[ch-1][cw-1]=1
c=0

d=[[0,1],[-1,0],[1,0],[0,-1]]
d2=[[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],
    [-1,-2],[-1,-1],[-1,1],[1,2],[0,-2],[0,2],
    [1,-2],[1,-1],[1,1],[1,2],
    [2,-2],[2,-1],[2,0],[2,1],[2,2]]

while st or st2:
  while st:
    s2=0
    h1,w1=st.popleft()
    if dh-1==h1 and dw-1 ==w1:
      print(c)
      exit()
    for m in d:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w:
        if s[y][x]=="." and vi[y][x]==-1:
          st.append([y,x])
        elif s[y][x]=="#":s2=1
        vi[y][x]=1
    if s2==1: st2.append([h1,w1])

  while st2:
    h1,w1=st2.popleft()
    for m in d2:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w and vi[y][x]==-1 and s[y][x]==".":
        vi[y][x]=1
        st.append([y,x])
  c+=1
print(-1)

Measured memory_bytes: 94124
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false

std::vector<long long> slide_minimum(std::vector<long long> A,int K){
    std::vector<long long> R;
    int N = A.size();
    std::deque<int> D;
    for(int i=0;i<N;i++){
        while(!D.empty() && A[D.back()]>=A[i]){D.pop_back();}
        D.push_back(i);
        if(i-K+1>=0){
            R.push_back(A[D.front()]);
            if(D.front()==i-K+1){
                D.pop_front();
            }
        }
    }
    return R;
}

signed main(void){
    int N,K,p;
    vector<int> P;
    vector<int> b;
    cin >> N >> K;
    REP(i,N){
        cin >> p;
        P.push_back(p);
    }
    
    int Ans = N-K+1;
    
    b.push_back(1);
    REP(i,N-1){
        b.push_back(1);
        if(P[i]<P[i+1]){
            b[i+1]+=b[i];
        }else{
            b[i+1]=1;
        }
    }
    #if debug
    REP(i,N){cout << P[i] << " ";}cout << endl;
    REP(i,N){cout << b[i] << " ";}cout << endl;
    #endif
    
    int f=0;
    REP(i,N){
        if(b[i]==K){
            Ans--;
            f=1;
        }
    }
    Ans+=f;
    
    vector<int>m,M;
    
    m=slide_minimum(P,K+1);
    REP(i,N){P[i]*=-1;}
    M=slide_minimum(P,K+1);
    REP(i,N){P[i]*=-1;}
    REP(i,M.size()){M[i]*=-1;}
    
    #if debug
    REP(i,N-K){cout << m[i] << " ";}cout << endl;
    REP(i,N-K){cout << M[i] << " ";}cout << endl;
    #endif
    
    REP(i,m.size()){
        if(P[i]==m[i] && P[i+K]==M[i]){
            Ans--;
        }
    }
    cout << Ans << endl;
    
    return 0;
}



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

int main() {
	int ans;
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;
	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 <bits/stdc++.h>

using namespace std;

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

const long long MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
  string S, T;
  cin >> S >> T;
  int koho = (int)S.size() - (int)T.size() + 1;
  vector<string> cond;
  for (int i = 0; i < koho; ++i) {
    bool good = true;
    for (int j = 0; j < T.size(); ++j) {
      if (S[i + j] != T[j] && S[i + j] != '?') good = false;
    }
    if (good) cond.push_back(S.substr(0, i) + T + S.substr(i + T.size()));
  }
  for (int i = 0; i < cond.size(); ++i) {
    for (int j = 0; j < cond[i].size(); ++j) {
      if (cond[i][j] == '?') cond[i][j] = 'a';
    }
  }
  string res('z', 100);
  for (int i = 0; i < cond.size(); ++i) {
    res = min(res, cond[i]);
  }
  if (cond.empty()) res = "UNRESTORABLE";
  cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

void solve(int W,int N){
    vector<int> v(N),w(N);
    char c;
    rep(i,N) cin>>v[i]>>c>>w[i];

    // dp[i][j] : look until i-th , weight sum <= j
    vector<vector<int>> dp(N+10,vector<int>(W+10,0));
    for(int i=0;i<N;i++){
        // use v[i],w[i]
        for(int j=0;j<=W;j++){
            if(j+w[i]<=W){
                dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }else{
                dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            }
        }
    }

    {   // check
        int mx=0;
        for(int i=0;i<=N;i++) for(int j=0;j<=W;j++) mx = max(mx,dp[i][j]);
        assert(mx==dp[N][W]);
    }

    for(int i=0;i<=W;i++) if(dp[N][i]==dp[N][W]){
        printf("%d\n%d\n",dp[N][W],i);
        return;
    }
}

int main(){
    int w,n;
    int cnt=0;
    while(1){
        cin>>w;
        if(w==0) break;
        cin>>n;
        printf("Case %d:\n",++cnt);
        solve(w,n);
    }
}

Measured memory_bytes: 6864
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::setprecision(15);}}fIO;
template<typename T> using V = std::vector<T>;
template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; }
/*-*/

int main() {
	int n;
	std::cin >> n;
	V<lnt> a(n);
	fill(a);

	lnt g=0;
	rep(i,n) g=std::gcd(g,a[i]);

	lnt N=1e6+1;
	V<lnt> prime(N,true),primes;
	for(lnt i=2;i<N;i++) {
		if(!prime[i]) continue;
		for(lnt j=2;j*i<N;j++) {
			prime[i*j]=false;
		}
		primes.emplace_back(i);
	}
	std::map<lnt,lnt> map;
	rep(i,n) {
		for(int j=0;primes[j]*primes[j]<=a[i];j++) {
			if(a[i]%primes[j]) continue;
			map[primes[j]]++;
			while(a[i]%primes[j]==0) a[i]/=primes[j];
		}
		if(a[i]!=1) map[a[i]]++;
	}
	lnt max=0;
	for(auto e:map) max=std::max(max,e.second);
	if(max<=1) {
		print("pairwise coprime");
		return 0;
	}
	if(g==1) {
		print("setwise coprime");
		return 0;
	}
	print("not coprime");
}


Measured memory_bytes: 24292
N = int(input())
a = list(map(int,input().split()))
b = [0]*(10**5+10)
for e in a:
    b[e+1] += 1
ans = 0
for k in range(10**5+2):
    ans = max(ans,b[k]+b[k+1]+b[k+2])
print(ans)


Measured memory_bytes: 84768
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 1e9 + 7;

template <int mod>
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inv() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
};

using modint = ModInt<MOD>;

signed main() {
  int N, M;
  cin >> N >> M;
  vector<int> S(N), T(M);

  for (int i = 0; i < N; i++) cin >> S[i];
  for (int i = 0; i < M; i++) cin >> T[i];

  static modint dp[2020][2020];
  for (int i = 0; i < 2020; i++) dp[i][0] = dp[0][i] = 1;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j];
      if (S[i] != T[j]) {
        dp[i + 1][j + 1] = dp[i + 1][j + 1] - dp[i][j];
      }
    }
  }

  cout << dp[N][M].x << endl;
  return 0;
}


Measured memory_bytes: 32256
N = int(input())
ps = list(map(int, input().split()))


wrong_p = []
wrong_idx = []
for i in range(N):
    if ps[i] != i+1:
        wrong_idx.append(i)

if len(wrong_idx) == 0:
    print("YES")
elif len(wrong_idx) > 2:
    print("NO")
elif len(wrong_idx) == 1:
    print("NO")
else:
    if ps[wrong_idx[0]] == wrong_idx[1]+1:
        print("YES")
    else:
        print("NO")


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;



/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/

int n;
char s, t, b;

//(y, x)
pair<int, int> getPos(char c)
{
	switch (c)
	{
	case 'A':
		return make_pair(0, 0);
		break;
	case 'B':
		return make_pair(0, 1);
		break;
	case 'C':
		return make_pair(0, 2);
		break;
	case 'D':
		return make_pair(1, 0);
		break;
	case 'E':
		return make_pair(1, 1);
		break;
	case 'F':
		return make_pair(1, 2);
		break;
	case 'G':
		return make_pair(2, 0);
		break;
	case 'H':
		return make_pair(2, 1);
		break;
	case 'I':
		return make_pair(2, 2);
		break;
	}
}

int vx[] = {1, -1, 0, 0};
int vy[] = {0, 0, 1, -1};
int tx, ty, bx, by;
double dp[3][3][16];

double dfs(int x, int y, int n)
{
	if (dp[x][y][n] != -1) return dp[x][y][n];
	
	if (n == 0 && x == tx && y == ty) return 1;
	if (n == 0) return 0;
	
	double ret = 0;
	for (int i=0; i<4; i++)
	{
		int nx = x + vx[i];
		int ny = y + vy[i];
		if (0 <= nx && nx <= 2 && 0 <= ny && ny <= 2)
		{
			if (nx == bx && ny == by)
			{
				ret += dfs(x, y, n - 1) * 0.25;
			} else {
				ret += dfs(nx, ny, n - 1) * 0.25;
			}
		} else {
			ret += dfs(x, y, n - 1) * 0.25;
		}
	}
	
	return dp[x][y][n] = ret;
}

int main()
{
	
	while (cin >> n, n)
	{
		cin >> s >> t >> b;
		int sx = getPos(s).second;
		int sy = getPos(s).first;
		tx = getPos(t).second;
		ty = getPos(t).first;
		bx = getPos(b).second;
		by = getPos(b).first;
		rep(i, 3) rep(j, 3) rep(k, 16) dp[i][j][k] = -1;
		cout << fixed << setprecision(8);
		cout << dfs(sx, sy, n) << endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 1232
// Problem : B - Mix Juice
// Contest : AtCoder - AtCoder Beginner Contest 171
// URL : https://atcoder.jp/contests/abc171/tasks/abc171_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//mst,pq,mp,st,q
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int n,k;
		cin>>n>>k;
		int arr[n];
		for(int i=0;i<n;++i)
		cin>>arr[i];
		sort(arr,arr+n);
		int sum = 0;
		for(int i=0;i<k;++i)
		sum+=arr[i];
		cout<<sum;		
    }
    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
void solve(){
    int x,y;
    cin>>x>>y;
    if((4*x-y)%2 == 0 && (4*x-y)>=0 && (y-2*x)%2==0  && (y-2*x)>=0){
        cout<<"Yes";
    }
    else
        cout<<"No";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--){
        solve();
        cout<<endl;
    }
 }


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main(){
  int A, B;
  cin >> A >> B;
  if ((A+B)%2==0) cout << (A+B)/2 << endl;
  else cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 3572
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def time_to_zero(n, carry):
    ans = 0
    amari = 0
    if n % carry:
        amari = 1
    return n // carry + amari

def main():
    N = I()
    l = []
    ans = 0
    for i in range(5):
        al = I()
        l.append(al)
    A, B, C, D, E = l
    m = min(l)
    minute = 0
    if N % m != 0:
        minute += 1
    minute += N // m
    minute += 4
    print(minute)
    # city_capa = N
    # prev_tr_capa = A
    # for tr_capa, next_tr_capa in zip(l, l[1:]+[0]):
    #     t = time_to_zero(city_capa, tr_capa)
    #     city_capa = city_capa - (t-1) * min(tr_capa, next_tr_capa)
    #     ans += t
    # print(ans)
main()



Measured memory_bytes: 78188
#include<cstdio>
#define M 505
#define N 10000
long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}
long long lcm(long long x,long long y){return x/gcd(x,y)*y;}
int b[N],i,j,l,m,n,r,t;bool w[N];long long a[M][M];
int main()
{
	for(int i=2;i<N;i++)
	{
		if(!w[i])w[b[t++]=i]=true;
		for(j=0;i*b[j]<N;j++)
		{
			w[i*b[j]]=true;
			if(i%b[j]==0)break;
		}
	}
	scanf("%d",&n);
	for(i=1;i<=n;i++)a[i][0]=a[0][i]=a[n+1][i]=a[i][n+1]=1;
	if(n==2)return 0*puts("4 7\n23 10");
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(~(i^j)&1)a[i][j]=b[i+j>>1]*b[(n-j+(~n&1)+i>>1)+n];
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(!a[i][j])a[i][j]=lcm(lcm(a[i-1][j],a[i][j-1]),lcm(a[i][j+1],a[i+1][j]))+1;
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)printf("%lld%c",a[i][j],j==n?'\n':' ');
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int>a(2*n);
   
    for(int i = 0;i  <2*n;i++){
        a[i] = i;
    }
    /* 
    for(int j = 0;j < 2*n;j++){
                cout << a[j] + 1;
            }
            cout << endl;
    */
    for(int i = 0;i < m;i++){
        int k;
        cin >> k;
        if(k == 0){
            vector<int>b(n);
            vector<int>c(n);
            for(int j = 0;j < n ;j++){
               b[j] = a[j];
    
            }
            for(int j = 0;j < n;j++){
                c[j] = a[j + n]; 
            }
            for(int j = 0;j < n;j++){
                a[2 * j] = b[j];
                a[2 * j + 1] = c[j];
            }
            /* for(int j = 0;j < 2*n;j++){
                cout << a[j] + 1;
            }
            cout << endl;
            */

        }
        else{
            vector<int>b(k);
            vector<int>c(2*n - k);
            for(int j = 0;j < k ;j++){
               b[j] = a[j];
               //cout << b[j] + 1;
    
            }
            //cout << " b"<<endl;
            for(int j = 0;j < 2*n -k;j++){
                c[j] = a[j + k]; 
               // cout << c[j] + 1;
            }
            //cout << " c"<< endl;
            for(int j = 0;j < k ;j++){
               a[j+2*n -k] = b[j];
                
            }
            for(int j = 0;j < 2*n -k;j++){
                a[j] = c[j]; 
                
            }
            /* 
            for(int j = 0;j < 2*n;j++){
                //cout << a[j] + 1;
            }
            */
            //cout << endl;
        }
    }
    for(int i = 0;i < 2*n;i++){
        cout << a[i] + 1 << endl;
    }
    return 0;

}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
const int INFTY =2147483647;
int main(){
    ll a,b,c,k,ans=0;
    cin>>a>>b>>c>>k;
    ans+=min(a,k);
    k-=(a+b);
    if(k>0) ans-=(c,k);
    cout<<ans<<endl;
}

Measured memory_bytes: 3528
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

const ll Inf = 10000000000000000;

struct edge{
  int to;
  ll cost;
};

void dijkstra(int s, ll* d, vector<edge>* G, int N){
  fill(d, d + N, Inf);
  d[s] = 0;

  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));

  while(!que.empty()){
    P p = que.top();
    que.pop();
    int n = p.second;
    if(d[n] < p.first) continue;

    for(int i = 0; i < (int)G[n].size(); i++){
      edge e = G[n][i];
      if(d[e.to] > d[n] + e.cost){
        d[e.to] = d[n] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

//===========================================================
int main(){
  int N, M, s, t;
  cin >> N >> M >> s >> t;
  s--; t--;
  vector<edge> Ge[N], Gs[N];
  for(int i = 0; i < M; i++){
    int u, v;
    ll a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    Ge[u].push_back(edge{v, a});
    Ge[v].push_back(edge{u, a});
    Gs[u].push_back(edge{v, b});
    Gs[v].push_back(edge{u, b});
  }

  ll de[N], ds[N];
  dijkstra(s, de, Ge, N);
  dijkstra(t, ds, Gs, N);
  ll d[N];
  for(int i = 0; i < N; i++) d[i] = de[i] + ds[i];
  //for(int i = 0; i < N; i++) cout << de[i] << " " << ds[i] << endl;

  ll ans[N];
  ans[N - 1] = d[N - 1];
  for(int i = N - 2; i >= 0; i--){
    ans[i] = min(ans[i + 1], d[i]);
  }

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

  return 0;
}

Measured memory_bytes: 19836
fun main(args: Array<String>) {
    val input = System.`in`.reader().readLines().map { it.split(" ").map(String::toInt) }
    val (n, d) = input[0]
    val posList = input.subList(1, input.size)

    var result = 0
    for (i in 0..(n - 1)) {
        for (j in (i + 1)..(n - 1)) {
            var cord = 0.0
            for (c in 0..(d - 1)) {
                cord += Math.pow(Math.abs(posList[i][c] - posList[j][c]).toDouble(), 2.0)
            }
            if (Math.sqrt(cord) == Math.sqrt(cord).toInt().toDouble()) {
                result++
            }
        }
    }
    println(result)
}

Measured memory_bytes: 35596
<?php
//error_reporting(0);
//$A = trim(fgets(STDIN));
list($D,$N) = explode(" ",trim(fgets(STDIN)));
//$A  = explode(" ",trim(fgets(STDIN)));
if ($N==100) $N=101;
switch($D) {
case 0:
  printf("%d\n",$N);
  break;
case 1:
  printf("%d\n",$N*100);
  break;
case 2:
  printf("%d\n",$N*10000);
  break;
}


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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL<<60;
const ll mod =1000000007;








int main() {
	string s;
	cin >> s;
	int n = s.size();

	string t = "";
	REP(i, n) {
		if (s[i] == 'A')t += 'A';
		else if (s.substr(i, 2) == "BC") {
			t += 'B';
			i++;
		}
		else t += "Z";
	}


	ll ans = 0;
	int m = t.size();
	int cnt = 0;
	REP(i, m) {
		if (t[i] == 'A')cnt++;
		else if (t[i] == 'B') {
			ans += cnt;
		}
		else {
			cnt = 0;
		}
	}
	cout << ans << endl;

}

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

#define BLACK 0
#define WHITE 1

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

int N;
vector<ll> dp[2];
vector<vector<int>> adj;

ll dfs(int c, int v, int u) {
    if (dp[c][v] == -1) {
        dp[c][v] = 1;
        for (int w : adj[v]) {
            if (w == u)
                continue;
            ll subtree = dfs(WHITE, w, v);
            if (c == WHITE)
                subtree = (subtree + dfs(BLACK, w, v)) % MOD;
            dp[c][v] = dp[c][v] * subtree % MOD;
        }
    }
    return dp[c][v];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    adj.resize(N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dp[BLACK].assign(N, -1);
    dp[WHITE].assign(N, -1);
    cout << (dfs(BLACK, 0, 0) + dfs(WHITE, 0, 0)) % MOD << endl;
}


Measured memory_bytes: 15616
import sys
def f0070(A,n,s):
  if n==1:return s in A
  A=sorted(A)
  b1=0
  b2=0
  c=0
  j=1
  for e,f in zip(A[:n][::-1],A[-n:]):
    b1+=j*e
    b2+=j*f
    j+=1
  if b1<=s<=b2:
    for i in range(len(A)):
      c+=f0070(A[:i]+A[i+1:],n-1,s-A[i]*n)
  return c

for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

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

using namespace std;

int main()
{
  // int n;
  // std::cin >> n;
  // std::vector<long long> l(n);
  // for(int i = 0; i < n; i++)
  // {
  //   std::cin >> l[i];
  // }
  // std::sort(l.begin(), l.end());
  
  int n; cin >> n;
  vector<long long> l(n);
  for (int i = 0; i < n; ++i) cin >> l[i];
  sort(l.begin(), l.end()); // L をソートしておく (二分探索に必要)

  // long long res = 0;
  
  // long long ans = 0;
  // for(int i = 0; i < n; ++i)
  // {
  //   for(int j = i+1; j < n; ++j)
  //   {
  //     // int k = std::distance(l.begin(),std::lower_bound(l.begin(), l.end(), l[i]+l[j]));
  //     int k = std::lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin();

  //     ans += std::max(k-(j+1),0);
  //   }
  // }
  // std::cerr << ans << std::endl;
  long long ans = 0;
    
  for (int i = 0; i < n; i++) {
      for (int j = i+1; j < n; j++) {
          // int k = std::lower_bound(l.begin(), l.end(), l[i] + l[j]) - l.begin();
          int k = std::distance(l.begin(),std::lower_bound(l.begin(), l.end(), l[i]+l[j]));

          ans += std::max(k - (j+1), 0);
      }
  }
  cout << ans << endl;
}




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

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(A: int, B: int, C: int):
    if A + B >= C:
        ret = YES
    else:
        ret = NO
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    solve(A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
#define min(x,y) (x<y)?(x):(y)
int main(){
	int n,m,k,p,q,r,c[105][105],t[105][105],v[105],u[105],i,a,b,f,x,y;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(n==0 && m==0)break;
		memset(c, 0,sizeof(c));
		memset(t, 0,sizeof(t));
		for(i=0;i<n;i++){
			scanf("%d%d",&p,&q);
			scanf("%d%d",&c[p][q],&t[p][q]);
			c[q][p]=c[p][q];t[q][p]=t[p][q];
		}
		scanf("%d",&k);
		for(i=0;i<k;i++){
			scanf("%d%d%d",&p,&q,&r);
			//memset(v,-1,sizeof(v));
			memset(u,0,sizeof(u));
			for(a=0;a<=m;a++)v[a]=100000000;
			v[p]=0;f=1;
			/*while(f<m){
				x=10000000;
				for(a=1;a<=m;a++){
					if(v[a]!=-1){
						for(b=1;b<=m;b++){
							if(r==0 && v[b]==-1 && c[a][b]!=0 && x>v[a]+c[a][b])x=v[a]+c[a][b],y=b;
							if(r==1 && v[b]==-1 && t[a][b]!=0 && x>v[a]+t[a][b])x=v[a]+t[a][b],y=b;
						}
					}
				}
				v[y]=x;f++;
			}
			printf("%d\n",v[q]);*/
			while(1){
				x=-1;
				for(a=1;a<=m;a++){
					if(u[a]==0 && (x==-1 || v[a]<v[x]))x=a;
				}
				if(x==-1)break;
				u[x]=1;
				//printf("%d\n",v[x]);
				for(a=1;a<=m;a++){
					if(r==0 && c[x][a]!=0)v[a]=min(v[a],v[x]+c[x][a]);
					if(r==1 && t[x][a]!=0)v[a]=min(v[a],v[x]+t[x][a]);
				}
			}
			printf("%d\n",v[q]);
		}
	}
	return 0;
}

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

using namespace std;

int main() {

    int n;
    cin >> n;

    vector<int> v;
    vector<int> ans;

    int temp;

    for(int i = 0; i < n; ++i) {
        cin >> temp;
        v.push_back(temp);
        ans.push_back(temp);
    }

    sort(v.begin(),v.end());

    for(int i = 0; i < n; ++i) {
        int left = v[n/2 - 1];
        int right = v[n/2];

        if(ans[i] < right)
            cout << right << '\n';
        else
            cout << left << '\n';
    }

    return 0;
}


Measured memory_bytes: 3948
// #pragma GCC optimize "trapv" Uncomment when dealing with huge numbers
/*<----------PBDS---------->

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
template <typename T>
using order_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

order_set<datatype>oset;
Kth smallest : *oset.find_by_order(k-1); // 0 based index
No of elements less than k : oset.order_of_key(k);
Erase X : oset.erase(x)
<----------PBDS---------->*/
#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define pb(x) push_back(x)
#define gcd(a,b) __gcd(a,b)
#define all(v) v.begin(),v.end()
#define lcm(a,b) (a*b)/gcd(a,b)
#define bits(x) __builtin_popcountll(x)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
	int n,k;
	cin >> n >> k;
	if(n<k){
		cout << min(n,abs(n-k));
		return 0;
	}
	int ans = n%k;
	n = n%k;
	ans = min(ans,abs(n-k));
	cout << ans;
}





Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
  
public class Main{
  public static void main(String[] args){
    Scanner stdIn=new Scanner(System.in);
    int a=stdIn.nextInt(), b=stdIn.nextInt(), c=stdIn.nextInt(),d;
    if (!(a<b)){
	d=a;
	a=b;
	b=d;
    }
    if (!(a<c)){
	d=a;
	a=c;
	c=d;
    }
    if (!(b<c)){
	d=b;
	b=c;
	c=d;
    }
    System.out.println(a+" "+b+" "+c);
  }
}



Measured memory_bytes: 26416
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int mod = 1e+9 + 7;

//マクロ
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main()
{

  int N;
  cin >> N;

  vector<int> a(N + 1);
  for (int i = 1; i <= N; i++)
  {
    cin >> a[i];
  }

  vector<int> ans;
  vector<int> b(N + 1, 0);
  for (int i = N; i >= 1; i--)
  {
    int sum = 0;
    for (int j = i; j <= N; j += i)
    {
      sum += b[j];
    }
    if ((sum + a[i]) % 2 == 1)
    {
      b[i]++;
      ans.push_back(i);
    }
  }

  reverse(ans.begin(), ans.end());

  cout << ans.size() << endl;
  rep(i, ans.size())
  {
    printf("%d%c", ans[i], i + 1 == ans.size() ? '\n' : ' ');
  }
}

Measured memory_bytes: 3192
#include<iostream>
#include<stdio.h>
using namespace std;

class Dice{
	public:
		Dice(){
			number = new int[6];
			work   = new int[6];
		};
		~Dice(){
			delete[] number;
			delete[] work;
		};

		void setLabel(int index, int num){
			number[index] = num;
		};

		void roll(char dst){
			for(int i=0; i<6; ++i) work[i] = number[i];
			switch(dst){
				case 'E':
					setNumber(work[3],work[1],work[0],work[5],work[4],work[2]);
					break;
				case 'N':
					setNumber(work[1],work[5],work[2],work[3],work[0],work[4]);
					break;
				case 'S':
					setNumber(work[4],work[0],work[2],work[3],work[5],work[1]);
					break;
				case 'W':
					setNumber(work[2],work[1],work[5],work[0],work[4],work[3]);
					break;
			}
		};

		int returnPeek(){
			return number[0];
		};

	private:
		void setNumber(int n0, int n1, int n2, int n3, int n4, int n5){
		number[0] = n0;
		number[1] = n1;
		number[2] = n2;
		number[3] = n3;
		number[4] = n4;
		number[5] = n5;
		}
	private:
		int* number;
		int* work;
};

int main(){
	Dice mydice;
	int label;
	char ch;
	for(int i=0; i<6; ++i){
		cin >> label;
		mydice.setLabel(i,label);
	}
	getchar();
	while( (ch=getchar()) != EOF){
		mydice.roll(ch);
	}
	cout << mydice.returnPeek() << endl;
	return 0;
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,a,b) for(ll i=(a);i<(b);i++)
#define frr(i,a,b) for(ll i=(a-1);i>=(b);i--)
#define vi vector<int>
#define de deque<int>
#define del deque<ll>
#define vl vector<ll>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define mpp map<ll,ll>
#define rev(a) reverse(a.begin(),a.end())
#define srt(a) sort(a.begin(),a.end())
#define ln(a) a.length()
#define sz(a) a.size()
#define endl "\n"
int M=1000000007;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

ll n;cin>>n;
ll mw;cin>>mw;
ll w[n],v[n];
f(i,0,n)cin>>w[i]>>v[i];
ll dp[105][100005];
memset(dp,M,sizeof dp);
dp[0][0]=0;
f(j,1,1001)
{
    if(j<=v[0])dp[0][j]=w[0];
}
f(i,1,n)
{
    f(j,0,(i+1)*1001)
    {
        if(j>=v[i]){dp[i][j]=min(dp[i-1][j],w[i]+dp[i-1][j-v[i]]);}
        dp[i][j]=min(dp[i-1][j],dp[i][j]);
    }
}
 ll ans=0;
    f(i,0,100001)
    {
        if(dp[n-1][i]<=mw){ans=i;}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 82432
#include <bits/stdc++.h>
using namespace std;
#define senor_SR ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef int32_t i32;

#define int long long
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pf push_front

#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define RFOR(i,a,b) for(ll i=a;i>=b;i--)
#define FILL(a,b,c) for(ll i=0;i<c;i++) a[i]=b;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()

#define endl "\n"
#define setpri(x) setprecision(x)
#define vp(x) cout<<#x<<" : "<< (x)<<" | "
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define farr(a,n) for(long long i=0;i<n;i++) cin>>a[i];
#define fvec(vec,n) for(long long i=0;i<n;i++) {ll tmp;cin>>tmp;vec.pb(tmp);}
#define parr(a,n) for(long long i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define prvec(v) for(long long i=v.size()-1;i>=0;i--) cout<<v[i]<<" "; cout<<endl;
#define pvecpair(v) for(long long i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<endl;

#define INF 1e17+4
#define MINF 
#define MAX_INT 100000
#define MOD 1000000007
ll mod(ll n) { n %= MOD; if (n < 0) return n + MOD; else return n;}
// vector<int> adj[1000002];
// int vis[1000002],dep[1000002],siz[1000002];

// void dfs(ll cur,ll par)
// {
//     vis[cur]=1;siz[cur]=1;
//     for(auto x:adj[cur])
//     {
//         if(vis[x]!=1)
//         {
//             dep[x]=dep[cur]+1;
//             dfs(x,cur);
//             siz[cur]+=siz[x];
//         }    
//     }
// }

// bool myfunc1(const pair<int,int> &a, const pair<int,int> &b) { return ;}

void solve()
{
    int n,m;cin>>n>>m;
    if(m>=n)
        cout<<"unsafe";
    else 
        cout<<"safe";
       
}




signed main()
{
    senor_SR;
    
    // ll t;cin>>t;while(t--)
        solve();
 
    return 0;
}

Measured memory_bytes: 3692
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

long long ans = 1;
long long mod = (pow(10,9)+7);

int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n;i++)
    {
        ans *= i;
        ans %= mod;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;

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

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; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define mp make_pair
#define PUTLINE cout<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

int c[20][20];
int r[20][20];

int main() {
	int x,y;
	for(;;){
		cin>>x>>y;
		if(x==0&&y==0)break;
		memset(c,0,sizeof(c));
		memset(r,0,sizeof(r));
		rep(i,y)rep(j,x)c[i][j+1]=in();
		rep(i,x)if(c[0][i+1]==0)r[0][i+1]=1;
		repn(i,1,y-1)repn(j,1,x){
			if(c[i][j]==0){
				if(c[i-1][j-1]==0)r[i][j]+=r[i-1][j-1];
				if(c[i-1][j]==0)r[i][j]+=r[i-1][j];
				if(c[i-1][j+1]==0)r[i][j]+=r[i-1][j+1];
				if(i>1&&c[i-2][j]==2)r[i][j]+=r[i-2][j];
			}
			if(c[i][j]==2){
				if(c[i-1][j]==0)r[i][j]+=r[i-1][j];
				if(i>1&&c[i-2][j]==2)r[i][j]+=r[i-2][j];
			}
		}
		int result=0;
		repn(i,1,x)result+=r[y-1][i];
		repn(i,1,x)if(c[y-2][i]==2)result+=r[y-2][i];
//rep(i,y){
//rep(j,x)cout<<" "<<r[i][j+1];
//cout<<endl;
//}
		cout<<result<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
import scala.io.StdIn.{readLine,readInt}
import scala.language.postfixOps

object Main {
  private[this] var cnt = 0
  private[this] val l = new Array[Int](250001)
  private[this] val r = new Array[Int](250001)

  def merge(a:Array[Int],left:Int,mid:Int,right:Int) = {
    val n1 = mid-left
    val n2 = right-mid
    Array.copy(a,left,l,0,n1)
    l(n1) = Int.MaxValue
    Array.copy(a,mid,r,0,n2)
    r(n2) = Int.MaxValue
    var i=0
    var j=0
    for(k<-left until right) {
      if(l(i)<=r(j)){
        a(k) = l(i)
        i += 1
      } else  {
        a(k)=r(j)
        j += 1
      }
      cnt += 1
    }
  }

 def getSortIndex(n:Int):Iterator[IndexedSeq[(Int,Int)]] = {
    var w = n
    var h = 0
    while(w>1) {
      h += 1
      w = w/2
    }

    def scan(h:Int,l:List[IndexedSeq[(Int,Int)]]):List[IndexedSeq[(Int,Int)]] = {
      if(h==0) l
      else
        scan(h-1,(for(i<-l.head;j<-List((i._1,(i._2+i._1)/2),((i._2+i._1)/2,i._2))) yield j)::l)
    }
    scan(h-1,List(IndexedSeq((0,n/2),(n/2,n)))).to[Iterator]
  }

  def main(args:Array[String]) = {
    val n = readInt
    val a = readLine.split(" ").map(_.toInt)
    val l = getSortIndex(n)
    for(e2<-l) {
      for(e<-e2) {
        val mid = (e._2+e._1)/2
        if(e._2-e._1>1)
          merge(a,e._1,mid,e._2)
      }
    }
    merge(a,0,n/2,n)
    println(a.mkString(" "))
    println(cnt)
  }
}

Measured memory_bytes: 317916
(let* ((s (read-line))
       (a (parse-integer (subseq s 0 2)))
       (b (parse-integer (subseq s 2 4))))
  (cond ((and (<= 1 a 12) (<= 1 b 12)) (princ "AMBIGUOUS"))
        ((<= 1 a 12) (princ "MMYY"))
        ((<= 1 b 12) (princ "YYMM"))
        (t (princ "NA"))))

Measured memory_bytes: 10592
from math import gcd
from functools import reduce
import sys
input = sys.stdin.readline


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


def count_factor_2(num):
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    return count


def main():
    n, m = map(int, input().split())
    A = list(map(lambda x: int(x)//2, input().split()))

    check = len(set(map(count_factor_2, A)))
    if check != 1:
        print(0)
        return

    lcm_a = reduce(lcm, A)
    step = lcm_a * 2
    ans = (m + lcm_a) // step
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 21180
from collections import deque

INF = 10**18

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x) - 1, input().split())
Dh, Dw = map(lambda x:int(x) - 1, input().split())
S = [input() for _ in range(H)]

dist = [[None for j in range(W)] for i in range(H)]
dist[Ch][Cw] = 0

queue = deque()
queue.append((Ch, Cw))

while queue:
    x, y = queue.popleft()
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if dx == dy == 0:
                continue
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '#':
                continue
            if (dx == 0 and dy == 1) or (dx == 0 and dy == -1) or (dx == 1 and dy == 0) or (dx == -1 and dy == 0):
                if dist[nx][ny] == dist[x][y] + 1 or dist[nx][ny] is None:
                    dist[nx][ny] = dist[x][y]
                    queue.appendleft((nx, ny))
            else:
                if dist[nx][ny] is not None:
                    continue
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))

print(dist[Dh][Dw] if dist[Dh][Dw] is not None else -1)

Measured memory_bytes: 91972
import sys
input = sys.stdin.readline
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_dic = {} #value: idx
for i in range(N):
    if A[i] not in A_dic:
        A_dic[A[i]] = []
    A_dic[A[i]].append(i)

# その時の最大のAに１つ使う　これを繰り返す
total = 0
rest = M
if N == 1:
    while rest > 0:
        rest -= 1
        A[0] //= 2
    total = A[0]
elif N == 2:
    while rest > 0:
        rest -= 1
        if A[0] >= A[1]:
            A[0] //= 2
        else:
            A[1] //= 2
    total = A[0] + A[1]
else:
    hq = [-A[i] for i in range(N)]
    heapq.heapify(hq)
    while rest > 0:
    #     temp_idx = A_items[0][1]
    #     while A_items[0][0] >= A_items[1][0]:
    #         rest -= 1
    #         A_items[0][0] //= 2
    #         A[temp_idx] //= 2
    #     idx = 2
    #     while A_items[0][0] < A_items[idx][0]:
    #         idx += 1
    #         if idx >= N-1:
    #             break
    #     u, v = A_items[0], A_items[idx-1]
    #     A_items[idx-1] = u
    #     A_items[0] = v
    # total = sum(A)
        
        max_v = heapq.heappop(hq) * (-1)
        max_idx = A_dic[max_v].pop()
        A[max_idx] //= 2
        if max_v//2 not in A_dic:
            A_dic[max_v//2] = []
        A_dic[max_v//2].append(max_idx)
        heapq.heappush(hq, (max_v//2) * (-1))
        rest -= 1
    total = sum(A)
    


print(total)

Measured memory_bytes: 105752
from sys import stdin
input = stdin.readline

# map(int, input().rstrip().split())

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

a, b = map(int, input().rstrip().split())

print((a-1)*(b-1))


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  cin >> N >> K;
  
  int t = 1;
  for (int i =0; i<N; i++){
    if (t<K){
      t *= 2;
    }
    else{
      t += K;
    }
  }
  cout << t << endl;
 
}

Measured memory_bytes: 256
fn main() {
    let a: i64 = read();
    let b: i64 = read();
    let k: i64 = read();

    use std::cmp;
    println!(
        "{} {}",
        cmp::max(a - k, 0),
        cmp::max(b - cmp::max(k - a, 0), 0)
    );
}

use std::io::stdin;
use std::io::Read;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let token: String = cin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 4352
#include<stdio.h>
#include<ctype.h>

int main(){
	char s1[12],s2[12],s3[12];
	scanf("%s %s %s",s1,s2,s3);
	printf("%c%c%c\n",toupper(s1[0]),toupper(s2[0]),toupper(s3[0]));

}

Measured memory_bytes: 128
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")
// -------------------</optimizations>--------------------

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) int(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define SIZE 26     
#define watch(x) cout << (#x) << " is " << (x) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
 
const ll mod = 1e9 + 7;
const int inf = 1e9 + 5;
const int N = 105;

int weight[N],val[N];

signed main(){
    fastio;
    int i,j,n,w,ans=0,sum=0;
    cin>>n>>w;
    for(i=1;i<=n;++i){
        cin>>weight[i]>>val[i];
        sum+=val[i];
    }
    int dp[n+1][sum+1];
    fill(dp,0);
    for(j=1;j<=sum;++j){
        dp[0][j]=inf;
    }
    for(i=1;i<=n;++i){
        for(j=1;j<=sum;++j){
            dp[i][j]=dp[i-1][j];
            if(j-val[i]>=0){
                dp[i][j]=min(dp[i][j],weight[i]+dp[i-1][j-val[i]]);
            }
        }
    }
    for(i=1;i<=sum;++i){
        if(dp[n][i]<=w){
            ans=max(ans,i);
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 39680