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

int main() {
    long long k;
    cin >> k;
    long long sum = 0;
    for (long long i = 1; i <= k; i++) {
        for (long long j = 1; j <= k; j++) {
            for (long long a = 1; a <= k; a++) {
                sum = sum + __gcd(i,__gcd(j,a));
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	a, b := nextInt(), nextInt()
	if a == b {
		fmt.Println("Draw")
	} else if a == 1 {
		fmt.Println("Alice")
	} else if b == 1 {
		fmt.Println("Bob")
	} else if a > b {
		fmt.Println("Alice")
	} else {
		fmt.Println("Bob")
	}
}


Measured memory_bytes: 640
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String A = sc.next();
    if(Character.isUpperCase(A.charAt( 0 ) ) ){
      System.out.println("A");
    } else {
      System.out.println("a");
    }
  }
}

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

#define rep(i,x,y) for(int i=(x); i < (y); i++)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " L:" << __LINE__ << ")" << std::endl;
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

using i64=int64_t;

void solve() {
	int d, e;
	while (true) {
		cin >> d >> e;
		if (d == 0 && e == 0) break;

		double min = 999999;
		for (int i = 0; i < d; i++) {
			double dir = sqrt(i * i + (d - i) * (d - i));
			double din = fabs(dir - e);

			if (din < min) {
				min = din;
			}
		}

		cout << min << endl;
	}
}

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(16);
	solve();
	return 0;
}

Measured memory_bytes: 3264
#include <stdio.h>
int main(void){
    // Your code here!
    int r, c, i, j;
    int hyo[101][101]={};
    
    scanf("%d %d", &r, &c);
    for(i=0; i<r; i++){
        for(j=0; j<c; j++){
            scanf("%d", &hyo[i][j]);
            hyo[i][c]+=hyo[i][j];
            hyo[r][j]+=hyo[i][j];
            hyo[r][c]+=hyo[i][j];
        }
    }
    
    for(i=0; i<=r; i++){
        for(j=0; j<=c; j++){
            printf("%d", hyo[i][j]);
            if(j<c) printf(" ");
            else printf("\n");
        }
    }
    return 0;
}



Measured memory_bytes: 2044
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
typedef long double LD;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-8
#define INF 1e9
#define LINF 1e18

int const MaxSize = 1000 + 10;
string N;

int main() {

	ios_base::sync_with_stdio(false);
	//freopen("/Users/george/A_1.in", "r", stdin);

	cin >> N;

	int ps = 0;

	int ans = 0;

	LP(si, 0, N.size())
	{
		int d = N[si] - '0';

		if (d) {
			int curBest = ps + d - 1 + (N.size() - si - 1) * 9;

			ans = max(ans, curBest);

			ps += d;
		}
	}

	//ps += N[N.size() - 1] - '0';

	ans = max(ans, ps);

	cout << ans;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std;
long long h, w;

int main()
{
    long long answer = 999999999999999;
    cin >> h >> w;
    for(long long i = 1; i <= h - 1; i++){
        long long s1, s2, s3;
        s1 = i * w;
        if(((h - i) * w) % 2 == 0){
            s2 = (h * w - s1) / 2;
            s3 = s2;
        } else {
            s2 = ((h - i) * w + min(h - i, w)) / 2;
            s3 = h * w - s1 - s2;
        }
        answer = min(answer, max(s1, s2) - min(s1, s3));
    }
    for(long long i = 1; i <= w - 1; i++){
        long long s1, s2, s3;
        s1 = i * h;
        if(((w - i) * h) % 2 == 0){
            s2 = (h * w - s1) / 2;
            s3 = s2;
        } else {
            s2 = ((w - i) * h + min(w - i, h)) / 2;
            s3 = h * w - s1 - s2;
        }
        answer = min(answer, max(s1, s2) - min(s1, s3));
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define sz(v) (ll)(v).size()
#define int long long
#define mod 1000000007

int day;
int c[27];
int d[366][26], ansday[366];

void read_input() {
        //freopen("b1.in", "r", stdin);
        cin >> day;
        for (int i= 0; i< 26; i++) {
                cin >> c[i];
        }
        for (int i= 0; i< day; i++) {
                for (int j= 0; j< 26; j++) {
                        cin >> d[i][j];
                }
        }
}

void read_ans() {
        for (int i= 0; i< day; i++) {
                int x; cin >> x;
                ansday[i]= x- 1;
        }
}

void simu() {
        int lastuse[27]= {};
        int finalscore= 0;
        for (int i= 0; i< day; i++) {
                int choose= ansday[i];
                int score= d[i][choose];
                lastuse[choose]= i+ 1;
                int dec= 0;
                for (int j= 0; j< 26; j++) {
                        dec+= c[j]* ((i+ 1)- lastuse[j]);
                }
                finalscore+= score- dec;
        }
        cout << finalscore<< "\n";
}

void query() {
        int m; cin >> m;
        vector<pair<int, int>> vp;
        for (int i= 0; i< m; i++) {
                int a, b; cin >> a>> b;
                vp.push_back({a, b});
        }
        for (int i= 0; i< m; i++) {
                int wday= vp[i].first- 1;
                int wc= vp[i].second- 1;
                ansday[wday]= wc;
                simu();
        }
}

void sol() {
        int lastuse[27]= {};
        for (int i= 0; i< day; i++) {
                vector<pair<int, int>> r;
                for (int j= 0; j< 26; j++) {
                        int dec= 0;
                        for (int k= 0; k< 26; k++) {
                                if (k== j) continue;
                                dec+= c[k]* ((i+ 1)- lastuse[k]);
                        }
                        r.push_back( { (d[i][j]- dec), j } );
                }
                sort(all(r));
                reverse(all(r));
                ansday[i]= r[0].second;
                lastuse[r[0].second]= i;
        }
        for (int i= 0; i< day; i++) {
                cout << ansday[i]+ 1<< "\n";
        }
}

void solve() {
        read_input();
        sol();
        //read_ans();
        //simu();
        //query();
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int t = 1;
        //cin >> t;
        while ( t-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 3724
a,b,c,x,y=map(int,input().split())
if c*2<a+b:
    if x<y:
        if c*2*max(x,y)>min(x,y)*c*2+b*(max(x,y)-min(x,y)):
            print(min(x,y)*c*2+b*(max(x,y)-min(x,y)))
        else:
            print(c*2*max(x,y))
    else:
        if c*2*max(x,y)>min(x,y)*c*2+a*(max(x,y)-min(x,y)):
            print(min(x,y)*c*2+a*(max(x,y)-min(x,y)))
        else:
            print(c*2*max(x,y))
else:
    print(a*x+b*y)


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

typedef struct position {
    int x = 0;
    int y = 0;
    void print(){
        cout << "x: " << x << ", y: " << y << endl;
    }
} Position;

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

int h, w;
vector<vector<int>> d;
vector<string> m;
int bfs() {
    int ans = -1;
    d.assign(h, vector<int>(w, -1));
    d[0][0] = 0;
    queue<Position> q;
    q.push({0, 0});
    while (not q.empty()) {
        Position p = q.front();
        q.pop();
        for (auto i = 0; i < 4; i++) {
            Position tmp = p;
            tmp.x += dx[i];
            tmp.y += dy[i];
            if (tmp.x < 0 or tmp.x > h - 1) continue;
            if (tmp.y < 0 or tmp.y > w - 1) continue;
            if (m[tmp.x][tmp.y] == '#') continue;
            if (d[tmp.x][tmp.y] >= 0) continue;
            d[tmp.x][tmp.y] = d[p.x][p.y] + 1;
            q.push(tmp);
            if (tmp.x == h - 1 and tmp.y == w - 1) ans = d[tmp.x][tmp.y];
        }
    }

    return ans;
}

int main(){
    cin >> h >> w;

    m.resize(h);
    int count = 0;
    for (auto i = 0; i < h; i++) {
        cin >> m[i];
        for (auto j = 0; j < w; j++) {
            if(m[i][j] == '#') count++;
        }
    }

    int dist = bfs();
    if(dist < 0) {
        cout << -1 << endl;
        return 0;
    }
    cout << h * w  - (dist + 1) - count << endl;
    return 0;
}

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

int main() {
    int n, ww;
    cin >> n >> ww;
    int w[n], v[n];
    rep(i, n) cin >> w[i] >> v[i];
    ll dp[n+1][ww+1];
    rep(i, ww+1) dp[0][i] = 0;

    rep(i, n){
        rep(j, ww+1){
            if(j >= w[i]) dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]);
            else dp[i+1][j] = dp[i][j];
        }
    }

    // rep(i, n+1){
    //     rep(j, ww+1){
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    cout << dp[n][ww] << endl;
    return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int x, y;
  cin >> x >> y;
  int val = 0;
  bool horizon = true;
  vector<int> hori, ver;
  for(int i=0;i<s.size();i++) {
    if(s[i] == 'T') {
      if(horizon) hori.emplace_back(val);
      else ver.emplace_back(val);
      val = 0;
      horizon = !horizon;
    }
    else val++;
  }
  if(val) {
    if(horizon) hori.emplace_back(val);
    else ver.emplace_back(val);
    val = 0;
  }
  int start = 0;
  bool xTrue = false, yTrue = false;
  if(s[0] == 'F') {
    start += hori[0];
    hori.erase(hori.begin());
  }
  vector<vector<int>> dp(hori.size()+1, vector<int>(8030));
  for(int i=0;i<hori.size()+1;i++) {
    for(int j=0;j<8030;j++) {
      if(i == 0) {
        if(j == 0) dp[i][j] = 1;
        else dp[i][j] = 0;
      }
      else if((abs(j-hori[i-1]) < 8030 && dp[i-1][abs(j-hori[i-1])]) || (abs(j+hori[i-1]) < 8030 && dp[i-1][abs(j+hori[i-1])])) dp[i][j] = 1;
      else dp[i][j] = 0;
    }
  }
  if(s[0] == 'T' && dp[hori.size()][abs(x)]) xTrue = true;
  else if(s[0] == 'F' && abs(x-start) < 8030 && dp[hori.size()][abs(x-start)]) xTrue = true;
  vector<vector<int>> dp2(ver.size()+1, vector<int>(8030));
  for(int i=0;i<ver.size()+1;i++) {
    for(int j=0;j<8030;j++) {
      if(i == 0) {
        if(j == 0) dp2[i][j] = 1;
        else dp2[i][j] = 0;
      }
      else if((abs(j-ver[i-1]) < 8030 && dp2[i-1][abs(j-ver[i-1])]) || (abs(j+ver[i-1]) < 8030 && dp2[i-1][abs(j+ver[i-1])])) dp2[i][j] = 1;
      else dp2[i][j] = 0;
    }
  }
  if(dp2[ver.size()][abs(y)]) yTrue = true;
  if(xTrue && yTrue) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 251520
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
 
##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N, M = rip()
    S = [0] * M
    C = [0] * M
    for i in range(M):
        S[i], C[i] = rip()
 
    for i in range(1000):
        s = str(i)
        if len(s) != N: continue
        chk = True
        for j in range(M):
            chk &= s[S[j] - 1] == str(C[j])
        if chk:
            print(i)
            sys.exit(0)
    
    print(-1)
 
 
if __name__ == "__main__":
    main()

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

int main(){
	char x,y;
	cin >> x >> y;
	if(x < y){
		cout << '<' << endl;
	} else if (x == y){
		cout << '=' << endl;
	} else{
		cout << '>' << endl;
	}
    return 0;
}




Measured memory_bytes: 256
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    input! {
    a:isize,
    }
    println!("{}",(a*(a+1))/2)
}

Measured memory_bytes: 2124
import sys
input = sys.stdin.readline

N, H = map(int, input().split())
a, b = [0] * N, [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())

max_a = max(a)
b = [x for x in sorted(b, reverse=True) if x > max_a]

cnt = 0
for bi in b:
    H -= bi
    cnt += 1
    if H <= 0:
        break

if H > 0:
    cnt += H // max_a
    if H % max_a != 0:
        cnt += 1

print(cnt)


Measured memory_bytes: 12712
#!/usr/bin/env python3
# -*- coding: utf-8-*-
def f(N):
    for i in range(1, 3501):
        a = 4 * i - N
        b = N * i
        if a <= 0:
            continue
        for j in range(i, 3501):
            c = a * j - b
            d = b * j
            if c <= 0:
                continue
            if d % c == 0:
                return (i, j, d//c)


if __name__ == '__main__':
    N = int(input())
    h, n, w = f(N)
    print(h, n, w)


Measured memory_bytes: 3060
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        p: [f64; n],
    }
    let mut dp = vec![vec![0.0; n + 1]; n + 1];
    dp[0][0] = 1.0;
    for i in 0 .. n {
        for j in 0 .. n + 1 {
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
        }
        for j in 0 .. n {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }
    let mut tot = 0.0;
    for i in (n + 2) / 2 .. n + 1 {
        tot += dp[n][i];
    }
    puts!("{}\n", tot);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 94460
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;
 
inline char nc(){
	/*
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
  	*/return getchar();
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline int read(char *s)
{
    char c=nc();int len=0;
    for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
    for(;(c>='a' && c<='z');s[len++]=c,c=nc());
    s[len++]='\0';
    return len;
}
 
inline void read(char &x){
  for (x=nc();!(x>='A' || x<='B');x=nc());
}
 
int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

char ch[10000];

int main()
{
	read(ch);
	putchar(ch[0]-(97-65));
	read(ch);putchar(ch[0]-(97-65));
	read(ch);putchar(ch[0]-(97-65));
	puts("");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

vector<string> dfs(string s, ll depth, vector<char> symbol)
{
    vector<string> ret;
    if (depth == 0)
    {
        ret.push_back(s);
        return ret;
    }

    for (ll i = 0; i < symbol.size(); i++)
    {
        auto vec = dfs(s + symbol[i], depth - 1, symbol);
        for (auto &&e : vec)
        {
            ret.push_back(e);
        }
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

enum Tenki
{
    Sunny,
    Cloudy,
    Rainy
};

int main()
{
    map<ll, ll> mp;
    mp[2] = 1;
    mp[3] = 2;
    mp[4] = 3;
    mp[5] = 4;
    mp[6] = 5;
    mp[7] = 6;
    mp[8] = 7;
    mp[9] = 8;
    mp[10] = 9;
    mp[11] = 10;
    mp[12] = 11;
    mp[13] = 12;
    mp[1] = 13;

    ll A, B;
    cin >> A >> B;

    if (mp[A] == mp[B]) {
        cout << "Draw" << endl;
    } else if (mp[A] < mp[B]) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#define cost(i,j) abs(h[i]-h[j])
using namespace std;
int h[100001],dp[100001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    dp[0]=0,dp[1]=0,dp[2]=abs(h[2]-h[1]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+cost(i,i-1),dp[i-2]+cost(i,i-2));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

bool match4(const std::string& S,
            std::string::const_iterator begin)
{
  if (begin == S.end()) return true;

  std::vector<std::string> match_list = {"dream", "dreamer", "erase", "eraser"};

  bool judge = false;
  for (auto m : match_list) {
    std::string target(begin, begin+m.size());
    // std::cout << target << " " << m << std::endl;
    if (target == m) judge = judge || match4(S, begin+m.size());
  }

  return judge;
}

int main()
{
  std::string S;
  std::cin >> S;

  std::cout << (match4(S, S.begin()) ? "YES" : "NO") << std::endl;
}

Measured memory_bytes: 11560
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int h, w; cin >> h >> w;
	int a[h+1][w+1];
	
	// init
	for( int i = 0; i <= h; ++i ){
		for( int j = 0; j <= w; ++j ){
			a[i][j] = '.';
		}
	}
	int cnt = 0;
	for( int i = 0; i < h; ++i ){
		for( int j = 0; j < w; ++j ){
			char c; cin >> c;
			a[i][j] = c;
			if( c == '#' ) ++cnt;
		}
	}
	
	bool flag = true;
	if( a[0][0] == '.' || a[h-1][w-1] == '.' || cnt != w+h-1 ){
		flag = false;
	} else {
		int x = 0, y = 0;
		for( int i = 0; i < w+h-2; ++i ){
			if( a[x+1][y] == a[x][y+1] ){
				flag = false;
				break;
			} else {
				if( a[x+1][y] == '#' ){
					++x;
				} else {
					++y;
				}
			}
		}
	}
	
	cout << ( flag ? "P" : "Imp" ) << "ossible" << endl;
	return 0;
}

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

const int maxN = 40, maxA = 10, maxB = 10, inf = 1000000;

int main(void){
    // Your code here!
    int N, Ma, Mb;
    int ans;
    cin >> N >> Ma >> Mb;
    
    int dp[N+1][maxA*maxN+1][maxB*maxN+1];
    int i, j, k;
    
    for(i=0; i<=N; i++){
        for(j=0; j<=maxA*maxN; j++){
            for(k=0; k<= maxB*maxN; k++){
                dp[i][j][k] = inf;
            }
        }
    }
    
    dp[0][0][0] = 0;
    int a, b, c;
    
    for(i=0; i<N; i++){
        cin >> a >> b >> c;
        for(j=0; j<=maxA*maxN; j++){
            for(k=0; k<= maxB*maxN; k++){
                if(j-a < 0 || k-b < 0){
                    dp[i+1][j][k] = dp[i][j][k];
                }
                else {
                    dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a][k-b]+c);
                }
            }
        }
    }
    
    ans = inf;
    a = Ma;
    b = Mb;
    while(a <= maxA*maxN && b <= maxB*maxN){
        ans = min(ans, dp[N][a][b]);
        a = a+Ma;
        b = b+Mb;
    }
    
    if (ans==inf){
        cout << -1 << endl;
    }
    else{
        cout << ans << endl;
    }

}


Measured memory_bytes: 25984
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3+10;
ll n,a[N];
ll cnt[N];
ll sum=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(int i=1;i<=2000;i++)
	cnt[i]=cnt[i-1]+cnt[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			int x=a[i],y=a[j];
			int z=y-x;
			sum+=cnt[x+y-1]-cnt[z];
			if(x>=z+1)
			sum--;
			if(y>=z+1)
			sum--;
		}
	}
	cout<<sum/3<<endl;
}

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

using namespace std;

int main(void)
{
    int A, B;
    cin >> A;
    cin >> B;

    int total = 1;
    int tap = 0;

    while (total < B)
    {
        total += (A - 1);
        tap++;
    }

    cout << tap << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<string.h>
int check(char,char);

int main(){
    char s[100002];
    scanf("%s",s);
    long int n;
    n=strlen(s);
    int i,ans=0;
    for(i=0;i<=n/2;i++){
        char a,b;
        a=s[i];
        b=s[n-i-1];
        if((a=='b'&&b=='d')||(a=='d'&&b=='b')||(a=='p'&&b=='q')||(a=='q'&&b=='p')){
        }else{
            ans=2;
        }
    }
    if(ans==0){
        printf("Yes");
    }else{
        printf("No");
    }
    return 0;
}

int check(char a,char b){
    int ans=3;
    if((a=='b'&&b=='d')||(a=='d'&&b=='b')||(a=='p'&&b=='q')||(a=='q'&&b=='p')){
    }else{
        ans=2;
    }
    return ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  long long a;
  //vector<long long> va;
  vector<long long> vc(N,0);
  for (long long i=0;i<N;i++){
    cin>>a;
    //va.push_back(a);
    if ((N-a-1)%2==0){
      vc[(N-a-1)/2]++;
      vc[(N+a-1)/2]++;
    }
    else{
      cout<<0<<endl;
      return 0;
    }
  }
  for (long long i=0;i<N;i++){
    if (vc[i]!=2){
      cout<<0<<endl;
      return 0;
    }
  }
  //cout<<pow(2,N/2)<<endl;
  long long ans=1;
  long long mod=pow(10,9)+7;
  for (long long i=0;i<N/2;i++){
    ans=ans*2%mod;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1024
N,M = map(int, input().split())
P = []
S = []
for _ in range(M):
    p,s = map(str, input().split())
    P.append(int(p))
    S.append(s)

prob = [0]*(N+1)
WA = 0
AC = 0
for i in range(M):
    if prob[P[i]] >= 0 and S[i] == "WA":
        prob[P[i]] += 1
        WA += 1
    elif prob[P[i]] >= 0 and S[i] == "AC":
        AC += 1
        prob[P[i]] *= -1
        if prob[P[i]] == 0:
            prob[P[i]] = -1

for i in range(N+1):
    if prob[i] > 0:
        WA -= prob[i]

print(AC, WA)

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

int N,a;
map<int,int> cnt;
int ans;

int main(void){
    cin >> N;
    rep(i,N){
        cin >> a;
        cnt[a]++;
    }
    
    for (auto itr = cnt.begin();itr!=cnt.end();itr++){
        int key = itr ->first;
        int value = itr ->second;
        if(value >= key) ans += (value - key);
        else ans += value;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4736
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using P = pair<ll,ll>;
using um = unordered_map<ll,ll>;
#define fl cout<<flush;
#define endl '\n'
template <typename T> inline void prt(T v){cout<<v<<'\n';}
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=(ll)1e9+7;
const ll MOD2=998244353;
const ld pi=3.14159265358979323846;
const ld eps=1e-10;

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll K;
    cin >> K;
    ll M=0;
    for(ll i=0;i<2000000;++i){
        M*=10;
        M+=7;
        M%=K;
        if(M==0){
            prt(i+1);
            return 0;
        }

    }
    prt(-1);

    return 0;
}



Measured memory_bytes: 3644
#include<bits/stdc++.h>
const int N=200007;
int n,fa[N],ed[N],tk=0,deg[N];
std::vector<int>e[N];
int v1[N],v2[N],ss[N],sp=0,ab[N][2];
void f1(int w){
	for(int i=0;i<e[w].size();++i)f1(e[w][i]);
	++tk;
	for(int i=0;i<e[w].size();++i)ed[v1[e[w][i]]]=tk;
	for(v1[w]=0;ed[v1[w]]==tk;++v1[w]);
}
void f2(int w){
	ss[++sp]=w;
	f1(w);
	for(v2[w]=v1[w]+1;ed[v2[w]]==tk;++v2[w]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",fa+i),++deg[fa[i]];
	std::queue<int>q;
	for(int i=1;i<=n;++i)if(!deg[i])q.push(i);
	while(q.size()){
		int w=q.front(),f=fa[w];q.pop();
		if(!--deg[f])q.push(f);
		e[f].push_back(w);
	}
	for(int i=1;i<=n;++i)if(deg[i]){
		for(int w=i;deg[w];deg[w]=0,f2(w),w=fa[w]);
	}
	ss[0]=ss[sp];
	for(int t=0;t<2;++t){
		ab[0][t]=1,ab[0][t^1]=0;
		for(int i=1;i<=sp;++i){
			int w=ss[i],u=ss[i-1];
			ab[i][0]=ab[i][1]=0;
			for(int j=0;j<2;++j)if(ab[i-1][j]){
				int v=j?v2[u]:v1[u];
				ab[i][v==v1[w]]=1;
			}
		}
		if(ab[sp][t])return puts("POSSIBLE"),0;
	}
	return puts("IMPOSSIBLE"),0;
}

Measured memory_bytes: 12288
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();
		sc.close();
		if(a == 1) {
			a = 14;
		}
		if(b == 1) {
			b = 14;
		}
		if(a > b) {
			System.out.println("Alice");
		}else if(a < b) {
			System.out.println("Bob");
		}else {
			System.out.println("Draw");
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>
#include <complex>

using int64 = long long;
using uint64 = unsigned long long;

using namespace std;

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

    int h, w, k;
    cin >> h >> w >> k;

    vector<string> s(h);
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }

    constexpr int INF = (1 << 28);

    int ans = INF;
    for (int mask = 0; mask < (1 << (h - 1)); mask++) {
        int num = 1;
        vector<int> ids(h);
        for (int r = 0; r < h; r++) {
            if (r > 0 && ((mask >> (r - 1)) & 1)) {
                num++;
            }
            ids[r] = num - 1;
        }

        int score = num - 1;
        vector<int> counts(num, 0);
        for (int c = 0; c < w + 1; c++) {
            vector<int> add_counts(num, 0);

            bool ok = true;
            for (int r = 0; r < h; r++) {
                if (counts[ids[r]] > k) {
                    goto done;
                }
                if (c < w && s[r][c] == '1') {
                    add_counts[ids[r]]++;
                    ok = ok && (counts[ids[r]] + add_counts[ids[r]] <= k);
                }
            }
            if (!ok) score++;
            for (int i = 0; i < num; i++) {
                if (ok) counts[i] += add_counts[i];
                else counts[i] = add_counts[i];
            }
        }
        ans = min(ans, score);
        done:
            ;
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, s: str):

    # DP[i][j]はi文字目までをみたす順列のうち、最後がjで終わるものの個数
    DP = [[0]*(N+1) for _ in range(N)]
    DP[0][1] = 1

    for i in range(1, N):
        acc = list(accumulate(DP[i-1]))
        for j in range(1, (i+1)+1):
            if s[i-1] == "<":
                DP[i][j] = acc[j-1]
            else:
                DP[i][j] = acc[i+1] - acc[j-1]
            DP[i][j] %= MOD

    print(sum(DP[N-1]) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = next(tokens)  # type: str
    solve(N, s)


if __name__ == '__main__':
    main()


Measured memory_bytes: 116380
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int a[100010],n,cnt=1;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++)
	{
		if(a[i]!=a[i+1])
		{
			cnt++;
		}
	}
	if(cnt&1)
	{
		printf("%d\n",cnt);
	}
	else
	{
		printf("%d\n",cnt-1);
	}
}

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

template <class T> inline bool chmin(T& a, T b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N;
  cin >> N;
  vector<int> ts(N + 1);
  ts[0] = 0;
  int w;
  for(int i = 1; i <= N; ++i) {
    cin >> w;
    ts[i] = ts[i - 1] + w;
  }
  int ans = 1000000;
  for(int t = 1; t < N; ++t) {
    int s1 = ts[t];
    int s2 = ts[N] - ts[t];
    chmin(ans, abs(s1 - s2));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	while(1){
		char d;
		char ans[101000];
		char f[1010000],g[101000];
		int n;
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>d;
			f[i]=d;
			cin>>d;
			g[i]=d;
		}
		int s;
		cin>>s;
		for(int i=0;i<s;i++){
			cin>>d;
			ans[i]=d;
			for(int j=0;j<n;j++){
				if(ans[i]==f[j]){
					ans[i]=g[j];
					break;
					
				}
			}
		}
		for(int i=0;i<s;i++){
			cout<<ans[i];
		}
		cout<<endl;
	}
}

Measured memory_bytes: 3076
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.ABC118
{
    class B
    {
        public static void Solve()
        {
            var s = Console.ReadLine().Split(' ');
            int n = int.Parse(s[0]);
            int m = int.Parse(s[1]);

            var c = Enumerable.Repeat(0, m).ToArray();
            for(int i = 0; i < n; i++)
            {
                s = Console.ReadLine().Split(' ');
                int k = int.Parse(s[0]);
                for(int j = 1; j <= k; j++)
                {
                    int a = int.Parse(s[j]);
                    c[a-1]++;
                }
            }

            Console.WriteLine(c.Count(x => x == n));
        }
    }
}
namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            ABC118.B.Solve();
        }
    }
}


Measured memory_bytes: 13268
//ABC 128 D enque

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

typedef long long ll;
ll n,k,v[55];

ll solve(ll l,ll r)
{
   vector<ll> t;
   
   for(int i=0;i<=l;i++)    
      t.push_back(v[i]);
   
   for(int i=r;i<n;i++)
      t.push_back(v[i]);
   
   sort(t.begin(),t.end()); 
   
   ll lim=k-t.size();          
   if(lim<0)
       return 0;        
   
   ll sum=0;
   for(int i=0;i<t.size();i++){
      if(t[i]<0&&lim>0){   
         lim--;
      }else                 
	     sum+=t[i];
   }
   
   return sum;
}

int main()
{
   cin>>n>>k;
   
   for(int i=0;i<n;i++)  cin>>v[i];
   
   ll ans=0;
   
   for(int i=-1;i<n;i++)
     for(int j=i+1;j<=n;j++){
        ans=max(ans,solve(i,j));
     }
   
   cout<<ans<<endl;
   return 0;
}



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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){

  while(x->left!=NIL){
    x=x->left;
  }

  return x;

}

Node treeSearch(Node u, int k){

  if(u==NIL || k==u->key) return u;
  if(k<u->key) return treeSearch(u->left,k);
    else return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){

  if (x->right!=NIL) return treeMinimum(x->right);
    
  root=x->parent;

  while(root!=NIL && x==root->right){
    x=root;
    root=root->parent;
  }
  return root;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z->left==NIL || z->right==NIL){ y=z;
   }
  else y=treeSuccessor(z);
 
  if(y->left!=NIL) {x=y->left;
   }
  else x=y->right;

  if(x!=NIL) {x->parent=y->parent;
    }
  if(y->parent==NIL){ root=x;
    }
  else if(y==y->parent->left) {y->parent->left=x;
    }
  else y->parent->right=x;

  if(y!=z) {z->key=y->key;
  }
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key) x=x->left;
    else x=x->right;
    z->parent=y;
  }

    if(y==NIL) root=z;
    else if (z->key<y->key)
		 y->left=z;
    else y->right=z;

}

void inorder(Node u){

  if(u!=NIL) {

    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);

  }

}
void preorder(Node u){

  if(u!=NIL){

  printf(" %d",u->key);
 preorder(u->left);
 preorder(u->right);

  }

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

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

lli n, k, s;

int main(void){
	cin >> n >> k >> s;
	queue<lli> q;
	while(k--) q.push(s);
	while(q.size() < n){
		if(s < 1e9) q.push(s+1);
		else q.push(1);
	}
	while(!q.empty()){
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 4452
#include <iostream>
#include <sstream>
#include <stdio.h>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
#include <map>
#define FORi(N) for(int i=0;i<N;++i)
#define FORj(N) for(int j=0;j<N;++j)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll gcd(ll m,ll n){
  if(n==0)return abs(m);
  return(gcd(n,m%n));
}
void putYN(bool b){
  if(b){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}
int main(){
  ll N;
  cin>>N;
  vector<ll> ae(5);
  FORi(5){
    cin>>ae[i];
  }
  ll time=0;
  ll num=0;
  FORi(5){
    ll tmp = 4+((N-1)/(ae[i])+1);
    time=max(tmp,time);
  }
  cout<<time<<endl;
  return 0;
}


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

int main(void) {
	int x, n;
	int p[100 + 1] = { 0 };
	int i, flag = 1;
	int isOK = 1;
	int ans1, ans2;

	scanf("%d", &x);
	scanf("%d", &n);

	if (n == 0) {
		printf("%d\n", x);
		return 0;
	}

	for (i = 1; i < n+1; i++) {
		scanf("%d", &p[i]);
	}

	ans1 = x;
	ans2 = x;
	for (i = 1; i < n + 1; i++) {
		isOK = 1;
		if (p[i] == ans1) {
			ans1++;
			flag = 0;
			isOK = 0;
		}
		if (p[i] == ans2) {
			ans2--;
			flag = 0;
			isOK = 0;
		}
		if (isOK == 0) {
			i = 0;
		}
	}

	if (flag == 1) {
		printf("%d\n", x);
	}
	else {
		if (abs(x - ans2) == abs(x - ans1)) {
			printf("%d\n", ans2);
		}
		else if (abs(x - ans2) < abs(x - ans1)) {
			printf("%d\n", ans2);
		}
		else {
			printf("%d\n", ans1);
		}
	}

	return 0;
}

Measured memory_bytes: 1736
/*
Dont BLUNDER
*/

// #pragma GCC optimize("O3")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;


 */
//#define d long double
#define int long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define pi acos(-1)

#define init(x,a) memset(x,a,sizeof(x))
#define all(c) c.begin(),c.end()
int const mod1 = 998244353;
int const mod = 1000000007;
#define bitcount(x)       __builtin_popcountll(x)
#define l first
#define r second
const int inf = LLONG_MAX;
int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ) {stringstream ss; ss << number; return ss.str();}
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define haha ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// * Using PBDS *
/*typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
               os; */

struct cmp
{
	bool operator() (pii a, pii b) {
		return (a.l < b.l);
	}
};

int modexp(int x, int n) {
	if (n == 0) {
		return 1;
	}
	else if (n & 1) {
		return (modexp((x * x) % mod, n / 2) % mod * x % mod) % mod;
	}
	else {
		return (modexp((x * x) % mod, n / 2) % mod);
	}
}

int modinv(int n)
{
	return modexp(n, mod - 2);
}

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



signed main()
{

// #ifndef ONLINE_JUDGE

// 	freopen("inp.txt", "r", stdin);

// 	freopen("out1.txt", "w", stdout);
// #endif
	haha
	int n;
	cin >> n;
	int ans = modexp(10, n );
	//cout << ans << endl;
	int ans1 = 2 * modexp(9, n );
	ans1 %= mod;
	ans = (ans - ans1 + mod) % mod;

	ans1 = modexp(8, n );;
	ans %= mod;
	ans = (ans + ans1 + mod) % mod;
	cout << ans;





}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    vector<pair<ll, ll>> p(n, {0, 0});
    rep(i, n)
    {
        cin >> p[i].second >> p[i].first;
    }

    sort(ALL(p));
    multiset<ll> s;
    if (p[0].first < p[0].second)
    {
        cout << "No" << endl;
        return 0;
    }

    s.insert(p[0].first - p[0].second);
    ll last = *s.begin();
    rep(i, 1, n)
    {
        ll dur = p[i].first;
        ll cost = p[i].second;
        ll newval = last + (dur - p[i - 1].first);
        s.erase(last);
        s.insert(newval);
        auto itr = s.lower_bound(cost);
        if (itr == s.end())
        {
            cout << "No" << endl;
            return 0;
        }
        ll val = *itr;
        itr++;

        s.erase(val);
        s.insert(val - cost);
        if (val == newval)
        {
            last = val - cost;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
#define PI 3.14159265358979323846
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

const int MAX = 12000;
bool can[MAX];

int main(){
  int ans = 0;
  int n, s;

  scanf("%d", &n);
  can[0] = true;
  for(int i = 0;i < n;++i){
    scanf("%d", &s);
    for(int i = MAX;i >= 0;--i)
      if(can[i]) can[i + s] = true;
  }

  for(int i = 0;i < MAX;++i)
    if(can[i] && i % 10 != 0)
      relaxMax(ans, i);

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

  return 0;
}


Measured memory_bytes: 256
// Karm Karta ja, Phal Ki Chinta na Kar:)
#include <bits/stdc++.h>
using namespace std;
#include<stdio.h>
typedef long long int ll;
#define INF 1e18+3
#define M 1000000007
#define PI 3.14159265358979323846
ll fast(ll n,ll a,ll m)
{
    if(n==0)
        return 1;
    else if(n==1)
        return a;
    else
    {
        ll r=fast(n/2,a,m);
        if(n%2==0)
            return (((r%m)*(r%m))%m);
        else
            return (((((r%m)*a)%m)*r)%m);
    }
}
int main()
{
    ll a,b;
    cin>>a>>b;
    ll g=__gcd(a,b);
    a/=g;
    a*=b;
    cout<<a;

}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

#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++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/



//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

/*最小公倍数*/
template<typename T>
T lcm(T x, T y) {
	T tmp = gcd(x, y);
	return x * y / tmp;
}

int cost[55][55];
char mp[55][55];
int check[55][55];


int main() {

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

	int h, w;
	cin >> h >> w;

	int black = 0;
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cost[i][j] = INF;
			cin >> mp[i][j];
			if (mp[i][j] == '#') {
				cost[i][j] = INF;
				check[i][j] = -1;
				black++;
			}
			else
			{
				check[i][j] = 0;
			}
		}
	}

	
	queue<pii> que;

	que.push(pii(0, 0));
	cost[0][0] = 0;


	while (!que.empty()) {

		int y = que.front().first;
		int x = que.front().second;
		que.pop();
		
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (0 <= ny && ny < h && 0 <= nx && nx < w && mp[ny][nx] != '#' && check[ny][nx] == 0) {

				que.push(pii(ny, nx));
				check[ny][nx] = 1;
				cost[ny][nx] = min(cost[ny][nx], cost[y][x] + 1);
			}
		}
	}


	if (cost[h-1][w-1] == INF) {
		cout << "-1" << endl;
	}
	else
	{
		cout << h * w - black - cost[h-1][w-1] - 1 << endl;
	}




	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int ans = 0;
    for (int i = 0; i <= N; i++){
        int j = i/10000 + ((i%10000)/1000) + ((i%1000)/100) + ((i%100)/10) + (i%10);
        if (A <= j && j <= B) ans += i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;

#define for0(i, n) for (ll i = 0; i < (ll)(n); ++i) // 0 based indexing
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i) // 1 based indexing
#define forc(i, l, r) for (ll i = (ll)(l); i <= (ll)(r); ++i) // closed interver from l to r r inclusive
#define forr0(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i) // reverse 0 based.
#define forr1(i, n) for (ll i = (ll)(n); i >= 1; --i) // reverse 1 based

#define ff first
#define ss second
#define pb push_back

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector < ll > hash;
  hash.assign(3,0);
  ll a,b;
  cin >> a >>b;
  hash[a-1] = 1;
  hash[b-1] = 1;
  for0(i,3) { if(hash[i] == 0) cout << i+1<<endl; }
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define pb push_back
#define ll long long
#define all(x) x.begin() , x.end()
#define mod(x,m) ((x%m + m )%m)
#define rep(i, start, end) for(int i = start; i < end; ++i)
using namespace std;
using namespace __gnu_pbds;
void OJ();

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

int mp[1000009] , a[1000009];

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

    int n; cin >> n; vector<int> vec(n);
    for ( int& i : vec ) cin >> i,mp[i]++;
    sort( all(vec) );

    int cnt = 0;
    for (int i = 1; i <= vec.back(); ++i){
        if ( mp[i] > 1 ) a[i]++;
        for ( int j = i+i; j <= vec.back(); j += i ){
            if ( mp[i] > 0 ) a[j]++;
        }
    }

    for ( int i = 1; i <= 1e6; ++i ){
        if ( mp[i] > 0 && a[i] > 0 ) cnt += mp[i];
    }

    cout << n - cnt;
    return 0;
}

void OJ(){
#ifndef ONLINE_JUDGE
    freopen( "C:\\Users\\ehab\\Desktop\\Code Forces\\CF\\in.txt" , "r" , stdin  );
    // freopen( "C:\\Users\\ehab\\Desktop\\Code Forces\\CF\\out.txt", "w" , stdout );
#endif // ONLINE_JUDGE
}
/*ll binEXP( ll x , ll pw , ll MOD )
{ ll res=1; while(pw>0){ pw%2 ? res *= x : 0; x *= x; x%=MOD; pw /= 2; res%= MOD; } return res%=MOD; }*/

Measured memory_bytes: 11788