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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

llong N, X;
vector<llong> S;
vector<vector<llong> > memo;

llong dp(llong now, llong num){
	if(now == N)
		return num;
	if(memo[now][num] != -1)
		return memo[now][num];

	llong ret = 0;
	ret = (ret + dp(now+1, num%S[now])) % mod;
	ret = (ret + dp(now+1, num)*(N-now-1)) % mod;

	return memo[now][num] = ret;
}

int main(){

	cin >> N >> X;
	S.resize(N);
	for(auto &x : S)
		cin >> x;
	sort(ALL(S), greater<>());

	memo.resize(N, vector<llong>(X+1,-1));
	cout << dp(0,X) << endl;

	return 0;
}

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

#define ll long long int
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)

int main(){
	ios::sync_with_stdio(0);
	int a, b;
	cin >> a >> b;
	cout << a * b << endl;
}



Measured memory_bytes: 3640
A, B, C, D = list(map(int, input().split(' ')))

turn = 0
while A > 0 and C > 0:
  if turn % 2 == 0:
    C -= B
  else:
    A -= D
  turn += 1

if A <= 0:
  print('No')
else:
  print('Yes')

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


def solve(S: int):
    from itertools import takewhile, count
    SS = tuple(map(int, str(S)))
    ans = 0
    t = [0] * 2020
    t[0] = 1
    u, cnt = 0, 0
    for i, n in enumerate(reversed(SS)):
        u = (n * pow(10, i, 2019) + u) % 2019
        cnt += t[u]
        t[u] += 1
    return cnt



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    print(solve(S))

if __name__ == '__main__':
    main()


Measured memory_bytes: 11484
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
using namespace std;
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

const ll mod = 998244353;

ll mod_pow(ll n, ll k) {
    ll ret = 1;
    ll cur = n;
    while(k) {
        if(k & 1) (ret *= cur) %= mod;
        cur = cur * cur % mod;
        k /= 2;
    }
    return ret;
}

ll mod_inv(ll n) { return mod_pow(n, mod - 2); }

const size_t SIZE = 1e6 + 10;
ll cnt_arr[SIZE];
ll sum_arr[SIZE];

int main() {
    ll N;
    cin >> N;
    while(N--) {
        ll a;
        cin >> a;
        cnt_arr[a]++;
    }

    ll ans = 0;
    ll inv2 = mod_inv(2);
    for(ll g = 1e6; 1 <= g; g--) {
        ll sum = 0;
        ll past_sum = 0;
        ll pow2_sum = 0;
        for(ll m = 1; g * m < SIZE; m++) {
            ll tmp = g * m;
            (sum += cnt_arr[tmp] * tmp % mod) %= mod;
            (past_sum += sum_arr[tmp]) %= mod;
            (pow2_sum += cnt_arr[tmp] * (tmp * tmp % mod) % mod) %= mod;
        }
        sum = sum * sum % mod;
        sum = sum + (mod - pow2_sum) % mod;
        sum = sum * inv2 % mod;
        sum = sum + (mod - past_sum) % mod;
        ans += sum * mod_inv(g) % mod;
        sum_arr[g] = sum;
    }

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


Measured memory_bytes: 15872
#include<iostream>
#include<string>
#include<queue>
int n;
std::string s;
int count=0;
void solve(){
    for(int i=0; i<n-2; i++){
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
            count++;
        }
    }
    std::cout << count << "\n";
}
int main(){
    std::cin >> n;
    std::cin >> s;
    solve();
    return 0;
}

Measured memory_bytes: 256
from operator import mul
from functools import reduce


def inpl():
    return list(map(int, input().split()))


def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def root(x):
    if parent[x] == x:
        return (x)
    else:
        parent[x] = root(parent[x])
        return (parent[x])


def same(x, y):
    return (root(x) == root(y))


def union(x, y):
    x = root(x)
    y = root(y)
    if (x == y):
        return False

    parent[x] = min(x, y)
    parent[y] = min(x, y)
    return True


N, M = inpl()
AB = [inpl() for _ in range(M)]
parent = [i for i in range(N)]
waku = [1] * N
anslist = [0] * M
ans = 0

for i, auau in enumerate(AB[::-1]):
    a = auau[0] - 1
    b = auau[1] - 1
    ra = root(a)
    rb = root(b)
    union(a, b)
    if ra != rb:
        ans -= cmb(waku[ra], 2) + cmb(waku[rb], 2)
        waku[root(a)] = waku[ra] + waku[rb]
        ans += cmb(waku[root(a)], 2)
    else:
        pass

    anslist[M - 1 - i] = ans

all_comb = cmb(N, 2)
for i in range(1, M):
    print(all_comb - anslist[i])
print(all_comb)


Measured memory_bytes: 36832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const int MAX = 1000000010;
const ll MOD = 1000000007;

int main() {
    int N; cin >> N;
    int x = N % 10;
    if (x == 2 || x == 4 || x == 5 || x == 7 || x == 9) {
        cout << "hon" << endl;
    } else if (x == 0 || x == 1 || x == 6 || x == 8) {
        cout << "pon" << endl;
    } else {
        cout << "bon" << endl;
    }

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>

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

	double debt = 100000.0;
	for( int i=0; i<N; ++i ) {
		debt *= 1.05;
		debt = ( static_cast<int>( debt ) / 1000
			+ ((static_cast<int>( debt )%1000)>0?1:0)) * 1000;
	}

	std::cout << static_cast<int>( debt ) << std::endl;
}

Measured memory_bytes: 0
N, Y = map(int, input().split())
flag = False
for i in range(N+1):
    for j in range(N-i+1):
        if (Y - 10000*i - 5000*j) // 1000 == N-i-j:
            flag = True
            print(i, j, N-i-j)
            break
    if flag:
        break
if flag == False:
    print('-1 -1 -1')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

const char mod[] = "YGBR";
int N , M , K;
char qbxf[2007][2007] , ans[1007][1007];

int main(){
	cin >> N >> M >> K;
	for(int i = -1000 ; i <= 1000 ; ++i)
		for(int j = -1000 ; j <= 1000 ; ++j)
			qbxf[i + 1000][j + 1000] = mod[((i + 1000) / K & 1) * 2 + ((j + 1000) / K & 1)];
	for(int i = -1000 ; i <= 1000 ; ++i)
		for(int j = -1000 ; j <= 1000 ; ++j)
			if((i + j) >= 0 && (i - j) >= 0 && !((i + j) & 1))
				ans[(i + j) / 2][(i - j) / 2] = qbxf[i + 1000][j + 1000];
	for(int i = 1 ; i <= N ; ++i){
		for(int j = 1 ; j <= M ; ++j)
			putchar(ans[i][j]);
		putchar('\n');
	}
	return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll a,c,d,b,ans;
int32_t main(){
CODE_START;
cin>>a;
cin>>b;
cin>>c;
cin>>d;
ll x=a%c;
ll y=a+(c-a%c)%c;
ll z=b%c;
ll q=b-b%c;
ans=b-a+1;
if(y==q&&y>=a){
    ans=ans-1;
}else if(q>=a&&y>=a){
ans=ans-(q-y)/c-1;
}
x=a%d;
y=a+(d-a%d)%d;
z=b%d;
q=b-b%d;
if(y==q&&y>=a){
    ans=ans-1;
}else if(q>=a&&y>=a){
ans=ans-(q-y)/d-1;
}
ll lcm=(c*d)/__gcd(c,d);
x=a%lcm;
y=a+(lcm-a%lcm)%lcm;
z=b%lcm;
q=b-b%lcm;
if(y==q&&y>=a){
    ans=ans+1;
}else if(q>=a&&y>=a)
ans=ans+(q-y)/lcm+1;
cout<<ans;
}



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

namespace AizuOnlineJudge
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]X Cubic
            string line = Console.ReadLine().TrimEnd();
            int x = int.Parse(line);

            Console.WriteLine(Math.Pow(x, 3));
        }
    }
}



Measured memory_bytes: 7888
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <fstream>
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (1 << 30);
const ll inf = (1LL << 60LL);
const int maxn = 3e5 + 5;
int n;
int arr[maxn];
int cnt[maxn];
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> arr[i];
    }
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; i < n; i += 2){
        cnt[arr[i]] ++;
    }
    int mxx = 0, num = -1;
    for(int i = 0; i < maxn; i ++){
        if(mxx < cnt[i]){
            mxx = cnt[i];
            num = i;
        }
    }
    int ret = abs((n / 2) - mxx);
    int mxx2 = 0, num2 = -1;
    memset(cnt, 0, sizeof cnt);
    vector<pair<int, int> > v;
    for(int i = 1; i < n; i += 2){
        cnt[arr[i]] ++;
    }
    for(int i = 0; i < maxn; i ++){
        if(mxx2 < cnt[i]){
            mxx2 = cnt[i];
            num2 = i;
        }
        v.push_back(make_pair(cnt[i], i));
    }
    if(num == num2){
        sort(v.begin(), v.end());
        ret += abs((n / 2) - v[(int)v.size() - 2].first);
    }
    else{
        ret += abs((n / 2) - mxx2);
    }
    
    
    memset(cnt, 0, sizeof cnt);
    for(int i = 1; i < n; i += 2){
        cnt[arr[i]] ++;
    }
    int mxx3 = 0, num3 = -1;
    for(int i = 0; i < maxn; i ++){
        if(mxx3 < cnt[i]){
            mxx3 = cnt[i];
            num3 = i;
        }
    }
    int ret2 = abs((n / 2) - mxx3);
    int mxx4 = 0, num4 = -1;
    memset(cnt, 0, sizeof cnt);
    vector<pair<int, int> > v2;
    for(int i = 0; i < n; i += 2){
        cnt[arr[i]] ++;
    }
    for(int i = 0; i < maxn; i ++){
        if(mxx4 < cnt[i]){
            mxx4 = cnt[i];
            num4 = i;
        }
        v2.push_back(make_pair(cnt[i], i));
    }
    if(num3 == num4){
        sort(v2.begin(), v2.end());
        ret2 += abs((n / 2) - v2[(int)v2.size() - 2].first);
    }
    else{
        ret2 += abs((n / 2) - mxx4);
    }
    cout << min(ret, ret2) << endl;
    return 0;
}



Measured memory_bytes: 14060
program ABC_073_A_September9
   implicit none
   character(2) N
   read(*, *) N
   if(N(1:1) == '9') then
	   write(*, *) 'Yes'
   else if(N(2:2) == '9') then
	   write(*, *) 'Yes'	   
   else 
       write(*, *) 'No'
   end if
end program ABC_073_A_September9

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

using namespace std;

typedef double Real;

Real EPS = 1e-8;

int sgn(Real a, Real b=0){return a<b-EPS?-1:a>b+EPS?1:0;}
Real sqr(Real a){return sqrt(max(a,(Real)0));}

struct Point{
  Real add(Real a, Real b){
    if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0;
    return a+b;
  }
  Real x, y;
  Point(){}
  Point(Real x,Real y) : x(x) , y(y){}

  Point operator + (Point p){return Point(add(x,p.x), add(y,p.y));}
  Point operator - (Point p){return Point(add(x,-p.x), add(y,-p.y));}
  Point operator * (Real d){return Point(x*d,y*d);}
  Point operator / (Real d){return Point(x/d,y/d);}
  Real norm(){return sqr(x*x+y*y);}
  Real dist(Point a){return (*this-a).norm();}
  Real dot(Point a){return x*a.x+y*a.y;}
  Real cross(Point a){return x*a.y-y*a.x;}
};

struct circle{
  Point p;
  Real r;
  circle(){}
  circle(Point p, Real r) : p(p) , r(r){}
};

circle circumscribed_circle(Point p, Point q, Point r){
  Point a,b,c;
  circle res;
  a=(q-p)*2;
  b=(r-p)*2;
  //c.x=p.dot(p)-q.dot(q);  
  //c.y=p.dot(p)-r.dot(r);

  c.x=p.x*p.x-q.x*q.x+p.y*p.y-q.y*q.y;
  c.y=p.x*p.x-r.x*r.x+p.y*p.y-r.y*r.y;

  res.p.x=a.y*c.y-b.y*c.x;
  res.p.y=b.x*c.x-a.x*c.y;
  res.p=res.p/a.cross(b);
  return circle(res.p, p.dist(res.p));
}

int main(void){
  int n;
  cin >> n;
  while(n--){
    vector<Point>v(3);
    for(int i=0;i<3;i++)
      cin >> v[i].x >> v[i].y;

    circle res=circumscribed_circle(v[0],v[1],v[2]);
    //cout << res.p.x << " " << res.p.y << " " << res.r << endl;
    printf("%.3f %.3f %.3f",res.p.x,res.p.y,res.r);
    cout << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1276
N, *A = map(int, open(0))
 
A.sort()
 
if N % 2 == 1:
    L, M, R = A[: N//2], A[N//2], A[N//2+1:]
    print((sum(R) - sum(L)) * 2 + max(- M + L[-1], M - R[0]))
else:
    L, R = A[:N // 2], A[N // 2:]
    print((sum(R) - sum(L)) * 2 - R[0] + L[-1])

Measured memory_bytes: 7760
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();
		int i=0;
		
		while(a>0 && c>0){
		    if(i%2==0){
		        c = c-b;
		    }else{
		        a = a-d;
		    }
		    i++;
		}
		
		if(a<=0){
    		System.out.println("No");
		}else{
		    System.out.println("Yes");
		}
	}
}


Measured memory_bytes: 35872
import heapq

N, K = map(int, input().split())
d = list(map(int, input().split()))

min_d = -10**9

for k in range(min(K+1, N+1)):
    for a in range(0, k+1):
        b = k - a
        hq = d[: a] + d[N - b: N]
        heapq.heapify(hq)
        kk = k
        while kk < K and hq != []:
            hq_d = heapq.heappop(hq)
            if hq_d >= 0:
                heapq.heappush(hq,hq_d)
                break
            else:
                kk += 1
        min_d = max(min_d, sum(hq))        
        
print(min_d)

Measured memory_bytes: 3064
#include <iostream>
#include<bits/stdc++.h>
#define ll long long
#define   ull unsigned long long 
const int MAX=3e5;
const int mod=1e9+7;
using namespace std;
int cnt[MAX];
int dp[200][200];
int main(){
	int n;
	cin>>n;
	int arr[n+1];
	int pre[n+1];
	int suf[n+1];
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	pre[1]=arr[1];
	suf[n]=arr[n];
	int ans[n+1];
	for(int i=2;i<=n;i++)
		pre[i]=__gcd(pre[i-1], arr[i]);
	for(int i=n-1;i>=1;i--)
		suf[i]=__gcd(suf[i+1], arr[i]);
	int mx=-1;
	for(int i=2;i<=n;i++)
		mx=max(__gcd(pre[i-1], suf[i+1]), mx);
	mx=max(max(mx , suf[2]), pre[n-1]);
	cout<<max(mx, pre[n]);

}

Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
#define INF 1000000007
#define ll long long
#define rep(i_, __start, __end) for(ll i_=(ll)__start; i_<(ll)__end; i_++)
#define print(_a) cout << _a << endl;
#define printarray(a, len) rep(ii,0,len) cout << a[ii] << " ";
#define printarray2(aa, len) rep(ij,0,len) printarray(aa[ij], aa[ij].size()); print("");


int main(){
    ll n, x, y;
    double total=0, count=0.0;
    vector<ll> xy[10];
    ll town[] = {0,1,2,3,4,5,6,7};
    cin >> n;
    rep(i, 0, n){
      cin >> x >> y;
      xy[i].push_back(x);
      xy[i].push_back(y);
    }

    do{
      rep(i, 0, n-1){
        total += sqrt((xy[town[i]][0] - xy[town[i+1]][0]) * (xy[town[i]][0] - xy[town[i+1]][0]) 
        + (xy[town[i]][1] - xy[town[i+1]][1]) * (xy[town[i]][1] - xy[town[i+1]][1]));
      }
      count++;
    }while(next_permutation(town, town+n));
    total /= count;

    cout << fixed << setprecision(10) << total << endl;
  
  return 0;
}

Measured memory_bytes: 256
inp = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
l = inp.shift().split(' ')
N = l.shift() * 1
K = BigInt(l.shift())
l = inp.shift().split(' ')
c = 1
n = 1
k = new Array(l.length)
while (K) {
    if (k[n-1]) {
        K = K % BigInt(c - k[n-1])
        if (K === 0n) {
            break;
        }
    } else {
        k[n-1] = c
        c++
    }
    n = l[n - 1]
    K = K - 1n
}
console.log(n)

Measured memory_bytes: 49876
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1; y=0;
		return a;
	}
	int g=gcd(b,a%b,x,y);
	int t1=y;
	int t2=x-(a/b)*y;
	x=t1;
	y=t2;
	return g;
}
int flag=0;
void dfs(vector<set<int> >&v,int s,int vis[],set<int> &vv)
{
	vis[s]=1;
	vv.insert(s);
	for(auto x: v[s])
	{
		if(!vis[x])
			dfs(v,x,vis,vv);
	}
}
int main() {
	// your code goes here
   int n,m,k; cin>>n>>m>>k;
   vector<set<int> > v(n+1),v2(n+1);
   for(int i=0;i<m;++i)
   {
   	int a,b; cin>>a>>b;
   	if(a==b)continue;
   	v[a].insert(b);
   	v[b].insert(a);
   }
   for(int i=0;i<k;++i)
   {
   	int a,b; cin>>a>>b;
   	if(a==b)continue;
   	v2[a].insert(b);
   	v2[b].insert(a);
   }
   int vis[n+1];
   memset(vis,0,sizeof(vis));
   int ans[n+1];
   memset(ans,0,sizeof(ans));
   for(int i=1;i<=n;++i)
   {
   	  set<int> vv;
   	  if(vis[i])continue;
   	  dfs(v,i,vis,vv);
   	  int sz=vv.size();
   	  for(auto x: vv)
   	  {
   	  	int cnt=0;
   	  	for(auto bb: v2[x])
   	  	{
   	  		if(v[x].count(bb))continue;
   	  		if(vv.count(bb))cnt++;
   	  	}
   	  	ans[x]=sz-1-cnt-v[x].size();
   	  }
   }
   for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
}

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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    if ((n-1)%(k-1) == 0) {
        cout << (n-1)/(k-1) << endl;
    }
    else {
        cout << (n-1)/(k-1) + 1 << endl;
    }
    return 0;
}
    

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

long long dp[6005][9005];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int offset = 3000;

	long long N, M;
	cin >> N >> M;
	
	dp[0][offset] = 1;
	for(int i = 0; i < 3*N; i ++) {
		for(int j = -N; j <= 3*N; j ++) {
			dp[i+1][j+1+offset] = (dp[i+1][j+1+offset] + dp[i][j+offset]) % M;
			dp[i+2][j-1+offset] = (dp[i+2][j-1+offset] + dp[i][j+offset] * (i+1) % M) % M;
			dp[i+3][j+offset] = (dp[i+3][j+offset] + dp[i][j+offset] * (i+1) % M * (i+2) % M) % M;
		}
	}
	long long ans = 0;
	for(int i = 0; i <= N; i ++) ans = (ans + dp[3*N][3*i+offset]) % M;
	cout << ans << '\n';
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<vector<int>> input(n, vector<int>(n));
  
  for(int i = 0; i < n; ++i){
    string s;
    cin >> s;
    
    for(int j = 0; j < n; ++j){
      input[i][j] = s[j];
    }
  }
  
  auto func = [&](int k){
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        
        int p1_first = (i+k)%n;
        int p1_second = j;
        int p2_first = (j+k)%n;
        int p2_second = i;
        
        //対称でない時
        if(input[p1_first][p1_second] != input[p2_first][p2_second]){
          return false;
        }
      }
    }
    
    return true;
  };
  
  int count = 0;
  
  for(int k = 0; k < n; ++k){//ずらした数
    count += func(k) * n;
  }
  cout << count << endl;
}

Measured memory_bytes: 640
// http://codeforces.com/contest/1315/problem/D
// Greedy
// time complexity limitation
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <deque>

#define ll long long
#define ull unsigned long long


using namespace std;

const int MOD = 1e9+7;
const int inf = 0x3f3f3f3f;
const int PI = acos(-1.0);

const int N = 2e5+10;


int main() {
	#ifdef local
		if(freopen("/Users/Andrew/Desktop/Problems/data.txt", "r", stdin) == NULL) printf("can't open this file!\n");
	#endif

    int n;
    cin >> n;
    int ans = 0;
    ans += (n/500)*1000;
    n = n%500;
    ans += (n/5)*5;
    cout << ans << endl;

	#ifdef local
	fclose(stdin);
	#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){

int n,s=0;

cin>>n;

int a[n+1];

a[0]=0;

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

cin>>a[i];

if(a[i]>a[i-1])

s+=a[i]-a[i-1];} 

cout<<s;
return 0;
}


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

using namespace std;

int main(){
	int n;
	cin >> n;
	int a[n];

	for(int i=0;i<n;i++){
		cin >> a[i];
	}

	int dp[n-1]={0};
	dp[0] = 0;
	for(int i=1;i<n;i++){
		dp[i] = INT_MAX;

		int step_1, step_2;
		if(i-1 >= 0){
			dp[i] = min(dp[i], dp[i-1] + abs(a[i]-a[i-1]));
		}
		if(i-2 >= 0){
			dp[i] = min(dp[i], dp[i-2] + abs(a[i]-a[i-2]));
		}
	}

	cout << dp[n-1] << endl;
	return 0;
}

Measured memory_bytes: 4376
n, m = map(int, input().split())
d_net = {}  # dict of path
d_path = {}  # dict of return path

for i in range(m):
    a, b = map(int, input().split())
    if a in d_net:
        d_net[a].append(b)
    else:
        d_net[a] = [b]

    if b in d_net:
        d_net[b].append(a)
    else:
        d_net[b] = [a]

start_list = d_net[1]
tmp_list = []
for no in start_list:
    d_path[no] = 1
    tmp_list.append(no)

while True:
    next_list = []
    for no in tmp_list:
        for next_no in d_net[no]:
            if next_no not in d_path:
                d_path[next_no] = no
                next_list.append(next_no)
    tmp_list = next_list
    if(tmp_list == []):
        break
print("Yes", end="\n")
for i in range(2, n+1):
    print(d_path[i], end="\n")


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

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


signed main(){

	int n;
	cin >> n;
	vector<int> a(n, -1);
	vector<vector<int>> inv(n);
	for(int i = 1; i < n; ++i){
		cin >> a[i];
		inv[--a[i]].emplace_back(i);
	}

	vector<int> v(n, -1);

	function<void(int)> f = [&](int x){
		vector<int> t;
		for(auto& y : inv[x]){
			if(v[y] == -1)
				f(y);
			t.emplace_back(v[y]);
		}
		if(t.empty()){
			v[x] = 0;
			return ;
		}
		sort(t.begin(), t.end(), greater<int>());
		for(int i = 0; i < t.size(); ++i)
			t[i] += i;
		v[x] = *max_element(t.begin(), t.end()) + 1;
	};
	f(0);
	cout << v[0] << endl;
}


Measured memory_bytes: 15872
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;

const int INF = 1e9 + 5;

int main() {
    int n;
    scanf("%d", &n);
    int k;
    scanf("%d", &k);
    vector<int> h(n);
    for(int& x : h) {
        scanf("%d", &x);
    }
    vector<int> dp(n, INF);
    dp[0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j <= i + k; ++j) {
            if(j < n) {
                dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
            }
        }
    }
    printf("%d\n", dp[n-1]);
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<vd> vvd;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())
int num[3][3];
int main(){
  ll n,T;
  cin>>n>>T;
  vll cost(0);
  REP(i,n){
    ll c,t;cin>>c>>t;
    if(t<=T){cost.push_back(c);}
  }
  if(SIZE(cost)==0){cout<<"TLE"<<endl;}
  else{
    sort(cost.begin(),cost.end());
    cout<<cost[0]<<endl;
  }
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int K,S;
	cin>>K>>S;
	int ans=0;
	rep(x,K+1)rep(y,K+1)if(0<=S-x-y&&S-x-y<=K)ans++;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var N=Arr.shift()-0;
   if(N==0)break;
   var pm=[];
   for(var i=0;i<N;i++){
      var arr=(Arr.shift()).split(" ").map(Number);
      var m=arr[0];
      var a=arr[1];
      var b=arr[2];
      pm.push([a,m]);
      pm.push([b-0.1,-1*m]);
   }
   pm.sort(function(a,b){
   a=a[0];
   b=b[0];
   return a-b;
   });
   var flag="OK";
   var sum=0;
   for(var i=0;i<pm.length;i++){
      sum+=pm[i][1];
      if(sum>150){flag="NG";break;}
   }
   console.log(flag);
}

Measured memory_bytes: 13628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(N);
    vector<Pll> pp(N);
    rep(i,N){
        cin >> A[i] >> B[i];
        pp[i] = Pll(A[i],B[i]);
    }
    sort(pp.begin(), pp.end());
    priority_queue<ll> que;
    ll id = 0;
    ll ans = 0;
    REP(i,1,M+1){
        while(id < N && pp[id].fi <= i){
            que.push(pp[id].se);
            id++;
        }
        if(que.empty())continue;
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 7312
N = int(input())
A = list(map(int, input().split()))

ans = [0]*8
leng = 0

for i in range(N):
    now = A[i]//400
    if now < 8:
        ans[now] = 1
    else:
        leng += 1

mi = sum(ans) if sum(ans) > 0 else 1
print(mi, sum(ans) + leng)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
int main(){
	string N;int K;
	cin>>N>>K;
	int len=N.length();
	if(K==1){
		printf("%d",(len-1)*9 + (N[0]-'0'));
	}
	else if(K==2){
		int sum=(len-2)*(len-1)/2*81+(N[0]-'1')*(len-1)*9;
		for(int i=1;i<len;i++){
			if(N[i]!='0'){
				sum+=(N[i]-'0')+(len-i-1)*9;
				break;
			}
		}
		printf("%d",sum);
	}
	else{
		int sum=(len-3)*(len-2)*(len-1)/6*729+(N[0]-'1')*(len-1)*(len-2)/2*81;
		for(int i=1;i<len;i++){
			if(N[i]!='0'){
				sum+=(N[i]-'1')*(len-i-1)*9+(len-i-1)*(len-i-2)/2*81;
				for(int j=i+1;j<len;j++){
					if(N[j]!='0'){
						sum+=(N[j]-'0')+(len-j-1)*9;
						break;
					}
				}
				break;
			}
		}
		printf("%d",sum);
	}
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  if(A >= K){
    cout << K << endl;
  }else if(A + B >= K){
    cout << A << endl;
  }else{
    cout << A - (K - (A + B)) << endl;
  }
}

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	long long a, b; cin >> a >> b;
	long long x = min(a, b);
	while (a % x != 0 || b % x != 0) {
		x--;
	}
	cout << (a * b) / x;
}
 


Measured memory_bytes: 256
pm = {}

while (s = gets) != "\n"
  (n, c) = s.chomp.split(/,/).map(&:to_i)
  pm[n] = [] if !pm.key?(n)
  pm[n].push(c)
end

tm = {}

while s = gets
  (n, c) = s.chomp.split(/,/).map(&:to_i)
  tm[n] = [] if !tm.key?(n)
  tm[n].push(c)
end

pm.keys.sort.each do |k|
  if tm.key?(k)
    puts "#{k} #{pm[k].size + tm[k].size}"
  end
end

Measured memory_bytes: 8616
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

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

class UnionFind {
private:
    vector<int> par, sizes;

public:

    UnionFind(int n = 100010) : par(n), sizes(n, 1) {
        rep(i, n) par[i] = i;
    }

    int root(int x) {
        if (x == par[x]) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return sizes[root(x)];
    }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h,w; cin >> h >> w;
  char c[400][400];
  rep(i,h) rep(j,w) cin >> c[i][j];
  UnionFind uf(h*w);
  rep(i,h-1) rep(j,w){
    if(c[i][j] != c[i+1][j]){
      uf.unite(i*w+j,(i+1)*w+j);
    }
  }
  rep(i,h) rep(j,w-1){
    if(c[i][j] != c[i][j+1]){
      uf.unite(i*w+j,i*w+j+1);
    }
  }

  ll black[400*400]={},white[400*400]={};
  rep(i,h) rep(j,w){
    if(c[i][j] == '#') black[uf.root(i*w+j)]++;
    else white[uf.root(i*w+j)]++;
  }
  
  ll ans = 0;
  rep(i,h*w) ans+= black[i] * white[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

vector<int> to[100005];
int udis[100005];
int vdis[100005];

queue<int> q;

void bfs1(int u) {
    q.push(u);    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y: to[x]) {
            if (udis[y]<0) {
                udis[y] = udis[x] + 1;
                q.push(y);
            }
        }
    }
}
void bfs2(int u) {
    q.push(u);    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y: to[x]) {
            if (vdis[y]<0) {
                vdis[y] = vdis[x] + 1;
                q.push(y);
            }
        }
    }
}

int main(){
    int n, u, v;
    cin >> n >> u >> v;
    u--; v--;
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        to[a].emplace_back(b);
        to[b].emplace_back(a);
    }
    rep(i, n) udis[i] = -1;
    rep(i, n) vdis[i] = -1; 
    udis[u] = 0;
    vdis[v] = 0;
    bfs1(u);
    bfs2(v);
    int ans = 0;
    if (udis[v]==1 && to[u].size()==1) {
        cout << "0" << endl;
        return 0;
    }
    rep(i, n) {
        if (to[i].size()==1 && udis[i]<vdis[i]) {
            ans = max(ans, vdis[i]-1);
        }
    }
    
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6656
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector<vector<char>> grid(h+2, vector<char>(w+2, '.'));
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			cin >> grid[i][j];
		}
	}
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			if(grid[i][j] == '.') continue;
			bool ok = false;
			rep(k,4){
				if(grid[i+dy[k]][j+dx[k]] == '#') ok = true;
			}
			if(!ok){
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <array>

using namespace std;

int main(int argc, const char *argv[])
{
  string s, t;
  cin >> s >> t;
  
  array<set<int>, 26> s_positions;
  for (int i = 0; i < s.size(); i++) {
    s_positions[s[i] - 'a'].insert(i);
  }
  
  bool exists = all_of(t.begin(), t.end(),
      [&](char ch) { return s_positions[ch - 'a'].size() > 0; });
  if (!exists) {
    cout << "-1\n";
    return 0;
  }

  int s_cur = 0, t_cur = 0;
  long long repeat_cnt = 0;
  while (t_cur < t.size()) {
    char t_ch = t[t_cur];
    auto &ch_positions = s_positions[t_ch - 'a'];
    auto it = ch_positions.lower_bound(s_cur);
    if (it != ch_positions.end()) {
      s_cur = *it + 1;
      t_cur++;
    } else {
      s_cur = 0;
      repeat_cnt++;
    }
  }

  cout << repeat_cnt * static_cast<long long>(s.size()) + s_cur << "\n";
  return 0;
}

Measured memory_bytes: 5120
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int ans = 0;
    int prev = 0;
    int count =0;
    for (int i = 0; i < N; i++) {
      int num = sc.nextInt();
      if(num<=prev){
        count++;
      }else{
        ans = Math.max(ans,count);
        count=0;
      }
      prev = num;
    }
    ans = Math.max(ans,count);

    System.out.println(ans);

  }

}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int T = 1e5 + 10;

bool ok(ll x, const vector<ll> &v) {
    for(auto y : v) x -= x%y;
    return (x==2);
}

int main() {
    ios_base::sync_with_stdio(false);
    int k; cin >> k;
    ll ans1 = 2, ans2 = 2;
    vector<ll>v;

    for(int i = 0; i < k; i++) {
        int x; cin >> x;
        v.pb(x);
    }

    for(int i = k-1; i >= 0; i--) {
        ans1 = ((ans1/v[i])+(ans1%v[i]?1:0))*v[i];
        ans2 = (ans2/v[i]+1)*v[i]-1;
    }

    if(ok(ans1,v)) cout << ans1 << " " << ans2 << endl;
    else cout << -1 << endl;

    return 0;
}



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

string s[200005];
int n, ans;

int main() {
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++){
        getline(cin, s[i]);
    }
    sort(s + 1, s + n + 1);
    ans = 0;
    for (int i = 1; i <= n; i++){
        if (s[i] != s[i + 1]){
            ans++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 10020
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String a = scan.next();
		String b = scan.next();
		String two = a + b;
		int twonum = Integer.parseInt(two);
		double result = Math.sqrt(twonum);
		int fin = (int)result;
		if(fin*fin == twonum ){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;cin>>s;
	int len=s.length();int n=0;int nn=pow(10,len-1);
	for(int i=0;i<len;i++)
	{
		n*=10;n+=s[i]-'0';
	}
	int ans=0;
	for(int i=1;i<len;i+=2)
	{
		int tmp=9;
		for(int j=2;j<=i;j++) tmp*=10;	
		ans+=tmp;
	}
	//cout<<ans<<" "<<n<<" "<<nn<<endl;
	if(len%2)
	{
		ans+=(n-nn+1);
	}
	cout<<ans<<endl;
 } 

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int k;
	cin >> k;
	int cnt = 0;
	vector<string> vec1;
	for (int i = 1; i <= 9; ++i) {
		++cnt;
		if (i == k) {
			cout << i;
			return 0;
		}
		string x = "";
		x += (i + '0');
		vec1.push_back(x);
	}
	while (true) {
		vector<string> vec2;
		for (string x : vec1) {
			for (int j = -1; j <= 1; ++j) {
				string s = x;
				//cout << x << '\n';
				if (s.back() - '0' + j != -1 and s.back() - '0' + j != 10) {
					++cnt;
					s += (s.back() + j);
					vec2.push_back(s);
					if (cnt == k) {
						cout << s;
						return 0;
					}
				}
				
			}
		}
		vec1 = vec2;
	}
}

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

int main(){
    int n,i,minp,maxp=-1000000000;
    cin >> n;
    int m[n];
    for(i=0;i<n;i++)cin >> m[i];
    minp=m[0];
    for(i=1;i<n;i++){
        maxp=max(maxp,m[i]-minp);
        minp=min(minp,m[i]);
    }
    cout << maxp << endl;
    return 0;
}

Measured memory_bytes: 3836
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
const int SIZE = 10005;

struct BSTNode
{
	int key;
	BSTNode *lchild, *rchild;
	BSTNode(int k = 0, BSTNode* l = nullptr, BSTNode* r = nullptr)
		:key(k), lchild(l), rchild(r){}
};
typedef BSTNode* BSTree;
BSTree insert(BSTree& T, int key)
{
	if (!T)
	{
		T = new BSTNode(key);
		return T;
	}
	else if (key > T->key)
		T->rchild = insert(T->rchild, key);
	else
		T->lchild = insert(T->lchild, key);
	return T;
}

void pre_order(const BSTree T)
{
	if (!T)
		return;
	cout << ' ' << T->key;
	pre_order(T->lchild);
	pre_order(T->rchild);
}

void in_order(const BSTree T)
{
	if (!T)
		return;
	
	in_order(T->lchild);
	cout << ' ' << T->key;
	in_order(T->rchild);
}
int main(void)
{
	ios::sync_with_stdio(false);
	int n, key;
	int Tsize;
	char str[10];
	cin >> n;
	BSTree T = nullptr;
	while (n--)
	{
		cin >> str;
		if (str[0] == 'i')
		{
			cin >> key;
			insert(T, key);
		}
		else
		{
			in_order(T);
			cout << endl;
			pre_order(T);
			cout << endl;
		}
	}
	return 0;
}

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

int main(){
  int count[200001] = {0};
  int N;
  cin>>N;
  for(int i=1; i<=N-1;i++){
   int A;
    cin >> A;
    count[A]++;
  }
  for(int i=1; i<=N;i++){
   cout << count[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 4420
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














string S;
string week[7] = { "SUN","MON","TUE","WED","THU","FRI","SAT" };
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S;
	rep(i, 0, 7) if (week[i] == S) {
		int ans = 7 - i;
		cout << ans << endl;
		return;
	}
}







Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, x int
	fmt.Scan(&n, &x)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)

	ans := 0
	for i := 0; i < n; i++ {
		if a[i] <= x {
			ans++
		}
		x -= a[i]
	}
	if ans > 0 && x > 0 {
		ans--
	}

	fmt.Println(ans)
}


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

int main() {
    int n,count=0;
    cin>>n;
    vector<int> p(n);
    rep(i,n) cin>>p.at(i);

    for (int i=1; i<n-1; i++) {
        if ((p.at(i-1)<p.at(i)&&p.at(i)<p.at(i+1))||p.at(i-1)>p.at(i)&&p.at(i)>p.at(i+1)) count++;
    }

    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int gcd(int p, int q) {
  while (q != 0) {
    int r = p % q;
    p = q;
    q = r;
  }
  return p;
}
 
int main() {
  int k;
  scanf("%d", &k);
 
  long sum = 0;
  for (int a=1; a<=k; a++)
    for (int b=1; b<=k; b++)
      for (int c=1; c<=k; c++)
        sum += gcd(gcd(a, b), c);
 
  printf("%ld\n", sum);  
 
  return 0;
}

Measured memory_bytes: 1732
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string>
#include<cmath>
 
int main(void){
    int N;
    scanf("%d",&N);
    long long int ans=0;
    for(int m=0;m<=N;m++){
        if(m%3==0){}else if(m%5==0){}else{
            ans+=m;
        }
    }
    printf("%lld",ans);
}

Measured memory_bytes: 3816
// https://atcoder.jp/contests/abc055/tasks/abc055_a
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i, n) for (int i = 0; i < n; i++)
#define EACH(i, n) for (auto &i: n)

int main() {
  int n;

  cin >> n;

  int pay = n * 800;
  int back = (n / 15) * 200;

  cout << pay - back << endl;

  return 0;
}


Measured memory_bytes: 256
/*
    Mbak Sana Dong
*/
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool visited[81][81][6500];
int a[81][81], b[81][81], arr[81][81];
int r,c;
int sana;
void dfs(int x, int y, int val)
{
    val = abs(val);
    if(visited[x][y][val]) return;
    if(val >= 6500) return;
    visited[x][y][val] = 1;
    if(x == r && y == c)
    {
        sana = min(sana ,val);
        return;
    }
    if(x < r)
    {
        dfs(x+1, y, val + arr[x+1][y]);
        dfs(x+1, y, val - arr[x+1][y]);
    }
    if(y < c)
    {
        dfs(x, y+1, val + arr[x][y+1]);
        dfs(x, y+1, val - arr[x][y+1]);
    }
}
int main()
{
    int n,m,i,j,k,x,y,ans,curr,temp;
    scanf("%d %d",&r,&c);
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            scanf("%d", &b[i][j]);
        }
    }
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            arr[i][j] = abs(a[i][j] - b[i][j]);
        }
    }
    sana = 1e9;
    dfs(1, 1, arr[1][1]);
    printf("%d\n", sana);
    return 0;
}


Measured memory_bytes: 41344
#include<iostream>
#include<map>
#include<algorithm>
#include <iomanip>
#include <cmath>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <list>


constexpr int INF = 1050000000;
constexpr int MOD = 1000000007;
constexpr long long LONGINF = 1005000000000000000;
using namespace std;

using ll = long long;
/*    UnionFind


class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> height;
	std::vector<int> m_size;

public:
	UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	void init(int size_) {
		parent.resize(size_);
		height.resize(size_, 0);
		m_size.resize(size_, 1);
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		int t = size(x) + size(y);
		m_size[x] = m_size[y] = t;
		if (height[x] < height[y]) parent[x] = y;
		else parent[y] = x;
		if (height[x] == height[y]) ++height[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		if (parent[x] == x) return m_size[x];
		return size(parent[x] = find(parent[x]));
	}
};


*/

int GCD(int a, int b) {
	while (b) {
		int tmp = a % b;
		a = b;
		b = tmp;
	}
	return a;
}

int s(int a) {
	int n = a;
	map<int, int> mp;
	for (int i = 2; i*i <= a; i++) {
		while (n%i == 0) {
			n /= i;
			mp[i];
		}
	}
	mp[n];
	int check = 1;
	for (auto x : mp) {
		check *= x.first;
	}

	return check;
}

int main() {


		int p, q; cin >> p >> q; if (p == 0 && q == 0) { return 0; }

		int G = GCD(p, q);

		p /= G;
		q /= G;

		cout << s(q) << endl;

}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
#define vall(x) (x).begin(), (x).end()
using namespace std;
using lli = long long int;
void YESNO(bool), YesNo(bool);
template <class T1, class T2> bool chmin(T1 &l, const T2 &r);
template <class T1, class T2> bool chmax(T1 &l, const T2 &r);
template <class T1, class T2> void vadd(vector<T1> &v, T2 x);

#define int long long int

void solve(long long X) {
  lli a = 100;
  int cnt = 0;
  while (a < X) {
    a = 1.01 * (double)(a);
    cnt++;
  }
  cout << cnt << endl;
}

signed main() {
  long long X;
  scanf("%lld", &X);
  solve(X);
  return 0;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2> bool chmin(T1 &l, const T2 &r) {
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2> bool chmax(T1 &l, const T2 &r) {
  return (l < r) ? (l = r, true) : false;
}

template <class T1, class T2> void vadd(vector<T1> &v, T2 x) {
  for (auto &s : v)
    s += T2(x);
}


Measured memory_bytes: 3768