akhauriyash/Code-Regression huggingface dataset:
def f(n):
    if n % 2 == 0:
        return int(n / 2)
    else:
        return int(3*n + 1)

s = int(input())
l = [s]

for i in range(1, 1000000 + 1):
    x = f(s)

    if x in l:
        print(i + 1)
        break

    l.append(x)
    s = x


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

int main() {
  int a, b;
  cin >> a >> b;
  int sum = 0;
  int sa = b - a;
  for(int i = 1; i <= sa; i++) sum += i;
  int ans = sum - b;
  
  cout << ans << endl;
  return 0;
}

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

#define long long long int
using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(9);
    int n;
    cin >> n;
    vector<int> a(n);
    bool b = true;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    while (true) {
        for (int i = 0; i < n; ++i) {
            if (a[i] % 2 == 0) {
                a[i] /= 2;
            } else {
                b = false;
                break;
            }
        }
        if (b) ans++;
        else break;
    }

    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(N)]
res = []
if M > 0:
    for i in range(2**3):
        h = []
        for j in range(3):
            if (i>>j) & 1:
                h.append(1)
            else:
                h.append(-1)
        res.append(sum(sorted([l[0]*h[0] + l[1]*h[1] + l[2]*h[2] for l in xyz])[-M:]))
else:
    res.append(0)

print(max(res))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

    vector<long> H(N);
    for (int n = 0; n < N; n++) {
        cin >> H[n];
    }

    int count = 0;
    int max_count = 0;
    for (int n = 0; n < N - 1; n++) {
        if (H[n] >= H[n + 1]) {
            count++;
        } else {
            if (max_count < count) {
                max_count = count;
            }
            count = 0;
        }
    }
    if (max_count < count) {
        max_count = count;
    }

    cout << max_count << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define INF LLONG_MAX 
#define dd double 
#define fi first
#define se second
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define dll deque<long long>
#define qll queue<long long>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define vvll vector<vector<ll>>
#define vpll vector<pair<long long,long long>>
#define vpcl vector<pair<char,long long>>
#define vpsl vector<pair<string,long long>>
#define stll stack<long long>
#define stc stack<char>
#define mll map<long long,long long>
#define pll pair<long long,long long>
#define psl pair<string,long long>
#define mcl map<char,long long>
#define msl map<string,long long>
#define pcl pair<char,long long>
#define mmll multimap<long long,long long> 
#define mmcl multimap<char,long long>
#define mmsl multimap<string,long long>
#define sll set<long long>
#define sc  set<char>
#define ss  set<string>
#define msll multiset<long long>
#define msc  multiset<char>
#define mss  multiset<string>
#define lb lower_bound
#define up upper_bound
#define lt length
#define clr clear
#define ap append
#define sz size
#define sub substr
#define ull unsigned long long int
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
//#include <boost/multiprecision/cpp_int.hpp> 
//using boost::multiprecision::cpp_int; 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

ll modexp(ll x,ll n,ll p){    //modular exponential function
  if(n==0){return 1;}
  ll u = modexp(x,n/2,p);
  u = u*u%p;
  if(n%2==1){u=(u*x)%p;}
  return u;
}

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

ll m = 1000000007;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll n,k; cin>>n>>k;
    ll arr[n]; rep(i,0,n-1){cin>>arr[i];}
    ll pst[k+1][n], dp[k+1][n];
    // pst -> prefix sum array
    // dp[i][j] -> ways to distribute i candies among j children;
    rep(i,0,k){
        rep(j,0,n-1){
            if(i==0){dp[i][j]=1; pst[i][j]=1; continue;}
            if(j==0){
                if(arr[j]>=i){
                    dp[i][j] = 1;
                    if(i>=1){pst[i][j] = (1 + pst[i-1][j]%m)%m;}
                    else{pst[i][j]=1;}
                }
                else{dp[i][j]=0; pst[i][j]=pst[i-1][j]%m;}
             continue;
            }
            if(arr[j]>=i){
                dp[i][j] = pst[i][j-1]%m;
                pst[i][j] = (pst[i-1][j]%m + dp[i][j]%m)%m;
            }
            else{
                dp[i][j] = ((pst[i][j-1]%m - pst[i-arr[j]-1][j-1]%m) + m)%m;
                pst[i][j] = (pst[i-1][j]%m + dp[i][j]%m)%m;
            }
        }
    }
    cout<<dp[k][n-1];
}


Measured memory_bytes: 159772
def kaibun(s):
    flg = True
    i, j = 0, len(s)-1
    while i <= j:
        if s[i] != s[j]:
            flg = False
        i += 1
        j -= 1
    return flg


sr = input()
n = len(sr)
flg = kaibun(sr)
s2 = sr[:(n-1)//2]
flg *= kaibun(s2)
s3 = sr[(n+3)//2-1:]
flg *= kaibun(s3)
if flg:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
N,x = map(int,input().split(" "))
a = input().split(" ")
a = [int(i) for i in a]
a = sorted(a)
c = 0
for i in range(N):
    x -= a[i]
    if x >= 0:
        c += 1
if x > 0:
    c -= 1
print(c)

Measured memory_bytes: 3060
N = gets.to_i

INFTY = 1<<21
WHITE = 0
GRAY  = 1
BLACK = 2

@m = N.times.map{gets.split.map{|i| i == '-1' ? INFTY : i.to_i }}

def prim
  d = Array.new(N){INFTY}
  p = Array.new(N){-1}
  color = Array.new(N){WHITE}

  d[0] = 0

  loop do
    minv = INFTY
    u = -1
    (0...N).each do |i|
      if minv > d[i] && color[i] != BLACK
        u = i
        minv = d[i]
      end
    end

    break if u == -1
    color[u] = BLACK

    (0...N).each do |v|
      if color[v] != BLACK && @m[u][v] != INFTY
        if d[v] > @m[u][v]
          d[v] = @m[u][v]
          p[v] = u
          color[v] = GRAY
        end
      end
    end
  end

  sum = 0

  (0...N).each do |i|
    sum += @m[i][p[i]] if p[i] != -1
  end

  return sum
end

puts prim


Measured memory_bytes: 6912
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
flag=True
count=0
sm=sum(A)
t=sm/(4*M)
for i in range(M):
    if A[i]<t:
        flag=False
        break
    count+=1
if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main(){
    string S,T;
    cin>>S>>T;
    
    bool ans=false;
    for(int i=0;i<S.size();++i){
        if(S == T){
            ans=true;
            break;
        }
        S=S.back()+S.substr(0,S.size()-1);
    }
    if(ans){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n, 0);
    ll mi = INT_MAX;
    ll sum = 0;
    int minus = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] < 0)
            minus++;
        sum += abs(a[i]);
        mi = min(mi, abs(a[i]));
    }
    cout << sum - (minus % 2 == 0 ? 0 : 2 * mi) << endl;
}

Measured memory_bytes: 1024
from decimal import Decimal
n, k = map(int, input().split())
A = tuple(map(int, input().split()))

pa = Decimal(1)
#for i in range(k):
#    pa *= A[i]

for kk in range(k, n):
    ppa = pa*A[kk]/A[kk-k]
    if ppa > pa:
        print('Yes')
    else:
        print('No')
    pa = ppa


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

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

for(int i=1;i<=9;i++)
{
    int b = n%i;
    int c = n/i;
    if(b==0&&c<10)
    {
    cout<<"Yes"<<endl;
    return 0;
    }
}cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>
#define PI 3.1415926535

using namespace std;

int main(){
  double A, B, H, M;
  cin >> A >> B >> H >> M;
  double deg_m = M * 6.0;
  double deg_h = H * 30.0 + M / 60.0 * 30.0;
  double rad = abs(deg_m - deg_h) / 180.0 * PI;
  cout << fixed << setprecision(10) << pow(pow(A, 2) + pow(B, 2) - 2 * A * B * cos(rad), 0.5) << "\n";
  return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x, y) CPP_CAT_I(x, y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x, y) x##y

#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;
// }}}

constexpr i64 INF = 1'010'000'000'000'000'017LL;

constexpr i64 MOD = 1'000'000'007LL;

constexpr f64 EPS = 1e-12;

constexpr f64 PI = 3.14159265358979323846;

#define M5 100007
#define M9 1000000000

// util {{{
#define FOR(i, start, end) for (i64 i = (start), CPP_CAT(i, xxxx_end) = (end); i < CPP_CAT(i, xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f, c, ...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); })(c))
#define ll long long int
#define VI vector<int>
template <typename C>
i64 SIZE(const C &c)
{
    return static_cast<i64>(c.size());
}

template <typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

template <typename T, typename U, typename Comp = less<>>
bool chmax(T &xmax, const U &x, Comp comp = {})
{
    if (comp(xmax, x))
    {
        xmax = x;
        return true;
    }
    return false;
}

template <typename T, typename U, typename Comp = less<>>
bool chmin(T &xmin, const U &x, Comp comp = {})
{
    if (comp(x, xmin))
    {
        xmin = x;
        return true;
    }
    return false;
}
// }}}

// init {{{
struct ProconInit
{
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit()
    {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

//--------------------------------------------------------------------

bool isOK(int mid, double key)
{
}

int binary_search(double key)
{
    int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int right = 2000000000;
    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;

        if (isOK(mid, key))
            right = mid;
        else
            left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

bool isKaibun(string st)
{
    bool ans = true;
    int n = st.length();
    REP(i, n / 2)
    {
        if (st[i] != st[n - i - 1])
        {
            return false;
        }
    }
    return true;
}

int toInt(char a)
{
    return a - '0';
}

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

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

void solve()
{
    ll N, D;
    cin >> N >> D;
    int ans = 0;
    REP(i, N)
    {
        ll x, y;
        cin >> x >> y;
        if (x * x + y * y <= D * D)
        {
            ans++;
        }
    }
    cout << ans;
}

signed main()
{

    solve();

    return 0;
}


Measured memory_bytes: 3648
"use strict";

class Main {
  public static main(input: string[]): void {
    
        let result = 0;
    const value = input[1].split(/\s/).map(Number);
    const cost = input[2].split(/\s/).map(Number);
    const length = value.length;
    for (let i = 0; i < length; i++) {
      let benefit = value[i] - cost[i];
      if (benefit > 0) {
        result += benefit;
      }
    }

    console.log(result);
  }
}

Main.main(
  require("fs")
    .readFileSync("/dev/stdin", "utf8")
    .split(/\n/)
);


Measured memory_bytes: 7500
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A = np.array(A)

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()


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

struct Dice {
	int top;
	int north;
	int east;
	int south;
	int west;
	int bottom;
};

int main() {
	Dice d;
	int tmp;
	char com;
	cin >> d.top >> d.south >> d.east >> d.west >> d.north >> d.bottom;
	cin.get(com);
	while (1) {
		cin.get(com);
		if (com == '\n')break;
		if (com == 'N') {
			tmp = d.top;
			d.top = d.south;
			d.south = d.bottom;
			d.bottom = d.north;
			d.north = tmp;
		} else if (com == 'E') {
			tmp = d.top;
			d.top = d.west;
			d.west = d.bottom;
			d.bottom = d.east;
			d.east = tmp;
		} else if (com == 'S') {
			tmp = d.top;
			d.top = d.north;
			d.north = d.bottom;
			d.bottom = d.south;
			d.south = tmp;
		} else if (com == 'W') {
			tmp = d.top;
			d.top = d.east;
			d.east = d.bottom;
			d.bottom = d.west;
			d.west = tmp;
		}
	}
	cout << d.top << endl;
	return 0;
}

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

int main() {
  int n, h, w, i, ans = 0;
  cin >> n >> h >> w;
  vector<int> a(n), b(n);
  for (i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  for (i = 0; i < n; ++i) {
    if (a[i] >= h && b[i] >= w) {
      ++ans;
    }
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
s = str(input())
S = [int(t) for t in s]
N=len(S)
S_1 = [i%2 for i in range(N)]
S_2 = [(i+1)%2 for i in range(N)]


n_1 =0
n_2 =0

for i in range(N):
    if S[i]!=S_1[i]:
        n_1 += 1
    else:
        n_2 += 1
    
ans = min(n_1,n_2)
print(ans)


Measured memory_bytes: 5620
# 広義最長部分増加数列の長さを求めるdef
# 配列LIS自体は広義最長部分増加文字列ではない
import bisect
def lis(seq):
    LIS = [seq[0]]
    for i in range(1, len(seq)):
        if seq[i] >= LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_right(LIS, seq[i])] = seq[i]
    return(len(LIS))

n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())

b = a[::-1]
print(lis(b))

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

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

  // 奇数マス空いている場合
  if ((B - A - 1) % 2 == 1) {
    cout << "Alice" << endl;
  } else {
    cout << "Borys" << endl;
  }

  return 0;
}

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

int main()
{
  long long n;
  cin >> n;
  long long i, f;
  f = 0;
  for(i = 2; i <= sqrt(n); i++)
  {
    if(n % i == 0)
    {
      f = n / i;
    }
  }
  if(f == 0)
  {
    f = n;
  }
  int count = 0;
  while(f != 0)
  {
    f /= 10;
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <array>
#include <numeric>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;



int main()
{
    ll N;
    cin >> N;
    vector<ll> d(N);
    rep(i, N) { 
        cin >> d[i];
    }
    sort(all(d));
    ll h = N / 2 - 1;
    print(d[h+1] - d[h]);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9 + 7;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 0; i <= n; i++)
#define rrep(i,n) for(int i=n;i>0;i--)
#define RREP(i,n) for(int i=n;i>=0;i--)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
using fint64 = int_fast64_t;
int dp[3005][3005];

int main() { 
	string s, t;
	cin >> s >> t;
	dp[0][0]=0;
		rep(i,s.size()){
			rep(j,t.size()){
				if(s[i]==t[j]){
					dp[i+1][j+1]=dp[i][j]+1;
				}else{
					dp[i+1][j+1]=max({dp[i][j],dp[i+1][j],dp[i][j+1]});
				}
			}
		}
		//int len=dp[s.size()][t.size()];
		//cerr<<len<<endl;
                int i = s.size(), j = t.size();
                int p = dp[i][j];
                stack<int> a;
                while (p) {
                  if (dp[i - 1][j] == p)
                    i--;
                  else if (dp[i][j - 1] == p)
                    j--;
                  else {
                    a.push(i);
                    i--;
                    j--;
                    p--;
                  }
                }
                //auto itr = a.begin();
                while(!a.empty()) {
                  cout << s[a.top()-1];
				  a.pop();
                  //itr++;
                }
                cout << endl;
                return 0;
}


Measured memory_bytes: 35456
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;

string s;
map<char, int> mp;
set<string> st;

int p [10]={0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,2};
int q [10]={1 ,1 ,1 ,2 ,2 ,3 ,2 ,2 ,3 ,3};
int r [10]={2 ,3 ,4 ,3 ,4 ,4 ,3 ,4 ,4 ,4};
ll D[5];

//解説AC

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  REP(i, n) {
    cin >> s;
    if(s[0]=='M') D[0]++;
    if(s[0]=='A') D[1]++;
    if(s[0]=='R') D[2]++;
    if(s[0]=='C') D[3]++;
    if(s[0]=='H') D[4]++;    
  }
  
  ll ans = 0;
  REP(i, 10) ans += D[p[i]]*D[q[i]]*D[r[i]];
  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;
typedef tuple<ll, ll, ll> T;

ll N, K;

int main(void){
    
    scanf("%lld %lld", &N, &K);
    
    vector<ll> v(K, 0);
    for(ll i = 1; i <= N; ++i) ++v[i % K];
    
    ll ans = 0;
    for(ll a = 0; a < K; ++a){
        ll bc = (K - a) % K;
        if((bc * 2) % K == 0) ans += v[a] * v[bc] * v[bc]; 
    }
    printf("%lld\n", ans);
    
    return 0;
}

Measured memory_bytes: 1792
N, M = gets.chomp.split(' ').map(&:to_i)
broken_steps = M.times.map { [gets.to_i, true] }.to_h

if broken_steps.keys.each_cons(2).map { |a, b| a - b }.any? { |n| n == -1 }
  puts 0
  exit
end

puts 1.upto(N).reduce([1]) { |acc, n|
  next acc.push(0) if broken_steps[n]
  a = [n-1, n-2].reject { |n_| n_ < 0 }
  res = a.empty? ? 0 : a.map { |i| acc[i] }.reduce(:+)
  acc.push(res)
}.last % 1_000_000_007

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

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

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

		int tmp_i = i;
		int sum = 0;
		while (true) {			
			sum += tmp_i % 10;
			tmp_i /= 10;
			if (tmp_i == 0) break;
		}
		if (a <= sum && sum <= b) ans += i;

	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)

int main(){
  ll A,B;
  cin>>A>>B;
  A--;
  B--;
  ll a[3]={0};
  a[A]=1;
  a[B]=1;
  for(ll i=0;i<3;i++){
    if(a[i]==0)
    cout<<i+1<<endl;
  }

}








Measured memory_bytes: 256
import atexit
import io
import sys

buff = io.BytesIO()
sys.stdout = buff


@atexit.register
def write():
    sys.__stdout__.write(buff.getvalue())


s = raw_input()
if 8-s.count('o') <= 15-len(s):
	print 'YES'
else:
	print 'NO'

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

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> bool chmax(T& a,const T& b){return a < b ? (a = b,true) : false;}
template<typename T> bool chmin(T& a,const T& b){return b < a ? (a = b,true) : false;}
typedef long long ll;

class UnionFind{
	private:
		vector<int> parent;
		vector<int> rank;
	public:
		UnionFind(int n)
			:parent(n),rank(n,1){
			for(int i = 0;i < n;i++) parent [i] = i;
		}
		int find(int x){
			if(parent [x] == x) return x;
			return parent [x] = find(parent [x]);
		}
		bool connect(int x,int y){
			x = find(x),y = find(y);
			if(x == y) return false;
			if(rank [x] < rank [y]) swap(x,y);
			if(rank [x] == rank [y]) rank [x]++;
			parent [y] = x;
			return true;
		}
		bool same(int x,int y){
			return find(x) == find(y);
		}
};

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

bool in_range(int y,int x)
{
	return y >= 0 && y < N && x >= 0 && x < N;
}

int main()
{
	scanf("%d",&N);

	vector< pair<int,int> > ans;
	UnionFind uf(N * N);
	for(int i = 4;i >= 2;i--){
		FOR(y,0,N){
			for(int x = y % 2 == 0;x < N;x += 2){
				int cnt = 0;
				FOR(j,0,4){
					int y1 = y + dy [j],x1 = x + dx [j];
					if(in_range(y1,x1) == false) continue;
					bool flag = true;
					FOR(k,0,j){
						int y2 = y + dy [k],x2 = x + dx [k];
						flag &= in_range(y2,x2) == false || uf.same(y1 * N + x1,y2 * N + x2) == false;
					}
					cnt += flag;
				}
				if(cnt == i){
					ans.push_back({x,y});
					FOR(j,0,4){
						FOR(k,0,j){
							int y1 = y + dy [j],x1 = x + dx [j],y2 = y + dy [k],x2 = x + dx [k];
							if(in_range(y1,x1) && in_range(y2,x2)){
								uf.connect(y1 * N + x1,y2 * N + x2);
							}
						}
					}
				}
			}
		}
	}

	int K = ans.size();
	printf("%d\n",K);
	FOR(i,0,K){
		printf("%d %d\n",ans [i].first,ans [i].second);
	}

	return 0;
}


Measured memory_bytes: 10736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;

void solve(string s) {
    int h = 0;
    int t = s.size() - 1;
    int ret = 0;
    bool flag = true;
    while (h <= t) {
        if (s[h] == s[t]) {
            h++;
            t--;
            continue;
        } else {
            if (s[h] == 'x') {
                ret++;
                h++;
                continue;
            } else if(s[t] == 'x'){
                ret++;
                t--;
                continue;
            } else {
                flag = false;
                break;
            }
        }
    }
    if (flag) {
        std::cout << ret << std::endl;
    } else {
        std::cout << -1 << std::endl;
    }

}

int main() {
    struct timeval start,end;
    long long span;
    string s;

    gettimeofday(&start,NULL);

    std::cin >> s;
    solve(s);

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 512
#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin >> s>>t;
    cout << t <<s<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
    #include <math.h>
    #include <vector>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    using namespace std;

int main() {
    int n,z=0,o=0;
    string s;cin>>s;
    for(int i=0; i<s.length();i++){
        if(s[i]=='0') z++;
        else o++;
    }
    cout << 2*min(z,o)<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
typedef long long ll;

using namespace std;

int main()
{
	ll x,y;
	ll n;
	ll ans=0;
	
	cin>>x>>y;
	n=x;
	while(n<=y)
	{
		ans++;
		n*=2;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#define SortAsc(c) std::sort(c.begin(), c.end())
#define SortDesc(c) std::sort(c.rbegin(), c.rend())

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> g(H);
  for (int i = 0; i < H; i++) {
    cin >> g.at(i);
  }

  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      // 空きマスの場合、周囲の爆弾の数を数える
      if (g.at(y).at(x) == '#') continue;

      int count = 0;
      for (int cy = -1; cy <= 1; cy++) {
        for (int cx = -1; cx <= 1; cx++) {
          int ty = y + cy;
          if (ty < 0 || H - 1 < ty) continue;

          int tx = x + cx;
          if (tx < 0 || W - 1 < tx) continue;

          if (g.at(ty).at(tx) == '#') {
            count++;
          }
        }
      }
      g.at(y).at(x) = char(count) + '0';
    }
  }

  for (auto s : g) cout << s << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;

//MOD,および逆元テーブルの作成
const int MAX = 510000;
const int MOD = 1000000007;

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


int main(){
COMinit();
long long N;
cin>>N;
long long x;
long long X[N]={};
for(int i=0;i<N;++i){
  cin>>x;
  X[i]=x;
}
long long ans=0;
long long dist=0;
long long MOD=1000000007;
long long total=1;
long long Y_total[N]={};
Y_total[0]=1;

for(int i=1;i<N;++i){
  total*=i;
  total%=MOD;
  if(total<0){
    total+=MOD;
  }
}

for(int i=1;i<N;++i){
  long long tmp=total*inv[i]%MOD;
  if(tmp<0){
    tmp+=MOD;
  }
  Y_total[i]=tmp;
}

long long summary[N]={};
for(int i=1;i<N;++i){
  summary[i]=(summary[i-1]+Y_total[i])%MOD;
}


for(int i=1;i<N;++i){
  dist=X[i]-X[i-1];
  ans+=(dist*summary[i]);
  ans%=MOD;
  if(ans<0){
    ans+=MOD;
  }
}

  cout<<ans<<"\n";
return 0;
}

Measured memory_bytes: 14592
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define read(a) scanf("%d", &a)
#define readl(a) scanf("%lld", &a)
#define reads(a) scanf("%s", a)
#define readf(a) scanf("%lf", &a)
#define readc(a) scanf("%c", &a)
#define debug(a, b) printf("%s = %d\n", a, b)
#define debug1(a, i, b) printf("%s[%d] = %d", a, i, b)
#define show(a) putchar(a)
#define pb emplace_back
#define mk make_pair
#define _rand mt19937 RAND(time(0))
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define mem(a) memset(a, 0, sizeof(a))
#define Buff ios::sync_with_stdio(false)
typedef long long ll;
typedef long long LL;
typedef int Int;
typedef double db;
using namespace std;
const int INF = 1e9 + 7;
const int N = 2e5 + 7;
const int M = 5e6 + 7;
char s[N];
ll dp[N];
signed main()
{
    int n, p;
    read(n); read(p);
    reads(s + 1);

    ll ans = 0;
    if(p == 2 || p == 5)
    {
        for(int i = 1; i <= n; i++)
            if((s[i]-'0') % p == 0)
                ans += 1ll*i;
    }
    else
    {
        ll d = 1, x = 0;
        for(int i = n; i; i--)
        {
            x += (s[i]-'0') * d;
            x %= p;

            d *= 10;
            d %= p;

            ans += dp[x];
            dp[x]++;
            if(x == 0) ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
/**

**/



Measured memory_bytes: 512
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
cnt = 0
for i in range(n):
    dm = min(a[i], b[i])
    b[i] -= dm; cnt += dm
    dmn = min(a[i + 1], b[i])
    a[i + 1] -= dmn; cnt += dmn
print(cnt)

Measured memory_bytes: 25316
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))
#define min3(x, y, z) min(x, min(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif

using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> list(N);
  rep(i, N) { cin >> list[i]; }
  int ans = 0;
  rep(i, N - 2) {
    if (list[i + 1] != max3(list[i], list[i + 1], list[i + 2]) and
        list[i + 1] != min3(list[i], list[i + 1], list[i + 2])) {
      ans++;
    }
  }
  cout << ans;
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
rep(i,N) {
  cin >> list[i];
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
//配列の内容表示
dout << "====listの内容====\n";
for (int edp = 0; edp < N; edp++) dout << list[edp] << endl;
dout << "====ここまで====\n";
*/


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

class F
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var s = Console.ReadLine().Split().Select(int.Parse).OrderByDescending(x => x).ToArray();

		var q = new int[n + 1].Select(_ => new List<int>()).ToList();
		q[n].Add(int.MaxValue);
		foreach (var hp in s)
		{
			var match = false;
			for (var i = q.Count - 1; i >= 0; i--)
				if (hp < q[i][0])
				{
					for (var j = i - 1; j >= 0; j--) q[j].Add(hp);
					q[i].RemoveAt(0);
					if (!q[i].Any()) q.RemoveAt(i);
					match = true;
					break;
				}
			if (!match) { Console.WriteLine("No"); return; }
		}
		Console.WriteLine("Yes");
	}
}


Measured memory_bytes: 45308
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll A[14][14],C[14];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll n,m,x;
    memset(A,0,sizeof(A));
    memset(C,0,sizeof(C));
    cin>>n>>m>>x;
    for(int i=0; i<n; i++)
    {
        cin>>C[i];
        for(int j=0; j<m; j++)
        {
            cin>>A[i][j];
        }
    }
    ll Ans=10000007;
    for(int i=0; i<=4095; i++)
    {
        string s = bitset<12>(i).to_string();
        reverse(s.begin(),s.end());
        ll Cost=0,ul[14];
        memset(ul,0,sizeof(ul));
        for(int j=0; j<n; j++)
        {
            if(s[j]=='0')
                continue;
            Cost+=C[j];
            for(int k=0; k<m; k++)
            {
                ul[k]+=A[j][k];
            }
        }
        bool flag=true;
        for(int j=0; j<m; j++)
        {
            if(ul[j]<x)
                flag=false;
        }
        if(flag==true)
            Ans=min(Ans,Cost);
    }
    if(Ans==10000007)
        cout<<-1<<endl;
    else
        cout<<Ans<<endl;


    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;

using namespace std;

ll A[200005];

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

	vector<ll> m, p;
	ll sum = 0;
	ll znum = 0;
	REP(i, N)
	{
		cin >> A[i];
		A[i] -= i + 1;
		sum += abs(A[i]);
		if (A[i] < 0)
		{
			m.push_back(A[i]);
		}
		else if (A[i] > 0)
		{
			p.push_back(A[i]);
		}
		else
		{
			znum++;
		}
	}

	sort(m.begin(), m.end(), [](ll a, ll b) {return abs(a) < abs(b); });
	sort(p.begin(), p.end(), [](ll a, ll b) {return abs(a) < abs(b); });

	ll min = 0;
	ll msum = 0;
	REP(i, m.size())
	{
		ll t = abs(m[i]);
		min = std::min(min, (ll)(p.size() + znum)*t - t*(ll)(m.size() - i) + (t*i - 2 * msum));
		msum += t;
	}
	ll psum = 0;
	REP(i, p.size())
	{
		ll t = abs(p[i]);
		min = std::min(min, (ll)(m.size() + znum)*t - t*(ll)(p.size() - i) + (t*i - 2 * psum));
		psum += t;
	}

	cout << sum - abs(min) << endl;

	return 0;
}

Measured memory_bytes: 3572
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
//using P=pair<ll,P<ll,ll>>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }

const ll INF=1e18;

int main(){
    ll x,y,a,b,c;
    cin>>x>>y>>a>>b>>c;
    V<ll> p(a),q(b),r(c);
    //set<P> stp,stq;
    V<priority_queue<ll,V<ll>,greater<ll>>> que(2);
    V<ll> z;
    rep(i,a){
        cin>>p[i];
        //que[0].push
        //stp.insert(P(p[i],P(i,1)));
    }
    //cinf(b,q);
    rep(i,b){
        cin>>q[i];
        //stp.insert(P(q[i],P(i,2)));
    }
    rep(i,c){
        cin>>r[i];
        /*stp.insert(P(r[i],P(i,3)));
        stq.insert(P(r[i],P(i,3));*/
    }
    sort(all(p),greater<ll>());
    sort(all(q),greater<ll>());
    sort(all(r),greater<ll>());
    ll ans=0;
    rep(i,x){
        ans+=p[i];
        que[0].push(p[i]);
    }
    rep(i,y){
        ans+=q[i];
        que[1].push(q[i]);
    }
    ll s=x,t=y;
    ll k=0;
    while(k<c){
        if(que[0].empty()){
            if(r[k]<=que[1].top()) break;
            ans-=que[1].top();
            ans+=r[k];
            que[1].pop();
        }else if(que[1].empty()){
            if(r[k]<=que[0].top()) break;
            ans-=que[0].top();
            ans+=r[k];
            que[0].pop();
        }else{
            ll z=0;
            ll cnt;
            if(que[0].top()<que[1].top()){
                cnt=que[0].top();
            }else{
                cnt=que[1].top();
                z^=1;
            }
            if(r[k]<=cnt) break;
            ans-=que[z].top();
            que[z].pop();
            ans+=r[k];
        }
        k++;
    }
    cout<<ans<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
(全探索できるなら全探索しろ)
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'\n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
*/

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

using namespace std;
#define flp(i, s, n) for(int i=0; i<n; i++)

int main(void)
{
	int A[3][3];
	for(int i=0; i<3; i++)
	{
		for(int j=0; j<3; j++)
			cin>>A[i][j];
	}
	int n;
	cin>>n;
	for(int i=0; i<n; i++)
	{
		int b;
		cin>>b;
		for(int x=0; x<3; x++)
		{
			for(int y=0; y<3; y++) if(A[x][y]==b) A[x][y]=0;
		}
	}

	flp(r,0,3) if(!A[r][0] && !A[r][1] && !A[r][2]){cout<<"Yes\n";return 0;}
	flp(c,0,3) if(!A[0][c] && !A[1][c] && !A[2][c]){cout<<"Yes\n";return 0;}
	if(!A[0][0] && !A[1][1] && !A[2][2]){cout<<"Yes\n";return 0;}
	if(!A[2][0] && !A[1][1] && !A[0][2]){cout<<"Yes\n";return 0;}
	cout<<"No\n";

	

	return 0;
}

Measured memory_bytes: 256
A,B,C = list(map(int,input().split()))
K = int(input())

ans = 0

while True:
    if B <= A:
        B *= 2
        ans += 1
    else:
        break
while True:
    if C <= B:
        C *= 2
        ans += 1
    else:
        break
if ans <= K:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9184
#include<stdio.h>
#include<string.h>
int min(int a,int b){return(a<b)?a:b;}
int main(void)
{
  int a=0,b=1,c,i=0;char s[1000005];
  if(scanf("%s",s)==1)
  {
    while(i<strlen(s)){c=a;a=min(a+s[i]-48,b+58-s[i]);b=min(c+s[i]-47,b+57-s[i]);i++;}
    return printf("%d",a),0;
  }
  else return 0;
}

Measured memory_bytes: 1152
N = int(input())
s = input()


# for i in range(N-2):
#     for j in range(i+1, N-1):
#         if s[i] == s[j]:
#             continue
#         for k in range(j+1, N):
#             if j-i == k-j:
#                 continue
#             if s[i] == s[k] or s[j] == s[k]:
#                 continue
#             cnt += 1

r = 0
g = 0
b = 0

for t in s:
    if t == "R":
        r += 1
    elif t == "G":
        g += 1

b = N - r - g
cnt = r * g * b

for i in range(1, N-1):
    j = 1
    while 0 <= i-j and i+j <= N-1:
        if s[i] != s[i-j] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            cnt -= 1
        j += 1

print(cnt)


Measured memory_bytes: 9168
import java.util.Scanner;

public class Main {
  private static Scanner sc;

  public static void main(String[] args) {
    sc = new Scanner(System.in);
    new Main().solve();
  }


  private void solve() {
    int N = sc.nextInt();
    int i = sc.nextInt();
    System.out.println(N + 1 - i);

  }
}



Measured memory_bytes: 21716
H,W,M=map(int,input().split())
h_lis=[0]*H
w_lis=[0]*W
hw_set=set()

for _ in range(M):
    h,w=map(int,input().split())
    h_lis[h-1]+=1
    w_lis[w-1]+=1
    hw_set.add((h-1,w-1))
    
h_max=max(h_lis)
w_max=max(w_lis)

h_maxlis=[i for i, x in enumerate(h_lis) if x==h_max]
w_maxlis=[i for i, x in enumerate(w_lis) if x==w_max]
import sys

for hi in h_maxlis:
    for wi in w_maxlis:
        if (hi,wi) not in hw_set:
            print(h_max+w_max)
            sys.exit()
else:
    print(h_max+w_max-1)

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

int main(){
    int a,b;
    cin>>a>>b;
    
    if ( a < b )
    cout<< "a < b" <<endl;
    
    if ( a > b )
    cout<< "a > b" <<endl;
    
    if ( a == b )
    cout<< "a == b" <<endl;
    
    return 0;
}


Measured memory_bytes: 3104
import scala.io.Source
import scala.collection.mutable.Map

object Main {
  def main(args: Array[String]) = {
    val lines = Source.stdin.getLines.toStream
    val inSeq = lines.drop(1).head.split(' ').map(_.toLong)

    println(dp(inSeq))
  }

  def dp(input: IndexedSeq[Long]): Long = {
    val memo = Array.ofDim[(Long, Long)](input.length + 1, input.length + 1)

    (1 to input.length).foreach { n =>
      memo(n-1)(n) = input(n-1) -> 0
    }

    (2 to input.length).foreach { area =>
      var res = Long.MaxValue
      (2 to area).foreach { tgLen =>
        // cand
        var locMin = Long.MaxValue
        var cost = 0L
        ((area - tgLen + 1) to (area - 1)).reverse.foreach { split =>
          // println(area, tgLen, split)
          var cand = memo(area - tgLen)(split)._2 + memo(split)(area)._2
          if (cand <= locMin) {
            locMin = cand
            cost = memo(area - tgLen)(split)._1 + memo(split)(area)._1
          }
          // locMin = math.min(
          //   locMin, memo((area - tgLen, split))._2 + memo((split, area))._2
          // )
        }

        // println(area - tgLen, area, locMin)
        memo(area - tgLen)(area) = cost -> (locMin + cost)
      }
    }
    memo(0)(input.length)._2
  }
}


Measured memory_bytes: 47924
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
using namespace         std;
#define                 int long long
#define                 double long double
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<'\n'
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 1014159
#define  vi vector<int>
#define  v  vector
#define die exit(0)
#define alln(arr) arr+1 , arr+1+n
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update> oset; 

int n,m,k,arr[N];
v<pi>dc;

bool check(string s)
{
    for(auto i : dc)
    {
        int x = i.X;
        int y = i.Y;
        if(x>=s.size())return 0;
        if(s[x]-'0'!=y)return 0;
    }
    return 1;
}

void solve()
{
    cin>>n>>m;

    int x = 1;

    forn(i,1,n-1)
    {
        x*=10;
    }
    int y;
    y=x*10-1;

    if(n == 1)
    {
        x--;
        y = 9;
    }

    forn(i,1,m)
    {
        int a,b;
        cin>>a>>b;
        a--;
        dc.pb({a,b});
    }

    forn(i,x,y)
    {
        if(check(to_string(i)))
        {
            cout<<i;
            return;
        }
    }
    cout<<-1;



}


signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    int t = 1;
    //cin>>t;
    forn(i,1,t)
    {
        solve();
        nl;
    }



    return 0;

}

//       clang++ c.cpp ; ./a.out < a.txt ;  

Measured memory_bytes: 256
import sys
cnt = 0

def merge_sort(a, left, right):
	if left + 1 < right:
		mid = int(left + (right - left) / 2)
		merge_sort(a, left, mid)
		merge_sort(a, mid, right)
		merge(a, left, mid, right)

def merge(a, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L = a[left:left + n1]
	R = a[mid:mid + n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)
	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			a[k] = L[i]
			i += 1
		else:
			if L[i] != sys.maxsize:
				global cnt
				cnt += n1 - i
			a[k] = R[j]
			j += 1

n = int(input())
a = list(map(int, input().split()))
merge_sort(a, 0, len(a))
print(cnt)


Measured memory_bytes: 27480
S = input()
T = input()
L = len(S)
dicS = {}
dicT = {}
ans = "Yes"
for i in range(L):
    if S[i] not in dicS:
        dicS[S[i]] = T[i]
    else:
        if T[i] != dicS[S[i]]:
            ans ="No"
    if T[i] not in dicT:
        dicT[T[i]] = S[i]
    else:
        if S[i] != dicT[T[i]]:
            ans = "No"
print(ans)


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

ll n, Q, k;
struct treedata {
    int pos; ll dist;
};
vector< vector<treedata> > graphlist(100100, vector<treedata>());
vector<ll> distgraph(100100, -1);

int main() {
    cin >> n;
    for(int i = 0; i < n-1; ++i) {
        int aa, bb;
        ll cc;
        cin >> aa >> bb >> cc;
        aa--; bb--;
        treedata indata;
        indata.pos = bb; indata.dist = cc;
        graphlist.at(aa).emplace_back(indata);
        indata.pos = aa;
        graphlist.at(bb).emplace_back(indata);
    }
    // cout << "ok" << endl;

    cin >> Q >> k;
    k--;
    queue<treedata> que;
    treedata first;
    first.pos = k; first.dist = 0;
    que.push(first);
    distgraph.at(k) = 0;

    while(!que.empty()) {
        treedata now = que.front();
        que.pop();
        for(int i = 0; i < (int)graphlist.at(now.pos).size(); ++i) {
            int npos = graphlist.at(now.pos).at(i).pos;
            ll ndist = graphlist.at(now.pos).at(i).dist + now.dist;
            if(distgraph.at(npos) == -1) {
                distgraph.at(npos) = ndist;
                treedata next;
                next.pos = npos; next.dist = ndist;
                que.push(next);
            }
        }
    }

    for(int i = 0; i < Q; ++i) {
        int xx, yy;
        cin >> xx >> yy;
        xx--; yy--;
        ll ans = 0;
        ans += distgraph.at(xx);
        ans += distgraph.at(yy);
        cout << ans << endl;
    }
}

Measured memory_bytes: 10736
#include<stdio.h>
int main()
{
    int n,i,temp=0;
    scanf("%d\n",&n);
    int array[n];
    for(i=0;i<n;i++)
    {
        scanf("%d",&array[i]);
    }
    for(i=0;i<n-1;i++)
    {
        if (array[i]!=i+1) {
            temp++;
        }
    }
    if(temp<=2)
    {
        printf("YES");
    }
    else
        
        printf("NO");
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main()
{
	char a[100]={0};
	scanf("%s",a);
	if(a[0]=='Y'&&a[1]=='A'&&a[2]=='K'&&a[3]=='I')
		printf("Yes");
	else
		printf("No");
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9 + 7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4] ={ 1,0,-1,0 };
int dy[4] ={ 0,1,0,-1 };

int H, W, D, Q;
int A[300][300], L[100000], R[100000], x[90000], y[90000];
int cost[90000], sum[90000]; //cost of (i->i+D)

signed main() {
	cin >> H >> W >> D;
	rep(i, H){
		rep(j, W){
			cin >> A[i][j];
			A[i][j]--;
			x[A[i][j]] = i;
			y[A[i][j]] = j;
		}	
	}	
	cin >> Q;
	rep(i, Q){
		cin >> L[i] >> R[i];
		L[i]--; R[i]--;
	}

	rep(i, H*W){
		cost[i] = (i+D < H*W ? abs(x[i+D]-x[i]) + abs(y[i+D]-y[i]) : 0);
		//cout << x[i+D] << " " << x[i] << " " << y[i+D] << " " << y[i] << " " << cost[i] << endl;
		sum[i] = (i-D >= 0 ? sum[i-D] : 0) + cost[i];
		//cout << cost[i] << " " << sum[i] << endl;
	}
	rep(i, Q) cout << (R[i]-D >= 0 ? sum[R[i]-D] : 0) - (L[i]-D >= 0 ? sum[L[i]-D] : 0)  << endl;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
long long a,b;

int main(){
    cin>>a>>b;
    if(a>0)cout<<"Positive";               
    else if(b>=0)cout<<"Zero";            
    else if((a&1)^(b&1))cout<<"Positive";  
    else cout<<"Negative";
    return 0;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();

    int ans = 0;
    for(int i=0; i<n; ++i) {
      if( sc.nextInt() >= k ) ++ans;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 48384