akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using i64 = long long;
using Mat = std::vector<std::vector<i64>>;

i64 mod;

Mat operator*(const Mat &lhs, const Mat &rhs) {
    int n = lhs.size();
    Mat ret(n, std::vector<i64>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) {
        ret[i][j] = (ret[i][j] + lhs[i][k] * rhs[k][j] % mod) % mod;
    }
    return ret;
}

Mat pow(Mat m, i64 k) {
    const int size = m.size();
    Mat ret(size, std::vector<i64>(size));
    for (int i = 0; i < size; i++) ret[i][i] = 1;
    while (k) {
        if ((k & 1) == 1) ret = m * ret;
        m = m * m;
        k >>= 1ll;
    }
    return ret;
}

int main() {
    i64 n, a, b;
    std::cin >> n >> a >> b >> mod;

    std::vector<i64> dcnt(20);
    i64 sum = 0;
    int initial = std::to_string(a).length();
    for (i64 i = initial; i < 20; i++) {
        i64 l = 0, r = n, th = 1;
        for (i64 j = 0; j < i; j++) th *= 10;
        while (r - l > 1) {
            i64 k = (l + r) / 2;
            i64 s = a + b * k;
            if (s < th) l = k;
            else r = k;
        }
        dcnt[i] = l + 1 - sum;
        sum = l + 1;
    }

    i64 dd = 10;
    i64 ret = 0, s = a;
    for (i64 i = 1; i <= 18; i++) {
        Mat m { { dd, 0, 0 }, { 1, 1, 0 }, { 0, b, 1 } };
        m = pow(m, dcnt[i]);
        ret = (ret * m[0][0] % mod + s * m[1][0] % mod + m[2][0]) % mod;
        s = (s * m[1][1] % mod + m[2][1]) % mod;
        dd = dd * 10 % mod;
    }
    std::cout << ret << std::endl;

    return 0;
}


Measured memory_bytes: 256
using System;

namespace ITP1_4_A
{
    class Program
    {
        static void Main(string[] args)
        {
            String[] inputs = Console.ReadLine().Split(' ');
            int a = Convert.ToInt32(inputs[0]);
            int b = Convert.ToInt32(inputs[1]);
            
            Console.Write( (a/b) + " " + (a%b) + " " + ( (double)a/(double)b ).ToString("F5") );
        }
    }
}

Measured memory_bytes: 20032
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
int main(){
  int d,n ;cin>>d>>n ;
  if(d==0&&n==100)cout<<101<<endl ;
  else if(d==1&&n==100) cout<<10100<<endl ; 
  else if(d==2&&n==100) cout<<1010000<<endl ; 
   else cout<<pow(100,d)*n<<endl ;  
   return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
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 long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

void  base_num(ll data,ll base){
    if(data==0) return;
    ll next=abs(data)%abs(base);
    if(data<0) next=(abs(base)-next)%abs(base);
    base_num((data-next)/base,base);
    cout << next;
}


int main(){
    ll a,b,c,d,ans;
    cin >> a >> b >> c >> d;
    a-=1;
    ll x,y;
    x=b-(b/c)-(b/d)+b/(c*d/gcd(c,d));
    y=a-(a/c)-(a/d)+a/(c*d/gcd(c,d));
    ans=x-y;
    cout << ans << endl;
    return 0;
}


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

class Program
{
    static void Main()
    {
        var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var D = input[0];
        var T = input[1];
        var S = input[2];
        Console.WriteLine(D > T * S ? "No" : "Yes");
    }
}


Measured memory_bytes: 28172
#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
int p[100010];
vector<pair<ll,ll>> vt;
vector<pair<ll, ll>> vt1;
vector<pair<ll, pair<ll, ll>>> vt2;
int find(int u)
{
	if (u == p[u])return u;
	return p[u] = find(p[u]);
}
int merge(int u, int v)
{
	u = find(u), v = find(v);
	if (u == v)return 0;
	p[u] = v;
	return 1;
}
int main()
{
	ll n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
		ll q, w;
		scanf("%lld %lld", &q, &w);
		vt.push_back({ q,i });
		vt1.push_back({ w,i });
	}
	sort(vt.begin(), vt.end());
	sort(vt1.begin(), vt1.end());
	for (int i = 1; i < n; i++)
	{
			vt2.push_back({vt[i].first-vt[i-1].first ,{ vt[i].second,vt[i - 1].second } });
			vt2.push_back({ vt1[i].first - vt1[i - 1].first ,{ vt1[i].second,vt1[i - 1].second } });
	}
	sort(vt2.begin(), vt2.end());
	ll dap = 0;
	for (int i = 0; i < vt2.size(); i++) {
		if (merge(vt2[i].second.first, vt2[i].second.second))
		{
			dap += vt2[i].first;
		}
	}
	printf("%lld", dap);
}

Measured memory_bytes: 13408
import java.util.*

private val readListInt: ()->List<Int> = { readLine()!!.split(' ').map(String::toInt) }
private val readString: ()->String = {readLine()!!}

fun main(args: Array<String>) {
    val S = readString()

    if (S == "ABC") {
        println("ARC")
    } else {
        println("ABC")
    }
}


Measured memory_bytes: 34396
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int a[2050];

int main()
{
    int x,y,n,z,w;
    while(~scanf("%d%d%d",&n,&z,&w))
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
        }
        if(n >= 2)
        x = max(abs(a[n]-w),abs(a[n-1]-a[n]));
        else x = abs(a[n]-w);
        if(n >= 3)
        y = min(abs(a[n-2]-a[n]),abs(a[n-1]-a[n]));
        else y = 0;
        int t = max(x,y);
        printf("%d\n",t);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define op1 freopen("C:\\acm\\Cproj\\in.txt","r",stdin);
#define pr freopen("C:\\acm\\Cproj\\out.txt","w",stdout)
#define pr2 freopen("C:\\acm\\Cproj\\std.txt","w",stdout)
#define pii pair<int,int>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
template <class T>
void read(T &val) { T x = 0; T bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int maxn = 1e6 + 11;
const int mod=1e9+7;
int n,m,x,y,t;

int main(){
    read(n);read(x);read(y);
    LL tt = n/x;
    if(n%x) tt++;
    cout<<tt*y<<endl;
    return 0;
}

Measured memory_bytes: 3596
import math

def insertionSort(A,n,g):
    cnt = 0
    for i in range(g,n):
        v = A[i]
        j = i-g
        while j >= 0 and A[j] > v:
            A[j+g], A[j] = A[j],A[j+g]
            j -= g
            cnt += 1
        A[j+g] = v
    return cnt

def shellSort(A,n):
    cnt = 0
    m = round(math.log(len(A),2))+1 # 事前処理をやる回数
    print(m)
    G = [round(len(A)*((1/2)**(a+1))) for a in range(m)] # 事前処理時の、各回の間隔
    print(*G)
    for i in range(0,m):
        cnt += insertionSort(A,n,G[i])
    return cnt

n = int(input())
A = [int(input()) for a in range(n)]
print(shellSort(A,n))
for a in A:
    print(a)



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

int main() {
    int n;
    vector<char> coler;
    cin >> n;
    for(int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if(c == 'Y') {
            cout << "Four" << endl;
            return 0;
        }
    }
    cout << "Three" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int k,a[]={0,1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
int main()
{
	scanf("%d",&k);
	printf("%d",a[k]);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

using namespace std;

int draw()
{
    int x,y;
    cin>>x>>y;

    if(x==0 && y==0)
        return 0;
    else
        for(int i = 0; i<x; i++)
        {
            for(int j = 0; j<y; j++)
            {
                if((i+j)%2==0)
                    cout<<"#";
                else
                    cout<<".";
            }
            cout<<endl;
        }
    cout<<endl;
    draw();
}

int main()
{

    draw();
    return 0;
}




Measured memory_bytes: 3092
/*
 * @Author       : nonameless
 * @Date         : 2020-09-19 20:19:51
 * @LastEditors  : nonameless
 * @LastEditTime : 2020-09-19 20:30:48
 */
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int)x.size()
#define toStr(name) (#name)
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const double eps = 1e-6;
const double PI  = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LNF  = 0x3f3f3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b,a % b):a;}
inline ll  gcd(ll  a, ll  b) { return b ? gcd(b,a % b):a;}
inline int lcm(int a, int b) { return a * b / gcd(a, b); }

template<class T>
inline void read(T &x){
    x = 0;
    int f = 1;
    char c = getchar();
    while(c < '0' || c > '9')   { if(c == '-') f = -1;  c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    x = x * f;
}

template<class T>
inline void out(string a, T x){ cout << a << " = " << x << endl; }

const int K = 15, N = 2e5 + 10;

const int mod = 998244353;

ll f[N], sum[N];
PII s[K];

int main(){

    int n, k; cin >> n >> k;
    for(int i = 1; i <= k; i ++) cin >> s[i].x >> s[i].y;
    f[1] = 1;
    sum[1] = 1;
    for(int i = 2; i <= n; i ++){
        for(int j = 1; j <= k; j ++){
            int a = s[j].x, b = s[j].y;
            if(a >= i) continue;
            a = i - a;
            b = max(0, i - b - 1);
            f[i] = (f[i] + sum[a] - sum[b] + mod) % mod;
        }
        sum[i] = (sum[i - 1] + f[i]) % mod;
    }
    cout << f[n] << endl;
    return 0;
}


Measured memory_bytes: 6740
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;

/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}

/* library */

/* main */

signed main() {
    int A, B, C;
    cin >> A >> B >> C;
    cout << max(0, C - (A - B)) << endl;
}

Measured memory_bytes: 256
function Main(input) {
    const lines = input.split(/\n/);
    const n = Number(lines[0]);
    var area = [];
    lines.slice(1).forEach(line=>{
        area.push(
            line.split(/\s/).map(str=>{return Number(str)})
        );
    });
    var count = 0;
    for(var down = 0; down < n; down++){
        var sum = 0;
        for(var i = 0; i < n; i++){
            if(i < down){
                sum += area[0][i];
            } else if(i > down){
                sum += area[1][i];
            } else {
                sum += (area[0][i] + area[1][i]);
            }
        }
        count = Math.max(count,sum);
    }
    console.log(count);
}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7500
N = int(input())
Happiness = [[int(h) for h in input().split()] for n in range(N)]

MaxTotalHappiness = [[0, 0, 0] for n in range(N)]
MaxTotalHappiness[0] = Happiness[0]

for i in range(N-1):
    MaxTotalHappiness[i+1][0] = max(MaxTotalHappiness[i+1][0], max(MaxTotalHappiness[i][1], MaxTotalHappiness[i][2]) + Happiness[i+1][0])
    MaxTotalHappiness[i+1][1] = max(MaxTotalHappiness[i+1][1], max(MaxTotalHappiness[i][0], MaxTotalHappiness[i][2]) + Happiness[i+1][1])
    MaxTotalHappiness[i+1][2] = max(MaxTotalHappiness[i+1][2], max(MaxTotalHappiness[i][0], MaxTotalHappiness[i][1]) + Happiness[i+1][2])

print(max(MaxTotalHappiness[N-1]))

Measured memory_bytes: 44128
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int sign(int j,int t){
  return (j&(1<<t))?1:-1;
}

int main(){
  int n,m; cin >>n >>m;
  vector<li> v[8];
  rep(i,n){
    li a,b,c; cin >>a >>b >>c; 
    rep(j,8){
      v[j].push_back(sign(j,0)*a+sign(j,1)*b+sign(j,2)*c);
    }
  }
  
  li ans=0;
  rep(j,8){
    li tmp=0;
    sort(v[j].begin(),v[j].end());
    rep(i,m){
      tmp-=v[j][i];
    }
    ans=max(ans,tmp);
  }
  print(ans);
}


Measured memory_bytes: 384
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    _, K = read_ints()
    A = read_ints()
    low, high = 0, max(A)+1
    while high-low > 1:
        mid = low+(high-low)//2
        # max log should be mid
        # 10, maximum log is 4
        required_cuts = sum((a-1)//mid for a in A)
        if required_cuts <= K:
            high = mid
        else:
            low = mid
    return high


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 91808
#include<stdio.h>
int main(void)
{
	int L, A, B, C, D,japanese=0,math=0,p=0;
	scanf("%d%d%d%d%d", &L, &A, &B, &C, &D);
	japanese = A % C;
	if (japanese > 0)
	{
		japanese = A / C + 1;
	}
	else if (japanese == 0)
	{
		japanese = A / C;
	}
	math = B % D;
	if (math > 0)
	{
		math = B / D + 1;
	}
	else if (math == 0)
	{
		math = B / D;
	}
	if (japanese>math)
	{
		p = L - japanese;
		printf("%d\n",p);
	}
	else
	{
		p = L - math;
		printf("%d\n",p);
	}
	return 0;
}

Measured memory_bytes: 1848
def prb2():
    a,b,c,d = map(int,input().split())
    t = (a+b)
    ak = (c+d)
    print('Yes' if t>ak else "No")

def prb3():
    n = int(input())
    d = set()
    for i in range(n):
        s = input()
        d.add(s)
    print(len(d))



#prb1()
#prb2()
prb3()

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

using namespace std;
#define  ll long long
#define ld long double
#define f first
#define s second

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    ll ans = 0 , ans2=0;
    for(int i=0; i<s.size(); i++)
    {
        if (i%2==0)
        {
            if (s[i]=='1') ans++;
        }
        else
        {
            if (s[i] == '0') ans++;
        }
    }

    ans2 = ans;
    ans = 0;
    for(int i=0; i<s.size(); i++)
    {
        if (i%2)
        {
            if (s[i]=='1') ans++;
        }
        else
        {
            if (s[i] == '0') ans++;
        }
    }

    cout << min(ans,ans2);

    return 0;
}

Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
n, x = map(int,input().split())

l = [0 for _ in range(n+1)] #バーガーの長さ
p = [0 for _ in range(n+1)] #パティの枚数
l[0] = 1
p[0] = 1
for i in range(1,n+1):
    l[i] = 3 + 2 * l[i-1]
    p[i] = 1 + 2 * p[i-1]
#print(l)
#print(p)

def solv(n, x): #答えを返します
    #print(n, x)
    if n == 0:
        if x == 1:
            return 1
        if x == 0:
            return 0
    else:
        if x <= 1:
            return 0
        elif 1 < x <= l[n-1] + 1:
            return solv(n-1, x - 1)
        elif x == l[n-1] + 2:
            return solv(n-1, x - 2) + 1
        elif l[n-1] + 3 <= x:
            if x == l[n]:
                return p[n-1] + 1 + solv(n - 1, x - 3 - l[n - 1])
            else:
                return  p[n-1] + 1 + solv(n - 1, x - 2 - l[n - 1])

print(solv(n,x))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
int main() {
	int n;
	scanf("%d", &n);
	Mint ans = modex(Mint(10), n) - modex(Mint(9), n) * 2 + modex(Mint(8), n);
	printf("%d\n", ans.val);
}


Measured memory_bytes: 3740
#include <iostream>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

ll a[500][500];
ll x[200000];
ll y[200000];
ll x2[200000];
ll y2[200000];

int main() {
	ll h, w, v;
	scanf("%d %d", &h, &w);
	rep(i, 0, h)rep(j, 0, w) {
		scanf("%d", &v);
		a[i][j] = v % 2;
	}

	ll cnt = 0;
	rep(i, 0, h) {
		rep(j, 0, w - 1) {
			if (a[i][j] & 1) {
				a[i][j + 1]++;

				y[cnt] = i + 1;
				x[cnt] = j + 1;
				y2[cnt] = i + 1;
				x2[cnt] = j + 2;
				cnt++;
			}
		}

		if (i != h - 1) {
			if (a[i][w - 1] & 1) {
				a[i + 1][w - 1]++;

				y[cnt] = i + 1;
				x[cnt] = w;
				y2[cnt] = i + 2;
				x2[cnt] = w;
				cnt++;
			}
		}
	}

	printf("%d\n", cnt);
	rep(i, 0, cnt)	printf("%d %d %d %d\n", y[i], x[i], y2[i], x2[i]);

	return 0;
}

Measured memory_bytes: 9728
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007

using namespace std;

int main(void) {
	int n;
	int p;
	int x, y;

	cin >> n;
	queue<int>a;
	FOR(i, 1, pow(2, n)) {
		cin >> p;
		a.push(p);
	}
	while (1) {
		x = a.front();
		a.pop();
		y = a.front();
		a.pop();
		if (x > y) {
			a.push(x - y);
		}
		else if (y > x) {
			a.push(y - x);
		}
		else {
			a.push(x);
		}
		if (a.size() == 1) {
			break;
		}
	}
	cout << a.front() << endl;
	return 0;
}

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

int main()
{
    int n;
    cin>>n;
    ll ans=0;
    int a[n][3];
    ll dp[n][3]={{0}};
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][1]+a[i][0],dp[i-1][2]+a[i][0]);
        dp[i][1]=max(dp[i-1][0]+a[i][1],dp[i-1][2]+a[i][1]);
        dp[i][2]=max(dp[i-1][1]+a[i][2],dp[i-1][0]+a[i][2]);
    }
    cout<<max(dp[n-1][0],(max(dp[n-1][1],dp[n-1][2])));
}



Measured memory_bytes: 3712
s_list = []
t_list = []

for i in range(0, int(input())):
    s_list.append(input())

for i in range(0, int(input())):
    t_list.append(input())

w_map = {}
for s in s_list:
    if s in w_map:
        w_map[s] += 1
    else:
        w_map[s] = 1

for t in t_list:
    if t in w_map:
        w_map[t] -= 1
    else:
        w_map[t] = -1

print(max(max(w_map.values()), 0))


Measured memory_bytes: 3064
#include <array>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define PB push


#define MOD 1000000007LL
#define EPS 1e-10

const int MAX_N = 100005;

int par[MAX_N];
LL sz[MAX_N];

void Init()
{
    REP(i, MAX_N)
    {
        par[i] = i;
        sz[i] = 1;
    }
}

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

bool Same(int x, int y)
{
    return Root(x) == Root(y);
}

void Unite(int x, int y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) return;

    par[x] = y;
    sz[y] += sz[x];
}

int main()
{
    Init();
    LL N, M;
    cin >> N >> M;
    vector<pii> edges;
    LL A, B;
    REP(i, M)
    {
        cin >> A >> B;
        edges.push_back(make_pair(A, B));
    }
    reverse(edges.begin(), edges.end());
    vector<LL> conveniences;
    for (const auto& edge : edges)
    {
        LL a = edge.first;
        LL b = edge.second;
        LL ra = Root(a);
        LL rb = Root(b);
        LL sa = sz[ra];
        LL sb = sz[rb];
        // printf("a = %d b = %d ra = %d rb = %d sa = %d sb = %d\n", a, b, ra, rb, sa, sb);
        Unite(edge.first, edge.second);
        LL convenience = (ra == rb) ? 0 : (sa * sb);
        conveniences.push_back(convenience);
        // cout << convenience << endl;
    }
    reverse(conveniences.begin(), conveniences.end());
    LL inconvenience = 0;
    REP(i, M)
    {
        inconvenience += conveniences[i];
        cout << inconvenience << endl;
    }
    return 0;
}


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

class dice{
public:
    vector<int> me = {1, 2, 3, 4, 5, 6};
    void N(){
        vector<int> tmp(6);
        tmp[0] = me[1]; tmp[1] = me[5]; tmp[2] = me[2];
        tmp[3] = me[3]; tmp[4] = me[0]; tmp[5] = me[4];
        me = tmp;
    }
    void E(){
        vector<int> tmp(6);
        tmp[0] = me[3]; tmp[1] = me[1]; tmp[2] = me[0];
        tmp[3] = me[5]; tmp[4] = me[4]; tmp[5] = me[2];
        me = tmp;
    }
    void S(){
        vector<int> tmp(6);
        tmp[0] = me[4]; tmp[1] = me[0]; tmp[2] = me[2];
        tmp[3] = me[3]; tmp[4] = me[5]; tmp[5] = me[1];
        me = tmp;
    }
    void W(){
        vector<int> tmp(6);
        tmp[0] = me[2]; tmp[1] = me[1]; tmp[2] = me[5];
        tmp[3] = me[0]; tmp[4] = me[4]; tmp[5] = me[3];
        me = tmp;
    }
    int TOP(){
        return me[0];
    }
};

int main(void){
    dice d;
    rep(i, 6) cin >> d.me[i];
    int q;
    cin >> q;
    rep(i, q){
        int a, b;
        cin >> a >> b;
        if(d.me[2] == a || d.me[3] == a){
            while(d.me[1] != b) d.N();
            if(d.me[2] == a) d.W();
            else d.E();
        }
        else {
            while(d.me[0] != a) d.N();
            d.E();
            while(d.me[1] != b) d.N();
            d.W();
        }
        cout << d.me[2] << endl;
    }
    return 0;
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ff first
#define ss second
#define endl '\n'
#define MAX INT_MAX
#define MIN INT_MIN
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
#define pb push_back
#define sz(a) (int)((a).size())
#define all(a) a.begin(),a.end()
#define loopf(i,a,b) for(int i = a;i < b;i++)
#define loopb(i,a,b) for(int i = a;i >= b;i--)
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< int,int > pii;


int32_t main()
{
    fast

   //int test=1;
   //cin>>test;


  //while(test--)
  //{
  
    string s;
    cin>>s;
    for(int i=0;i<3;i++)
    {
      if(s[i]=='7')
      {
        cout<<"Yes";
        return 0;
      }
    }

    cout<<"No";

  //while loop ending
 // }
  

return 0;
}


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

using namespace std;

#define S scanf
#define P printf
#define G getline
#define SZ size()
#define C clear()
#define B begin()
#define F front()
#define T top()
#define E end()
#define EM empty()
#define V vector
#define Q queue
#define DQ deque
#define PQ priority_queue
#define ST stack
#define FI first
#define SE second
#define PI acos(-1)
#define PS push
#define PP pop()
#define PSF push_front
#define PSB push_back
#define PPF pop_front()
#define PPB pop_back()
#define MP make_pair
#define LL long long int
#define ULL unsigned long long int
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>
#define PLI pair<long long int,int>
#define PLL pair<long long int,long long int>
#define MII map<int,int>
#define MSI map<string,int>
#define MIS map<int,string>
#define MLI map<long long int,int>
#define FAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)





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




LL mod_inverse(LL val,LL mod)
{
    LL mod1 = mod;
    LL y = 0;
    LL x = 1;
    LL quotient,temp;
    while(val > 1)
    {
        quotient = val / mod;
        temp = mod;
        mod = val % mod;
        val = temp;
        temp = y;
        y = x - quotient * y;
        x = temp;
    }
    if(x < 0)x += mod1;
    return x;
}

const LL mod=1e9+7;
LL a[100002],fact[100002];

void find_fact()
{
    LL i;
    fact[0]=fact[1]=1LL;
    for(i=2;i<=100000;i++)fact[i]=(fact[i-1]*i)%mod;
}

int main()
{
    FAST();

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    find_fact();
    LL i,k,n,ans=0LL;
    cin >> n >> k;
    for(i=1;i<=n;i++)cin >> a[i];
    sort(a+1,a+n+1,greater<LL>());
    for(i=1;i<=n;i++)
    {
        if(n - i >= k - 1LL) {
          LL p = mod_inverse(fact[n - i - (k - 1)], mod);
          LL q = mod_inverse(fact[k - 1], mod);
          LL down = (p * q) % mod;
          down = (a[i] * down) % mod;
          ans = (ans + down * fact[n - i]) % mod;
          if(ans < 0) ans += mod;
        }
        if(i >= k) {
          LL p = mod_inverse(fact[i - 1 - (k - 1)], mod);
          LL q = mod_inverse(fact[k - 1], mod);
          LL down = (p * q) % mod;
          down = (a[i] * down) % mod;
          ans = (ans - down * fact[i - 1]) % mod;
          if(ans < 0) ans += mod;
        }
    }
    if(ans < 0)ans+=mod;
    cout << ans;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<n;i++)
int main(void){
    // Your code here!
    vector<string> YN{"NO","YES"};
    vector<string> yn{"No","Yes"};
    int a,b,c;
    cin>>a>>b;
    cout<<(a-1)*(b-1)<<endl;
}


Measured memory_bytes: 256
#include<cstdio>


int main(){
    int N;
    scanf("%d", &N);
    N %= 10;
    if(N == 3) printf("bon");
    else if(N == 0 | N == 1 | N == 6 | N == 8) printf("pon");
    else printf("hon");
    return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>    
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//using namespace __gnu_pbds; 
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define int long long 
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N       = 1000 * 100 + 10;
const ll N2      = 70;
const ld PI  = 3.141592653589793;
//template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p = LLONG_MAX ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
ll lcm(ll a , ll b){return (a*b)/gcd(a,b);}

signed main()
{
    fastio();
    //cout<<fixed<<setprecision(20);
    //CHECK for LONG LONG and LONG DOUBLE
    /*comment for all except cc/cf    
    #ifndef ONLINE_JUDGE    
           freopen("input.txt","r",stdin);
           freopen("output.txt","w",stdout);
    #endif//*/
    int n,k;
    cin>>n>>k;
    int h[n] , dp[n] ;
    for (int i = 0; i < n; ++i)
    {
        dp[i] = MOD;
        cin>>h[i];
    }

    dp[0] = 0;
    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j <= k; ++j)
        {
            if((i-j)>=0)
            {
             dp[i] = min(dp[i-j] + abs(h[i] - h[i-j]),dp[i]);
            }
        }
    }
    cout<<dp[n-1];

    printclock;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
 
int main() { 
  int a , b ;
  cin>> a >> b ;
  if (((a+b)/2.0)-((a+b)/2)==0){
   cout<< (a+b)/2 << endl ;
  }
  else{ 
    cout<< (a+b)/2+1 << endl;
  }
}

Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String A = sc.next();
    String B = sc.next();
    String C = sc.next();
    
    char[]a = A.toCharArray();
    char[]b = B.toCharArray();
    char[]c = C.toCharArray();
    
    int AA = A.length();
    int BB = B.length();
    
    if(a[AA-1]==b[0] && b[BB-1]==c[0]){
    System.out.println("YES");
    }else{
    System.out.println("NO");    
    }
}
    }


Measured memory_bytes: 35748
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vec vector <ll>
#define pa pair<ll,ll>
#define mp make_pair
#define pb push_back
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s;
	cin>>s;
	if(s[2]==s[3] && s[4]==s[5])
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

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


bool check(char &c) {
    if(c== 'A'|| c == 'C' || c == 'G' || c == 'T') {
        return true;
    }else
        return false;
}
int main(void) {
    string s;
    cin >> s;

    int ans = 0;
    for(int i = 0; i < (int)s.length(); ++i) {
        int tmp = 0;
        if(check(s[i])){
            tmp++;
            for(int j = i+1; j < (int)s.length(); ++j) {
                if(check(s[j])) {
                    tmp++;
                }else{
                    break;
                }
            }
            ans = max(ans,tmp);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
ll n,m,a[100005],b,c;
ll ans;
vector<pair<ll,ll>> p;
main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=0;i<m;i++){
        cin>>b>>c;
        p.push_back({c,b});
    }
    sort(p.begin(),p.end(),greater<pair<ll,ll>>());
    int j=0;
    for(int i=0;i<n;i++){
        if(j<m&&p[j].second==0)j++;
        if(j<m)ans+=max(a[i],p[j].first),p[j].second--;
        else ans+=a[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3188
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def factorial(self, n):
        return self.fact[n]


def main():
    mod = 10 ** 9 + 7

    n, k = map(int, input().split())

    mi = min(k, n - 1)

    cl = Calc(max_value=n * 2 - 1, mod=mod)

    ret = 0
    for r in range(mi + 1):
        ret += cl.combination(n - 1, n - r - 1) * cl.combination(n, r)
        ret %= mod

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 36724
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "boost/multi_array.hpp"
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) int __VA_ARGS__; in(__VA_ARGS__)
//オーバーフロー対策
#define INL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
#pragma endregion RegionDefs

void solve()
{
    IN(a, b);
    if (a < 10 && b < 10)
    {
        cout << a * b << endl;
    }
    else
    {
        cout << -1 << endl;
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 892
//by tzupengwang™
#include<set>
#include<map>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;

int n , m ;
ii edg[ 400005 ] ;
int cpy[ 400005 ] ;
int spid[ 400005 ] ;
vector< int > v[ 100005 ] ;
vector< int > spv[ 400005 ] ;
set< int > st[ 100005 ] ;
map< ii , int > smap ;
int mpid ;
int dis[ 400005 ] ;

void init() {
  scanf( "%d%d" , &n , &m ) ;
  for ( int i = 0 ; i < m ; i ++ ) {
    int x , y , z ;
    scanf( "%d%d%d" , &x , &y , &z ) ;
    edg[ i * 2 ] = ii( x , y ) ;
    cpy[ i * 2 ] = z ;
    if ( smap.count( ii( x , z ) ) ) spid[ i * 2 ] = smap[ ii( x , z ) ] ;
    else smap[ ii( x , z ) ] = mpid , spid[ i * 2 ] = mpid ++ ;
    spv[ spid[ i * 2 ] ].push_back( i * 2 ) ;
    v[ x ].push_back( i * 2 ) ;
    edg[ i * 2 + 1 ] = ii( y , x ) ;
    cpy[ i * 2 + 1 ] = z ;
    if ( smap.count( ii( y , z ) ) ) spid[ i * 2 + 1 ] = smap[ ii( y , z ) ] ;
    else smap[ ii( y , z ) ] = mpid , spid[ i * 2 + 1 ] = mpid ++ ;
    spv[ spid[ i * 2 + 1 ] ].push_back( i * 2 + 1 ) ;
    v[ y ].push_back( i * 2 + 1 ) ;
  }
}

priority_queue< ii , vector< ii > , greater< ii > > pq ;

void process() {
  memset( dis , -1 , sizeof dis ) ;
  for ( int id : v[ 1 ] ) {
    pq.push( ii( 1 , id ) ) ;
  }
  while ( !pq.empty() ) {
    ii nnw = pq.top() ; pq.pop() ;
    int nid = nnw.second , dss = nnw.first ;
    int now = edg[ nid ].second ;
    int nwc = cpy[ nid ] ;
    if ( now == n ) {
      printf( "%d\n" , dss ) ;
      return ;
    }
    if ( dis[ nid ] != -1 ) continue ;
    dis[ nid ] = dss ;
    if ( st[ now ].count( nwc ) ) continue ;
    if ( st[ now ].size() == 0 ) {
      for ( int id : v[ now ] ) if ( dis[ id ] == -1 ) {
        if ( nwc == cpy[ id ] ) {
          pq.push( ii( dss , id ) ) ;
        } else {
          pq.push( ii( dss + 1 , id ) ) ;
        }
      }
    } else {
      if ( smap.count( ii( now , nwc ) ) ) {
        int iddd = smap[ ii( now , nwc ) ] ;
        for ( int id : spv[ iddd ] ) if ( dis[ id ] == -1 ) {
          pq.push( ii( dss , id ) ) ;
        }
      }
    }
    st[ now ].insert( cpy[ nid ] ) ;
  }
  printf( "-1\n" ) ;
}

int main() {
  init() ;
  process() ;
  return 0 ;
}


Measured memory_bytes: 82944
#include <bits/stdc++.h>
const int N=100005,mu=1000000007;
int n,k,a[N],dp[N],s[N],sum;
int main(){
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	dp[0]=s[0]=1;
	for (int i=1;i<=a[1];i++) s[i]=1;
	sum=a[1];
	for (int i=1;i<=n;i++){
		for (int j=0;j<=sum;j++) 
			if (j-a[i]>0) dp[j]=s[j]-s[j-a[i]-1];
			else dp[j]=s[j];
		s[0]=dp[0];
		sum+=a[i+1];
		sum=std::min(sum,k);
		for (int j=1;j<=sum;j++) s[j]=((s[j-1]+dp[j])%mu+mu)%mu;
	}
	printf("%d\n",(dp[k]+mu)%mu);
}

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

using ll = long long int;
using P = std::pair<int, ll>;

constexpr ll INF = 1e15;

#define rep(i, n) for (int i = 0; i < n; ++i)

using T = std::tuple<ll, int, ll>; //time,pos,coin

int n;
std::vector<T> g[55];
std::vector<P> ec;

std::vector<std::vector<ll>> d;

int am;

int cut(int x)
{
    return (x >= am * (n - 1)) ? am * (n - 1) : x;
}

int main()
{
    int m, s;

    std::cin >> n >> m >> s;

    ec.resize(n + 1);

    rep(i, m)
    {
        int u, v, a, b;
        std::cin >> u >> v >> a >> b;
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
        am = std::max(am, a);
    }

    rep(i, n)
    {
        std::cin >> ec[i + 1].first >> ec[i + 1].second;
    }

    std::priority_queue<T, std::vector<T>, std::greater<>> que;

    que.emplace(0, 1, cut(s));

    d.resize(n + 1, std::vector<ll>(am * (n - 1) + 1, INF));

    d[1][cut(s)] = 0;

    std::vector<ll> ans(n + 1, INF);

    while (!que.empty())
    {
        ll t;
        int pos, ccoin;
        std::tie(t, pos, ccoin) = que.top();
        que.pop();

        if (d[pos][ccoin] < t)
            continue;

        //std::cerr << "DEBUG" << pos << ' ' << ccoin << std::endl;

        ans[pos] = std::min(ans[pos], t);

        for (auto u : g[pos])
        {
            int coin = ccoin;
            int to, aa;
            ll bb;
            std::tie(to, aa, bb) = u;
            int c = ec[pos].first;

            ll dd = ec[pos].second;
            coin -= aa;
            for (ll i = 0;; ++i)
            {
                if (coin >= am * (n - 1))
                {
                    if (d[to][am * (n - 1)] > t + dd * i + bb)
                    {
                        d[to][am * (n - 1)] = t + dd * i + bb;
                        que.emplace(t + dd * i + bb, to, am * (n - 1));
                    }
                    break;
                }

                if (coin >= 0 && d[to][coin] > t + dd * i + bb)
                {
                    //std::cerr << pos << ' ' << to << ' ' << coin << ' ' << aa << std::endl;
                    d[to][coin] = t + dd * i + bb;
                    que.emplace(t + dd * i + bb, to, coin);
                }
                coin += c;
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        std::cout << ans[i] << std::endl;

    return 0;
}

Measured memory_bytes: 53336
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
                    .map(|e| e.parse().ok().unwrap())
                    .collect()
}

fn main() {
    let xyz = read_vec::<f32>();
    let x = xyz[0_usize];
    let y = xyz[1_usize];
    let z = xyz[2_usize];

    let ans = ((x-z) / (y+z)).floor();

    println!("{}", ans)
}

Measured memory_bytes: 4352
#include <stdio.h>
#define MAX 1000000
int main(void){
 	int i,j;
	int a[MAX+1];
	int counter;
	int n;
	while(scanf("%d",&n) != EOF){
		  counter = 0;
		  for(i = 1; i <= n; i++){
			  a[i] = 0;
		  }
		  for(i = 2; i <= n; i++){
			  if(a[i]){continue;}
			  for(j = i; j <= MAX; j += i){
				  if(j == i){a[i] = 0;}
				  else{a[j] = 1;}
			  }
		  }
		  for(i = 2; i <= n; i++){
			  if(!a[i]){
				  counter++;
			  }
		  }
		  printf("%d\n",counter);
	}
 	return 0;
}

Measured memory_bytes: 4312
#include <stdio.h>

//何乗するかを決定する係数
int N = 3;
// コマンドライン引数を受け取る。
int main(void){

  int input_num;
  int answer = 1;

  scanf("%d",&input_num);

  // N乗を計算するfor文
  for(int i=0;i<N;i++){
    answer *= input_num;
  }
  printf("%d\n",answer);
  return(0);
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n;
    cin >> n;
    double ans = 0;
    for(int i =0 ; i < n; i++){
        double x;
        cin >> x;
        ans += 1/x;
    }
    cout << fixed << setprecision(6) << 1/ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int x,n;
  cin >> x >> n;
  vector<int> data(n);
  for ( int i = 0 ; i < n ; i++ ) {
    cin >> data.at(i);
  }
  int a,b,count = 0;
  bool h = true;
  while(h = true) {
    bool f = true, g = true;
     a = x-count;
     b = x+ count;
    for ( int i = 0 ; i < n ; i++ ) {
      if (data.at(i)== a) {
        f = false;
      break;
      }
    }
    
    if (f) {
      cout << a << endl;
      break;;
    }
    
    for ( int i = 0 ; i < n ; i++ ) {
      if (data.at(i)== b ) {
        g = false;
        break;
      }
    }
    
    if (g) {
      cout << b << endl;
      break;;
    }
    
    count++;
    
  }
}

Measured memory_bytes: 3632
sx, sy, tx, ty = map(int, input().split())
X = tx - sx
Y = ty - sy

saitan = "U" * Y + "R" * X + "D" * Y + "L" * (X + 1) \
            + "U" * (Y + 1) + "R" * (1 + X) + "D" \
            + "R" + "D" * (Y + 1) + "L" * (1 + X) \
            + "U"

print(saitan)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++ )
#define MAX 100
enum {SPACE, LOSE, BACK};

double C[MAX+2][MAX+1];
int S[MAX+1], N, T, L, B;

void compute(){
    C[0][0] = 1;
    rep(i, T) rep(j, N+1){
	for ( int k = 1; k <= 6; k++ ){
	    int t =  (j+k>N) ? 2*N-(j+k) : j+k;
	    int s = (S[j]==LOSE) ? i+2 : i+1;
	    if ( S[t] == BACK ) t = 0;
	    if ( j == N ) t = N;
	    C[s][t] += C[i][j]/6;
	}
    }

    printf("%.8lf\n", C[T][N]);
}

main(){
    int x;
    while( cin >> N >> T >> L >> B && N){
	rep(i, T+1) rep(j, N+1) C[i][j] = 0;
	rep(i, N+1) S[i] = SPACE;
	rep(i, L) { cin >> x; S[x] = LOSE; }
	rep(i, B) { cin >> x; S[x] = BACK; }
	compute();
    }
}

Measured memory_bytes: 0