akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#define ll long long

using namespace std;

ll dp[1001][1001];
char maze[1001][1001];
ll mod = 1e9 + 7;

int main()
{
  int n,m;
  cin>>n>>m;
  for(int i = 0 ; i<n ; i++)
  {
    for(int j = 0 ; j<m ; j++)
    {
      cin>>maze[i][j];
    }
  }

  int no_to_fill = 1;
  for(int i = 0 ; i<n ; i++)
  {
    if(maze[i][0] == '#')
        no_to_fill = 0;
    dp[i][0] = no_to_fill;
  }

  no_to_fill = 1;
  for(int i = 0 ; i<m ; i++)
  {
    if(maze[0][i] == '#')
        no_to_fill = 0;
    dp[0][i] = no_to_fill;
  } 

  dp[0][0] = 0;

  for(int i = 1 ; i<n ; i++)
  {
    for(int j = 1 ; j<m ; j++)
    {
      if(maze[i][j] == '#')
        dp[i][j] = 0;
      else
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
    }
  } 

  /*for(int i = 0 ; i<n ; i++)
  {
    for(int j = 0 ; j<m ; j++)
    {
      cout<<dp[i][j]<<" ";
    }
    cout<<endl;
  }  */

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

Measured memory_bytes: 9088
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int h,w,n;
    int i,j;
    scanf("%d",&h);
    scanf("%d",&w);
    scanf("%d",&n);
    if(h>w)
    {
        i=n%h;
        if(i==0)
        {
            j=n/h;
        }
        else {j=n/h+1;}
    }
    else
    {
        i=n%w;
        if(i==0)
        {
            j=n/w;
        }
        else {j=n/w+1;}
    }
    printf("%d",j);
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
    int i = 0;
    int N;
    scanf("%d", &N);

    int change;
    while(N-1000*i>0){
        change = N - 1000 * i;
        i++;
    }
    printf("%d", 1000-change);
    return 0;
}

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

using namespace std;
const int N= 200005;
vector<int>grp[N];
int dfs(int x,vector<int> &vis){
  if(vis[x])
    return 0;
  vis[x]=1;
  int cnt=1;
  for(auto curr:grp[x]){
    if(!vis[curr]){
      cnt=cnt+dfs(curr,vis);
    }
  }
  return cnt;
}

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

  vector<int>vis(n+1,0);
  map<pair<int,int>,int> mp;
  while(m--){
    int a,b;
    cin>>a>>b;
    if(mp[{a,b}]==1)
      continue;
    grp[a].push_back(b);
    grp[b].push_back(a);
    mp[{a,b}]=1;
    mp[{b,a}]=1;
  }
  int ans=0;
  //max conn comp size
  for(int i=1;i<=n;++i){
    ans=max(dfs(i,vis),ans);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 49328
def lscan; gets.split.map(&:to_i); end
def bye(msg); puts msg.to_s; exit; end
n = gets.to_i

best = 2e18
1.upto(n) do |x|
  y = n/x
  break if x > y
  next if n/x*x != n
  best = [x+y, best].min
end

p best-2

Measured memory_bytes: 1788
function Main(input) {
  var helix = {
    "A": "T",
    "T": "A",
    "C": "G",
    "G": "C"
  };
  var count = 0;
  var maxCount = 0;
  for ( var i = 0; i < input.length; i++) {
    if(helix[input[i]]) {
      count++;
    } else {
      if ( maxCount <= count){
        maxCount = count;
      }
      count = 0;
    }
  }
  if(maxCount <= count) {
    maxCount = count;
  }
  console.log(maxCount);
}

process.stdin.setEncoding('utf-8');
process.stdin.on('data', function(data){
  Main(data.trim());
});


Measured memory_bytes: 7500
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数の個数*/int divisor_number(int n){auto p = prime_factor(n); int res = 1; for(auto x:p)res*=(x.second+1); return res;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    string a,b; cin >> a >> b;
    bool ok = 0;
    for(int i = 1; i*i<=100100; i++) if(stoi(a+b)==i*i) ok=1;
    Yn(ok);

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll X; cin >> X;
  ll result;
  if (X<=599) result = 8;
  else if (X<=799) result = 7;
  else if (X<=999) result = 6;
  else if (X<=1199) result = 5;
  else if (X<=1399) result = 4;
  else if (X<=1599) result = 3;
  else if (X<=1799) result = 2;
  else result = 1;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {

	int K=0,N=0,i=0,max=0,d=0;
	int A[200000];


	scanf("%d %d",&K,&N);

	while(i<N){
		scanf("%d",&A[i]);
		i++;
	}

	i=0;

	while(i<N-1){
		d = abs(A[i]-A[i+1]);
		if(2 * d > K){
			d= K - d;
		}

		if(d>max){
			max = d;
		}
		i++;
	}

	d = abs(A[N-1]-A[0]);
			if(2 * d > K){
				d= K - d;
			}

			if(d>max){
				max = d;
			}


	printf("%d", K-max);

	return 0;
}



Measured memory_bytes: 896
#include<iostream>

using namespace std;

int main(void) {

	int h, w, x ,y;
	

	while (1)
	{
		cin >> h >> w;

		if (h == 0 && w == 0)
			break;

		y = 0;
		while (1)
		{
			x = 0;

			while (1)
			{
				cout << "#";
				x++;
				if (x == w)
					break;

				cout << ".";
				x++;
				if (x == w)
					break;

			}
			cout << endl;
			x = 0;
			y++;
			if (y == h)
				break;

			while (1)
			{
				
				cout << ".";
				x++;
				if (x == w)
					break;

				cout << "#";
				x++;
				if (x == w)
					break;

			}
			cout << endl;
			x = 0;
			y++;
			if (y == h)
				break;
		}
	
		cout << endl;

	}
	return 0;
}


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

int main() {
  int N;
  long long Ans=0;
  cin>>N;
  rep(i,N+1){if(i%3!=0 && i%5!=0){Ans+=i;}}
  cout<<Ans<<endl;
}

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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void)
{
	//変数の宣言
	char s[100010];
	int len;
	int i,j;
	int flag=0;
	int ans;
	//データの読み込み
	scanf("%s",&s);
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	len=strlen(s);
	if(len%2==1){
		i=1;
		while(flag==0){
			if(s[len/2]!=s[len/2+i]||s[len/2]!=s[len/2-i]){
				i--;
				flag=1;
			}else{
				i++;
				if(2*i-1==len){
					i--;
					flag=1;
				}
			}
		}
		ans=len/2+i+1;
	}else{
		if(s[len/2-1]!=s[len/2]){
			ans=len/2;
		}else{
			i=1;
			while(flag==0){
				if(s[len/2]!=s[len/2+i]||s[len/2]!=s[len/2-i-1]){
					flag=1;
				}else{
					i++;
//					printf("i=%d\n",i);
					if(2*i==len+2){
						i--;
						flag=1;
					}
				}
			}
//			printf("i=%d\n",i);
			ans=len/2+i;
		}
	}
	
//	printf("計算部分終了\n");
	
	//出力
	printf("%d",ans);
	
//	printf("結果の出力終了\n");
	
}



Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_5_D
#include <iostream>
using namespace std;

bool div(int n){
  if(n % 3 == 0) return true;
  else return false;
}
bool isIn3(int n){
  if((n-3) % 10 == 0) return true;
  else return false;
}

bool in3(int n){
  while(n > 10){
    n /= 10;
    if(isIn3(n)) return true;
  }
  return false;
}


int main(){
  int n;
  cin >> n;
  for(int i=1; i <= n; i++){
    if(div(i) || isIn3(i)|| in3(i)) cout << " " << i;
  }
  cout << endl;
}

Measured memory_bytes: 1164
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int a = sc.nextInt();
		int b = sc.nextInt();
		char[] s = sc.next().toCharArray();

		int n = s.length;

		if (n == a + b + 1) {
			boolean flag = true;
			for (int i = 0; i < n; i++) {
				if (i < a) {
					if (s[i] < '0' || s[i] > '9') {
						flag = false;
					}
				} else if (i == a) {
					if (s[i] != '-') {
						flag = false;
					}
				} else {
					if (s[i] < '0' || s[i] > '9') {
						flag = false;
					}
				}
			}

			if (flag) {
				pr.println("Yes");
				return;
			}
		}

		pr.println("No");
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 21844
from collections import defaultdict
s=str(input())
n=len(s)
m=2019
d=[0]
for i in range(n):
    d.append((d[-1]+int(s[n-i-1])*pow(10,i,m))%m)
p=defaultdict(int)
ans=0
for i in d:
    ans+=p[i]
    p[i]+=1
print(ans)

Measured memory_bytes: 78020
#include <stdio.h>
 
int main(int argc, const char * argv[]) {
    int n,m,l;
    int i,j,r;
    int a[100][100],b[100][100];
    long sum=0;
    scanf("%d %d %d",&n,&m,&l);
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(i=0;i<m;i++){
        for(j=0;j<l;j++){
            scanf("%d",&b[i][j]);
        }
    }
    for(i=0;i<n;i++){
       for(r=0;r<l;r++){
           sum=0;
            for(j=0;j<m;j++){
            sum = sum+a[i][j]*b[j][r];
                        }
           printf("%ld",sum);
           if(r+1!=l){
               printf(" ");
           }
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2104
#!/usr/bin/env python3
import sys

# refered to
# rank : http://at274.hatenablog.com/entry/2018/02/02/173000
# size : abc120 kaisetsu
class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    # 親が同じか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 


YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ab = sorted([[a[i], b[i]] for i in range(M)], key=lambda x:(x[0], x[1]))

    p1 = []

    for i,j in ab:
        if(i == 1):
            p1.append(j)
        else:
            break
    
    p1 = set(p1)

    for i,j in ab:
        if(i in p1 and j == N):
            print(YES)
            exit()

    print(NO)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()


Measured memory_bytes: 57040
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type PrefMax struct {
	arr []int
}

func (p *PrefMax) insert(idx, val int) {
	for idx < len(p.arr) {
		p.arr[idx] = max(p.arr[idx], val)
		idx += idx & -idx
	}
}

func (p *PrefMax) query(idx int) int {
	ret := 0
	for idx > 0 {
		ret = max(ret, p.arr[idx])
		idx -= idx & -idx
	}
	return ret
}

func New(n int) *PrefMax {
	p := &PrefMax{
		arr: make([]int, n+1),
	}
	return p
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}

const Mod = 998244353

type Pair struct {
	x int
	d int
}

type ByX []Pair

func (a ByX) Len() int {
	return len(a)
}

func (a ByX) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a ByX) Less(i, j int) bool {
	return a[i].x < a[j].x
}

func main() {
	r := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscanf(r, "%d\n", &n)

	rb := make([]Pair, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(r, "%d %d\n", &rb[i].x, &rb[i].d)
	}

	sort.Sort(ByX(rb))

	p := New(n)
	sku := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		lo, hi := i, n-1
		for lo <= hi {
			mid := (lo + hi) / 2
			if rb[i].x+rb[i].d <= rb[mid].x {
				hi = mid - 1
			} else {
				lo = mid + 1
				sku[i] = mid
			}
		}
		sku[i] = max(sku[i]+1, p.query(sku[i]+1))
		p.insert(i+1, sku[i])
	}

	dp := make([]int, n+1)
	dp[n] = 1
	for i := n - 1; i >= 0; i-- {
		dp[i] = (dp[i+1] + dp[sku[i]]) % Mod
	}

	fmt.Println(dp[0])
}


Measured memory_bytes: 10880
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	vector<int> dish;
	for (int i = 0; i < 5; i++) {
		int k; cin >> k;
		dish.push_back(k);
	}
	int time = 0;
	int ch = 1;
	while (ch != 0) {
		ch = 0;
			for (int i = 0; i < dish.size(); i++) {
				if ((dish[i]) % 10 == 0&&dish.size()>1) {
					ch = ch + 1;
				
					time = time + dish[i];
					
					dish.erase(dish.begin() + i);
				}
			}
	}
	ch = 1;
	
		while (dish.size() >1) {
			for (int r = 9; r >= 1; r--) {
				for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r&&dish.size()>1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}
				for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r && dish.size() > 1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r && dish.size() > 1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r && dish.size() > 1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r && dish.size() > 1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}for (int i = 0; i < dish.size(); i++) {
					if (dish[i] % 10 == r && dish.size() > 1) {
						time = time + dish[i] + 10 - r;
						
						dish.erase(dish.begin() + i);
					}
				}
			}
		}
	
		cout << time + dish[0];
	
	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;

typedef long long int64;
const int64 inf = (int64)1e18;

typedef vector<pair<int, int> > edge;
typedef vector<edge> graph;

struct SegTree {
	
	vector<vector<int64> > dat;
	int size;
	
	void init(int n, vector<int64> arg)
	{
		size = 1;
		while(size < n) size *= 2;
		
		dat.resize(size * 2);
		for(int i = 0; i < size; ++i)
			dat[i + size].push_back(i < arg.size() ? arg[i] : -inf);
		
		for(int i = size - 1; i > 0; --i) {
			int l = i * 2 + 0, r = i * 2 + 1;
			dat[i].resize(dat[l].size() + dat[r].size());
			merge(dat[l].begin(), dat[l].end(), dat[r].begin(), dat[r].end(), dat[i].begin());
		}
	}
	
	int find(int a, int b, int64 x, int k, int l, int r)
	{
		if(a >= r || b <= l)
			return 0;
		if(a <= l && b >= r)
			return dat[k].end() - lower_bound(dat[k].begin(), dat[k].end(), x);
		
		int mid = (l + r) / 2;
		int lv = find(a, b, x, k * 2 + 0, l, mid);
		int rv = find(a, b, x, k * 2 + 1, mid, r);
		
		return lv + rv;
	}
	
	int find(int a, int b, int64 x)
	{
		return find(a, b, x, 1, 0, size);
	}
};

void dijkstra(int s, graph &g, vector<pair<int64, int> > &dist)
{
	int n = g.size();
	
	dist.resize(n);
	for(int i = 0; i < n; ++i)
		dist[i] = make_pair(inf, i);
	
	priority_queue<pair<int64, int> > q;
	q.push(make_pair(0LL, s));
	
	while(!q.empty()) {
		
		int64 d = -q.top().first;
		int v = q.top().second;
		q.pop();
		if(dist[v].first < d)
			continue;
		
		dist[v].first = d;
		
		for(int i = 0; i < g[v].size(); ++i) {
			
			int w = g[v][i].first, cost = g[v][i].second;
			if(dist[w].first == inf)
				q.push(make_pair(-(d + cost), w));
		}
	}
}

int main()
{
	int n, m, q;
	graph g;
	
	scanf("%d%d", &n, &m);
	g.resize(n);
	for(int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a].push_back(make_pair(b, c));
		g[b].push_back(make_pair(a, c));
	}
	scanf("%d", &q);
	
	vector<pair<int64, int> > sdist, gdist;
	vector<int64> arg;
	
	dijkstra(0, g, sdist);
	dijkstra(n - 1, g, gdist);
	sort(sdist.begin(), sdist.end());
	
	arg.resize(n);
	for(int i = 0; i < n; ++i)
		arg[i] = gdist[sdist[i].second].first;
	
	SegTree tree;
	
	tree.init(n, arg);
	
	for(int query = 0; query < q; ++query) {
		
		int64 fs, fg;
		
		scanf("%lld%lld", &fs, &fg);
		
		int ub = upper_bound(sdist.begin(), sdist.end(), make_pair(fs, n)) - sdist.begin();
		
		int ans = tree.find(0, ub, fg);
		
		//printf("[debug] (%d, %d) -> ub:%d -> %d\n", fs, fg, ub, ans);
		
		printf("%d\n", ans);
	}
	
	return 0;
}

/* ハラスメントに負けず */
/* 0完太陽にも負けず */
/* はやく人権を獲得したい */
/* nullmineralが書きましたが */
/* 責任はまったくとりません */

Measured memory_bytes: 41520
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool F(vector<ll> a){
    ll n = a.size();
    ll S = 0;
    for(ll i = 0; i < n; i++)
        S += a[i] - 1;
    if(S % 2 == 1) return 1;
    if(n % 2 == 0) return 0;
    ll X = S + n - 1;
    ll Y = 1;
    if(X == 0) return 0;
    while(X % 2 == 0) Y*=2, X/=2;
    ll N = 0;
    for(ll i = 0; i < n; i++)
        if(a[i] == 1 || ((a[i] % Y) && ((a[i] - 1)%Y)))
            return 0;
        else if(a[i] % Y) N++;
    if(N > 1) return 0;
    for(ll i = 0; i < n; i++){
        if(a[i]%Y){
            a[i] --;
        }
    }
    ll G = a[0];
    for(ll i = 0; i < n; i++){
        G = __gcd(G, a[i]);
    }
    for(ll i = 0; i < n; i++)
        a[i] /= G;
    if(F(a)) return 0;
    else return 1;
}
main(){
    ll n;
    cin >> n;
    vector<ll> v;
    for(ll i = 0; i < n; i++){
        ll a;
        cin >> a;
        v.push_back(a);
    }
    if(F(v)){
        cout << "First"<<endl;
    }
    else cout<< "Second"<<endl;

}


Measured memory_bytes: 19188
N=int(input())
# 例外のN=0について
if N==0:
    print(0)
    exit()

a=1
b=0
up=[a]
low=[b]
ct=1
while not b<=N<=a:
    if ct%2==0:
        a+=(-2)**ct
    else:
        b+=(-2)**ct
    ct+=1
    up.append(a)
    low.append(b)
# print(ct)
# print(up)
# print(low)

# 頭の桁から決める
ans=['0']*ct
r=N
for i in range(ct-1):
    # print(low[ct-i-2], up[ct-i-2], r-(-2)**(ct-i-1))
    tmp=r-(-2)**(ct-i-1)
    if low[ct-i-2]<=tmp<=up[ct-i-2]:
        ans[i]='1'
        r=tmp
ans[ct-1]=str(r)
# print(ans)

print((''.join(ans)))

Measured memory_bytes: 62024
alpha = list("abcdefghij")


def dfs(v, depth):
    if depth == N:
        print(v)
        return
    if depth <= N:
        for next_ in alpha[: len(set(list(v))) + 1]:
            dfs(v + next_, depth + 1)


if __name__ == "__main__":
    N = int(input())

    dfs("a", depth=1)


Measured memory_bytes: 72964
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
using LL = long long;

int main(){
    int n;
    int ai;

    cin >> n;
    string ans = "APPROVED";
    for (int i=0;i <n;i++){
        cin >> ai;
        if(ai%2==0){
            if(ai%3!=0 and ai%5!=0){
                ans = "DENIED";
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
  char str[30];
  int len, i;

  scanf("%[^\n]", str);
  len=strlen(str);
  for(i=0; i<len; i++){
    putchar(str[len-i-1]);
  }
  putchar('\n');
  return 0;
}

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

int main(){
	
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int sum = 0;


	if(k-a >0){
		sum += a;
		k = k-a;
	}else{
		sum += k;
		k=0;
	}
	if(k-b>0){
		k = k-b;
	}else{
		k=0;
	}
	while(k>0 && c>0){
		k--;c--;
		sum +=-1;
	}
	cout<<sum<<endl;
	return 0;

}

Measured memory_bytes: 3192
#include <stdio.h>

int main(void) {
  int i, a, b, work;

  scanf("%d%d", &a, &b);

  if (a < b) {
    work = a;
    a = b;
    b = work;
  }

  do {
    work = a % b;
    a = b;
    b = work;
  } while (b > 0);

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

  return 0;
}

Measured memory_bytes: 592
from sys import stdin

n,m=map(int,input().split())
hyo=list(map(int,input().split()))
sum=0
for i in hyo:
    sum+=i
giri=sum/(4*m)
ok=0
for i in hyo:
    if i>=giri:
        ok+=1
if ok>=m:
    print("Yes\n")
else:
    print("No\n")

Measured memory_bytes: 38384
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

typedef long long ll;

using namespace std;


int main(){
    int a[10],b[10];
    
    for(int i=0;i<10;i++)
        scanf("%d",&a[i]);
    sort(a,a+10);
    
    for(int i=0;i<10;i++)
        scanf("%d",&b[i]);
    sort(b,b+10);
    
    printf("%d %d\n",a[7]+a[8]+a[9],b[7]+b[8]+b[9]);
    
    return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << - 1 << endl;}
void unhap() {cout << ":(" << endl;}

int main() {
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  for (int i = 0; i < n; i++) cin >> p.at(i);
  for (int i = 0; i < n; i++) cin >> q.at(i);
  ll aa = 1, bb = 1;

  for (int j = 0; j < n - 1; j++) {
    ll a = 1, b = 1;
    for (int i = 1; i <= n - 1 - j; i++) {
      a *= i;
      b *= i;
    }
    aa += a * (p.at(j) - 1);
    bb += b * (q.at(j) - 1);
    for (int i = j + 1; i < n; i++) {
      if (p.at(i) > p.at(j)) p.at(i)--;
      if (q.at(i) > q.at(j)) q.at(i)--;
    }
  }
  cout << max(aa - bb, bb - aa) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<string>

using namespace std;
 
typedef long long ll;

ll memo[110][101000];

const ll MOD = 1e9 + 7;

ll a[110];

ll dp(ll i, ll j){
  if( j == 0){ return 1;}
  if( j < 0){ return 0;} //インデックスがマイナスのやばい場合を除外
  if( i < 0){ return 0;}
  //初期値 i == 0(0人に配る）も一通りとして考える
  if( memo[i][j] != -1){ return memo[i][j];}
  //すでに書き込まれている場合
  return memo[i][j] = ( (dp(i-1,j) + dp(i,j-1)) % MOD - dp( i-1,j-a[i-1] - 1)  +  MOD )% MOD;}
                       
  int main(){
    ll N,K; cin >> N >> K;
    for(ll i = 0; i < 110; i++){
      for(ll j = 0; j < 101000; j++){
        memo[i][j] = -1;}} //初期化(未記入)
    
    for(ll i = 0; i < N; i++){
      cin >> a[i];} //i番目の個の上限記入
    
    cout << dp(N,K) <<endl; return 0;}
      
    
  


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

int main()
{
	int i,x,n,mn,mx=0;
	cin>>x>>n;
	if(n==0) mn=x;
	else
	{
		mn=1000;
		vector<bool>p(101,false);
		for(i=0;i<n;i++)
		{
			int in;
			cin>>in;
			mx=max(mx,in);
			p[in]=true;
		}
		for(i=0;i<=101;i++)
		{
			if(p[i]==false)
			{
				if(abs(x-i)<abs(x-mn)) mn=i;
				if(abs(x-i)==abs(x-mn)) mn=min(mn,i);
			}
		}
	}
	cout<<mn<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define upperlimit 1000100
#define INF 1000000100
#define INFL 1000000000000000100
#define eps 1e-8
#define endl '\n'
#define sd(n) scanf("%d",&n)
#define slld(n) scanf("%lld",&n)
#define pd(n) printf("%d",n)
#define plld(n) printf("%lld",n)
#define pds(n) printf("%d ",n)
#define pllds(n) printf("%lld ",n)
#define pdn(n) printf("%d\n",n)
#define plldn(n) printf("%lld\n",n)
#define REP(i,a,b) for(i=a;i<=b;i++)
#define mp make_pair
#define pb push_back
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define F first
#define S second
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
 
ll gcd(ll n1,ll n2){
    if(!n1)return n2;
    if(!n2)return n1;
    if(n1%n2==0)return n2;
    return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent){
    base%=mod;
    ll ans=1;
    while(exponent){
        if(exponent&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        exponent/=2;
    }
    ans%=mod;
    return ans;
}
 
 
int main(){
int a;
int b;
int c;
 
cin>>a>>b>>c;
if(b-a==c-b){
     cout<<"YES"<<endl;
}
else{
     cout<<"NO";
}
    return 0 ;
 
 
}

Measured memory_bytes: 256
object Main extends App {
  
  val sc = new java.util.Scanner(System.in)
  val a, b = sc.nextInt()
  
  val negativeCount = if (a < 0) {
    if (b > 0) a else a.abs - b.abs + 1
  } else {
    0
  }
  if (a <= 0 && 0 <= b) {
    println("Zero")
  } else if (negativeCount % 2 != 0) {
    println("Negative")
  } else {
    println("Positive")
  }  
}

Measured memory_bytes: 55364
#include<bits/stdc++.h>
using namespace std;
using ll =  long long;
int main()
{
    int a, b;
    cin >> a >> b;
    if ( (a == 1 && b == 2) ||(a == 2 && b == 1)) cout << 3 << endl;
    else if((a== 2 && b == 3)||(a== 3&& b==2))cout << 1 << endl;
    else cout << 2 << endl;
}


Measured memory_bytes: 3568
def main():
	A,B,C,X,Y = map(int,input().split())
	ans = A*X + B*Y
	for i in range(1,min(X,Y)+1):
		ans = min(ans,ans-A-B+2*C)
	if Y < X:
		for i in range(Y+1,X+1):
			ans = min(ans, ans - A + C * 2)
	else:
		for i in range(X+1, Y+1):
			ans = min(ans, ans - B + C * 2)
	print(ans)
main()

Measured memory_bytes: 63884
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int my_binary_search(vector<long long> array, int left, int right, long long value){
    int med;
    while (left < right) {
        med = (left+right)/2;
        if (array[med] == value) return med;
        else if (array[med] > value) right = med;
        else left = med + 1;
    }
    return right;
}

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    const int inf = 1000000001;
    vector<long long> l(n, inf);
    l[0] = a[0];
    int length = 1;
    for(int i = 1; i < n; i++){
        //cout << "a[i]= " << a[i] << endl;
        //cout << "length= " << length << endl;
        if(l[length-1] < a[i]){
            l[length++] = a[i];
        }else{
            //int j = my_binary_search(l, 0, length-1, a[i]);
            //l[j] = a[i];
            *lower_bound(l.begin(), l.end(), a[i]) = a[i];
        }
        //for(int k = 0; k < length; k++) cout << l[k] << " "; cout << endl;
        
    }
    cout << length << endl;
}

Measured memory_bytes: 4332
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int N, K;

int main() {
    cin >> N >> K;

    int ans = 0, a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        if (a >= K) ans++;
    }

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


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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    ll N;
    cin>>N;
    ll cnt=0;
    vector<ll> f(10100,0);
    REP2(x,1,110){
        REP2(y,1,110){
            REP2(z,1,110){
                ll tmp;
                tmp=pow(x,2)+pow(y,2)+pow(z,2)+x*y+y*z+z*x;
                if(tmp>10010) continue;
                f[tmp]++;
            }
        }
    }
    REP2(i,1,N+1){
        cout<<f[i]<<endl;
    }
    
}

Measured memory_bytes: 3672
n, k = map(int, input().split())
v = list(map(int, input().split()))
m = min(n, k)
max_score = 0
for i in range(m+1):
    for j in range(m+1-i):
        vals = v[:i] if j == 0 else v[:i] + v[-j:]
        minus = list(filter(lambda x : x < 0, vals))
        minus.sort()
        score = sum(vals) - sum(minus[:min(k - i - j, len(minus))])
        if max_score < score:
            max_score = score
print(max_score)

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

int main() {
    std::string text;
    cin >> text;
    int ans = 0;
    for (int i = 0; i < sizeof(text); i++){
        if (text[i] == '1') {
            //cout << text[i] << endl;
            ans++;
        };
        //ans = ans + [i];
    };
    cout << ans << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
#define for1(i,a,n)  for(int i=0;i<n;i++)
#define rep(i, c) for(int i = 0; i < (int)c; i++)
using namespace std;
//**********************************************DO IT NOW***************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
signed main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    { 
        int n;
        cin>>n;
        int a[1000000],b[1000000];
        for(int i=2;i<=n;i++)
        cin>>a[i];
        for(int i=2;i<=n;i++)
        b[a[i]]++;
        for(int i=1;i<=n;i++)
        cout<<b[i]<<"\n";
        
    }
}
    
// 🍪 🍪 🍪


Measured memory_bytes: 6704
import java.util.*;
import java.util.Map.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String strS = sc.next();
        String strT = sc.next();
        int n = strS.length();
        
        Map<String, Integer> s = new HashMap<String, Integer>();
        for (int i = 0; i < n; i++) {
            String str = String.valueOf(strS.charAt(i));
            if (s.containsKey(str)) {
                
                s.put(str, s.get(str) + 1);
            } else {
                s.put(str, 1);
            }
        }
        
        Map<String, Integer> t = new HashMap<String, Integer>();
        for (int i = 0; i < n; i++) {
            String str = String.valueOf(strT.charAt(i));
            if (t.containsKey(str)) {
                
                t.put(str, t.get(str) + 1);
            } else {
                t.put(str, 1);
            }
        }
        
        int index = 0;
        int[] aryS = new int[s.size()];
        for (Entry<String, Integer> entry : s.entrySet()) {
            aryS[index] = entry.getValue();
            index++;
        }
        
        index = 0;
        int[] aryT = new int[t.size()];
        for (Entry<String, Integer> entry : t.entrySet()) {
            aryT[index] = entry.getValue();
            index++;
        }
        
        boolean clear = true;
        if (aryS.length != aryT.length) {
            clear = false;
        } else {
            Arrays.sort(aryS);
            Arrays.sort(aryT);
        
            for (int i = 0; i < aryS.length; i++) {
                if (aryS[i] != aryT[i]) {
                    clear = false;
                    break;
                } 
            }
        }

        
        if (clear) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


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

int main() {

        std::string s;

        std::cin >> s;

        if (s.length() == 3) {
                for (auto i = 2; i >= 0; --i) {
                        std::cout << s[i];
                }
                std::cout << std::endl;
        }
        else {
                std::cout << s << std::endl;
        }

        return 0;
}

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

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")

typedef long long ll;
typedef unsigned long long ull;
// typedef __int128_t lll;
#define fatnet ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

const ll MOD1 = 1e9 + 7;
const ll MOD2 = 2000003983; // 3571 1e9 + 97
const ll MOD3 = 1e9 + 9;
const ll p1 = 1e6 + 3;
const ll p2 = 2017; // 131 37
const ll p3 = 37;
const ll INF = 5e18;

int main() {
    fatnet;

    ll n;
    cin >> n;
    vector < ll > a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll ans = 0;
    for (int i = 1; i < n - 1; ++i)
        if ((a[i] >= a[i - 1] && a[i + 1] >= a[i]) || (a[i] <= a[i - 1] && a[i + 1] <= a[i]))
            ++ans;
    cout << ans << "\n";

    return 0;
}


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

int main ()
{
    int n, id;
    int card[53] = {0};
    char c;
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
         cin >> c >> id;
         switch(c)
        {
            case 'S': card[id]    = 1; break;
            case 'H': card[id+13] = 1; break;
            case 'C': card[id+26] = 1; break;
            case 'D': card[id+39] = 1; break;
        }
    }
    
    for (int i = 1;i <= 52;i++)
    {
        if (card[i] == 0)
        {
            switch(i)
            {
                case  1 ... 13: cout << "S " << i    << endl; break;
                case 14 ... 26: cout << "H " << i-13 << endl; break;
                case 27 ... 39: cout << "C " << i-26 << endl; break;
                case 40 ... 52: cout << "D " << i-39 << endl; break;
            }
        }
    }
    
    //cout << endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

int main(){
  int n;
  cin >> n;
  vector<ll> x(n), y(n);
  REP(i,n){
    cin >> x[i] >> y[i];
  }

  map<pair<ll, ll>, int> mp;
  REP(i,n)REP(j,n){
    if(i==j)continue;
    ll xi = x[i] - x[j];
    ll yi = y[i] - y[j];

    mp[{xi, yi}]++;
  }

  int ans=0;
  for(auto v: mp){
    chmax(ans, v.second);
  }
  cout << n - ans << endl;
}



Measured memory_bytes: 3668
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000
	mod            = 1e9 + 7
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
)

func main() {
	r := getInt()
	fmt.Println(pow(r, 2))
}

type Graph struct {
	n     int
	edges [][]int
}

func NewGraph(n int) *Graph {
	g := &Graph{
		n:     n,
		edges: make([][]int, n),
	}
	return g
}

func (g *Graph) AddEdge(u, v int) {
	g.edges[v] = append(g.edges[v], u)
	g.edges[u] = append(g.edges[u], v)
}

func dfs(c int, edges [][]int, visited map[int]struct{}) {
	visited[c] = struct{}{}

	for _, v := range edges[c] {
		_, flag := visited[v]
		if flag {
			continue
		}
		dfs(v, edges, visited)
	}
}

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func powMod(n, p int) int {
	if p == 0 {
		return 1
	} else if p%2 == 0 {
		t := powMod(n, p/2)
		return calcMod(t * t)
	} else {
		return calcMod(n * powMod(n, p-1))
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray)-1])
}

func calcMod(x int) int {
	return x % mod
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func isPrime(n int) bool {
	if n < 2 {
		return false
	} else if n == 2 {
		return true
	} else if n % 2 == 0 {
		return false
	}

	sqrtN := int(math.Sqrt(float64(n)))
	for i := 3; i <= sqrtN; i += 2 {
		if n % i == 0 {
			return false
		}
	}

	return true
}


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

int main() {
  string s ;
  cin>>s;
  int i=0 ,cnt=0 ;
  while(i<s.size()){
  if(s.at(i)=='o'){cnt++; }
    i++;
  }
if(cnt+15-s.size()>=8)
  cout<<"YES"<<endl ;
  else
  cout<<"NO"<<endl ;
}

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

//#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")

#define int long long
typedef pair <int, int> pii;
const int maxn = 2e5 + 5;
int a[maxn], cnt[maxn];

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
//	long double l;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	int ans = 0;
	for (int i = 0; i < maxn; i++) {
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	for (int i = 0; i < n; i++) {
		cout << ans - cnt[a[i]] + 1 << '\n';
	}
}


Measured memory_bytes: 4736
#include <iostream>
using namespace std;
long pos[26];

int main() {
  string s; cin >> s;
  long n = s.size();
  long ans = n * (n - 1) / 2 + 1;
  for(int i = 0; i < n; ++i) ++pos[s[i]-'a'];
  for(int i = 0; i < 26; ++i) ans -= pos[i] * (pos[i] - 1) / 2;
  cout << ans;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

int main() {
    init();

    int a, b; cin >> a >> b;
    int h = 0;
    FOR(i, 0, b - a)h += i;
    cout << h - a << "\n";
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int num = 0;

		if (a <= b) {
			num = a;
		} else {
			num = a-1;
		}

		System.out.println(num);

		scan.close();

	}

}


Measured memory_bytes: 23764
use std::collections::HashSet;

fn main() {
    let xn = read_vec::<i32>();
    let x = xn[0];
    let n = xn[1];
    if n == 0 {
        println!("{}", x);
        return;
    }

    let v = read_vec::<i32>();
    let mut set: HashSet<i32> = HashSet::new();
    for p in v.into_iter() {
        set.insert(p);
    }

    if !set.contains(&x) {
        println!("{}", x);
        return;
    }

    let mut d = 1;
    let mut ret = 0;
    loop {
        let a = x - d;
        if !set.contains(&a) {
            ret = a;
            break
        }
        let b = x + d;
        if !set.contains(&b) {
            ret = b;
            break;
        }
        d += 1;
    }
    println!("{}", ret);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 2192
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

long long lcm(long long a, long long b)
{
    return a * b / __gcd(a, b);
}

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

    cout << lcm(A, B) << endl;
}

Measured memory_bytes: 256
import numpy as np
N = int(input())
A = list(map(int, input().split()))
ans = A[0]
if 0 in A:
  ans = 0
for i in range(N-1):
  ans = ans * A[i+1]
  if ans > 10**18 or ans < -1:
    ans = -1  

print(ans)

Measured memory_bytes: 40164
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main(){
  int r,d,x;cin>>r>>d>>x;
  int i;
  int ans=x;
  rep(i,10){
    ans=r*ans-d;
    cout<<ans<<endl;
  }

}


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

int main()
{
  int n,m;
  char s[101][11],t[101][11];
  int i,j;
  int a[101],b[101];
  int p;
  int c=-100;
  int ans=-100;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",s[i]);
    a[i]=0;
    p=0;
    for(j=0;j<i;j++){
      if(strcmp(s[i],s[j])==0){
        p=1;
        a[j]++;
        break;
      }
    }
    if(p==0) a[i]++;
  }
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%s",t[i]);
    b[i]=0;
    p=0;
    for(j=0;j<n;j++){
      if(strcmp(t[i],s[j])==0){
        p=1;
        a[j]--;
        break;
      }
    }
  }
  for(i=0;i<n;i++){
    if(ans<a[i]) ans=a[i];
  }
  if(ans<0) ans=0;
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)


int main(){
	
    std::array<unsigned long long, 86> L;
    L[0] = 1, L[1] = 3;
    int N; std::cin >> N;
    for(int i = 2; i <= 86; i++){
        L[i] = L[i - 1] + L[i - 2];
    }

    std::cout << L[N - 1];

	system("pause");
	return 0;
}

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

using namespace std;

int main(){
	int H, W, i, j;
	char ch;
	scanf("%d%d", &H, &W);
	char maze[H+1][W+1];
	long long int dp[H+1][W+1], p = 1000000007;
	for(i=0;i<H;i++){
		scanf("%c", &ch);
		for(j=0;j<W;j++){
			scanf("%c", &ch);
			if(ch == '.') maze[i][j] = 0;
			else maze[i][j] = 1;
		}

	}

	//printf("\n");


	dp[0][0] = 1;
	for(i=1;i<W;i++){
		if(dp[0][i-1] && !maze[0][i]) dp[0][i] = 1;
		else dp[0][i] = 0;
	}

	for(j=1;j<H;j++){
		if(dp[j-1][0] && !maze[j][0]) dp[j][0] = 1;
		else dp[j][0] = 0;
	}

	for(i=1;i<H;i++){
		for(j=1;j<W;j++){
			if(maze[i][j]) {
				dp[i][j] = 0;
				continue;
			}
			dp[i][j] = (dp[i][j-1] + dp[i-1][j])%p;
		}
	}
	/*for(i=0;i<H;i++){
		for(j=0;j<W;j++)
			printf("%lld ", dp[i][j]);
		printf("\n");
	}*/
	printf("%lld\n", dp[H-1][W-1]);

}

Measured memory_bytes: 9088