akhauriyash/Code-Regression huggingface dataset:
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

fn main() {
    input! {
        h:usize,w:usize,
        a:[Chars;h],
    }
    let mut v = vec![vec![false; w]; h];

    let mut q = VecDeque::new();
    q.push_back((0, 0));
    while let Some(x) = q.pop_front() {
        v[x.0][x.1] = true;
        if x.0 + 1 < h && a[x.0 + 1][x.1] == '#' {
            q.push_back((x.0 + 1, x.1));
        } else if x.1 + 1 < w && a[x.0][x.1 + 1] == '#' {
            q.push_back((x.0, x.1 + 1));
        }
    }
    if !v[0][0] || !v[h - 1][w - 1] {
        println!("Impossible");
        return;
    }
    let mut ok = true;
    for i in 0..h {
        for j in 0..w {
            if a[i][j] == '#' {
                if !v[i][j] {
                    println!("Impossible");
                    return;
                }
            }
        }
    }
    println!("Possible");
}


Measured memory_bytes: 2200
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
 
const int maxn = 110;
 
ll n;
ll a[maxn];
ll ans;
 
int main()
{
	scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	
	ans=0ll;
	a[0]=0;
	for(int i=n;i>=1;i--)
	{
		ll x=a[i-1],y=a[i];
		if(y-x>=n)
		{
			ll tmp=n+1ll; //n-i+1
			ll temp=(y-x-(n-1ll)+tmp-1ll)/tmp;
			
			ll dec=temp*(ll)(n-i+1); ans+=dec;
			for(int j=1;j<i;j++) a[j]+=dec;
			for(int j=i;j<=n;j++) a[j]-=(ll)i*temp;
		}
		sort(a+1,a+n+1);
	}
	while(a[n]>=n)
	{
		ll temp=a[n]/n; ans+=temp; a[n]-=temp*n;
		for(int i=1;i<n;i++) a[i]+=temp;
		sort(a+1,a+n+1);
	}
	printf("%lld\n",ans);
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

	int a, b, c;
	cin>>a>>b>>c;

	int cnt = 0;
	for(int x = a;x <= b;x++){
	if(c % x == 0) cnt++;
	}

	cout<<cnt<<endl;

	return 0;
}
	


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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#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 ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 	2 * (int)1e5 + 1000;
int n, k, r, s, p, ans;
string t;
 
char judge(char x) {
	if (x == 'r') return 'p';
	else if (x == 'p') return 's';
	else if (x == 's') return 'r';
}
void add(char x) {
	if (x == 'r') ans += r;
	else if (x == 'p') ans += p;
	else if (x == 's') ans += s;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
#endif
	
	ans = 0;
	cin >> n >> k;
	cin >> r >> s >> p;
	cin >> t;
	fore(i, 0, k - 1) {
		char win = judge(t[i]);
		add(win);
	}
	fore(i, 0, k - 1) {
		int now = 1;
		for (int j = i + k; j < n; j += k) {
			if (j >= n) break;
			char win = judge(t[j]);
			if (t[j] == t[j - k]) {
				if (now % 2 == 0) add(win); 
				++now;
			} else {
				add(win);
				now = 1;
			}
		}
	}
	cout << ans << '\n';
		
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 512
from math import factorial

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


def sq(a, b, mod):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return sq(a, b // 2, mod)**2 % mod
    else:
        return sq(a, b - 1, mod) * a % mod


def nCk(n, k, mod=10 ** 9 + 7):
    x = max(k, n - k)
    y = min(k, n - k)
    kkai = 1
    for i in range(2, y + 1):
        kkai = (kkai * i) % mod
    nkkai = 1
    for i in range(x + 1, n + 1):
        nkkai = (nkkai * i) % mod
    answer = sq(kkai, mod - 2, mod) * nkkai % mod
    return answer


mod = 10 ** 9 + 7

s = pow(2, n, mod) - 1 - nCk(n, a, mod) - nCk(n, b, mod)

s = (s + mod) % mod

print(s)


Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
    int r,c,i,j;
    int table[110][110]={};
    
    scanf("%d %d",&r,&c);
    
    
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&table[i][j]);
                table[i][c]+=table[i][j];
                table[r][j]+=table[i][j];
                table[r][c]+=table[i][j];
        }
    }
    
    for(i=0;i<=r;i++){
        for(j=0;j<=c;j++){
        printf("%d",table[i][j]);
        if(j!=c)printf(" ");
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2088
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
void read (long long &x) { 
	long long f = 1; x = 0; char s = getchar (); while (s < '0' || s > '9') {if (s == '-') f = -1; s = getchar ();}
	while (s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = getchar ();} 
	x *= f;
}
struct st {
	long long l, r, id;
}k[1000005];
long long a[1000005], bit[1000005], n ,m;
bool cmp (st x, st y) {
	return x.r < y.r;
}
long long lowbit (long long x) {
	return x & (-x);
}
void add (long long x, long long y) {
	for (long long i = x; i <= n; i += lowbit (i)) bit[i] += y;
}
long long sum (long long x) {
	long long cnt = 0;
	for (long long i = x; i >= 1; i -= lowbit (i)) cnt += bit[i];
	return cnt;
}
long long vis[1000005], ans[1000005];
int main () {
	read (n);read (m);
	for (long long i = 1; i <= n; i++) read (a[i]);
	for (long long i = 1; i <= m; i++) read (k[i].l), read (k[i].r), k[i].id = i;
	sort (k + 1, k + 1 + m, cmp);
	long long last = 1;
	for (long long i = 1; i <= m; i++) {
		for (long long j = last; j <= k[i].r; j++) {
			if (vis[a[j]]) add (vis[a[j]], -1);
			add (j, 1);
			vis[a[j]] = j;
		}
		last = k[i].r + 1;
		ans[k[i].id] = sum (k[i].r) - sum (k[i].l - 1);
	}
	for (long long i = 1; i <= m; i++) printf ("%lld\n", ans[i]);
	return 0;
}

Measured memory_bytes: 30996
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int>d(N);
	for (int i = 0; i < N; i++)cin >> d[i];
	sort(d.begin(), d.end());
	cout << d[N / 2] - d[N / 2 - 1];
}


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

template <int MOD>
struct ModInt {
    using lint = long long;
    using mint = ModInt<MOD>;

    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // assignment
    ModInt& operator=(const ModInt& x) {
        if (this != &x) { this->val = x.val; }
        return *this;
    }

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt operator~() const {
        // non-recursive extended euclidean algorithm
        int s = val, t = MOD;
        mint sx = 1, sy = 0, tx = 0, ty = 1;
        while (s % t != 0) {
            int div = s / t;
            s -= t * div;
            sx -= tx * div;
            sy -= ty * div;

            std::swap(s, t);
            std::swap(sx, tx);
            std::swap(sy, ty);
        }
        return mint(tx);
    }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= ~x; }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<mint>>
        dp(n, std::vector<mint>(n + 1, 0)),
        ndp(n, std::vector<mint>(n + 1));
    dp[n - 1][1] = 1;
    // 孤立点の数，頭の強連結成分のサイズ

    for (int i = 0; i < m; ++i) {
        for (auto& v : ndp) {
            std::fill(v.begin(), v.end(), 0);
        }

        for (int s = 0; s < n; ++s) {
            for (int t = 1; s + t <= n; ++t) {
                int u = n - (s + t);
                if (s > 0) {
                    // 孤立点のどれかに移動
                    ndp[s - 1][t] += dp[s][t] * s;
                }

                // 頭に移動
                ndp[s][t + u] += dp[s][t] * t;

                // それ以外に移動
                ndp[s][t] += dp[s][t] * u;
            }
        }

        std::swap(dp, ndp);
    }

    std::cout << dp[0][n] << std::endl;
    return 0;
}


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

int main() {
  long long N, Y=1000, K=0;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A.at(i);
  rep(i, N-1){
    if(A.at(i)<A.at(i+1)){
      K=Y/A.at(i);
      Y+=(A.at(i+1)-A.at(i))*K;
    }
  }
 cout << Y << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <functional>
#include <sstream>
using namespace std;

#define REP(i,a,n) for(int i=(a);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()

int main(){
	string in1,in2;
	int t; scanf("%d",&t);
	while(t--){
		char str[100];
		cin>>in1>>in2;
		if( in1.size()>80 || in2.size()>80 ){
			puts("overflow"); continue;
		}
		reverse(all(in1)); reverse(all(in2));
		int k = 0;
		int i;
		for(i=0; i<min(in1.size(),in2.size()); i++){
			k = (in1[i]-'0')+(in2[i]-'0') + k;
			str[i] = (k%10)+'0';
			k /= 10;
		}
		if( i==in1.size() ){ //in2
			for(; i<in2.size(); i++){
				k = (in2[i]-'0')+k;
				str[i] = (k%10)+'0';
				k /= 10;
			}
		}else{ //in1
			for(; i<in1.size(); i++){
				k = (in1[i]-'0')+k;
				str[i] = (k%10)+'0';
				k /= 10;
			}
		}
		if( k!=0 )str[i++] = k+'0';
		str[i] = 0;
		if( i>80 ){
			puts("overflow"); continue;
		}
		reverse(str,str+i);
		puts(str);
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define rush() int T;scanf("%d",&T);while(T--)
#define mm(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define pf(a) printf("%d\n",a)
#define pf2(a,b) printf("%d %d\n",a,b)
#define p_f(a) printf("%d ",a)
#define fi first
#define se second
#define db double
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const db eps=1e-9;
int a,b;
int main()
{
    cin>>a>>b;
	int ans=ceil(a*1.0/b);
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    cin>>s;
    n=s.size();
    int b[n];
    b[0]=0;
    if(s[0]=='B')
        b[0]+=1;
    
    else
        b[0]=0;
    for(int i=1;i<n;i++)
    {
        b[i]=b[i-1];
        if(s[i]=='B')
            b[i]+=1;
    }
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='W') ans+=(i-1>=0?b[i-1]:0);
    }
    cout<<ans;
    return 0;
}

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()
S=''
for i in range(H):
    S+=input()

C=Counter(S)
cnt1=cnt2=0
# 縦横とも偶数
if H%2==0 and W%2==0:
    for k, v in C.items():
        if v%4!=0:
            No()
            exit()
    # 全て4つ組
    Yes()
# 縦偶数
elif H%2==0:
    for k, v in C.items():
        if v%4!=0:
            if v%2==0:
                cnt2+=1
            else:
                No()
                exit()
    # 2つ組がH/2以下で残りが4つ組
    if cnt2<=H//2:
        Yes()
    else:
        No()
# 横偶数
elif W%2==0:
    for k, v in C.items():
        if v%4!=0:
            if v%2==0:
                cnt2+=1
            else:
                No()
                exit()
    # 2つ組がW/2以下で残りが4つ組
    if cnt2<=W//2:
        Yes()
    else:
        No()
# 両方奇数
else:
    for k, v in C.items():
        if v%4!=0:
            if v%2==0:
                cnt2+=1
            elif v%3==0:
                cnt1+=1
                cnt2+=1
            else:
                cnt1+=1
    # 1つ組1つ、2つ組が(H+W)/2-1以下で残りが4つ組
    if cnt1==1 and cnt2<=(H+W)//2-1:
        Yes()
    else:
        No()


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
    int n, nn, nr;
    cin >> nn;
    n = (1 << nn);

    multiset <int, greater<int> > slimes, added;
    for (int i = 0; i < n; i++) {
        cin >> nr;
        slimes.insert(nr);
    }

    added.insert(*slimes.begin());

    for (int generation = 0; generation < nn; generation ++) {
        vector <int> children;
        for (auto &&slm :added) {
            if (slimes.upper_bound(slm) == slimes.end()) {
                cout << "No\n";
                return 0;
            }
            children.push_back(*(slimes.upper_bound(slm)));
            slimes.erase(slimes.upper_bound(slm));
        }

        for (auto &&newSlime: children) {
            added.insert(newSlime);
        }
    }

    cout << "Yes\n";
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    string ans = "";
    rep(i,n) ans += "ACL";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
N,K = map(int,input().split())
A=list(map(lambda x:int(x)-1,input().split()))

loop_start=-1
visited={0}
cur=0
while True:
    cur=A[cur]
    if cur in visited:
        loop_start=cur
        break
    else:
        visited.add(cur)


assert loop_start!=-1
#print("start=>",loop_start)

before_loop=0
before_path=[0]
cur=0
while cur!=loop_start:
    cur=A[cur]
    before_loop+=1
    before_path.append(cur)
#print("bef",before_loop)

loop_path=[loop_start]
cur=A[loop_start]
while cur!=loop_start:
    loop_path.append(cur)
    cur=A[cur]
#print("loop=>",loop_path)
#print("llop len=>",len(loop_path))

if K>=before_loop:
    K-=before_loop
    print(loop_path[K%len(loop_path)]+1)
else:
    print(before_path[K]+1)



Measured memory_bytes: 126464
#include <iostream>
#include "string"
#define REP(i, n) for(int i=0;i<n;++i)

typedef long long ll;
using namespace std;
int main(){
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if (u == s) {
        a--;
    } else {
        b--;
    }
    cout << a << " " << b << endl;
    return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
#define INF = 1000000100;

int main(){
    ll A,B,K;
    cin >> A >> B >> K;
    if(K<=A) cout << A-K << " " << B << endl;
    else if(A<K && K<=A+B) cout << 0 << " " << B-(K-A) << endl;
    else cout << 0 << " " << 0 << endl;
    return 0;

}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[6];
int vis[1000];
int main(){
	int n;
	scanf("%s",a);
	n=strlen(a);
	for(int i=0;i<n;i++){
		vis[a[i]]++;
	}
	for(int i=0;i<4;i++)
		if(vis[a[i]]!=2){
			puts("No");
			return 0;
		}
	puts("Yes");
	return 0;
}

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

int  main()
{
    int n,k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i =0;i<n;i++)
        cin >> v[i];
        
    vector<bool> dp(k+1,false);
    
    for(int i = 0;i <= k; i++)
    {
        for(int j = 0;j < n ;j++)
        {
            if(i - v[j] < 0)
                break;
            else if(!dp[i - v[j]])
                dp[i] = true;
        }
    }
    if(dp[k])
        cout << "First" << endl;
    else
        cout << "Second" << endl;
    return 0;
}

Measured memory_bytes: 3564
import java.util.Scanner;

public class Main{
	 public static void main(String[] args) {
		 String result;
	        Scanner scan = new Scanner(System.in);
	        if (scan.nextInt() >= 3200) {
	            result = scan.next();
	        } else {
	            result = "red";
	        }
	        System.out.println(result);
	    }
	}

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

int k, x;

class Problem{
public:
  string solve(int k, int x){
    int res = k * 500;
    if(res >= x)return "Yes";
    else return "No";
  }
};

int main(){
  cin>>k>>x;
  Problem A;
  cout<<A.solve(k, x)<<endl;  
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int SZ = 200200;
class UF {
public:
	int P[SZ + 1];
	UF() : P() {
		rep1(i, SZ) P[i] = -1;
	}
	int find(int A) {
		if (P[A] < 0) return A;
		return P[A] = find(P[A]);
	}
	bool unite(int A, int B) {
		int a = find(A);
		int b = find(B);
		if (a == b) return false;
		if (P[a] > P[b]) swap(a, b);
		P[a] += P[b];
		P[b] = a;
		return true;
	}
} uf;

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


	int N;
	cin >> N;

	int Y[200000], id[200000];
	rep(i, N) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		Y[x] = y;
		id[x] = i;
	}

	set<pair<int, int>> ST;
	for (int x = N - 1; x >= 0; x--) {
		int y = Y[x];
		int i = id[x];

		auto itr = ST.lower_bound(mp(y, 0));
		if (itr == ST.end()) {
			ST.insert(mp(y, i));
		}
		else {
			pair<int, int> saigo;
			for (; itr != ST.end(); itr++) {
				uf.unite(i + 1, (*itr).second + 1);
				saigo = *itr;
			}
			ST.erase(ST.lower_bound(mp(y, 0)), ST.end());
			ST.insert(saigo);
		}
	}

	rep1(i, N) {
		co(-uf.P[uf.find(i)]);
	}

	Would you please return 0;
}

Measured memory_bytes: 7228
/***********************************************************
 *This code By @1353055672(Ligen)                          *
 *[Warning]You're not excepted to understand this code!    *
 *NOIP 2019 RP++                                           *
 ***********************************************************/
//#pragma GCC optimize(3)
#define ADD_STACK int size = 512 << 20;\
	char *pp = (char*)malloc(size) + size;  \
	__asm__("movl %0, %%esp\n" :: "r"(pp))
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<fstream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<vector>
#define ll long long
#define ull unsigned long long
#define mn 200020
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<(0))?(-(x)):(x))
#define infll (ll)(1e18)
#define infint (1<<30)
#define mod (int)(1e9+7)
#define FOR(a,b,c) for (register int a=b;a<=c;++a)
#define FORD(a,b,c) for (register int a=b;a>=c;--a)
using namespace std;
//char buf[1<<20],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
	ll x=0,f=1;char c;
	for(c=getchar();c<'0'||c>'9';f=((c=='-')?-1:f),c=getchar());
	for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());return x*f;
}
template<typename T>
inline void write(T a){
	if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
	while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
}
inline void write_(){return;}
template<typename T,typename... Args>
inline void write_(T a,Args... b){write(a);putchar(' ');write_(b...);}
inline void writeln(){putchar('\n');return;}
template<typename T,typename... Args>
inline void writeln(T a,Args... b){write(a);putchar(' ');writeln(b...);}
//need c++11

//inline void write(ll a){
//    if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
//    while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
//}
//inline void write_(ll a){write(a);putchar(' ');}
//inline void writeln(ll a){write(a);putchar('\n');}
inline ll gcd(ll a,ll b){return a==0?b:gcd(b%a,a);}
inline ll lcm(ll a,ll b){return 1ll*a/gcd(a,b)*b;}
inline ll Pow(ll n,ll a){ll b=1;while(a){if(a&1)b=1ll*b*n%mod;n=1ll*n*n%mod;a>>=1;}return b;}
//---------------------Head Files--------------------------//
#define int ll
int x[20][20];
signed main(){
	#ifdef _WIN32
		// freopen("0.in","r",stdin);
		// freopen("0.out","w",stdout);
		long double be=clock();
	#endif
	int n=read(),m=read();
	FOR(i,1,n)FOR(j,1,m)x[i][j]=read();
	int num=0,sq=0,ans=0;
	FOR(i,1,n)FOR(j,i+1,n){
		num=0;
		FOR(k,1,m)num+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
		sq=sqrt(num);
		if(sq*sq==num)++ans;
	}
	writeln(ans);
	#ifdef _WIN32
		long double en=clock();
		printf("Time: %.0Lfms\n",en-be);
		fclose(stdin);fclose(stdout);
	#endif
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    string s;
    cin >> s;
    s+="R";
    vector<int> a(s.length(),0);
    int countr=0;
    int countl=0;
    int lx,rx=-1;
    for(int i=0; i+1<s.length(); i++){
        if(s[i]=='R'&&s[i+1]=='L'){
            countr++;
            rx=i;
            lx=i+1;
            a[rx]=1;a[lx]=1;
            a[rx]=(countr+1)/2;
            a[lx]=(countr)/2;
            countr=0;
        }else if(s[i]=='L'&&s[i+1]=='R'){
            countl++;
            a[rx]+=(countl)/2;
            a[lx]+=(countl+1)/2;
            countl=0;
        }else if(s[i]=='R'){
            countr++;
        }else if(s[i]=='L'){
            countl++;
        }
    }
    for(int i=0; i+2<a.size(); i++)cout << a[i] << " ";
    cout << a[a.size()-2] << endl;
}

Measured memory_bytes: 1024
#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

#define ll long long

const ll mod = (ll)1e9 + 7;

using namespace std;

// done[i][j] := ivs jをやったかどうか
bool done[1001][1001];
// next[i] := iが何試合やったか
int nx[1001];
// iが今日試合をしたか
bool fighted[1001];


signed main() {
	int n; cin >> n;

	vector<vector<int>> a(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n - 1; ++j) {
			int aij; cin >> aij;
			a[i].push_back(aij);
		}
	}

	ll ans = 0;
	while (1) {
		for (int i = 1; i <= n; ++i)
			fighted[i] = false;
		int ok = 0;
		for (int i = 1; i <= n; ++i) {
			if (fighted[i]) continue;
			if (nx[i] == n - 1) continue;
			if (fighted[a[i - 1][nx[i]]]) continue;
			if (a[a[i - 1][nx[i]] - 1][nx[a[i - 1][nx[i]]]] != i) continue;
			fighted[i] = true;
			nx[a[i - 1][nx[i]]]++;
			fighted[a[i - 1][nx[i]]] = true;
			done[i][a[i - 1][nx[i]]] = true;
			done[a[i - 1][nx[i]]][i] = true;
			nx[i]++;
			ok++;
		}
		if (ok == 0) break;
		ans++;
	}

	bool exist = true;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			exist = exist && done[i][j];
		}
	}

	if (!exist) {
		cout << -1 << endl;
	}
	else {
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(b<c || d<a){
        cout << 0 << endl;
    }
    else if(b>=d && c>=a) cout << d-c << endl;
    else if(d>b && a>c) cout << b-a << endl;
    else if(b-c>=d-a) cout << d-a << endl;
    else if(d-a>b-c) cout << b-c << endl;
}


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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
// const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
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);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  // a+2√ab + b < c
  //2 √ab < c
  int64 a, b, c;
  cin >> a >> b >> c;
  c -= a + b;
  if(c > 0 && (__int128_t) 4 * a * b < (__int128_t) c * c) cout << "Yes\n";
  else cout << "No\n";
}


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

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1e9+7
#define LINF (long long)4e18



int main(){
    int a,b;
    cin >> a >> b;
    int c = b-a;
    int sum = 0;
    rep(i,c){
        sum += i+1;
    }
    int ans = sum - b;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long X, A, B;
int main() {
    cin >> X >> A >> B;
    if(A >= B) {
        cout << "delicious" << endl;
    }else {
        if((B-A) <= X) {
            cout << "safe" << endl;
        }else {
            cout << "dangerous" << endl;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,w;
    cin>>n>>w;
    ll p[n+1],v[n+1];
    for(int i=1;i<=n;i++)cin>>p[i]>>v[i];
    ll dp[n+1][w+1];
    for(int i=0;i<=n;i++){
        dp[i][0] = 0;
    }
    for(int i=0;i<=w;i++){
        dp[0][i] = 0;
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            if( j - p[i] >= 0){
                dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-p[i]]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
            //cout<<dp[i][j]<<" "<<i<<" "<<j<<" "<<v[i]<<" "<<p[i]<<"\n";
            //cout<<dp[i][j]<<" ";
        }
        //cout<<"\n";
    }
    cout<<dp[n][w]<<"\n";
    return 0;
}

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


int main(){


    string s;

    string t = "abcdefghijklmnopqrstuvwxyz";

    int i, j;

    int f = 0;

    map< char, int > mp;


    cin >> s;


    for( i = 0 ; i < 26 ; i = i + 1 ){

         mp[ t.at(i) ] = 0;

         }


    for( i = 0 ; i < s.size() ; i = i + 1 ){

         for( j = 0 ; j < 26 ; j = j + 1 ){

              if( t.at(j) == s.at(i) ){

                  mp[ t.at(j) ] += 1;

                  break;

                  }

              }

         }

              
    for( i = 0 ; i < 26 ; i = i + 1 ){

         if ( mp[ t.at(i) ] == 0 ){

              f = 1;

              break;

              }

         }


    if( f == 1 ) cout << t.at(i) << endl;

    else cout << "None" << endl;


    return 0;

    }


Measured memory_bytes: 512
N = int(input())
M = [0] * 100
for i in range(1, N+1):
    i = str(i)
    l, r = int(i[0]), int(i[-1])
    M[l*10+r] += 1
ans = 0
for i, cnt in enumerate(M):
    l, r = divmod(i, 10)
    ans += cnt * M[r*10+l]
print(ans)


Measured memory_bytes: 9124
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define all(a) a.begin(),a.end()
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define dbg_v(v) cout<<#v<<":";for(auto c:v) cout<<" "<<c; cout<<endl;
int power(ll x,ll y){ll res = 1;while(y>0){if(y&1)res = (res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}
void solve(){
	int h,a;
	cin>>h>>a;
	int ans=(h+a-1)/a;
	cout<<ans<<endl;
}
int main(){ 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}


Measured memory_bytes: 3592
n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  if a[i] in dic:
    dic[a[i]]+=1
  else:
    dic[a[i]]=1
q=int(input())
ans=0
for key,value in dic.items():
  ans+=key*value
for i in range(q):
  b,c=map(int,input().split())
  if b in dic:
    if c in dic:
      dic[c]+=dic[b]
      ans+=dic[b]*(c-b)
      del dic[b]
    else:
      dic[c]=dic[b]
      ans+=dic[b]*(c-b)
      del dic[b]
  print(ans)

Measured memory_bytes: 20908
/// Bismillah Hir Rahmanir Rahim

/**
    Practice like Cristiano Ronaldo
        Play Like Leo Messi..
**/

#include <bits/stdc++.h>

using namespace std;

#define PI                    acos(-1.0)
#define Pi                    3.141592653589793
#define ff                    first
#define ss                    second
#define pb                    push_back
#define space                 " "
#define cubert(x)             (exp(log(x)/3))
#define all(x)                (x).begin(), (x).end()
#define clr(ar)               memset(ar, 0, sizeof(ar))
#define eprintf(...)          fprintf(stderr, __VA_ARGS__)

/*
template <class T> T gcd(T a,T b){ if(b == 0) return a; return gcd( b,a % b ); }
template <class T> T lcm(T a, T b ){ return ( a * b ) / gcd( a,b ); }
template<class T> string ToString(const T &x){ stringstream s; s << x; return s.str(); }
template<class T> int ToInteger(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
*/

typedef  long long int            ll;
typedef  map<string,int>          msi;
typedef  map<int,int>	          mii;
typedef  map<char,int>            mci;
typedef  map<int,string>	      mis;
typedef  pair<int,int> 	          ii;
typedef  pair<string, int>        psi;
typedef  vector<int> 	          vi;
typedef  vector<string> 	      vs;
typedef  vector< ii >             vii;

template<class T1> void deb(T1 e1)
{
    cout << e1 << endl;
}
template<class T1,class T2> void deb(T1 e1, T2 e2)
{
    cout << e1 << space << e2 << endl;
}
template<class T1,class T2,class T3> void deb(T1 e1, T2 e2, T3 e3)
{
    cout << e1 << space << e2 << space << e3 << endl;
}

#define sf                    scanf
#define pf                    printf

#define sf1(a)                scanf("%d", &a)
#define sf2(a,b)              scanf("%d %d",&a, &b)
#define sf3(a,b,c)            scanf("%d %d %d", &a, &b, &c)
#define sf4(a,b,c,d)          scanf("%d %d %d %d", &a, &b, &c, &d)

#define sf1ll(a)              scanf("%I64d", &a)
#define sf2ll(a,b)            scanf("%I64d %I64d", &a, &b)
#define sf3ll(a,b,c)          scanf("%I64d %I64d %I64d", &a, &b, &c)
#define sf4ll(a,b,c,d)        scanf("%I64d %I64d %I64d %I64d", &a, &b, &c, &d)

#define READ                  freopen("in.txt", "r", stdin);
#define WRITE                 freopen("out.txt", "w", stdout);
/// The End.

void check_time()
{
#ifdef the_badcoder
    eprintf("%.5lf\n", (double)clock() / CLOCKS_PER_SEC);
#endif
}

const int res = 1e5 + 1;
const ll mod = 1e9 + 7;


/**
        ACCEPT FAILURE.
**/


int main()
{

    int n;
    sf1( n );
    
    if( n <= 999 )
    {
        deb("ABC");
    }
    else {
        deb("ABD");
    }
    return 0;

}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
#include <cmath>
#include <iomanip> //setprecision(2)
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
        ll n,m,ans=0;

        cin >> n >> m;
        ll x[m],d[m-1];
        rep(i,m){
                cin>>x[i];
        }
        sort(x,x+m);
        ans=x[m-1]-x[0];


        rep(i,m-1){
                d[i]=x[i+1]-x[i];
        }
        sort(d,d+m-1,greater<int>());
        if(n>=m) {
                cout<<0<<endl;
        }
        else{
                rep(i,n-1){
                        ans-=d[i];
                }

                cout << ans << endl;
        }
        return 0;
}


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


long long dp[1<<10][1<<10], pre[1<<10];
int mid[1<<10][1<<10];


int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> pre[i + 1];
    pre[i + 1] += pre[i];
  }
  for (int i = 0; i + 2 <= n; ++i) {
    mid[i][i + 2] = i + 1;
    dp[i][i + 2] = pre[i + 2] - pre[i];
  }
  for (int l = 3; l <= n; ++l) {
    for (int i = 0; i + l <= n; ++i) {
      int &opt = mid[i][i + l] = mid[i][i + l - 1];
      auto key = [&](int k) {
        return dp[i][k] + dp[k][i + l] + pre[i + l] - pre[i];
      };
      for (int k = mid[i][i + l - 1]; k <= mid[i + 1][i + l]; ++k) {
        opt = min(opt, k, [&](int a, int b) { return key(a) < key(b); });
      }
      dp[i][i + l] = key(opt);
    }
  }
  cout << dp[0][n] << '\n';
}


Measured memory_bytes: 6016
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;

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

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

void pushHeap(vector<int>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}

int popHeap(vector<int>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  int i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}

vector<bool> ver;
void dfs(const graph &g,int v,int a,int b){
  ver[v]=true;
  for(auto i:g[v]){
    if(ver[i])continue;
    if((v==a && i==b) || (v==b && i==a))continue;
    dfs(g,i,a,b);
  }
}

int main(){
  int i,j,k,cnt=0;
  int n,m;
  cin>>n>>m;
  int b[n+1],c[2*m];
  for(i=1;i<=n;i++)b[i]=0;
  for(i=0;i<2*m;i++){
    cin>>c[i];
    b[c[i]]++;
  }
  for(i=1;i<=n;i++){
    if(b[i]%2!=0){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
}

Measured memory_bytes: 1408
import queue

K = int(input())
q = queue.Queue()

for i in range(1,10):
  q.put(i)

for i in range(K):
  x = q.get()
  if x % 10 != 0:
    q.put(10*x+(x%10)-1)
  q.put(10*x+x%10)
  if x % 10 != 9:
    q.put(10*x+(x%10)+1)

print(x)

Measured memory_bytes: 12452
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 n = saori.saori_hayami();
		int k = saori.saori_hayami();
		int[] x = new int[n];
		for(int i = 0;i < n;i++){
			x[i] = saori.saori_hayami();
		}
		int ans = 0;
		int num = 0;
		for(int i = 0;i < x.length;i++){
			num = 0;
			ans += Math.min(x[i], k-x[i])*2;
		}
		System.out.println(ans);
		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: 22740
#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef vector < ll > vl;

const int MAXD = 105;
const int MAXN = 10005;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 18;
const double EPS = 1e-9;
const double PI = 3.1415926535;

int dp[MAXN][MAXD];

int add(const int& a, const int& b) {
    if(a + b >= MOD)
        return (a + b - MOD);
    return (a + b);
}

int subt(const int& a, const int& b) {
    if(a - b < 0)
        return (a - b + MOD);
    return (a - b);
}

int main() {
    int D, ans;
    string K;

    cin >> K >> D;
    int sz = K.size();

    for(int i = 0; i <= K[0] - '0' - 1; i++)
        dp[0][i % D] += 1;                         
    int sum_of_max = (K[0] - '0') % D;        
  
    for(int i = 0; i < sz - 1; i++) {
        int next_znam = K[i + 1] - '0';
        for(int j = 0; j < D; j++)
            for(int znam = 0; znam <= 9; znam++)
                dp[i + 1][(j + znam) % D] = add(dp[i + 1][(j + znam) % D], dp[i][j]);

        for(int znam = 0; znam <= next_znam - 1; znam++)
            dp[i + 1][(sum_of_max + znam) % D] = add(dp[i + 1][(sum_of_max + znam) % D], 1);
        sum_of_max = (sum_of_max + next_znam) % D;
    }

    if(sum_of_max == 0)                          
        cout << dp[sz - 1][0] << endl;
    else                                            
        cout << subt(dp[sz - 1][0], 1) << endl;

    return 0;
}



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

int main() {
    int w,kijun;
    bool flg=false;
    cin >> w;

    for (int i = 11; i>=0 ; i--){
        kijun = pow(3,i);
        if (w >= (kijun - (kijun / 2)) && w <= (kijun + (kijun / 2))) {
            cout << "+";
            w -= kijun;
            flg = true;
        } else if (w <= (kijun - (kijun / 2) ) * -1 && w >= (kijun + (kijun / 2) ) * -1 ) {
            cout << "-";
            w += kijun;
            flg = true;
        } else if (flg) {
            cout << "0";
        }
    }

    // if (w >= 122 && w <= 202) {
    //     cout << "+";
    //     w -= 243;
    //     flg = true;
    // } else if (w < -122 && w >= -121) {
    //     cout << "-";
    //     w += 243;
    //      flg = true;
    // } else if (flg) {
    //     cout << "0";
    // }

    // if (w >= 41 && w <= 121) {
    //     cout << "+";
    //     w -= 81;
    //     flg = true;
    // } else if (w < -41 && w >= -121) {
    //     cout << "-";
    //     w += 81;
    //      flg = true;
    // } else if (flg) {
    //     cout << "0";
    // }

    // if (w >= 14 && w <= 40) {
    //     cout << "+";
    //     w -= 27;
    //     flg = true;
    // } else if (w < -14 && w >= -40) {
    //     cout << "-";
    //     w += 27;
    //      flg = true;
    // } else if (flg) {
    //     cout << "0";
    // }

    // if (w >= 4 && w <= 13) {
    //     cout << "+";
    //     w -= 9;
    //     flg = true;
    // } else if (w < -4 && w >= -13) {
    //     cout << "-";
    //     w += 9;
    //      flg = true;
    // } else if (flg) {
    //     cout << "0";
    // }

    // if (w > 1 && w <= 3) {
    //     cout << "+";
    //     w -= 3;
    //      flg = true;
    // } else if (w < -1 && w >= -3) {
    //     cout << "-";
    //     w += 3;
    //      flg = true;;
    // } else if (flg){
    //     cout << "0";
    // }

    // if (w >= 1) {
    //     cout << "+";
    // } else if (w <= -1) {
    //     cout << "-";
    // } else {
    //     cout << "0";
    // }

    cout << endl;




    return 0;
}



Measured memory_bytes: 3272
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

vector<ll> dp;
vector<vector<ll>> g;
vector<ll> a;

void dfs(vector<ll>& now, ll v, ll p=-1) {
  // Update now
  ll pre;
  ll len = now.size();
  ll idx = lower_bound(all(now), a[v]) - now.begin();
  if (idx == len) { // idx is end(), should be added.
    now.push_back(a[v]);
  } else { // idx < len. should replace.
    pre = now[idx];
    now[idx] = a[v];
  }

  dp[v] = now.size();

  for (ll u : g[v]) {
    if (u == p) { continue; }
    dfs(now, u, v);
  }

  // Revert now
  if (idx == len) {
    now.pop_back();
  } else {
    now[idx] = pre;
  }
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  dp.resize(n);
  g.resize(n);
  a.resize(n);

  rep(i,n) {
    cin >> a[i];
  }
  rep(iter,n-1) {
    ll u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<ll> now;
  dfs(now, 0);

  rep(i,n) {
    cout << dp[i] << endl;
  }
}


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

const ll MX = 1e18;


int main() {
    int n;
    cin >> n;
    ll ans = 1;
    bool ng = false;
    
    rep(i, n) {
        ll a;
        cin >> a;
        if (a == 0) {
            cout << 0 << endl;
            return 0;
        }
        if (ng || MX /ans < a) { // オーバーフローするとき
            ng = true;
        }
        ans *= a;
    }
    if (ng) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3668