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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) (1 + (int)((a) - 1)/(int)(b))
//#define int long long

signed main(){
    int a, b, k;
    cin >> a >> b >> k;
    set<int> ans;
    reps(i, a, a+k-1) ans.insert(i);
    reps(i, b-k+1, b) ans.insert(i);
    for(int i : ans){
        if(i < a || b < i) continue;
        cout << i << endl;
    }
}

Measured memory_bytes: 256
/*
  ->->->->->-> Vora Mahammadasim <-<-<-<-<-<-
*/
#include<bits/stdc++.h>
#include<stdio.h>
#define int long long
#define pb emplace_back
#define Mod 1000000007
#define all(a) a.begin(),a.end()
using namespace std;
signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int ans = 0;
    int n = s.size();
    int ref = 0,x= 1;
    int p = 0;
    int t[2020] = {0};
    t[0] = 1;
    for(int i=n-1;i>=0;i--){
        ref = ( ref + (s[i] - '0') * x )%2019;
        x = x*10 % 2019;
        ans += t[ref];
        t[ref]++;
    }
    cout<<ans;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reve(a) reverse(a.begin(), a.end())
#define PI 3.14159265359
typedef long long ll;
const ll MOD = 1e9+7;

ll gcd(ll a, ll b){
  if(b==0) return a;
  return gcd(b, a%b);
}
/*ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}*/

ll lcm(ll a, ll b){
  ll g = gcd(a, b);
  b /= g;
  a *= b;
  return a;
}

//素数判定 O(√n)
bool is_prime(int64_t n){
  for(int64_t i = 2; i*i<=n; i++){
    if(n%i==0) return false;
  }
  return n!=1;
}

//約数の列挙 O(√n)
vector<int64_t> dividor(int64_t n){
  vector<int64_t> res;
  for(int64_t i=1; i*i<=n; i++){
    if(n%i==0){
      res.push_back(i);
      if(i != n/i) res.push_back(i);
    }
  }
  return res;
}

//素因数分解 O(√n)
map<int64_t, int64_t> prime_factor(int64_t n){
  map<int64_t, int64_t> res;
  for(int64_t i=2; i*i<=n; i++){
    while(n%i==0){
      res[i]++;
      n /= i;
    }
  }
  if(n != 1) res[n] = 1;
  return res;
}
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

  


int main(){ 
  int64_t x; cin >> x;
  map<int64_t, int64_t> A;
  map<int64_t, int64_t> B;
  for(int64_t i=0; i<=8000; i++){
    int64_t w = i;  
    rep(j, 4) {w *= i;}
    //cout << w << endl;
    A[i]=w;
    A[-i]=-w;
    //cout << A[2*i] << endl;
    //cout << A[2*i+1] << endl;
    B[w]=i;
    B[-w]=-i; 
  }
  int64_t g;
  for(int64_t i=-8000; i<=8000; i++){
    g =  A[i]+x;
    //cout << A[i] << endl;
    //cout << g << endl;
    if(B.count(g)){
      //cout << 1 << endl;
      cout << B[g] << " " << i << endl;
      break;
    }
  }
  /*for(auto p: B){
    cout << p << endl;
  }*/
}

Measured memory_bytes: 5560
n = int(input())
s = input()
ans = 0
for i in range(1, n):
    f1 = s[:i]
    f2 = s[i:]
    f1 = list(set(f1))
    cnt = 0

    for j in range(len(f1)):
        if f1[j] in f2:
            cnt += 1
    ans = max(ans, cnt)
print(ans)


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
  int top=0,s[100];
  char str[100];

  while((scanf("%s",str))!=EOF){
  	if(str[0]=='+'){
  		s[top-2]=s[top-2]+s[top-1];
  		top--;
  	}
  	else if(str[0]=='-'){
  		s[top-2]=s[top-2]-s[top-1];
  		top--;
  	}
  	else if(str[0]=='*'){
  		s[top-2]=s[top-2]*s[top-1];
  		top--;
  	}
  	else{
  		s[top]=atoi(str);
  		top++;
  	}
  }

	printf("%d\n",s[top-1]);
	
  return 0;
}




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

int main(){
	int N; int sum=0; int T=0;
	int w[1000];
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> w[i];
		sum+=w[i];
	}
	int min=sum;
	int rec=sum;
	int sum_1=0; 
	while(T<N-1){
		sum_1=0;
		for(int i=0;i<=T;i++){
			sum_1+=w[i];
		}
		if(min>abs(sum_1-(sum-sum_1))){
			min = abs(sum_1-(sum-sum_1));
		}
		T++;
	}
	cout << min;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// typedef
using ll  = long long;
using str = string;
using PL  = pair<ll, ll>;
using P   = pair<int, int>;
using VL  = vector<ll>;
using VI  = vector<int>;
using VS  = vector<str>;
using VP  = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using VVI = vector<VI>;

// const num
const ll INF         = 1e18 + 18;
const ll MAX         = 100005;
const ll MOD         = 1000000007;
const long double PI = acosl(-1.0);

// loop
#define REP(i, a, b) for(ll(i) = (a); (i) < (b); (i)++)
#define RREP(i, a, b) for(ll(i) = (a); (i) >= (b); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)

// YesNo
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
// All
#define ALL(v) v.begin(), v.end()
#define deduplicate(v) (v).erase(unique(ALL(d)), (v).end())

str judge[4] = {"AC", "WA", "TLE", "RE"};
int main(void) {
	int n;
	int ans[4] = {0, 0, 0, 0};
	str s[100010];
	cin >> n;
	rep(i, n) {
		cin >> s[i];
		rep(j, 4) {
			if(s[i] == judge[j]) {
				ans[j]++;
				continue;
			}
		}
	}
	rep(i, 4) { cout << judge[i] << ' ' << 'x' << ' ' << ans[i] << endl; }

	return 0;
}

Measured memory_bytes: 6720
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;

	void run() {
		Scanner sc = new Scanner(System.in);
		for (;;) {
			int n = sc.nextInt();
			if ( n == 0) break;
			int[][] map = new int[10][10];
			for (int[] a: map) fill(a, INF);
			for (int i=0;i<10;i++) map[i][i] = 0;
			int max = 0;
			for (int i=0;i<n;i++) {
				int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
				map[a][b] = map[b][a] = min(map[a][b], c);
				max = max(max, max(a, b));
			}
			max++;
			for (int k=0;k<max;k++) for (int i=0;i<max;i++) for(int j=0;j<max;j++) 
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			
			int p = 0, c = INF;
			for (int i=0;i<max;i++) {
				int sum = 0;
				for (int j=0;j<max;j++) sum += map[i][j];
				if (c > sum) {
					p = i;
					c = sum;
				}
			}
			System.out.println(p + " " + c);
			
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

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

Measured memory_bytes: 19624
# 9_C
n = int(input())
score_t, score_h = 0, 0
for i in range(n):
    t, h = input().split()
    if t > h:
        score_t += 3
    elif h > t:
        score_h += 3
    else:
        score_t += 1
        score_h += 1
print(f"{score_t} {score_h}")


Measured memory_bytes: 5612
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top = 0, S[1000];

void push(int x) {
	S[++top] = x;
}

int pop() {
	top--;
	return S[top+1];
}

int main(void) {
	int a,b;
	char s[100];

	while(scanf("%s",s) != EOF) {
		if(s[0] == '+') {
			a = pop();
			b = pop();
			push(a + b);
		} else if(s[0] == '-') {
			b = pop();
			a = pop();
			push(a - b);
		} else if(s[0] == '*') {
			b = pop();
			a = pop();
			push(a * b);
		} else {
			push(atoi(s));
		}
	}
	
	printf("%d\n",pop());
	
	return 0;
}

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

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        return;

    }

    public static string Solve()
    {
        int N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        int[] A = new int[N];
        for(int i = 0;i<N;i++)
        {
            A[i] = int.Parse(str[i]);
        }
        str = Console.ReadLine().Split(' ');
        int[] B = new int[N];
        for (int i = 0; i < N; i++)
        {
            B[i] = int.Parse(str[i]);
        }

        int[] D = new int[N];
        for (int i = 0; i < N; i++)
        {
            D[i] = A[i] - B[i];
        }
        Array.Sort(D);
        Array.Reverse(D);
        //Console.WriteLine("[{0}]", string.Join(", ", D));
        int cnt = 0;
        int tail = N - 1;
        for(int i = 0;i < N;i++)
        {
            if (D[i] < 0) return "-1";
            int lest = D[i];
            if(D[tail] < 0)
            cnt++;
            while(lest > 0)
            {
                if (D[tail] < 0)
                {
                    if (lest + D[tail] >= 0)
                    {
                        lest += D[tail];
                        D[tail] = 0;
                        tail--;
                        cnt++;
                    }
                    else
                    {
                        D[tail] += lest;
                        break;
                    }
                }
                else return cnt.ToString();
            }
        }

        return cnt.ToString();
    }
}


Measured memory_bytes: 35932
#include<bits/stdc++.h>
using namespace std;
int n,m,x,c[20],a[20][20],b[20],ans=1e9;
void dfs(int deep,int num){
	bool f=0;
	if (num>ans) return ;
	for (int i=0;i<m;i++) if (b[i]<x) f=1;
	if (f==0){
		ans=min(ans,num);
		return ;
	}
	for (int i=deep+1;i<n;i++){
		for (int j=0;j<m;j++) b[j]+=a[i][j];
		if (f==0){
			ans=min(ans,num);
			return ;
		}
		dfs(i,num+c[i]);
		for (int j=0;j<m;j++) b[j]-=a[i][j];
	}
}
int main(){
	cin>>n>>m>>x;
	for (int i=0;i<n;i++){
		cin>>c[i];
		for (int j=0;j<m;j++) cin>>a[i][j];
	}
	dfs(-1,0);
	if (ans==1e9)
		cout<<-1<<endl;
	else
		cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1000000007;
int a[200005];
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int res = 1;
    if (a[n] < 0)
    {
        if (k & 1)
            for (int i = n - k + 1; i <= n; i++)
                res = 1LL * res * a[i] % Mod;
        else
            for (int i = 1; i <= k; i++)
                res = 1LL * res * a[i] % Mod;
    }
    else
    {
        int l = 1, r = n;
        if (k & 1)
            res = 1LL * res * a[r] % Mod, r--, k--;
        while (k)
        {
            if (1LL * a[l] * a[l + 1] > 1LL * a[r] * a[r - 1])
                res = 1LL * res * a[l] % Mod * a[l + 1] % Mod, l += 2;
            else
                res = 1LL * res * a[r] % Mod * a[r - 1] % Mod, r -= 2;
            k -= 2;
        }
    }
    res = (res + Mod) % Mod;
    return 0 * printf("%d\n", res);
}


Measured memory_bytes: 4576
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int k, a, b;
  scanf("%d%d%d", &k, &a, &b);
  if (a % k == 0 || b % k == 0 || fabs(floor(a / k) - floor(b / k)) >= 1)
    puts("OK");
  else
    puts("NG");
}

Measured memory_bytes: 1636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int max;
    cin >> max;
    long long count = 0;
    for (int i = 1; i < n; i++){
        int a;
        cin >> a;
        max = max > a ? max : a;
        if (a < max){
            count += (max - a);
        }
    }

    cout << count << endl;

    return 0;

}

Measured memory_bytes: 3592
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 1000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
llint gcd(llint a, llint b) {
	if (b > a)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
llint Tow(int m,int n) {//2のn乗
	if (n == 0)return 1;
	llint x = Tow(m,n / 2);
	x *= x;
	if (n % 2 == 1)x *= m;
	return x;
}
ll max(ll a, ll b) {
	if (a < b)return b;
	else return a;
}

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = 0;; i++) {
		if (a <= 0) {
			cout << "No" << endl;
			break;
		}
		if(c<=0) {
			cout << "Yes" << endl;
			break;
		}
		if (i % 2 == 0)c -= b;
		else a -= d;
	}
	return 0;
}

Measured memory_bytes: 3632
n = [0 for i in range(10001)]
for z in range(1, 100, 1):
    for y in range(1, 100, 1):
        for x in range(1, 100, 1):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp > 10 ** 4:
                break
            else:
                n[tmp] += 1
N = int(input())
for i in range(1, N+1, 1):
    print(n[i])

Measured memory_bytes: 9292
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    prev=1
    cnt=0
    for i in range(k,n):
        if i==0: continue
        prev=a[cnt]
        crnt=a[i]
        if crnt > prev: print('Yes')
        else: print('No')
        prev=crnt
        cnt+=1
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 31444
#include <iostream>

using namespace std;

#define OUT(s) cout << s << endl;
#define IN(a) cin >> a;

int main() {
  int P, Q, R;
  cin >> P >> Q >> R;
  if (P < Q) {
    if (Q < R) {
      OUT(P + Q);
    } else {
      OUT(P + R);
    }
  } else {
    if (P < R) {
      OUT(P + Q);
    } else {
      OUT(Q + R);
    }
  }
}

Measured memory_bytes: 256
n = gets.to_i
g = Array.new(n){[]}

edges = Array.new(n-1) # へんの色を格納

(n-1).times do |i|
  a, b = gets.split.map(&:to_i)
  a -= 1
  b -= 1
  g[a] << [b, i]
  g[b] << [a, i]
end

q = []
root = 0
color_num = 0 
g[root].each do |child, i|
  color_num += 1
  q << [child, root, color_num]
  edges[i] = color_num
end

until q.empty?
  now, parent, c = q.shift
  ccnt = 0
  g[now].each do |child, i|
    next if child == parent
    ccnt += 1
    if ccnt == c
      ccnt += 1
    end
    q << [child, now, ccnt]
    edges[i] = ccnt
  end
end

p edges.max
puts edges

Measured memory_bytes: 28156
Q, H, S, D = map(int, input().split())
N = int(input())

cands = [(0, Q*8), (1, H*4), (2, S*2), (3, D)]
cands = sorted(cands, key=lambda x: (x[1], x[0]))
if cands[0][0] == 3:
    if N % 2 == 1:
        dcost = N // 2 * D
        if cands[1][0] == 2:
            print(dcost + S)
        elif cands[1][0] == 1:
            print(dcost + 2 * H)
        else:
            print(dcost + 4 * Q)
    else:
        print(N // 2 * D)
elif cands[0][0] == 2:
    print(N * S)
elif cands[0][0] == 1:
    print(N * 2 * H)
elif cands[0][0] == 0:
    print(N * 4 * Q)

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private void solve() {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		List<List<Integer>> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		for (int i = 0; i < M; i++) {
			int A = in.nextInt() -1;
			int B = in.nextInt() -1;
			list.get(A).add(B);
			list.get(B).add(A);
		}
		
		//二部グラフ判定
		boolean bip = true;
		
		int[] color = new int[N];
		LinkedList<Integer> stack = new LinkedList<>();
		color[0] = 1;
		stack.push(0);
		
		while(!stack.isEmpty()) {
			int node = stack.pop();
			int size = list.get(node).size();
			for (int i = 0; i < size; i++) {
				int next = list.get(node).get(i);
				if(color[next] == 0){
					color[next] = (-1)*color[node];
					stack.push(next);
				}else{
					if(color[next] == color[node]){
						bip = false;
					}
				}
			}
		}
		
		if(bip){
			int plus = 0;
			int minus = 0;
			for (int i = 0; i < N; i++) {
				if(color[i] == 1) plus ++;
				else minus ++;
			}
			System.out.println(1L*plus*minus-M);
		}else{
			System.out.println(1L*N*(N-1)/2-M);
		}
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}

Measured memory_bytes: 103208
from itertools import product
from operator import mul

N, M = map(int, input().split())
cakes = [list(map(int, input().split())) for i in range(N)]

ans = 0
for sxyz in product([-1, 1], repeat=3):
    vs = []
    for cake in cakes:
        vs += [sum(map(mul, sxyz, cake))]

    vs.sort()
    ans = max(ans, sum(vs[N - M:]))

print(ans)


Measured memory_bytes: 3828
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
ll mod = 1e9+7;

int main(){

	ld a,b,c;
	cin>>a>>b>>c;

if(a+ b+ 2*sqrtl(a*b) < c)
		cout<<"Yes\n";
	else
		cout<<"No\n";
 	return 0;
}

Measured memory_bytes: 256
/*
	*	Created By: 'Present_Sir'
	*	Created On: Sunday 13 September 2020 05:56:14 PM IST
*/

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define lgt(s) ((int)s.length())
#define int long long
using namespace std;

const int Mod = 1e9+7;

template <int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod) x -= mod;
    }
    ModInt& operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0) x += mod;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
 
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
 
    friend ostream& operator<<(ostream& s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream& operator>>(istream& s, ModInt<mod>& a) {
        s >> a.x;
        return s;
    }
};
 
using mint = ModInt<Mod>;
class Solver{
    public:
        void test(){
            //int t; cin>>t; for(int i=1; i<=t; ++i)
            {
                //cout<<"Case #"<<i<<": ";
                this->solve();
            }
        }
        void solve(){
            int n;
            cin >> n;
            if(n == 1){
                cout<<0<<endl;
                return;
            }
            mint ans = 1; 
            for(int i=0; i<n; ++i){
                ans *= 8;
            }
            mint a=1;
            for(int i=0; i<n; ++i){
                a*=9;
            }
            mint k = 1;
            for(int i=0; i<n; ++i){
                k*=10;
            }
            //cout<<k<<" "<<ans<<endl;
            cout<<(k-a*2+ans)<<endl;
        }
};


int32_t main(){
    IOS;
    Solver S;
    S.test();
    return 0;
}



Measured memory_bytes: 3520
import collections


class Solution:
    def solve(self, N: int, S):

        counter = collections.Counter(S)

        most_common = counter.most_common()

        num = most_common[0][1]

        answer = []

        for s in most_common:
            if s[1] == num:
                answer.append(s[0])
            else:
                break

        return sorted(answer)


if __name__ == '__main__':

    # standard input
    N = int(input())

    S = []
    for n in range(N):
        S.append(input())

    # solve
    solution = Solution()
    ans = solution.solve(N, S)
    for s in ans:
        print(s)


Measured memory_bytes: 47452
from collections import Counter
n=int(input())
D={}
SC=Counter(input())
for k,v in SC.items():
    D[k]=v
for i in range(n-1):
    temp={}
    C=Counter(input())
    for k in D.keys():
        if k in C:
            temp[k]=min(D[k],C[k])
    D=temp
L=[]
for k,v in D.items():
    for i in range(v):
        L.append(k)
print(''.join(sorted(L)))

Measured memory_bytes: 3316
N = int(input())
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
    s = input()
    s = sorted(s)
    s = "".join(s)
    d[s] += 1

ans = 0
for s in d.keys():
    n = d[s]
    ans += n*(n-1)//2

print(ans)

Measured memory_bytes: 62168
import java.util.Arrays;
import java.util.Scanner;

class Main{

	static char[][] map;
	static int H;
	static int W;

	public static void main(String[] args) {



		Scanner sc = new Scanner(System.in);			//文字の入力
		int N =sc.nextInt();
		long[] a = new long[N];
		
		for(int i = 0;i < N;i++){
			a[i] = sc.nextInt()-(i+1);
		}
		
		long[] c = a.clone();
		Arrays.sort(c);
		long mid = c[N/2];
		

		
		long ans =0 ;
		for(int i = 0;i < N;i++){
			ans += Math.abs(a[i]-mid);
		}
		System.out.println(ans);

	}
}





Measured memory_bytes: 85888
/*
 * ITP1_11_D: Rolling the dice IV (compare many dices)
 */

#include <stdio.h>

int is_same_dice(int dice[], int dice2[]);

// rolling relations by index (N, S, E, W, clockwise, anti-clockwise)
int T[6][1 + 6] = {{0, 2, 6, 3, 4, 1, 5},
    {0, 5, 1, 3, 4, 6, 2},
    {0, 4, 2, 1, 6, 5, 3},
    {0, 3, 2, 6, 1, 5, 4},
    {0, 1, 3, 5, 2, 4, 6},
    {0, 1, 4, 2, 5, 3, 6}};
int move['Z'];

void rotate(int direction, int p[])
{
    int q[1 + 6];
    int i;

    for (i = 1; i <= 6; i++)
        q[i] = p[T[move[direction]][i]];

    for (i = 1; i <= 6; i++)
        p[i] = q[i];

    return;
}

int main(void)
{
    int dice[100][1 + 6]; // one-based indexing
    int ndice; // number of dices
    int i, j, n;

    move['N'] = 0;
    move['S'] = 1;
    move['E'] = 2;
    move['W'] = 3;
    move['C'] = 4; // Clockwise
    move['A'] = 5; // Anti-clockwise

    scanf("%d", &ndice);
    for (n = 0; n < ndice; n++) {
        for (i = 1; i <= 6; i++)
            scanf("%d", &dice[n][i]);
        for (j = 0; j < n; j++) {
            if (is_same_dice(dice[n], dice[j])) {
                printf("No\n");
                return 0;
            } 
        }
    }
    printf("Yes\n");

    return 0;
}

int is_same_dice(int dice[], int dice2[])
{
    int top = dice2[1];
    int front = dice2[2];

    // align the top face.
    if      (top == dice[2])
        rotate('N', dice);
    else if (top == dice[3])
        rotate('W', dice);
    else if (top == dice[4])
        rotate('E', dice);
    else if (top == dice[5])
        rotate('S', dice);
    else if (top == dice[6]) {
        rotate('N', dice);
        rotate('N', dice);
    } else
        return 0;

    // align the front face.
    int count = 0;
    while (dice[2] != front && count <= 3) {
        count++;
        rotate('C', dice);
    }
    // cannot adjust the front face even by one rotation.
    if (count == 4) {
        return 0;
    }

    // compare the remain faces.
    if (dice[3] == dice2[3] && dice[4] == dice2[4] &&
            dice[5] == dice2[5] && dice[6] == dice2[6])
        return 1;
    else
        return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;



int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	string s;
	cin >> s;
	if (s == "ARC") {
		cout << "ABC";
	}	else {
		cout << "ARC";
	}
}


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

void trace(vector<int> &a,int N){
  for(int i=0;i<N;i++){
    if(i){
      cout<<" ";
    }
    cout<<a[i];
  }
  cout<<endl;
  
}

int selectionsort(vector<int> &v,int N){
  int cnt=0;
  for(int i=0;i<N;i++){
    int minj=i;
    for(int j=i;j<N;j++){
      if(v[j]<v[minj]){
        minj=j;
      }
    }
    if(i !=minj){
      swap(v[i],v[minj]);
      cnt++;
    }
  }
  return cnt;
}
int main() {
  int N;
  cin>>N;
  for(int i=1;i<10;i++){
    int d;
    d=111*i-N;
    if(d>=0){
      cout<<111*i<<endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
typedef pair<int,int> pii;
#define mp make_pair
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
int n,k,s;
int main()
{
	n=gi();k=gi();s=gi();
	for(int i=1;i<=n;i++)if(k)printf("%d ",s),k--;else if(s==1e9)printf("1 ");else printf("%d ",s+1);
	puts("");
	return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mof = 1000000007;
ll dp[111][8];
int h,w,k;
bool ok(int s)
{
    
    for(int i=1;i<w-1;++i)
    {
        if(((s>>i)&1) && ((s>>(i-1))&1))
            return 0;
    }
    return 1;
}
int main()
{
    cin>>h>>w>>k;
    int nxt;
    dp[0][0] = 1;
    for(int i=1;i<=h;++i)
    {
        for(int pre = 0; pre < w ;pre++)
        {
            for(int x = 0;x < 1<<(w-1) ;++x)
            {
                if(ok(x))
                {
                    //cout<<"i= ";
                    //cout<<i<<endl;
                    //cout<<"pre = ";
                    //cout<<pre<<endl;
                    //cout<<"x = ";
                    //cout<<x<<endl;
                    
                    bitset<8> bs(x);
                    if(bs.test(pre))
                        nxt = pre + 1;
                    else if(pre > 0 && bs.test(pre-1))
                        nxt = pre - 1;
                    else
                        nxt = pre;
                    //cout<<nxt <<endl;
                    dp[i][nxt] += dp[i-1][pre];
                    dp[i][nxt] %= mof;
                }
            }
        }
        
    }
    cout<<dp[h][k-1]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<std::pair<i64, i64>> vec;
	for(int i = 0; i < n; i++) {
		int a, b; scanf("%d%d", &a, &b);
		
		vec.push_back({a, b});
	}
	sort(begin(vec), end(vec));
	
	i64 ans = 0;
	for(auto v: vec) {
		if(v.second > m) {
			ans += v.first * m;
			break;
		} else {
			ans += v.first * v.second;
			m -= v.second;
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main(void){
    int n;
    cin >> n;
    int c[510];
    int s[510];
    int f[510];
    int ans=0;
    for(int i=1;i<n;i++){
        cin >>c[i] >>s[i] >>f[i];
    }
    c[0]=0;
    s[0]=1;
    f[0]=1;
    c[n]=0;
    f[n]=1;
    s[n]=0;
    for(int i=1;i<=n;i++){
        ans=0;
        for(int j=i;j<=n;j++){    

            if(j==i){
                ans=s[j];
                //cout <<"start;"<<s[j]<<endl;
            }else{
                if(j-1!=i){
                    if(ans%f[j-1]){
                    ans=ans-ans%f[j-1]+f[j-1];
                    }
                    //cout<<"dep;"<<ans<<endl;
                }
                ans=max(s[j],ans+c[j-1]);
                //cout<<"arr;"<<ans<<endl;

            }

        }
        cout << ans <<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
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; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;


int main() {
    ll N,M;
    cin >> N >> M;
    ll sum = 0;
    for (ll i = 0;i<M;i++) {
        ll a;
        cin >> a;
        sum += a;
    }
    if (N - sum >= 0) cout << N - sum << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 3632
word = gets.chomp.downcase
words = Array.new
while true do
  begin
    buf_word = gets.chomp.gsub(/[^A-Za-z\s]/,'').downcase.split
  rescue
    words.pop
    break
  end
  #break if buf_word[0] == 'end_of_text'
  words.concat(buf_word);
end

puts words.count word

Measured memory_bytes: 6104
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

signed main() {
    int a[3][3];
    int n;
    vector<int> b;

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

    cin >> n;

    b.resize(n);

    for(int i = 0; i < n; ++i)
    {
        cin >> b[i];
        for(int j = 0; j < 3; ++j)
        {
            for(int k = 0; k < 3; ++k)
            {
                if(a[j][k] == b[i])
                {
                    a[j][k] = 0;
                }
            }
        }
    }

    bool isYes = false;
    for(int i = 0; i < 3; ++i)
    {
        if(a[i][0] == a[i][1] && a[i][1] == a[i][2] && a[i][2] == 0)
        {
            isYes = true;
        }
        if(a[0][i] == a[1][i] && a[1][i] == a[2][i] && a[2][i] == 0)
        {
            isYes = true;
        }
    }

    if(a[0][0] == a[1][1] && a[1][1] == a[2][2] && a[2][2] == 0) isYes = true;
    if(a[2][0] == a[1][1] && a[1][1] == a[0][2] && a[0][2] == 0) isYes = true;

    cout << (isYes ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
struct node{int to,nxt;}e[maxn<<1];
int n,tot,mx,root,head[maxn],dep[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void add(int u,int v){e[++tot].to=v;e[tot].nxt=head[u];head[u]=tot;}

void dfs(int x,int fa){
    if(dep[x]>mx){mx=dep[x];root=x;}
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
        if(v!=fa)dep[v]=dep[x]+1,dfs(v,x);
}
int main(){
    n=read();
    for(int i=2;i<=n;i++){int u=read(),v=read();add(u,v);add(v,u);}
    dfs(1,0);mx=0;memset(dep,0,sizeof(dep));
    dep[root]=1;dfs(root,0);
    if(mx%3==2)puts("Second");
    else puts("First");
    return 0;
}


Measured memory_bytes: 14208
//
// LIS and LDS
//
// verified:
//   ARC 091 E - LISDL
//     https://beta.atcoder.jp/contests/arc091/tasks/arc091_c
//

/*
    0 〜 N-1 の順列であって
    LIS (最長増加部分列) の長さが A
    LDS (最長減少部分列) の長さが B
    となるものを 1 つ求める
 
    
*/


#include <iostream>
#include <vector>
using namespace std;


// LIS and LDS
// A + B <= N+1, AB >= N are necessarily and sufficient
vector<long long> LISLDS(long long N, long long A, long long B) {
    vector<long long> res;
    for (long long i = B-1; i >= 0; --i) res.push_back(i);
    
    if (A == 1) return res;
    
    long long rem = N - B;  //  残りの数字の数
    long long p = rem / (A-1);  //  
    long long r = rem % (A-1);  // 
    
    long long b = r;
    long long c = A-1-b;
        for (int i = 0; i < c; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p; ++j) {
            res.push_back(size + p - 1 - j);
        }
    }
    
    for (int i = 0; i < b; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p+1; ++j) {
            res.push_back(size + p+1 - 1 - j);
        }
    }

    
    return res;
}

int main() {
    long long N, A, B; cin >> N >> A >> B;
    if (A + B > N+1 || A * B < N) cout << -1 << endl;
    else {
        vector<long long> res = LISLDS(N, A, B);
        for (int i = 0; i < res.size(); ++i) {
            cout << res[i] + 1;
            if (i != (int)res.size() - 1) cout << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 6512
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <iomanip> 

using ll = long long;
using ull = unsigned long long;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;(i) < ((int)(n));++(i))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline void print(T&& x){cout<<x<<endl;}// 改行付き出力
template<typename T>inline T SUM(vector<T> vec){return accumulate(all(vec),(T)0);} // vectorの中身を全部足す
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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 ctoi(char c){return c-'0';}


// TODO: write
int main() {
  int n,k;cin>>n>>k;
  vector<int> a(n);rep(i,n)cin>>a[i];
  vector<ll> dp(n,INFL);
  dp[0] = 0;

  rep(i,n-1){
    rep(j,min(k,i+1)){
      chmin(dp[i+1], abs(a[i+1] - a[i-j]) + dp[i-j]);
    }
  }
  print(dp[n-1]);
  return 0;
}

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

class team{
public:
  int I,U,A,P;
  bool operator<(const team x)const{
    if(A!=x.A)return A>x.A;
    if(P!=x.P)return P<x.P;
    return I<x.I;
  }
};

int main(){
  int n,num[2000];
  team t[500];

  while(cin >> n,n){
    for(int i=0;i<=1000;i++)num[i] = 0;
    for(int i=0;i<n;i++)cin >> t[i].I >> t[i].U >> t[i].A >> t[i].P;

    sort(t,t+n);

    int cnt = 0;
    for(int i=0;i<n;i++){
      if(cnt<10 && num[t[i].U]<3){
	cout << t[i].I << endl;
	cnt++;
      }
      else if(cnt<20 && num[t[i].U]<2){
	cout << t[i].I << endl;
	cnt++;
      }
      else if(cnt<26 && num[t[i].U]<1){
	cout << t[i].I << endl;
	cnt++;
      }
      num[t[i].U]++;
    }
  }
}

Measured memory_bytes: 0
#ifdef LOCAL111
#else
	#define NDEBUG
#endif
#include <bits/stdc++.h>
const int INF = 1e8;
using namespace std;

#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--)
#define RBP(i,a) for(auto& i : a)
#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 << ": "
#define rangej(a,b,c) ((a) <= (c) and (c) < (b))
#define rrangej(b,c) rangej(0,b,c)
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;
typedef pair<LL,LL> LP;

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,m;
	while(cin >> n >> m){
		int q;
		cin >> q;
		vector<int> a(q);
		REP(i,q) cin >> a[i], a[i]--;
		vector<int> v;
		v.reserve(m);
		vector<bool> f(m,false);
		RREP(i,q){
			if(!f[a[i]]){
				f[a[i]] = true;
				v.push_back(a[i]);
			}
		}
		REP(i,m){
			if(!f[i]){
				v.push_back(i);
			}
		}
		int p = SZ(v)-1;
		RREP(i,SZ(v)-1){
			if(v[i+1] > v[i]){
				p--;
			}else break;
		}
		vector<int> mp(m,-1000);
		REP(i,SZ(v)){
			mp[v[i]] = i;
		}
		vector<int> cntv(m,0);
		dpite(ALL(mp));
		RREP(i,q){
			int po = mp[a[i]];
			if(po == 0 or cntv[po] < cntv[po-1]){
				cntv[po]++;
			}else{

			}
		}
		string ans = "Yes";
		dpite(ALL(cntv));
		REP(i,p){
			if(cntv[i] < n){
				ans = "No";
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  ll h, n;
  cin >> h >> n;
  rep(i, 0, n) {
    int a;
    cin >> a;
    h -= a;
  }
  if(h <= 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <math.h>

int main(void){
    int n;
    int a[100000+5];
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &a[i]);
    
    int p=1;
    int cnt=0;
    while(p!=2){
        if(a[p]==-1){
            // 一度でも触れたボタンなら無限ループなので終了
            printf("-1\n");
            return 0;
        }
        cnt++;
        int next=a[p];
        a[p]=-1;
        p=next;
    }
    
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 2120
#include<bits/stdc++.h>
using namespace std;
int dp[1000010][4];
const int mod=1e9+7;
int main(){
	int n; cin>>n;
	dp[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<4;++j){
			(dp[i][j]+=dp[i-1][j]*8ll%mod)%=mod;
			(dp[i][j|1]+=dp[i-1][j])%=mod;
			(dp[i][j|2]+=dp[i-1][j])%=mod;
		}
	}
	printf("%d\n",dp[n][3]);	
} 

Measured memory_bytes: 19144
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5010;

int n, f[N][N], ans;
char s[N];

int main()
{
	scanf("%d%s", &n, s + 1);
	
	for (int i = n; i >= 1; --i)
	{
		for (int j = n; j > i; --j)
		{
			if (s[i] == s[j]) f[i][j] = min(f[i + 1][j + 1] + 1, j - i);
			ans = max(ans, f[i][j]);
		}
	}
	// f[i][j] = min(f[i+1][j+1] + 1 , j-i) ;
	// 
	cout << ans;
	
	return 0;
}


Measured memory_bytes: 96768
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    As = list(map(int, input().split()))
    MAX = 10**18

    if 0 in As:
        print(0)
        return

    ans = 1
    for a in As:
        ans *= a
        if ans > MAX:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 21612
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;



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

    //double x = a / 0.08;
    for (int i = 0;; i++) {
        if ((int)(i * 0.1) == (int)b&&(int)(i*0.08)==(int)a) {
            cout << i << endl;
            return 0;
        }
        if ((int)(i * 0.1) > b) {
    //        cout << i * 0.1;
            cout << -1 << endl;
            return 0;
        }
   //     cout << i*0.1 << endl;
    }


    return 0;

}

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

A.sort(reverse=True)
dic={}
for a in A:
    dic[a]=dic.get(a,0)+1

ans=0

for a in A:
    small=(1<<(len(format(a,"b")))) -a
    if small==a:
        if dic[a]>=2:
            dic[a]-=2
            ans+=1
        continue
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a]-=1
        dic[small]-=1
        ans+=1
print(ans)

Measured memory_bytes: 33984
#include <iostream>
#include <set>
#include <numeric>

using namespace std;

typedef long long ll;

set<ll> divisors(ll n) {
    set<ll> ans;
    for (ll i = 2; i * i <= n; ++i) if (n % i == 0) ans.insert(i), ans.insert(n / i);
    if (n > 1) ans.insert(n);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = divisors(n - 1).size();
    auto d = divisors(n);
    for (auto i = d.begin(); i != d.end(); ++i) {
        ll t = n;
        while (t % *i == 0) t /= *i;
        if (t % *i == 1) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int H = Integer.parseInt(sc.next());
        final int W = Integer.parseInt(sc.next());
        final int K = Integer.parseInt(sc.next());
        final char s[][] = new char[H][W];
        int t[][] = new int[H][W];
        for (int i=0; i<H; i++) {
            s[i] =  sc.next().toCharArray();
        }
        sc.close();

        int cnt = 0;
        boolean b = false;
        for (int i=0; i<H; i++) {
            b = false;
            for (int j=0; j<W; j++) {
                if (s[i][j]=='#') {
                    cnt++;
                    t[i][j] = cnt;
                    b = true;
                }
                if (b && s[i][j]=='.') {
                    t[i][j] = cnt;
                }
            }
        }
        for (int i=H-1; i>=0; i--) {
            int c = -1;
            for (int j=W-1; j>=0; j--) {
                if (t[i][j]>0) {
                    c = t[i][j];
                } else if (c>0) {
                    t[i][j] = c;
                }

            }
        }
        for (int j=0; j<W; j++) {
            for (int i=0; i<H; i++) {
                if (t[i][j]==0) {
                    if (i>0) {
                        t[i][j] = t[i-1][j]; 
                    }
                }
            }
        }
        for (int j=0; j<W; j++) {
            for (int i=H-1; i>=0; i--) {
                if (t[i][j]==0) {
                    if (i<H-1) {
                        t[i][j] = t[i+1][j]; 
                    }
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                pw.print(t[i][j]);
                if (j<W-1) {
                    pw.print(" ");
                }
            }
            pw.println();
        }
        pw.flush();
    }
}

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

using namespace std;
typedef long long ll;
ll prefix[200009];
char a[300][300];
int c[400][400];
vector<int>row[400];
int done[400];
int main() {
 int h,w,k;cin>>h>>w>>k;ll num=1;
 for(int i=1;i<=h;i++){
     for(int j=1;j<=w;j++){
         cin>>a[i][j];
         if(a[i][j]=='#'){
             c[i][j]=num;num++;row[i].push_back(j);
         }
     }
 }int firs=0;int last=0;
  for(int i=1;i<=h;i++){
    
     if(row[i].size()){
         done[i]=1;
         if(firs==0){firs=i;}
         last=i;
         int s=row[i][0];
         int nm=c[i][s];
         for(int y=1;y<s;y++){
             c[i][y]=nm;
         }for(int jj=s;jj<=w;jj++){
             if(c[i][jj]!=0){nm=c[i][jj];}
             c[i][jj]=nm;
         }
         }
     }
 for(int j=firs-1;j>=1;j--){
     done[j]=1;
     for(int jj=1;jj<=w;jj++){
         c[j][jj]=c[j+1][jj];
     }
 }
  for(int i=1;i<=h;i++){
     for(int j=1;j<=w;j++){
         if(done[i]==0){
             c[i][j]=c[i-1][j];
         }
        cout<<c[i][j]<<" ";
     }cout<<endl;
 }
}

Measured memory_bytes: 4784
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

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

bool cmp(const int &a, const int &b) {
	return a > b;
}
int n, m, v, p;
int *a;
LL *s;

LL sum(int a, int b) {
	//printf("sum(%d, %d)\n", a, b);
	if (a == 0) {
		return s[b];
	}
	else {
		return s[b] - s[a - 1];
	}
}
int main() {
	scanf("%d%d%d%d", &n, &m, &v, &p);
	a = new int[n + 10];
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n, cmp);

	int pcur = -1;
	int res = 0;
	s = new LL[n + 10];
	s[0] = a[0];
	for (int i = 1; i < n; ++i) {
		s[i] = s[i - 1] + (LL)(a[i]);
	}
	for (int i = 0; i < n; ++i) {
		//cout << "i = " << i << endl;
		while (pcur == -1 || a[pcur] > a[i] + m) {
			++pcur;
		}
		if (i < p) {
			++res;
			continue;
		}
		if (pcur >= p) {
			break;
		}
		int n_free = (n - i - 1) + (p - 1);
		int n_cons = (v - n_free - 1);
		//printf("n_free = %d, n_cons = %d\n", n_free, n_cons);
		if (n_cons <= 0) {
			++res;
			continue;
		}
		LL ss = sum(p - 1, i - 1);
		LL ssn = (LL)(i - p + 1);
		ss += (LL)(m) * (LL)(n_cons);
		if (ss > ssn * (LL)(a[i] + m)) {
			break;
		}
		else {
			++res;
			continue;
		}

	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <string>
 
int main()
{
  int n, a, b, c, d;
  std::string str;
  std::cin >> n >> a >> b >> c >> d >> str;
  a--; b--; c--; d--;

  const auto entirePath = str.substr(a, std::max(c,d)-a+1);
  const std::string tourenai = "##";
  const bool blocked =
   std::search(entirePath.begin(), entirePath.end(), tourenai.begin(), tourenai.end()) != entirePath.end();

  const auto oikoshiPath = str.substr(b-1, std::min(d+1,n-1)-b+2);
  const std::string oikoseru = "...";
  const bool oikosenai =
    std::search(oikoshiPath.begin(), oikoshiPath.end(), oikoseru.begin(), oikoseru.end()) == oikoshiPath.end();

  if( c < d ) { std::cout << (blocked ? "No" : "Yes"); }
  else { std::cout << ((blocked || oikosenai) ? "No" : "Yes"); }

  //std::cout << "," << blocked << "," << oikosenai << std::endl;
}


Measured memory_bytes: 772