akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <vector>

#define mod 1000000007

typedef long long ll;

using namespace std;

// http://www.tbasic.org/reference/old/ExEuclid.html
// https://qiita.com/rintaromasuda/items/be6510090af04bad833d
ll modinverse(ll a, ll m) {
    ll x = 0, y = 1, gcd = m;
    ll px = 1, py = 0, pgcd = a;
    ll temp = 0;
    ll quotient;

    while (gcd > 0) {
        quotient = pgcd / gcd;

        temp = x;
        x = px - quotient * temp;
        px = temp;

        temp = y;
        y = py - quotient * temp;
        py = temp;

        temp = gcd;
        gcd = pgcd - quotient * temp;
        pgcd = temp;
    }
    if (px < 0) {
        px += m;
    }

    return px;
}

ll combination(int n, int r) {
    int i;
    ll u, d, inverse;

    u = 1;
    for (i = n; i > n - r; i--) {
        u = (u * i) % mod;
    }
    // d = 1;
    // for (i = r; i > 1; i--) {
    //     d *= i;
    // }
    // inverse = modinverse(d, mod);
    // return (u * inverse) % mod;
    d = u;
    for (i = r; i > 1; i--) {
        inverse = modinverse(i, mod);
        d = (d * inverse) % mod;
    }
    return d;
}

int main() {
    int N, M;
    int i;
    int num;
    ll ans;
    int count;
    vector <int> prime = {2};
    bool f;

    cin >> N >> M;

    count = 0;
    for (i = 3; i <= sqrt(M); i += 2) {
        f = true;
        for (int x : prime) {
            if (i % x == 0) {
                f = false;
                break;
            }
        }
        if (f) {
            prime.push_back(i);
        }
    }

    vector <int> c(prime.size(), 0);
    num = M;
    for (i = 0; i < prime.size(); i++) {
        while (num % prime[i] == 0) {
            c[i]++;
            num = num / prime[i];
        }
    }
    if (num != 1) {
        prime.push_back(num);
        c.push_back(1);
    }

    // for (i = 0; i < prime.size(); i++) {
    //     if (c[i] != 0) {
    //         cout << prime[i] << " " << c[i] << endl;
    //     }
    // }

    ans = 1;
    for (i = 0; i < prime.size(); i++) {
        if (c[i] != 0) {
            ans *= combination(c[i] + N - 1, c[i]);
            ans %= mod;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
from itertools import permutations
import sys
import heapq
from bisect import bisect_left, bisect_right
from collections import Counter
from collections import deque
from fractions import gcd
from math import factorial
from math import sqrt
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

#ここから書き始める
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()
ans = 0
for i in b:
    total1 = bisect_left(a, i)
    total2 = n - bisect_right(c, i)
    ans += total1 * total2
print(ans)


    
    



Measured memory_bytes: 24832
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	int n;
	while(cin >> n) {
		LL a, b;
		cin >> a >> b;
		vector<LL> x(n);
		REP(i,n) cin >> x[i];
		LL ans = 0;
		REP(i,n-1){
			// if((x[i+1]-x[i])*a < b){
				ans += min((x[i+1]-x[i])*a,b);
			// }
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力 解析
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            int iN = int.Parse(sS[0]);                                                              // 人数
            int iK = int.Parse(sS[1]);                                                              // 加点
            int iQ = int.Parse(sS[2]);                                                              // 問数
            List<int> lstN = new List<int>();
            for (int i = 0; i < iN; i++) { lstN.Add( iK - iQ); }                                    // 全員とりあえずの減点
            for (int i = 0; i < iQ; i++)
            {
                string s2 = System.Console.ReadLine().Trim();
                int iA = int.Parse(s2) - 1;
                lstN[iA] += 1;                                                                      // 正解で加点
            }

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 出力
            for (int i = 0; i < lstN.Count; i++)
            {
                if (lstN[i] > 0) { System.Console.WriteLine("{0}", "Yes".ToString().Trim()); }      // 　0より大でOK
                else { System.Console.WriteLine("{0}", "No".ToString().Trim()); }
            }

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 18524
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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 int MAX = 50010;
int n, m;
int c[22];
int dp[MAX];

int main() {
    cin >> n >> m;
    rep(i, m) cin >> c[i];

    rep(i, MAX) dp[i] = INF;
    dp[0] = 0;

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < m; j++) {
            if (i + c[j] <= n) chmin(dp[i + c[j]], dp[i] + 1);
        }
    }
    cout << dp[n] << endl;
}



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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

int n, m, f[110][110], deg[110];
vector< int > cand, sel;

int calc() {
	int res = 0;
	for_(i,0,size_of(sel)) {
		int mn = 1e9;
		for_(j,0,size_of(sel)) if (j != i) mn = min(mn, f[sel[i]][sel[j]]);
		res += mn;
	}
	return res;
}

int rec(int i, int s, int k) {
	if (s == k) return calc();
	if (i == size_of(cand)) return 0;
	
	int res = rec(i+1, s, k);
	
	sel.push_back(cand[i]);
	res = max(res, rec(i+1, s+1, k));
	sel.pop_back();
	
	return res;
}

int main() {
	cin >> n >> m;
	
	minit(f,0);
	minit(deg,0);
	
	for_(i,0,m) {
		int u, v, p; cin >> u >> v >> p;
		--u; --v;
		f[v][u] = f[u][v] = p;
		++deg[u]; ++deg[v];
	}
	
	int ans = 0;
	for_(i,2,15) {
		cand.clear();
		for_(j,0,n) if (deg[j] >= i - 1) cand.push_back(j);
		if (size_of(cand) >= i) ans = max(ans, rec(0, 0, i));
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1272
from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    n, m = map(int, next(inputs).split())
    an = list(map(int, next(inputs).split()))[:n]
    an.sort()
    bc = [ list(map(int, next(inputs).split())) for _ in range(m) ]
    bc.sort(key=lambda bc: bc[1], reverse=True) # sort by c
    
    x = 0
    y = 0
    ans = 0
    for i in range(n):
        if x < m and bc[x][1] >= an[i]:
            ans += bc[x][1]
            y += 1
            if y >= bc[x][0]:
                x += 1
                y = 0
                pass
            pass
        else:
            ans += an[i]
            pass
        pass
    return ans

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    print(main(gen_inputs()))
    pass


Measured memory_bytes: 33412
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    dp = [[0, 0] for _ in range(N+1)]
    dp[0][1] = - 10 ** 10
    for i in range(N):
        dp[i+1][0] = max(dp[i][0] + A[i], dp[i][1] - A[i])
        dp[i+1][1] = max(dp[i][0] - A[i], dp[i][1] + A[i])

    print(dp[N][0])

if __name__ == '__main__':
    main()

Measured memory_bytes: 25576
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const ll MOD = 1000000007;
const double EPS = 1e-9;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;



int main(void) {
    
    
    itn n;
    cin>>n;
    vs v(n);
    vi w(n);
    rep(i,n)cin>>v[i]>>w[i];
    string s;
    cin>>s;
    ll ans=0;
    bool f=0;
    for(int i=0;i<n;i++){
        if(f)ans+=w[i];
        if(s==v[i])f=1;
    }
    fin(ans);
    
    
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int n,a[100];
	cin>>n;
	unsigned long long ans=1000000000,sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=100;i++ )
	{
		sum=0;
		for(int j=0;j<n;j++)
		{
			sum += (a[j]-i)*(a[j]-i);
		}
		ans = min(ans,sum);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 510000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli A,B,C,D,E,F,N,M,K,L,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  Vec(P,lli,N,0);
  rep(i,0,N) cin >> P[i];
  rep(i,1,N)P[i]+=P[i-1];
  sum=INF;
  rep(i,0,N-1)chmin(sum,abs(P[i]-(P[N-1]-P[i])));
  Out(sum);
}

Measured memory_bytes: 1792
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define MAXN 15
#define MAXM 1000010
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
typedef long long LL;

int n,m,cnt[MAXN];
bool Map[MAXN][MAXN];
double f[2][2000][MAXN][2];

void Init()
{
    int i,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d",&u,&v); --u; --v;
        Map[u][v]=Map[v][u]=true;
        ++cnt[u]; ++cnt[v];
    }
}

void DP()
{
    int i,u,v,k,t,c;
    double ans=0,pre=0;
    f[0][1][0][1]=1;
    for(k=t=1;;k^=1,++t){
        memset(f[k],0,sizeof(f[k]));
        for(i=1;i<(1<<n)-1;++i)
            for(u=0;u<n;++u){
                if(!((1<<u)&i)) continue;
                for(v=0;v<n;++v){
                    if(!Map[u][v]) continue;
                    f[k][i|(1<<v)][v][0]+=f[k^1][i][u][0]/cnt[u]+f[k^1][i][u][1]/cnt[u];
                    f[k][i|(1<<v)][v][1]+=f[k^1][i][u][1]/cnt[u];
                }
            }
        for(u=ans=0;u<n;++u){
            f[k][(1<<n)-1][u][0]+=f[k^1][(1<<n)-1][u][0];
            f[k][(1<<n)-1][u][1]+=f[k^1][(1<<n)-1][u][1];
        }
        for(u=ans=0;u<n;++u) ans+=f[k][(1<<n)-1][u][0];
        if(t>n&&fabs(ans-pre)<1e-7){
            if((++c)>80) break;
        }
        else c=0;
        pre=ans;
    }
    printf("%.6f\n",ans);
}

int main()
{
    Init();
    DP();
    return 0;
}

Measured memory_bytes: 3684
import { count } from 'console';

process.stdin.resume();
process.stdin.setEncoding('utf8');

// 標準入力取込
let gInput = '';
process.stdin.on('data', (chunk) => (gInput += chunk));
process.stdin.on('end', () => main(gInput.split(/\r?\n/)));

// 解答
function main(inputs: string[]): void {
  const s = inputs[0];

  if (s.indexOf('B') > 0) {
    console.log('ARC');
  } else {
    console.log('ABC');
  }
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  for ( int i = 0; i < M; i++ ) {
    int a; cin >> a;
  }

  cout << N - M - 1 << endl;
  return 0;
}

Measured memory_bytes: 3132
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
pair < int , int > s[1 << 23];
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    set < pair < int , int > > S;
    int h,w,n;
    IOS;
    fi>>h>>w>>n;
    int sz = 0;
    while (n --)
    {
        int a,b;
        fi>>a>>b;
        S.insert({a,b});
        for (int i = max(a - 2,1);i <= a;++i)
            for (int j = max(b - 2,1);j <= b;++j)
                s[++sz] = {i,j};
    }
    sort(s+1,s+1+sz);
    sz = unique(s+1,s+1+sz) - s;--sz;
    vector < ll > ans(55,0);
    ans[0] = 1ll * (h - 2) * (w - 2);
    for (int i = 1;i <= sz;++i)
    if (s[i].x + 2 <= h && s[i].y + 2 <= w)
    {
        int cnt = 0;
        for (int a = s[i].x;a <= s[i].x + 2;++a)
            for (int b = s[i].y;b <= s[i].y + 2;++b)
                cnt += S.count({a,b});
        if (cnt) ++ans[cnt],--ans[0];
    }
    for (int i = 0;i <= 9;++i)
        fo << ans[i] << '\n';
    return 0;
}

Measured memory_bytes: 12032
def gcd(a, b):   # Greatest Common Divisor
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    
def lcm(a, b):   # Least Common Multiple
    return a*b // gcd(a, b)

n = int(input())
print(lcm(2, n))

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define w(x) scanf("%d",&x);while(x--)
#define ws(x) scanf("%d",&x);getchar();while(x--)
#define rep(i,b) for(i=0;i<=b;i++)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 2*acos(0.0)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const int N=1e6+2;
long long  mod=1e9+9;
int t,j,cs=0,n,a,b,i;
string s[55],ch;

int main()
{
    cin>>a>>b;
    cin.ignore();
    s[0]=(b,'0');
    for(i=1;i<=a;i++){
        cin>>ch;
        s[i]='0'+ch;
    }
    for(i=1;i<=a;i++){
        for(j=1;j<=b;j++){
            n=0;
            if(s[i][j]=='#'){
                continue;
            }
            if(s[i][j+1]=='#') n++;
            if(s[i][j-1]=='#') n++;
            if(s[i+1][j]=='#') n++;
            if(s[i-1][j]=='#') n++;
            if(s[i-1][j-1]=='#') n++;
            if(s[i-1][j+1]=='#') n++;
            if(s[i+1][j-1]=='#') n++;
            if(s[i+1][j+1]=='#') n++;
            s[i][j]=char(n+'0');
        }
    }
    for(i=1;i<=a;i++){
        for(j=1;j<=b;j++)
            cout<<s[i][j];
        cout<<endl;
    }
}



Measured memory_bytes: 3580
#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;

ull dp[100];

ull fib(int n) 
{
    if (n == 1 || n == 0) return 1;
    if (~dp[n]) return dp[n];
    return dp[n] = fib(n-1) + fib(n-2);
}

int main(void)
{
  int N;
  cin >> N;
  memset(dp, -1, sizeof(dp));
  cout << fib(N) << endl;
}

Measured memory_bytes: 3100
n = int(input())

t = list(map(int, input().split()))
a = list(map(int, input().split()))

MOD = 10 ** 9 + 7

if max(t) != max(a):
    print(0)
    exit()

if n == 1:
    print(1)
    exit()

ans = 1
for i in range(1, n - 1):
    if t[i] != t[i - 1]:
        if a[i] < t[i]:
            print(0)
            exit()
    elif a[i] != a[i + 1]:
        if t[i] < a[i]:
            print(0)
            exit()
    else:
        ans *= min(a[i], t[i])
        ans %= MOD

print(ans)



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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long int
#define mod 1000000007

void solve(int caseNo)
{
    int n;
    cin >> n;
    if(n < 2)   
    {
        cout << 0 << endl;
        return;
    }
    int ans = 1;
    for(int i=1;i<=n;i++)
    {
        ans *= 10;
        ans %= mod;
    }
    int a = 1;
    for(int i=1;i<=n;i++)
    {
        a *= 9;
        a %= mod;
    }
    ans -= a;
    ans += mod;
    ans %= mod;
    ans -= a;
    ans += mod;
    ans %= mod;
    a = 1;
    for(int i=1;i<=n;i++)
    {
        a *= 8;
        a %= mod;
    }
    ans += a;
    ans %= mod;
    cout << ans << endl;
    return;
}

int32_t main()
{
    IOS;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int cases;
    cases = 1;
    for(int i=1;i<=cases;i++)
    {
        solve(i);
    }
    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

int extended_gcd(int a, int b) {
    int r=b, old_r=a;
    int s=0, old_s=1;
    int t=1, old_t=0;
    int quotient, tmp;
        
    while (r) {
        quotient = old_r / r;
        tmp = r, r = old_r - quotient * r, old_r = tmp;
        tmp = s, s = old_s - quotient * s, old_s = tmp;
        tmp = t, t = old_t - quotient * t, old_t = tmp;
    }
    
    /* Bézout coefficients:      old_s, old_t */
    /* greatest common divisor:  old_r        */
    /* quotients by the gcd:     t, s         */
    
    printf("%d %d\n", old_s, old_t);
    return 0;
}

int main() {
    int a, b;
    scanf("%d %d ", &a, &b);
    extended_gcd(a,b);
    return 0;
}



Measured memory_bytes: 2092
N = int(input())
h = [int(x) for x in input().split()]

dp = [1000000 for _ in range(N)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
#     dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
#     dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))
    dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))
print(dp[-1])

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

int main(){
    int n;
    cin>>n;
    int count = 0;
    int ans = 0;
    for(int i=0;i<n;i++){
        int f,s;
        cin>>f>>s;
        if(f==s){
            count++;
        }else{
            ans = max(ans,count);
            count = 0;
        }
    }
    ans = max(count,ans);
    if(ans>=3) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
    

}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; 

int main(){
  int n;
  cin >> n;
  int p[n];
  int mn = inf;
  int ans = 0;
  for(int i=0; i<n; i++){
    cin >> p[i];
    mn = min(mn,p[i]);
    if(mn >= p[i]){
      ans++;
      //cout << i << endl;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
x1,y1,x2,y2 = map(int,input().split())

vec12 = (x2-x1, y2-y1)
vec23 = (y1-y2, x2-x1)
vec34 = (x1-x2, y1-y2)

x3,y3 = x2+vec23[0],y2+vec23[1]
x4,y4 = x3+vec34[0], y3+vec34[1]

print(x3, y3, x4, y4)

Measured memory_bytes: 9172
#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

int main(){
	int n; cin >> n; std::vector<int> a(3 * n);
	for(int i = 0; i < 3 * n; i++) cin >> a[i];
	
	std::vector<long> li;
	{
		long pos = 0;
		std::priority_queue<int, std::vector<int>, std::greater<int>> qu;
		for(int i = 0; i < 2 * n; i++){
			qu.push(a[i]); pos += a[i];
			
			if(i >= n - 1){
				if(qu.size() > n){
					pos -= qu.top();
					qu.pop();
				}
				
				li.push_back(pos);
			}
		}
	}
	
	reverse(begin(a), end(a));
	std::vector<long> li2;
	{
		long pos = 0;
		std::priority_queue<int> qu;
		for(int i = 0; i < 2 * n; i++){
			qu.push(a[i]); pos += a[i];
			
			if(i >= n - 1){
				if(qu.size() > n){
					pos -= qu.top();
					qu.pop();
				}
				
				li2.push_back(pos);
			}
		}
	}
	reverse(begin(li2), end(li2));
	
	long ma = -1e18;
	for(int i = 0; i < li.size(); i++) ma = std::max(ma, li[i] - li2[i]);
	cout << ma << endl;
	return 0;
}


Measured memory_bytes: 4460
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef vector<long long int> vint;
typedef vector<string> vstr;
typedef long long int llint;



int main(void) {
	llint jur = 0;
	string A, B;
	cin >> A >> B;
	llint sizA = A.length();
	llint sizB = B.length();

	if (sizA > sizB){
		cout << "GREATER" << endl;
		jur = 1;
	}
	else if (sizB > sizA){
		cout << "LESS" << endl;
		jur = 1;
	}
	else{
		for (int i=0 ; i < sizA; i++){
			if (A[i]>B[i]){
				cout << "GREATER" << endl;
				jur = 1;
				break;
			}
			else if(A[i]<B[i]){
				cout << "LESS" << endl;
				jur = 1;
				break;
			}
		}
	}
	if (jur == 0)cout << "EQUAL" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack> 
#include<queue>
#include<cmath>
#include<map>
#include<bitset>
#define LL long long
#define N 500100
#define M 1010
#define MOD 1000000007
#define FOR(i,l,r) for (int i = (l); i <= (r); i ++)
#define CLR(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
vector<pii> g[N];
LL dis[N];
int cnt;
int lg[N],f[N],p[N],d[N][25],rmq[N];
int rmq_init(int n){
	lg[0] = -1;
	FOR(i,1,n) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= n; i ++) d[i][0] = i;
	for (int j = 1; (1 << j) <= n; j ++)
	for (int i = 1; i + (1 << j) - 1 <= n; i ++)
		d[i][j] = rmq[d[i][j - 1]] < rmq[d[i + (1 << (j - 1))][j - 1]] ? d[i][j - 1] : d[i + (1 << (j - 1))][j - 1];
	return 0;
}
int query(int a,int b){
	if (a > b) swap(a,b);
	int k = lg[b - a + 1];
	return rmq[d[a][k]] <= rmq[d[b - (1 << k) + 1][k]] ? d[a][k] : d[b - (1 << k) + 1][k];
}
int query_lca(int u,int v){
	return f[query(p[u],p[v])];
}
int dfs(int u,int fa,int depth){
	//f[++ cnt] = u;
	//rmq[cnt] = depth;
	//p[u] = cnt;
	for (int i = 0; i < g[u].size(); i ++){
		int v = g[u][i].X,len = g[u][i].Y;
		if (v == fa) continue;
		dis[v] = dis[u] + (LL)len;
		dfs(v,u,depth + 1);
		//f[++ cnt] = u;
		//rmq[cnt] = depth;
	}
	return 0;
}
LL Distance(int x,int y){
	int lca = query_lca(x,y);
	return dis[x] + dis[y] - 2 * dis[lca];
}
int main(){
	int n;
	cin >> n;
	FOR(i,1,n - 1){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x].pb(pii(y,z));
		g[y].pb(pii(x,z));
	}
	int q,k;
	cin >> q >> k;
	cnt = 0;
	dis[k] = 0;
	dfs(k,-1,0);
	//rmq_init(cnt);
	while (q --){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",dis[x] + dis[y]);
	}
}

Measured memory_bytes: 29696
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
#define FOR(i,l,r) for (int i = (l); i < (r); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0)
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((int)(c).size())
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<int,int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const int INF = 1 << 30;
// const ll INF = 1LL << 62;
// --------------------------------------------------------


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    ll N; cin >> N;
    const ll D = 32;

    string ans = string(D + 1, '0');
    REP(i, D + 1) {
        ll l = 0, r = 0;
        REP(j, D - i) {
            if (j % 2 == 0) {
                r += pow(2, j);
            } else {
                l -= pow(2, j);
            }
        }
        ll b = pow(-2LL, D - i);
        if (l <= (N - b) && (N - b) <= r) {
            ans[i] = '1';
            N -= b;
            if (N == 0) break;
        }
    }
    int x = ans.find('1');
    if (x == -1) {
        ans = "0";
    } else {
        ans = ans.erase(0, x);
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 4072
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define DEC(i, a, b) for (int i = (a); i > (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin>>N;
  map<string,int> map;
  int ans = 0;
  string s;
  REP(i,N) {
    cin >> s;
    sort(ALL(s));
    ans += map[s];
    map[s] += 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11264
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#include <bits/stdc++.h>
using namespace std;


int main() {
	int K;
	string S;
    cin >> K;
	cin >> S;

	if(S.length() <= K){
		cout << S;
	}else{
		cout << S.substr(0, K) << "...";
	}
	
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if (max(a, b) > 8) cout << ":(";
    else cout << "Yay!";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

int n;

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

ll imos[100010];

vector<P> a;

vector<ll> step;
vector<ll> sz;
vector<ll> number;

signed main()
{
	cin >> n;

	for(int i = 1;i <= n;i++)
	{
		int t;
		cin >> t;
		a.push_back({t,i});
	}

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

	ll before = 0;
	step.push_back(0);
	sz.push_back(0);
	number.push_back(0);

	for(P& p : a)
	{
		if(p.first == before)
		{
			sz[sz.size() - 1]++;
		}
		else
		{
			step.push_back(p.second);
			number.push_back(p.first);
			sz.push_back(1);
			before = p.first;
		}
	}

	for(int i = step.size() - 1;i >= 1;i--)
	{
		//cout << number[i] << "->" << number[i - 1] << ":" << step.size() << endl;
		ll cou = number[i] - number[i - 1];
		imos[step[i]] += cou * sz[i];
		step[i - 1] = min(step[i - 1],step[i]);
		sz[i - 1] += sz[i];
	}

	for(int i = 1;i <= n;i++)
	{
		cout << imos[i] << endl;
	}
	return 0;
}



Measured memory_bytes: 7024
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
//           dx[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
int main() {
  long long n, a, b; cin >> n >> a >> b;
  if ((b - a) % 2 == 0) {
    cout << (b - a) / 2 << '\n';
  } else {
    long long A = a, B = b, tmp = A - 1;
    A = 1; B -= tmp;
    ++tmp;
    --B;
    tmp += (B - A) / 2;
    A = a; B = b;
    long long tmp2 = n - B;
    A += tmp2; B = n;
    ++tmp2;
    ++A;
    tmp2 += (B - A) / 2;
    cout << min(tmp, tmp2) << '\n';
  }
  return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<ll> s(n + 1);
    ll tmp = 0;
    s[0] = 0;
    rep(i, n){
        ll a;
        cin >> a;
        tmp += a;
        s[i + 1] = tmp;
    }
    sort(s.begin(), s.end());

    ll cnt = 0, ans = 0;
    rep(i, n){
        cnt += 1;
        if (s[i] != s[i + 1]){
            ans += cnt * (cnt - 1) / 2;
            cnt = 0;
        }
    }

    if (s[n - 1] == s[n]) ans += cnt * (cnt + 1) / 2;

    cout << ans << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    int n,k,s;cin >>n>>k>>s;
    int q=(s==2||s==1)?3:s-1;
    vector<int>a(n,q);
    for (int i = 0; i < k; ++i) {
        a[i]=s;
    }
    for (int i = 0; i < n; ++i) {
        cout <<a[i]<<endl;
    }
}


Measured memory_bytes: 3792
#include <cstdio>
using namespace std;
//http://tsutaj.hatenablog.com/entry/2018/03/09/225829
int max(int a, int b) { return a < b ? b : a; }
int board[2010][2010];
int main() {
    int N, K; scanf("%d%d", &N, &K);

    int sum = 0, white = 0;
    for(int i=0; i<N; i++) {
        int x, y; char c; scanf(" %d%d %c", &x, &y, &c);
        x %= 2*K, y %= 2*K;
        if(c == 'B') board[x+1][y+1]++, sum++;
        if(c == 'W') board[x+1][y+1]--, sum--, white++;
    }

    for(int i=1; i<=2*K; i++) {
        for(int j=1; j<=2*K; j++) {
            board[i][j] += board[i][j-1];
        }
    }

    for(int j=1; j<=2*K; j++) {
        for(int i=1; i<=2*K; i++) {
            board[i][j] += board[i-1][j];
        }
    }

    int ma = -(1 << 25);
    for(int i=0; i<=K; i++) {
        for(int j=0; j<=K; j++) {
            int a = board[i][j];
            int b = board[i+K][j+K] - board[i+K][j] - board[i][j+K] + board[i][j];
            int c = board[2*K][j] - board[i+K][j];
            int d = board[i][2*K] - board[i][j+K];
            int e = board[2*K][2*K] - board[2*K][j+K] - board[i+K][2*K] + board[i+K][j+K];
            int tmp = a + b + c + d + e;
            ma = max(ma, max(tmp, sum - tmp));
        }
    }
    ma += white;
    printf("%d\n", ma);
    return 0;
}

Measured memory_bytes: 15872
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<queue>
#include<vector>
#include<list>
#include<stack>
using namespace std;
typedef long long ll;

ll a[100010],b[100010];

int main()
{
	ll n,i,j;
	cin >> n;
	for (i = 0; i < n + 1; i ++)
		scanf ("%d",&a[i]);
	for (i = 0; i < n; i ++)
		scanf ("%d",&b[i]);
	ll ans = 0;
	for (i = 0; i < n; i ++)
	{
		if (b[i] <= a[i])
		{
			ans += b[i];
//			a[i] -= b[i];
		}
		else
		{
			ans += a[i];
			ll tem = min(b[i] - a[i],a[i + 1]);
			ans += tem;
			a[i + 1] -= tem;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long int
#define phi 1.6180339
#define rep(i,n) for(auto i=0;i<(n);i++)
#define endl "\n"
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define op1 cin.tie(NULL)
#define op2 cout.tie(NULL)
#define op3 std::ios_base::sync_with_stdio(false)
#define MAXX 1000001
using namespace std;
vector<int> arr(MAXX);
void trozen()
{
    int k;
    cin>>k;
    vector<int> ans;
    queue<int> Q;
    for(int i=1;i<=9;i++) ans.push_back(i),Q.push(i);
    if(k<=ans.size()){cout<<ans[k-1]<<endl;return;}
    while(true)
    {
        if(k<=ans.size()){cout<<ans[k-1]<<endl;return;}
        int ele=Q.front();
        Q.pop();
        for(int i=-1;i<=1;i++)
        {
            int ele1=ele%10;
            if((ele1+i)<0||(ele1+i)>9) continue;
            int add=(ele*10)+(ele1+i);
            ans.push_back(add);
            Q.push(add);
        }
    }
}
int32_t main()
{
    op1;op2;op3;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    trozen();
    return 0;
}


Measured memory_bytes: 12380
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (int i=0;i<N;i++)
#define loop(i,N,M) for(int i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

//変数
ll N, M;
vector<ll> x,y,z;
//解法
void solve() {

	ll ans = 0, sum;
	int xx = 1, yy = 1, zz = 1;

	while (1) {
		sum = 0;
		vector<ll> vec(N);
		rep(i, N) vec[i] = xx*x[i] + yy*y[i] + zz*z[i];
		SORTL2S(ll, vec);
		rep(i, M) sum += vec[i];
		ans = max(ans, sum);
		if (zz == -1 && yy == -1 && xx == -1) break;
		if (zz == -1 && yy == -1) xx *= -1;
		if (zz == -1) yy *= -1;
		zz *= -1;
	}

	cout << ans;

	return;
}

int main() {
	//入力

	cin >> N >> M;
	x.resize(N);
	y.resize(N);
	z.resize(N);

	rep(i, N) cin >> x[i] >> y[i] >> z[i];

	solve();
	cout << endl;
	return 0;
}

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

 
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
 int t=1;
    // cin>>t;
  while(t--){
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++){
      cin>>a[i];
  }
  sort(a,a+n);
  int sum =0;
  for(int i=0;i<k;i++){
      sum+=a[i];
  }
  cout<<sum;
  }
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 1000000009
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

vector<ll> dp(100000, 0);
//dp.at(i)は足場i+1にたどり着く最小コスト

int main(){
  ll N;
  cin >> N;
  vector<ll> h(N);
  rep(i, N){
    cin >> h.at(i);
  }
  dp.at(1) = abs(h.at(1) - h.at(0));
  rep(i, N-2){
    dp.at(i+2) = min(dp.at(i+1)+abs(h.at(i+2)-h.at(i+1)), dp.at(i)+abs(h.at(i+2)-h.at(i)));
  }
  cout << dp.at(N-1) << endl;
}

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

int main() {
    string s,t; cin >> s >> t;
    vector<string> ans;
    if(s.size()<t.size()) {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    for(int i = 0; i <= s.size()-t.size(); i ++) {
        string tmp = s;
        for(int j = 0; j < t.length(); j ++) {
            if(i+j>s.size()-1) break;
            if(tmp[i+j]=='?' || tmp[i+j]==t[j]) tmp[i+j] = t[j];
            else break;
            if(j==t.length()-1) {
                for(int k = 0; k < tmp.length(); k ++) {
                    if(tmp[k]=='?') tmp[k] = 'a';
                }
                ans.push_back(tmp);
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << (ans.size() > 0 ? ans[0] : "UNRESTORABLE") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

int main() {
	int i, j, k;
	int a, b;

	cin >> a >> b;

	string str = to_string(a) + to_string(b);

	int n = stoi(str);

	for (i = 0; i*i <= n; i++) {
		if (i*i == n) {
			cout << "Yes" << endl;
			getchar();
			getchar();
			return 0;
		}
	}

	cout << "No" << endl;

	getchar();
	getchar();
	return 0;
}

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


main(){
  int x ;
  cin >> x ;
  int ans = 0 ;
  int money = x ;
  int count ;
  count = money / 500 ;
  ans += count * 1000 ;
  money -= 500 * count ;
  count = money / 5 ;
  ans += count * 5 ;
  cout << ans ;
  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>;

const ll INF = 1000000000000000;

int main(){
	ll n;
	cin >> n;
	int time = sqrt(n);
	ll mx = INF;
	ll wa = 0;
	for(int i = 1; i <= time; i++){
		wa = 0;
		if(n%i != 0) continue;
		else{
			wa = i + n/i;
			mx = min(wa,mx);
		}
	}
	cout << mx -2 << endl;
}

Measured memory_bytes: 3652
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
bef = -1
for n in A:
    ans += B[n-1]
    if n-1==bef:
        ans += C[bef-1]
    bef = n

print(ans)


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

int main(){
  std::string s1;
  std::string s2 = "abcdefghijklmnopqrstuvwxyz";
  std::cin >> s1;
  int point = s2.find(s1) + 1;
  cout << s2[point];
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#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 f           first
#define se          second
#define maxn        201005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}  
void solve(){
    int x,y;
    cin >> x >> y;
    if(y%2 == 0 && y/2-x >= 0 && 2*x-y/2 >= 0)cout << "Yes\n";
    else cout << "No\n";
}

signed main()
{
    showoff;
    int T = 1;
    //cin >> T;
    FOR(t,1,T+1){   
        solve();
        cout << "\n";
    }
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...
 

Measured memory_bytes: 3612
import Data.List
import Data.Bool

main = print . solve . map read . words =<< getContents

solve :: [Int] -> Int
solve (n:hs) = r
    where (r, _) = foldl' (\(c, mh) h -> bool (c, mh) (c+1, h) (mh <= h)) (0, 0) hs


Measured memory_bytes: 508
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll A,B,N; cin >> A >> B >> N;
    if (N >= B-1) {
        ll ans = A*(B-1)/B;
        cout << ans << ln;
        return 0;
    }
    ll ans = A*N/B;
    cout << ans << ln;
    return 0;
}

Measured memory_bytes: 3640
#include<iostream>
using namespace std;
typedef long long ll;

int main(){
  ll a;
  while(cin >> a, a){
    ll ans = 0, k=1;
    while(a){
      int b = 10*(a%10<0);
      ans += (b+a%10) * k;
      (a -= b) /= -10; k *= 10;
    }
    cout << ans << endl;
  }    
}

Measured memory_bytes: 1160
import collections

n = int(input())
a = list(map(int, input().split()))

#累積和の計算
s = [0]
for i in range(n):
    s.append(s[i]+a[i])

#条件を満足する部分列をカウント
#累積和のうち，同じものから2つ選ぶ
c = list(collections.Counter(s).items())
ans = 0
for i, j in c:
    if j >= 2:
        ans += j*(j-1)//2

#出力
print(ans)



Measured memory_bytes: 147632
#include<stdio.h>
#define M 1000010
int zMIN(int a,int b){
  if(a==0||a>b)return b;
  return a;
}
int d1[M],d2[M];
int main(){
  int n=200,t[200],i,j;
  for(i=1;i<200;i++)t[i]=i*(i+1)*(i+2)/6;
  for(i=0;i<M;i++){
    for(j=1;j<200;j++){
      if(i+t[j]>=M)continue;
                d1[i+t[j]]=zMIN(d1[i+t[j]],d1[i]+1);
      if(t[j]%2)d2[i+t[j]]=zMIN(d2[i+t[j]],d2[i]+1);
    }
  }
  while(scanf("%d",&n),n)printf("%d %d\n",d1[n],d2[n]);
  return 0;
}

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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(false); cin.tie(0);
	cin.exceptions(cin.failbit);
	
	ll a, b; cin >> a >> b;
	
	if (a <= 0 && 0 <= b) {
		cout << "Zero" << endl;
		return 0;
	}

	ll cntneg = 0;
	if (a < 0) {
	if (b < 0)
		cntneg = b - a + 1;
	else
		cntneg = 0 - a;
	}

	if (cntneg % 2 == 0) {
		cout << "Positive" << endl;
	} else {
		cout << "Negative" << endl;
	}
}


Measured memory_bytes: 256
import java.math.*;
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        int l = sc.nextInt();
        int r = sc.nextInt();
        int d = sc.nextInt();

        int cnt = 0;

        for (int i=l; i<=r; i++) {
            if (i % d == 0) cnt++;
        }

        System.out.print(cnt);

    }


}



Measured memory_bytes: 35672
#include<iostream>
#include<cstdio>

#include<vector>
#include<string>

#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;
const int INF = 1e9+1;
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 N, K;


//最後には全部1になるんだから最初から1を拡大させていくのが良い
//

int main() {
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    
    int res = (N-1+K-2)/(K-1);

    cout << res << endl; 
}


Measured memory_bytes: 640