akhauriyash/Code-Regression huggingface dataset:
"""
https://twitter.com/kiri8128/status/1240504897419673600
https://twitter.com/kiri8128/status/1241033090773860353
"""
from collections import defaultdict
from math import gcd
from typing import Dict, Optional


def is_prime_miller_rabin(n: int) -> bool:
    """Miller–Rabin primality test"""
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11, 61}:
        return True
    elif n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0:
        return False

    if n < (1 << 32):
        L = [2, 7, 61]
    elif n < (1 << 48):
        L = [2, 3, 5, 7, 11, 13, 17]
    else:
        L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    d = n - 1
    d = d // (d & -d)

    for a in L:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True


def find_factor_rho(n: int) -> Optional[int]:
    """Pollard's rho algorithm using Brent's cycle finding method"""
    if n < 2:
        return None
    m = 1 << n.bit_length() // 8 + 1

    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if is_prime_miller_rabin(g):
                return g
            elif is_prime_miller_rabin(n // g):
                return n // g
    return None


def prime_factorize(n: int) -> Dict[int, int]:
    """Prime factorize n in O(n^(1/4))?.
    https://twitter.com/kiri8128/status/1240504897419673600
    """
    prime_factors = defaultdict(int)
    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            prime_factors[i] += 1
        i += 1 + i % 2
        if i != 101 or n < 1 << 20:
            continue
        while n > 1:
            if is_prime_miller_rabin(n):
                prime_factors[n], n = 1, 1
                break
            j = find_factor_rho(n)
            while n % j == 0:
                n //= j
                prime_factors[j] += 1
    if n > 1:
        prime_factors[n] += 1
    return prime_factors  # the keys are unsorted


def eulers_product_formula(n: int) -> int:
    """Calculate Euler's totient function.
    The time complexity depends on the implementation of prime factorization.
    """
    phi = n
    prime_factors = prime_factorize(n).keys()
    for p in prime_factors:
        phi *= 1 - (1 / p)
    return int(phi)


def main():
    N = int(input())
    print(eulers_product_formula(N))


if __name__ == "__main__":
    main()



Measured memory_bytes: 7252
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 2e5 + 5;
int n, a, b, c, d;
char tmp[maxn];
string s;

bool read() {
  if (scanf("%d%d%d%d%d", &n, &a, &b, &c, &d) < 5) {
    return false;
  }
  a--;
  b--;
  c--;
  d--;
  scanf("%s", tmp);
  s = tmp;
  return true;
}

bool check(int a, int b) {
  for (int i = a + 1; i + 1 < b; i++) {
    if (s[i] == '#' && s[i + 1] == '#') {
      return false;
    }
  }
  return true;
}

void solve() {
  if (!check(a, c) || !check(b, d)) {
    printf("No\n");
    return;
  }
  if (d < c) {
    bool ok = false;
    for (int i = b; i <= d; i++) {
      if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
        ok = true;
        break;
      }
    }
    if (!ok) {
      printf("No\n");
      return;
    }
  }
  printf("Yes\n");
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 640
//ysh_gpta
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
typedef long long ll;
#define vb vector<bool>
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define mkp make_pair
#define pb push_back
#define INF 1000000000000000
#define MOD 1000000007
#define ff first
#define ss second
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//ll gcd( ll a, ll b ){if(b==0) return a; else return gcd( b, a%b );}
//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}
//void printArray(vi &v){for(int i=0;i<v.size();i++) cout<<v[i]<<endl; cout<<endl; }
ll n,m;

bool isValid(ll i,ll j){
    if((i>=0 && i<n) && (j>=0 && j<m))
    return true;
    return false;
}


int main(){
   FastIO

   cin>>n>>m;
   vector<string> v(n);
   for(int i=0;i<n;i++)
   cin>>v[i];
   vvi dp(n,vi(m,0));
   for(int i=0;i<n;i++){
       if(v[i][0]=='#')
       break;
       dp[i][0]=1;
   }
   for(int i=0;i<m;i++){
       if(v[0][i]=='#')
       break;
       dp[0][i]=1;
   }
   for(int i=1;i<n;i++){
       for(int j=1;j<m;j++){
           if(v[i][j]=='#')
           continue;
           if(isValid(i-1,j) && isValid(i,j-1))
           dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
           else if(isValid(i-1,j))
           dp[i][j] = dp[i-1][j];
           else if(isValid(i,j-1))
           dp[i][j] = dp[i][j+1];
       }
   }
//    for(int i=0;i<n;i++){
//         for(int j=0;j<m;j++)
//         cout<<dp[i][j]<<" ";
//         cout<<endl;
//    }

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

Measured memory_bytes: 9216
package main

import (
	"fmt"
	"strings"
)

func hasSerial(a []string) bool {
	for i, v := range a {
		if i == 0 {
			continue
		}
		if a[i-1] == v {
			return true
		}
	}
	return false
}

func main() {
	var s string
	fmt.Scan(&s)
	a := strings.Split(s, "")

	if hasSerial(a) {
		fmt.Println("Bad")
	} else {
		fmt.Println("Good")
	}
}


Measured memory_bytes: 640
/*            AUTHOR - SHIVAM GUPTA
                       Jalpaiguri Govt. Engg College             */
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
vector<ll> ve[100005];
ll vis[100005],z;
ll a[100005],dp[100005],n,k;

ll f(ll x)
{
    if(dp[x]!=-1){
        return dp[x];
    }
    ll z=1e9;
    if(x>=n-1)
    return 0;
    for(ll i=1;i<=k and i+x<n;i++)
    z=min(z,abs(a[x]-a[x+i])+f(x+i));
    // cout<<x<<" "<<z<<"\n";
    return dp[x]=z;
}

void solve()
{
    vector<ll> v;        vector<pair <ll,ll>> vp;
    map<ll,ll> mp;       set<ll> st;        multiset<ll> mst;
    ll m=0,i=0,j=0,c=0,l=0,r=0,p=0,q=0,x=0,y=0,z=0,flag=0,sum=0;
    // ll a[300005]={0},b[300005]={0},ans[300005];
    string s,t;
    cin>>n;
    k=2;
    for(i=0;i<n;i++)
    cin>>a[i];
    for(i=0;i<=n;i++)dp[i]=-1;
    
    cout<<f(0)<<endl;
    
}
bool imp=false;int main()
{
    fio;
    int t=1;
    if(imp)
	cin>>t;
	ll j=t;
    while(t--){
    // cout<<"Case #"<<j-t<<": ";
    solve();}
    return 0;
}

Measured memory_bytes: 9216
using System;

namespace AOJ_Intro_SmallLargeEqual
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int a, b;
			string[] data;
			data = Console.ReadLine ().Split (" ".ToCharArray ());

			a = int.Parse (data [0]);
			b = int.Parse (data [1]);

			Console.WriteLine( (a > b) ? "a > b" : (a < b) ? "a < b" : "a == b");

		}
	}
}

Measured memory_bytes: 5280
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;

int main(void){
  int n;
  string s;
  cin >> n >> s;
  set<int> work[26];
  rep(i,n){
    int a = s[i]-97;
    work[a].insert(i+1);
  }
  int q;
  cin >> q;
  rep(i,q){
    int tmp;
    cin >> tmp;
    if(tmp == 1){
      int iq;
      char cq;
      cin >> iq >> cq;
      work[s[iq-1]-97].erase(iq);
      work[cq-97].insert(iq);
      s[iq-1] = cq;
    }
    else{
      int lq,rq;
      cin >> lq >> rq;
      int ans = 0;
      rep(i,26){
	if(*(work[i].lower_bound(lq)) <= rq && work[i].lower_bound(lq) != work[i].end()){
	  ans++;
	}
      }
      cout << ans << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 24196
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <limits.h>
//#include <math.h>

#define MIN(a, b) ((a<b) ? a : b)
#define N 100000

int main() {
  int n;
  scanf("%d", &n);
  int dp[n+1];
  dp[0] = 0;
  for (int i=1; i<n+1; i++) {
    dp[i] = 100001;
    for (int j=9; j<=i; j*=9) {
      for (int k=1; k<=i/j && k<9; k++) {
        dp[i] = MIN(dp[i], dp[i-k*j]+k);
      }
    }
    for (int j=6; j<=i; j*=6) {
      for (int k=1; k<=i/j && k<6; k++) {
        dp[i] = MIN(dp[i], dp[i-k*j]+k);
      }
    }
    for (int j=1; j<6 && j<=i; j++) dp[i] = MIN(dp[i], dp[i-j]+j);
  }
  printf("%d\n", dp[n]);
  return 0;
}


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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long LL;
const LL mod=1000000007;
#define MAX 10000
const double PI  = acos(-1.0);



int n, a[MAX][MAX];
LL d[MAX][MAX], flag[MAX][MAX];
LL ans = 0;


void warshall(){

    REP(k, n){
        REP(i, n){
            REP(j, n){

                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

                if (d[i][j] == d[i][k] + d[k][j] && i != k && j != k) {
					flag[i][j] = 1;
                }
            }
        }
    }
}


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;
    REP(i, n){
        REP(j ,n){
            cin >> a[i][j];
            d[i][j] = a[i][j];
        }
    }

    warshall();

    REP(i, n){
        REP(j ,n){
            if (a[i][j] == d[i][j]){
                if ( !flag[i][j]){
                    ans += a[i][j];
                }
            }
            else{
                ans = -1; break;
            }
        }
        if (ans < 0)break;
    }
    if( ans > 0) cout << ans / 2 << endl;

    else cout << ans << endl;

    return 0;

}


Measured memory_bytes: 61824
def examD():
    N, K = LI()
    A = [0]*N; B = [0]*N
    for i in range(N):
        A[i],B[i] = LI()
    ans = 0; bi = 32
    for i in range(bi+1):
        if K&(1<<(bi-i))==0:
            if i!=bi:
                continue
        mask = 2**(bi-i)
        for j in range(i):
            if K&(1<<(bi-j))==0:
                mask += 2**(bi-j)
#        print(i,mask)
        now = 0
        for i in range(N):
            if A[i]&mask>0:
                continue
#            print(A[i],B[i])
            now +=B[i]
        ans = max(ans,now)

    mask = K^(2**bi -1)
    now = 0
    for i in range(N):
        if A[i] & mask > 0:
            continue
        #            print(A[i],B[i])
        now += B[i]
    ans = max(ans, now)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()


Measured memory_bytes: 13020
def movement(x0, y0 , t, x1, y1) :
    total = abs(x1 - x0) + abs(y1 - y0)
    if total <= t and (t - total) % 2 == 0 :
        return "Yes"
    else :
        return "No"

n = int(input())
plan = []
x0, y0 = 0, 0


for i in range(n) :
    plan.append(list(map(int, input().split(" "))))

for i in range(1,n) :
    plan[n-i][0] -= plan[n-1-i][0]

for i in range(n) :
    judge = movement(x0, y0, plan[i][0], plan[i][1], plan[i][2])
    if judge == "Yes" :
        x0, y0 = plan[i][1], plan[i][2]
    else :
        print(judge)
        break

if x0 == plan[n-1][1] and y0 == plan[n-1][2] :
    print("Yes")
    


Measured memory_bytes: 27324
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int a = saori.saori_hayami();
		int b = saori.saori_hayami();
		if(a > 0){
			System.out.println("Positive");
		} else if(a <= 0 && 0 <= b){
			System.out.println("Zero");
		} else {
			if((Math.abs(a)-Math.abs(b)) % 2 == 0){
				System.out.println("Negative");
			} else {
				System.out.println("Positive");
			}
		}
		
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 23124
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;
typedef long long int64;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int k;
  cin>>k;
  vector<int64> a(k);
  for(int i=0;i<k;i++){
    cin>>a[i];
  }
  int64 min=2,max=2;
  for(int i=k-1;i>=0;i--){
    if(max<a[i]){
      cout<<-1<<endl;
      return 0;
    }
    int64 next_min=(min%a[i]==0?min:(min/a[i]+1)*a[i]);
    if(!(min<=next_min&&next_min<=max)){
      cout<<-1<<endl;
      return 0;
    }
    int64 next_max=(max%a[i]==0?max+a[i]-1:(max/a[i])*a[i]+a[i]-1);

    min=next_min;
    max=next_max;
  }
  cout<<min<<" "<<max<<endl;



  return 0;
}

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

int main(){
  int a, b, c, x;
  cin>>a>>b>>c>>x;
  int ans=0;
  for(int i=0;i<=a;i++){
    int tmp=x-500*i;
    for(int j=0;j<=b;j++){
      int tmp2=tmp-100*j;
      if (tmp2>=0 && tmp2<=50*c) ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int H,W;
    while(1){
        cin >> H >> W;
        if(H==0 && W==0)break;
            for ( int i = 0; i < H; i++ ){
                for ( int j = 0; j < W; j++ ){
                    if(i%2==0){
                        if(j%2==0){
                            cout << '#';
                        }else{
                            cout << '.';
                        }
                    }else{
                        if(j%2==0){
                            cout << '.';
                        }else{
                            cout << '#';
                        }
                    }
                }cout << endl;
            }cout << endl;
    }
    
}


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

int n,m;
double dp[(1<<16)][17];
double a[20][20];

double memo(int state,int enemy){
	if(enemy==m)return 1;
	if(state==(1<<n)-1)return 0;
	if(dp[state][enemy]>=0)return dp[state][enemy];
	double &res=dp[state][enemy];
	res=0;
	for(int i=0;i<n;i++){
		if(state&(1<<i))continue;
		double now=1,sum=0;
		for(int j=enemy;j<m;j++){
			sum+=now*(1-a[i][j])*memo((state|(1<<i)),j);
			now*=a[i][j];
		}
		sum+=now;
		res=max(res,sum);
	}
	return dp[state][enemy];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout<<fixed;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<(1<<16);i++)
	  for(int j=0;j<17;j++)
	  	dp[i][j]=-1;
	cout<<memo(0,0)<<endl;
	return 0;
}


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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(int N, const vector<ll>& xs)
{
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);

    string S, T;
    cin >> S >> T;

    auto ans = (S == T.substr(0, S.size()) ? "Yes": "No");

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 3596
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}


ll const mod = 1e9+7;

vector<vector<int>> tree;
vector<vector<ll>> ans;
void ret(int n, int p) {
  for (auto e:tree[n]) {
    if (e!=p) ret(e,n);
  }
  if (p>=0) {
  ans[p][0] *= ans[n][0]+ans[n][1]; //w
  ans[p][1] *= ans[n][0];
  ans[p][0]%=mod; ans[p][1]%=mod;
  }
}

int main() {
  int N,x,y;
  cin >> N;
  // if (N==1) {
  //   cout << 2 << endl;
  //   return 0;
  // }
  vector<ll> w,b;
  vector<vector<int>> tmp(N);
  vector<vector<ll>>tmp2(N,vector<ll>(2,1));
  tree = tmp; ans = tmp2;
  rep(i,N-1) {
    cin >> x >> y;
    x--; y--;
    tree[x].push_back(y);
    tree[y].push_back(x);
  }
  ret(0,-1);
  cout << (ans[0][0]+ans[0][1])%mod << endl;
}

Measured memory_bytes: 22272
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
typedef long long unsigned int llong;


int main(){
    int n;
    cin >> n;
    int _n;
    _n=n;
    int a=0;
    while(1){
        a+= n%10;
        if( n < 10) break;
        n = n/10;
    }
    if(_n % a == 0) printf("Yes\n");
    else printf("No\n");
}

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

using namespace std;

int main() {
  	int a, b, c;
  	cin >> a >> b >> c;
  	set <int> s;
  	s.insert(a);
  	s.insert(b);
  	s.insert(c);
  	cout << (int)s.size() << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<char>> a(H, vector<char>(W));

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> a.at(i).at(j);
        }
    }

    vector<char> temp(H), white(W, '.');
    for(int i = 0; i < H; i++){
        if(a.at(i) == white){
            for(int j = i; j < H-1; j++){
                swap(a.at(j), a.at(j+1));
            }
            i--;
            H--;
        }
    }

    int check;
    for(int i = 0; i < W; i++){
        check = 0;
        for(int j = 0; j < H; j++){
            if(a.at(j).at(i) == '.') check++;
        }
        if(check == H){
            for(int j = 0; j < H; j++){
                for(int k = i; k < W-1; k++){
                    swap(a.at(j).at(k), a.at(j).at(k+1));
                }
            }
            i--;
            W--;
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cout << a.at(i).at(j);
        }
        cout << endl;
    }
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,0,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
 
signed main(){
    int N;cin>>N;
    int A[N];
    int sum=0;
    REP(i,N){
        cin>>A[i];
        sum+=A[i];
    }
    int B[N],C[N];
    B[0]=A[0];
    C[0]=sum;
    REP(i,N-1)B[i+1]=B[i]+A[i+1];
    REP(i,N-1)C[i+1]=C[i]-A[i];
    int ans=INF;
    for(int i=0;i<N-1;i++){
        ans=min(ans,abs(B[i]-C[i+1]));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4992
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
#include<regex>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)) //整数型のまま切り上げ演算する
#define PI 3.14159265359

int main(void){
  int N,K;
  cin >> N >> K;
  
  vector<char> D(K);
  rep(i,K) cin >> D[i];
  
  int i = N;
  while(true) {
		string S = to_string(i);
		
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < S.size(); k++) {
				if (S[k] == D[j]) goto NEXT;
			}
		}

		cout << i << endl;
		return 0;

	NEXT:
		i++;
		continue;
	}
}

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


ll solve(ll b, vector<ll>& a, int n) {
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += abs(a[i] - (b + i + 1));
	}
	return sum;
}

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	ll l = 0, r = 1e9 + 1;
	while((r - l) > 10) {
		ll m1 = (l * 2 + r) / 3;
		ll m2 = (l + r * 2) / 3;
		ll cm1 = solve(m1, a, n);
		ll cm2 = solve(m2, a, n);
		// printf("%lld %lld | %lld %lld\n", m1, cm1, m2, cm2);
		if (cm1 < cm2) r = m2 + 1;
		else l = m1;
	}

	ll ans, cnt = 1e18;
	for (ll i = max(l - 10, -20ll); i <= r + 10ll; ++i) {
		ll ncnt = solve(i, a, n);
		// printf("i %lld ncnt %lld\n", i, ncnt);
		if (cnt > ncnt) {
			ans = i; cnt = ncnt;
		}
	}
	printf("%lld\n", cnt);
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

int N;
vector<ll> deque;
vector<vector<ll>> dp;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	deque.assign(N, 0);
	for(int i = 0; i < N; i++) cin >> deque[i];

	dp.assign(N, vector<ll>(N, 0));
	for(int r = 0; r < N; r++){
		for(int l = r; l >= 0; l--){
			if (l == r) dp[l][r] = deque[l];
			else {
				dp[l][r] = max(deque[l] - dp[l+1][r], deque[r] - dp[l][r-1]);
			}
		}
	}

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

Measured memory_bytes: 72576
#include<bits/stdc++.h>
using namespace std;
int a[51];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int sum=0;
	sort(a,a+n);
	for(int i=n-1;i>=n-k;i--)
	{
		sum+=a[i];
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a <9 && b < 9) System.out.println("Yay!");
        else System.out.println(":(");
    }
}

Measured memory_bytes: 35688
from itertools import product

n = int(input())
a = []
xys = [0] * n
for i in range(n):
    a_tmp = int(input())
    a.append(a_tmp)
    xys[i] = []
    for _ in range(a_tmp):
        xys[i].append(tuple(map(int, input().split())))

li = list(product(range(2), repeat=n))[::-1]
for l in li:
    reps = []
    for i in range(n):
        if l[i]:
            reps.append((i + 1, 1))
            reps += xys[i]
        else:
            reps.append((i + 1, 0))
    reps = list(set(reps))
    flg = True
    for i in range(1, n + 1):
        if (i, 1) in reps and (i, 0) in reps:
            flg = False
            break
    if flg:
        print(sum(l))
        exit()
print(0)


Measured memory_bytes: 49756
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


int h, w, k, ans[303][303];
string s[303];

int main(){
	cin >> h >>w >> k;
	for(int i = 0; i < h; i++){
		cin >> s[i];
	}
	
	int now = 1;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if(s[i][j] == '#'){
				for(int jj = 0; jj < w; jj++){
					if(ans[i][jj]) continue;
					if(j != jj && s[i][jj] == '#') break;
					ans[i][jj] = now;
				}
				now++;
			}
		}
	}
	for(int i = 1; i < h; i++){
		if(ans[i][0]) continue;
		for(int j = 0; j < w; j++){
			ans[i][j] = ans[i-1][j];
		}
	}
	for(int i = h-1; i >= 0; i--){
		if(ans[i][0]) continue;
		for(int j = 0; j < w; j++){
			ans[i][j] = ans[i+1][j];
		}
	}
	
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			printf("%3d ", ans[i][j]);
		}
		cout << endl;
	}
	
	return 0;
}

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

int main() {
  bool a = 1, b = 1;
  int n;
  cin >> n;
  vector<string> v(n);
  unordered_set<string> s;
  for(int i = 0; i < n; i++){
    cin >> v.at(i);
    s.insert(v.at(i));
  }
  if(s.size() != n)
    a = 0;
  for(int i = 0; i < n - 1; i++){
    if(v.at(i).at(v.at(i).size() - 1) != v.at(i + 1).at(0)){
      b = 0;
      break;
    }
  }
  if(a && b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;

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

    while (in.hasNext()) {
      int A = in.nextInt();
      int B = in.nextInt();
      int K = in.nextInt();

      ArrayList<Integer> commonDivisor = new ArrayList<Integer>();

      for (int i = 1; i <= 100; ++i) {
        if (A % i == 0 && B % i == 0) {
          commonDivisor.add(i);
        } 
      }

      System.out.println(commonDivisor.get(commonDivisor.size() - K));
    }
  }
}

Measured memory_bytes: 22996
#include <algorithm>
#include <iostream>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const auto MOD = static_cast<ll>(1e9 + 7);

ll a = 0, b = 0, c = 0;
ll turn = 0;
string A, B, C;

ll next(char ch) {
    if      (ch == 'a') return 0;
    else if (ch == 'b') return 1;
    else                return 2;
}

int main() {
    cin >> A >> B >> C;
    while (a <= A.size() && b <= B.size() && c <= C.size()) {
        switch (turn) {
            case 0:
                if (a == A.size()) {
                    cout << "A" << endl;
                    return 0;
                }
                turn = next(A[a++]);
                break;
            case 1:
                if (b == B.size()) {
                    cout << "B" << endl;
                    return 0;
                }
                turn = next(B[b++]);
                break;
            case 2:
                if (c == C.size()) {
                    cout << "C" << endl;
                    return 0;
                }
                turn = next(C[c++]);
                break;
            default:
                break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  for(int i=0;i<=n/100;++i){
    int curr = i*100;
    int tmp = n-curr;
    if(tmp>=0*i&&tmp<=5*i){
      cout<<1<<endl;
      return 0;      
    }
  }
  cout<<0<<endl;
  return 0;
}

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
ll nxt(){ll x;cin>>x;return x;}

bool is(string a){
	string s=a;
	reverse(all(s));
	return s==a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	string s;
	cin>>s;
	if(is(s)&&is(s.substr(0,s.size()/2))&&is(s.substr(s.size()/2+1))) cout<<"Yes";
	else cout<<"No";
    return 0;

}



Measured memory_bytes: 256
// itne me hi thakk gaye?
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3")
#define ll long long 
#define ull unsigned long long
using ld = long double;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ll rk = 256;
const ll mod2 = 998244353;
const ld PI = 3.141592653589793;
#define pb push_back
#define mp make_pair
#define vc vector
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll> 
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define all(x) (x).begin(), (x).end()
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define print(a) for(auto j:a) {cout<<j<<",";} cout << "\n";
#define endl '\n'
#define whatis(x) cout << "> "<<#x << " ==> " << x << endl;
#define lwi(x) cout << " your " << #x << " is ---> " << x << " ";
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
// // Printing pair
ostream & operator << (ostream & os, pair <ll, ll> const& x) {
    os << x.first << "," << x.second;
    return os;
}
 
// printing vector
template <class T>
ostream & operator << (ostream & os, vector <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
// printing set
template <class T>
ostream & operator << (ostream & os, set <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
    return os << "[ " << p.first << ", " << p.second << "]" ;
}
const int mxn = 1e6+5;
long long dp[405][405];
long long getSum(vc<ll> &arr, int l, int r) {
    long long s = 0;
    for(int i=l; i<=r; i++) s += arr[i];
    return s;
}
long long f(vc <ll> &arr, int l, int r) {
    if (l == r) return 0;
    if (dp[l][r]) return dp[l][r];
    long long &ans = dp[l][r];
    ans = -1;
    long long s = getSum(arr, l, r);
    for(int i=l; i<r; i++) {
        if (ans == -1) ans = f(arr, l, i) + f(arr, i+1, r) + s;
        else ans = min(ans, f(arr, l, i) + f(arr, i+1, r) + s);
    }
    return ans;
}
int32_t main(){
    FastIO;
    int n;
    cin >> n;
    vc <ll> arr(n);
    for(int i=0; i<n; i++)  cin >> arr[i];
    // vc <int> arr = {10, 20, 30, 40};
    cout << f(arr, 0, arr.size()-1) << endl;
    return 0;
}


Measured memory_bytes: 4924
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define vec vector<ll>
#define ms multiset<ll>
#define f(i,x,n) for(int i=x;i<n;i++)
#define int long long
#define mod 
#define endl "\n"
#define MAXN 300001 
const int INF = 1e9;
void fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
} 
int dp[3002][3002],l1,l2; 
string s1,s2;
int dfs(int x,int y)
{
	if(x>=l1||y>=l2)
		return dp[x][y]=0;
	if(dp[x][y]!=-1)
		return dp[x][y];
	if(s1[x]==s2[y])
	{
		return dp[x][y]=1+dfs(x+1,y+1);
	}
	else
		return dp[x][y]=max(dfs(x+1,y),dfs(x,y+1));
}
int32_t main() 
{
	fastio();
	cin>>s1>>s2;
	l1=s1.length();l2=s2.length();
	memset(dp,-1,sizeof(dp));
	int mx=dfs(0,0);
	if(mx==0)
	{
		cout<<" ";
		return 0;
	}
	f(i,0,l1)
	{
		f(j,0,l2)
		{
			if(dp[i][j]==mx&&dp[i+1][j+1]==mx-1&&s1[i]==s2[j])
			{	
				cout<<s1[i];
				mx--;
				break;
			}
		}
	}
}

Measured memory_bytes: 70912
#include <iostream>

using namespace std;

class LightList
{
private:
	const static int INVALID = -1;
	int front, back;
	int *allocate_array;

public:
	LightList(int size) : 
		front(0), back(0)
	{
		allocate_array = new int[size];
	}
	~LightList()
	{
		delete[] allocate_array;
	}
	void insert(int x)
	{
		allocate_array[front] = x;
		front++;
	}
	void remove(int x)
	{
		if (allocate_array[front - 1] == x) {
			allocate_array[front - 1] = INVALID;
			front--;
			return;
		}
		for (int i = front - 2; i > back; i--) {
			if (allocate_array[i] == x) {
				allocate_array[i] = INVALID;
				return;
			}
		}
		if (allocate_array[back] == x) {
			allocate_array[back] = INVALID;
			back++;
			return;
		}

	}
	void deleteFirst()
	{
		front--;
	}
	void deleteLast()
	{
		back++;
	}
	void print()
	{
		int i = front - 1;
		while (i >= back && allocate_array[i] == INVALID) i--;
		cout << allocate_array[i];
		i--;
		for (; i >= back; i--) {
			if (allocate_array[i] != INVALID)
				cout << ' ' << allocate_array[i];
		}
		cout << endl;
	}
};

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

	int n, size = 1000020;
	cin >> n;
	if (n < 1000020) size = n;
	LightList number_list(size);

	for (int i = 0; i < n; i++) {
		char command[12];
		int x;
		cin >> command;
		if (command[0] == 'i') { // insert x
			cin >> x;
			number_list.insert(x);
		}
		else { // delete???
			switch (command[6]) {
			case '\0': // delete x
				cin >> x;
				number_list.remove(x);
				break;
			case 'F': // deleteFirst
				number_list.deleteFirst();
				break;
			case 'L': // deleteLast
				number_list.deleteLast();
				break;
			}
		}
	}
	number_list.print();
	return 0;
}

Measured memory_bytes: 6700
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <ctime>
#include <cmath>
using namespace std;

long long max(long long a, long long b) {
	if (a > b) {
		return a;
	}
	return b;
}

long long task(int N, int W, vector<int> &weight, vector<long int> &value) {
	vector<vector<long long>> result(N + 1, vector<long long> (W + 1, 0));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= W; j++) {
			if (j >= weight[i-1]) {
				result[i][j] = max(result[i-1][j], value[i-1] + result[i-1][j - weight[i-1]]);
			} else {
				result[i][j] = result[i-1][j];
			}
		}
	}
	return result[N][W];
}

void read_input(int &N, int &W, vector<int> &weight, vector<long int> &value) {
	string seq;
	// read N, K
	getline(cin, seq);
	istringstream iss(seq);
	iss >> N;
	iss >> W;
	iss.clear();
	long int buf;
	for (int i = 0; i < N; i++) {
		getline(cin, seq);
		iss.str(seq);
		iss >> buf;
		weight.push_back(buf);
		iss >> buf;
		value.push_back(buf);
		iss.clear();
	}
}

int main() {
	int N, W;
	vector<int> weight;
	vector<long int> value;
	read_input(N, W, weight, value);
	//unsigned init_time = clock();
	cout << task(N, W, weight, value) << endl;
	//unsigned end_time = clock();
	//cout << double(end_time - init_time) / CLOCKS_PER_SEC << " seconds" << endl;
	return 0;
}

Measured memory_bytes: 80256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.next();
		//String t = sc.next();
		//String g = sc.next();
		long n = sc.nextLong();
		//long m = sc.nextLong();
		//long k = sc.nextLong();
		//long l = sc.nextLong();
		//long count=0;

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

		}*/
		if(n>=1000) {
			System.out.println("ABD");
		}else{
			System.out.println("ABC");
		}
		//System.out.println((int)Math.ceil((n+m)/2.0));
		//System.out.println(s.substring(0,1)+t.substring(1,2)+g.substring(2,3));
	}
}




Measured memory_bytes: 21972
def main():
    n, t = map(int, input().split())

    min_cost = 1001
    for _ in range(n):
        ci, ti = map(int, input().split())
        if ti <= t and ci < min_cost:
            min_cost = ci

    print('TLE' if min_cost == 1001 else min_cost)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9+7;
const int MAXN = 105;
struct Node {
    string s;
    int x, id;
}a[MAXN];
bool cmp(Node A, Node B) {
    if(A.s == B.s) return A.x > B.x;
    return A.s < B.s;
}
int main() {
    int n; cin>>n;
    for(int i=0; i<n; i++) {
        cin>>a[i].s>>a[i].x;
        a[i].id = i;
    }
    sort(a, a+n, cmp);
    for(int i=0; i<n; i++) cout<<a[i].id+1<<endl;
    return 0;
}


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

#define pb push_back
#define eb emplace_back
#define mk make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define DBG(x) cout << "[" << #x << "]: " << x << endl
using ll = long long;
using pii = pair<int, int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); }
template<class num> inline void rd(num& x) {
	char c, neg = 0; while(isspace(c = getchar_unlocked()));
	if(!isdigit(c)) neg = (c == '-'), x = 0;
	else x = c - '0';
	while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0';
	x = neg ? -x : x; }
template <class... Args> inline void rd(Args&... args) { (rd(args), ...); }

const int MAXN = 2e5 + 5, INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int fpow(int x, int y) {
	int r = 1;
	while(y) {
		if (y%2) r = 1ll * r * x % MOD;
		y /= 2;
		x = 1ll * x * x % MOD;
	}
	return r;
}

inline int add(int& x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
	return x;
}

inline int sub(int& x, int y) {
	x -= y;
	if (x < 0) x += MOD;
	return x;
}

inline int mul(int& x, int y) {
	return x = 1ll * x * y % MOD;
}

int main() {
	int n; rd(n);

	int ans = fpow(10, n);
	sub(ans, fpow(9, n));
	sub(ans, fpow(9, n));
	add(ans, fpow(8, n));

	printf("%d\n", ans);
}

Measured memory_bytes: 3692
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;

int main() {
	string s;
	cin >> s;
	string ans;
	rep(i, 0, s.size()) {
		if (i % 2 == 0) {
			string h;
			h = s[i];
			ans += h;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(sc.next());
            map.merge(a, 1, Integer::sum);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int k = e.getKey();
            int v = e.getValue();
            if (k > v) {
                ans += v;
            } else if (k < v) {
                ans += (v - k);
            }
        }
        System.out.println(ans);
    }
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<vector<char>> A(H, vector<char>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> A.at(i).at(j);
    }
  }
  
  vector<bool> row(H, false); //白しかない状態をfalse、1つでも黒があればtrueとするbool値
  vector<bool> col(W, false); //同上
  
  for (int i = 0; i < H; i++) { //二重ループで各要素を見ていき、黒があればi行とj列のboolはtrueに変更する
  	for (int j = 0; j < W; j++) {
		if (A.at(i).at(j) == '#') {
			row.at(i) = true;
			col.at(j) = true;
        }
    }
  }
      
  for (int i = 0; i < H; i++) {
	if (row.at(i)) { // i行目がtrueの場合
		for (int j = 0; j < W; j++) {
			if (col.at(j)) { // j列目がtrueの場合
				cout << A.at(i).at(j); // 出力する
            }
        }
		cout << endl;
    }
  }
}

Measured memory_bytes: 256
#include<iostream> 
#include<string> 
#include<vector> 
#include<algorithm> 
#include<cmath>
using namespace std; 


int main()
{
	int n, a, b;
	cin >> n >> a >> b;
	int ans = 0;
	for (int i = 1; i <=n; i++)
	{
		int w = 0;
		int p = i;
		for (;;)
		{
			w += p % 10;
			p = p / 10;
			if (p == 0)
			{
				break;
			}
			
		}
		
		if (a <= w && w <= b)
		{
			ans += i;
		}
	}
	cout << ans << endl;
	
}

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

#define ll long long 
#define sz(x) (int)x.size()

using namespace std;

int used[26];

int main(){
	string s;
	cin>>s;
	for(char c:s){
		used[c-'a']=1;
	}
	for(int i=0;i<26;i++){
		if(!used[i]){
			cout<<(char(i+'a'));
			return 0;
		}
	}
	cout<<"None";
	
	
}

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

#define INF (1001001001)

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

using namespace std;

int main()
{
	int x, y, s;

	while (scanf("%d %d %d", &x, &y, &s), x){
		int ans = -1;

		for (int i = 1; i < s; i++){
			for (int j = 1; j < s; j++){
				if (i * (100 + x) / 100 + j * (100 + x) / 100 == s){
					ans = max(ans, i * (100 + y) / 100 + j * (100 + y) / 100);
				}
			}
		}

		printf("%d\n", ans);
	}
}

Measured memory_bytes: 1172
x=int(input())
for A in range(10**3):
    k=A**5-x
    if k>=0:
        l=int(k**0.2)
        if l**5==k:
            print(A,l)
            break
    else:
        k=-k
        l=int(k**0.2)
        if l**5==k:
            print(A,-l)
            break


Measured memory_bytes: 9296
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    unordered_map<ll, ll> count;
    for(int i = 0; i < n; ++i){
        ll ai;
        cin >> ai;
        count[ai]++;
    }
    vector<ll> cand;
    for(auto it = count.begin(); it != count.end(); ++it){
        if(it->second >= 2){
            cand.push_back(it->first);
        }
        if(it->second >= 4){
            cand.push_back(it->first);
        }
    }
    if(cand.size() < 2){
        cout << 0 << endl;
    }else{
        sort(cand.begin(), cand.end());
        cout << cand.at(cand.size() - 2) * cand.at(cand.size() - 1) << endl;
    }
    return 0;
}

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

using namespace std;
#define ll long long
#define ld long double
#define PI 3.141592653L
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll INF = (ll)1e18;
const int N = 2e5 + 5;
const ll MOD = 1e9 + 7;

int parent[N];

int gcd(int a, int b) { 
    if (a == 0) 
        return b;  
    return gcd(b%a, a);  
} 
   
int lcm(int a, int b) {  
    return (a*b)/gcd(a,b);  
} 

ll pow(ll x, ll y, ll p) {
    if(y == 0) return 1;
    ll res = 1;
    x %= p;
    if(x == 0) return 0LL;
    while(y > 0) {
        if(y & 1) res = (res*x) % p;
        y >>= 1;
        x = (x*x) % p;
    }
    return res;
}

int find(int x) {
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

void Union(int x, int y) {
    int xPar = find(x), yPar = find(y);
    if(xPar != yPar) parent[xPar] = yPar;
}

int main()
{
    IOS
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}



Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int N;
vector<i64> A;

vector<pair<i64,i64>> MAX[2];

int main() {
  cin >> N;
  A.resize(1 << N);
  for(int i = 0;i < (1 << N);i++) cin >> A[i];
  MAX[0].resize(1 << N, {-1,-1});
  MAX[1].resize(1 << N, {-1,-1});

  MAX[0][0] = {A[0], 0};

  for(int state = 1;state < (1 << N);state++) {
    vector<pair<i64,i64>> vec;
    vec.push_back({A[state], state});
    for(int i = 0;i < N;i++) {
      if(state & (1 << i)) {
        int t = state & ~(1 << i);
        vec.push_back(MAX[0][t]);
        vec.push_back(MAX[1][t]);
      }
    }

    sort(all(vec));
    vec.erase(unique(all(vec)), end(vec));
    reverse(all(vec));
    MAX[0][state] = vec[0];
    MAX[1][state] = vec[1];
  }

  i64 ans = 0;

  for(int s = 1;s < (1 << N);s++) {
    ans = max(ans , MAX[0][s].first + MAX[1][s].first);
    cout << ans << endl;
  }
}


Measured memory_bytes: 13312
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(int i=0;i<(n); ++i)
using namespace std;
typedef long long ll;


int main()
{
	ll n;
	double sum = 0;
	cin >> n;
	vector <double>a(n);
	rep(i, n)cin >> a[i];
	rep(i, n) a[i] = pow(a[i], -1);
	sum = accumulate(a.begin(), a.end(), 0.0);
	cout << fixed << setprecision(10) << pow(sum,-1) << endl;
}

Measured memory_bytes: 256