akhauriyash/Code-Regression huggingface dataset:
use proconio::marker::Usize1;
use std::collections::HashSet;
// use itertools::Itertools;
fn main() {
    proconio::input! {
        n:usize,
        k:i64,
        xs:[Usize1;n],
    }
    // ループを探す: 0->a->b->c->d->b->c->d
    let mut mtable = vec![];
    let mut hset = HashSet::<usize>::new(); // loop確認時の検索用
    // 初期化
    mtable.push(0);
    hset.insert(0);
    let mut curr = 0usize;
    // サイクルをみつける。サイクルの始点の値を v0 とする
    let v0 = loop {
        let next = xs[curr];
        if hset.insert(next) == false { // すでに登録済み = ループした
            break next;
        }
        mtable.push(next);
        curr = next;
    };
    let i0 = mtable.iter().position(|&v| v == v0).unwrap();
    let cycle = (mtable.len() - i0) as i64;
    // 求解
    if k <= (i0 as i64) {
        println!("{}", mtable[k as usize] + 1); 
    } else {
        println!("{}", mtable[i0 + ((k-(i0 as i64)) % cycle) as usize] + 1);
    }
}

Measured memory_bytes: 9376
#include <iostream>
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
   
   ll h,a;
   cin>>h>>a;
   if(h%a==0)
    cout<<h/a<<endl;
    else
    cout<<(h/a)+1<<endl;
   return 0;
}

Measured memory_bytes: 256
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順

using namespace std;
using ll = long long int;

ll two_pointers(vector<ll> &minus,vector<ll> &plus,ll x){
    ll sum = 0;
    int right = plus.size() - 1;
    for(int i=0;i<minus.size();i++){
        for(int j=right;j>=0;j--){
            if(minus[i]*plus[j]<=x&&j!=0) continue;
            else if(minus[i]*plus[j]>x){
                sum += plus.size() - (j + 1);
                right = j;
                if(plus[0]==minus[0]&&i>j){
                    sum--;//sumにplus[i]^2が混じっているので取り除く
                }
                break;
            }else{
                sum += plus.size() * (minus.size() - i);
                if(plus[0]==minus[0]) sum -= minus.size() - i;
                right = -1;//これによりこのfor文は以降実行されない
            }
        }
    }
    return sum;
}

ll binary_search(bool which,ll xleft,ll xright ,vector<ll> &minus,vector<ll> &plus,ll K){
    while(xright-xleft>1){//leftを右に寄せて次のxを大きく　rightを左に寄せて次のxを小さく
        ll x = (xright + xleft) / 2;
        ll a = which ? (two_pointers(minus,minus,x) + two_pointers(plus,plus,x))/2
                     : two_pointers(minus,plus,x);
        if(K<=a) xright = x;//このxの値ではK番目の数<xの範囲の数の個数を数え上げている
        else xleft = x;//(a<K)このxの値では(x<K番目の数)の範囲の数の個数の数え上げで終わっている
    }
    return xright;
}

int main(){
    ll N,K;cin>>N>>K;
    vector<ll> plus,minus;
    ll zero = 0;
    for(int i=0;i<N;i++){
        int A;cin>>A;
        if(A>0) plus.push_back(A);
        else if(A<0) minus.push_back(A);
        else zero++;
    }

    sort(minus.begin(),minus.end(),greater<ll>());
    sort(plus.begin(),plus.end());

    ll pos = minus.size()*plus.size();
    if(K<=pos){//K番目の数は負である
        ll xleft = minus.back()*plus.back() - 1;
        ll xright = -1;
        cout << binary_search(false,xleft,xright,minus,plus,K) << endl;
    }else{
        pos += zero * ( minus.size() + plus.size() ) + zero * (zero-1) / 2;
        if(K<=pos) cout << 0 << endl;
        else{//K番目の数は正である
            ll xleft = 0;
            ll p = plus.size() - 1;
            ll m = minus.size() - 1;
            ll xright;
            if(p>=1&&m>=1) xright = max(plus[p]*plus[p-1],minus[m]*minus[m-1]);
            else if(p<1&&m>=1) xright = minus[m]*minus[m-1];//plusが1個以下
            else if(p>=1&&m<1) xright = plus[p]*plus[p-1];//minusが1個以下
            sort(plus.begin(),plus.end(),greater<ll>());
            sort(minus.begin(),minus.end());//減少関数にするための処理
            cout << binary_search(true,xleft,xright,minus,plus,K-pos) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

// head

const int N=401000;
int n,vis[N];
PII p[N];
ll ret,prec[N],sufc[N],c[N];

struct node {
	ll fgp,fgv;
	ll sp,sv;
}nd[4*N];
void upd(int p) {
	nd[p].sp=(nd[p+p].sp+nd[p+p+1].sp)%mod;
	nd[p].sv=(nd[p+p].sv+nd[p+p+1].sv)%mod;
}
void setf(int p,ll fgp,ll fgv) {
	nd[p].fgv=(nd[p].fgv+fgv*nd[p].fgp)%mod;
	nd[p].fgp=nd[p].fgp*fgp%mod;
	nd[p].sv=(nd[p].sv+fgv*nd[p].sp)%mod;
	nd[p].sp=nd[p].sp*fgp%mod;
}
void build(int p,int l,int r) {
	nd[p].fgp=1;
	if (l==r) {
	} else {
		int md=(l+r)>>1;
		build(p+p,l,md);
		build(p+p+1,md+1,r);
		upd(p);
	}
}
void push(int p) {
	if (nd[p].fgp!=1||nd[p].fgv!=0) {
		setf(p+p,nd[p].fgp,nd[p].fgv);
		setf(p+p+1,nd[p].fgp,nd[p].fgv);
		nd[p].fgp=1;
		nd[p].fgv=0;
	}
}
ll query(int p,int l,int r,int tl,int tr) {
	if (tl==l&&tr==r) return nd[p].sv;
	else {
		push(p);
		int md=(l+r)>>1;
		if (tr<=md) return query(p+p,l,md,tl,tr);
		else if (tl>md) return query(p+p+1,md+1,r,tl,tr);
		else return (query(p+p,l,md,tl,md)+query(p+p+1,md+1,r,md+1,tr))%mod;
	}
}
void modify(int p,int l,int r,int x,ll v) {
	if (l==r) {
		nd[p].sp=v;
	} else {
		push(p);
		int md=(l+r)>>1;
		if (x<=md) modify(p+p,l,md,x,v);
		else if (x>md) modify(p+p+1,md+1,r,x,v);
		upd(p);
	}
}

int main() {
	scanf("%d",&n);
	rep(i,1,n+1) scanf("%d",&p[i].fi),p[i].se=i;
	sort(p+1,p+n+1);
	rep(i,1,n+1) c[i]=p[i].fi-i+1;
	prec[0]=1;
	sufc[n]=1;
	rep(i,1,n+1) prec[i]=prec[i-1]*c[i]%mod;
	per(i,1,n+1) sufc[i-1]=sufc[i]*c[i]%mod;
	ll totval=0;
	build(1,1,n);
	per(i,1,n+1) {
		totval=(totval*(c[i+1]-1)+sufc[i+1])%mod;
		ret=(ret+totval*prec[i-1]%mod*(c[i]*(c[i]-1)/2%mod))%mod;
		ll key=prec[i]*(p[i+1].fi-p[i].fi)%mod;

		setf(1,c[i+1]-1,0);
		if (i<n) modify(1,1,n,p[i+1].se,sufc[i+1]);
		setf(1,1,key);
		if (p[i].se>1) ret=(ret+query(1,1,n,1,p[i].se-1))%mod;
	}
	printf("%lld\n",ret);
}


Measured memory_bytes: 30976
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()
	n := readInt()
	a := readInt()

	println(n*n - a)
}


Measured memory_bytes: 640
use std::io::*;
use std::str::FromStr;

//input
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let N: i32 = read();
    let i: i32 = read();
    println!("{}", N - i + 1)
}


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

int main() {
  string s;
  cin>>s;
  int n=s.size();
  vector<int> a(n);
  for (int i=0;i<(n-1);++i) {
    if (s[i]=='R' && s[i+1]=='L') {
      a[i]=1;
      a[i+1]=1;
    }
  }
  for (int i=0;i<n;++i) {
    if (a[i]>=1) {
      continue;
    } else if (s[i]=='R') {
      int q=i;
      while (a[q]==0) {
        q+=2;
      }
      a[q]+=1;
    } else {
      int p=i;
      while (a[p]==0) {
        p-=2;
      }
      a[p]+=1;
    }
  }
  for (int i=0;i<n;++i) {
    cout<<a[i]<<" ";
  }
}

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define X first
#define Y second
#define INF 1000 * 1000 * 1000
#define LL long long
#define LINF INF * (LL)INF
#define PB push_back
#define SZ(a) ((LL)a.size())
#define INVALID 2392139
const LL MAX = 300005;
const LL minim = -1000 * 1000 - 1;
const LL zsuv = MAX;
using namespace std;
using namespace __gnu_pbds;
const int mod = 1000 * 1000 * 1000 + 7;
int n , a , b , c , d;
string s;
bool can(int l , int r)
{
	for(int i = l + 1; i <= r; i++)
	{
		if(s[i - 1] == '#' && s[i] == '#')
			return false;
	}
	return true;
}
int main()
{
	cin >> n >> a >> b >> c >> d >> s;
	a--;b--;c--;d--;
	
	if(a < b && b < c && c < d)
	{
		if(can(b , d))
		{
			if(can(a , c))
			{
				cout << "Yes";
				return 0;
			}
		}
		cout << "No" << endl;
		return 0;
	}
	if(can(b , d))
	{
		bool ye = false;
		for(int i = b; i <= d; i++)
		{
			if(s[i] == '.' && s[i - 1] == '.' && s[i + 1] == '.')
			{
				ye = true;
			}
		}
		if(can(a , c) && ye)
		{
			cout << "Yes";
		}
		else
		{
			cout << "No";
		}
		return 0;
	}
	cout << "No";
	
	
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <cstdint>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

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

    int64_t ans = 0;
    for (int64_t i = 0; i < S.size(); ++i) {
        if (S.at(i) != T.at(i)) ans++;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 3836
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int train, bus;
    train = min(a, b);
    bus = min(c, d);
    cout << train + bus << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll dp[101][22][2];
int N;
int A[111];
ll solve(int no,int sum,int k){
  if(sum>20) return 0;
  if(sum<0) return 0;
  if(dp[no][sum][k]!=-1) return dp[no][sum][k];
  if(no==N-2){
    if(sum+(k?-A[no]:A[no])==A[N-1]) return 1;
    return 0;
  }
  return dp[no][sum][k]=solve(no+1,sum+(k?-A[no]:A[no]),0)
    +solve(no+1,sum+(k?-A[no]:A[no]),1);
}
int main(){
  memset(dp,-1,sizeof(dp));
  scanf("%d",&N);
  for(int i=0;i<N;i++) scanf("%d",&A[i]);
  printf("%lld\n",solve(1,A[0],0)+solve(1,A[0],1));
}

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

using namespace std;

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

    std::regex re(".*7.*");

    if(std::regex_match(n, re))
    {
        std::cout << "Yes";
    } else {
        std::cout << "No";
    }

    return EXIT_SUCCESS;
} 


Measured memory_bytes: 3096
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
int a[510][510];
inline void dfs(int l,int r,int k)
{
	if(l>=r)return ;
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++)
	{
		for(int j=mid+1;j<=r;j++)a[i][j]=k;
	}dfs(l,mid,k+1),dfs(mid+1,r,k+1);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n=read();
    dfs(1,n,1);
    for(int i=1;i<n;i++)
    {
    	for(int j=i+1;j<n;j++)pr1(a[i][j]);
    	pr2(a[i][n]);
    }
    return 0;
}

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

int main() {
	int n,m;cin>>n>>m;
	int a[m],b[m];
	map<int,int> ma;
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i];
		if(a[i]==1){
			ma[b[i]]=1;
		}
		if(b[i]==1){
			ma[a[i]]=1;
		}
	}
	int flag=0;
	for(int i=0;i<m;i++){
		if(a[i]==n){
			if(ma[b[i]]==1)flag=1;
		}
		if(b[i]==n){
			if(ma[a[i]]==1)flag=1;
		}
	}
	if(flag){
		cout<<"POSSIBLE"<<endl;
	}else{
		cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#define MAX 8


int make(int *num, int c) {
	int res = 0;
	for (int i = 0; i < MAX; i++) {
		res *= 10;
		res += num[(i + c) % MAX];
	}
	return res;
}


int main() {
	int p[MAX];
	int c[MAX] = { 4,1,4,1,2,1,2,1 };
	int ex, mx, fl1, fl2;

	while (std::cin>>p[0]>>p[1]>>p[2]>>p[3]>>p[4]>>p[5]>>p[6]>>p[7]) {
		fl1 = 0;

		mx = 114514;
		fl2 = 114514810;
		for (int i = 0; i < MAX; i++) {
			int temp;
			ex = 0;
			for (int j = 0; j < MAX; j++) {
				temp = p[j] - c[(j + i) % MAX];
				if (temp > 0) ex += temp;
			}

			temp = make(c, i);
			if (mx > ex) {
				mx = ex;
				fl1 = i;
				fl2 = temp;
			} else if (mx == ex && temp < fl2) {
				mx = ex;
				fl1 = i;
				fl2 = temp;
			}
		}


		for (int i = 0; i < MAX; i++) {
			if (i != MAX - 1)
				std::cout << c[(fl1 + i) % MAX] << " ";
			else
				std::cout << c[(fl1 + i) % MAX] << std::endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
#define all(x) (x).begin(),(x).end()
int INF = 100000000;

int main() {
  int A, B, C, D, E, F; cin >> A >> B >> C >> D >> E >> F;
  double d_b = 0;
  int ans_t = 0, ans_s = 0;
  for(int i = 0; i<=30; i++) {
    for(int j = 0; j<=30; j++) {
      if (i == 0 && j == 0) {
        continue;
      }
      if (100 * i * A + 100 * j * B > F) {
        break;
      }
      double water = 100 * i * A + 100 * j * B;
      int suger_b = E * (i * A + j * B);
      for(int k = 0; k<=3000; k++) {
        for(int l = 0; l<=3000; l++) {
          double suger = k * C + l * D;
          if (suger > suger_b) {
            break;
          }
          else if (water + suger > F) {
            break;
          }
          else {
            double d = suger / (water + suger);
            if (d_b < d) {
              d_b = d;
              ans_t = water + suger;
              ans_s = suger;
            }
          }
        }
      }
    }
  }
  if (ans_t == 0 && ans_s == 0) {
    cout << A * 100 << " " << 0 << endl;
  }
  else {
    cout << ans_t << " " << ans_s << endl;
  }
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))

cnt=0
l=[]
for i in a:
  p=i//400
  if p<=7:
    l.append(p)
  else:
    cnt+=1

d=len(set(l))

if d!=0:
  print(d,d+cnt)
else:
  print(1,cnt)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [1]*(10**6+1)
for i in range(n):
    if i + 1 < n and a[i] == a[i + 1]:
        b[a[i]] = 0
        continue
    for x in range(2*a[i], 10**6+1, a[i]):
        b[x] = 0
print(sum(b[x] for x in a))

Measured memory_bytes: 32184
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline().rstrip("\n")

    while line:
        N = int(line)
        A = [int(a) for a in raw_input().rstrip("\n").split(" ")]
        sorted_A = sorted(A)
        distance = abs(sorted_A[-1] - sorted_A[0])
        print(distance)
        line = sys.stdin.readline().rstrip("\n")

if __name__ == "__main__":
    main(sys.argv)

Measured memory_bytes: 2568
S = {}  ## クラスハッシュを先頭に置いておく
S["a"],S["b"],S["c"] = 3.times.map{gets.chomp.chars}

t = "a"
while true do  ## true まで繰り返す
  if S[t].length == 0
    puts t.upcase  ## 小文字から大文字に出力する
    break
  end
  t = S[t].shift  ## 配列の先頭要素を取り除いてそれを返す
end

Measured memory_bytes: 1788
#include<iostream>

using namespace std;

int main() {
	char x[3];
	int i;
	for (i = 0; i < 3; i++) {
		cin >> x[i];
	}
	if (x[0] == x[2]) {
		cout << "Yes";
	}
	else { cout << "No"; }
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

int main() {
	ll X; cin >> X;
	ll maxV = 0;
	for (int i = 1; i*i <= X; i++) {
		for (int j = 1; j*j <= X; j++) {
			ll ans = (ll)pow(i, j);
			if (ans <= X) {
				maxV = max(maxV, ans);
			}
		}
	}
	cout << maxV << endl;

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cmath>
using namespace std;
double x1,x22;
int x2,n1,n2,ans=1;
int main()
{
	cin>>n1>>n2;
	x2=n2;
	while(x2>0)
	{
		ans*=10;
		x2/=10;
	}
	n1=n1*ans+n2;
	x1=n1;
	x2=sqrt(x1);
	x1=sqrt(x1);
	x22=x2;
	if(x1==x22)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int a[n];
	for(int i = 0; i<n; i++)
		cin>>a[i];
	sort(a,a+n);
	cout<<a[n-1]-a[0]<<endl;
	return 0;
}

Measured memory_bytes: 256
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  var a = nexts(n+1);
  if(n === 0){
   if(a[0] === 1)return 1;
   return -1;
  }
  if(a[0])return -1;
  var INF = 1e8*n;
  var dp1 = Array(n+1);
  dp1[0] = 1;
  for(var i = 1; i <= n; i++){
    dp1[i] = Math.min(dp1[i-1]*2,INF);
    dp1[i] -= a[i];
    if(dp1[i] < 0)return -1;
  }
  var dp2 = Array(n+1);
  dp2[n] = 0;
  for(var i = n-1; i >= 0; i--){
    dp2[i] = dp2[i+1]+a[i+1];
  }
  var ans = 0n;
  for(var i = 0; i <= n; i++)ans += BigInt(Math.min(dp1[i],dp2[i]) + a[i]);
  return ans.toString();
}

Measured memory_bytes: 47476
N,Q = map(int,input().split())
S = input()
AC = [0] * N
buffer = []
lr =[]
for i in range(Q):
  buffer = list(map(int,input().split()))
  lr.append(buffer)
counts = 0
for i in range(N):
  if S[i:i+2] == "AC":
    counts +=1
  AC[i] =  counts
a =[0]
AC = a + AC
for q in range(Q):
  #print(str(lr[q][0])+" "+ str(lr[q][1]))
  print(AC[lr[q][1]-1] - AC[lr[q][0]-1])

Measured memory_bytes: 30636
import java.util.*;

class Main {
        public static void main(String args[]) {
                Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
                long[] S = new long[N];
                for (int i = 0; i < N; i++) {
                        S[i] = sc.nextLong();
                }
                int Q = sc.nextInt();
                int ans = 0;
                for (int i = 0; i < Q; i++) {
                        long T = sc.nextLong();
                        for (int j = 0; j < N; j++) {
                                if (T == S[j]) {
                                        ans++;
                                        break;
                                }
                        }
                }
                System.out.println(ans);
        }
}

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

const int N=1e5+5;
long long n,ans,tot;
int x,m,y,sz,lft;
int used[N];
vector<int> v;

int main()
{
    scanf("%lld%d%d",&n,&x,&m);
    for(y=x; !used[y]; y=1ll*y*y%m)
    {
        used[y]=1;
        v.push_back(y);
    }
    sz=int(v.size());
    if(n<=1ll*sz)
    {
        sz=int(n);
        for(int i=0; i<sz; i++)
            ans+=v[i];
    }
    else
    {
        int i;
        for(i=0; i<v.size(); i++)
        {
            if(v[i]==y)
                break;
            ans+=v[i];
        }
        n-=1ll*i;
        sz=int(v.size())-i;
        for(int j=i; j<v.size(); j++)
            tot+=v[j];
        ans+=n/sz*tot;
        lft=int(n%(1ll*sz));
        for(int j=i; j<i+lft; j++)
            ans+=v[j];
    }
    printf("%lld\n",ans);
    return 0;
}


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

using namespace std;

int main() {
int a;
int b;
int c;
int d;
cin>>a>>b>>c>>d;
if((abs(b-a)<=d&&abs(c-b)<=d)||abs(c-a)<=d){
	cout<<"Yes";
}
else{
	cout<<"No";
}
}

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

int main(){
  //input 入力
  int h,w;cin >> h >> w;

  //solve 処理
  rep(i,h){
    string s;cin >> s;
    cout << s << endl << s << endl;
  }
  
  //output 出力
  return 0;
  
}

Measured memory_bytes: 256
load = list()
n,m = map(int,input().split())
h = list(map(int,input().split()))
for i in range(m):
  x = list(map(int,input().split()))
  load.append(x)

good = [1] * n
for i in range(m):
  load[i][0] -= 1
  load[i][1] -= 1

for i,data in enumerate(load):
  #print(i,data) #data[0] , data[1] 展望台の番号
  if(h[data[0]] == h[data[1]]):
    good[data[0]] = 0
    good[data[1]] = 0
    continue

  if(h[data[0]] < h[data[1]]):
    good[data[0]] = 0
  elif(h[data[1]] < h[data[0]]):
    good[data[1]] = 0

print(sum(good))

Measured memory_bytes: 32012
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    int N; string S; cin>>N>>S;
    string ans=S;
    int count=0;
    for(int i=0;i<N;i++){
        int p=-1;
        if(S.at(i)=='(') p=1;
        count+=p;
        if(count==-1) {ans.insert(0,"("); count++;}
    }
    while(count>0){
        ans+=')';
        count--;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[200001];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=2;i<=n;++i)
	{
		if(a[i]==a[i-1])
		{
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long a = sc.nextLong();
		long b = sc.nextLong();
		int c = sc.nextInt();
		int d = sc.nextInt();
		long ans = 0;
		long countc = 0;
		long countd = 0;
		long countlcm = 0;
		long gcd = 0;
		long lcm = 0;

		long tmpc = c;
		long tmpd = d;

		if (d > c) {
			long tmp = tmpd;
			tmpd = tmpc;
			tmpc = tmp;
		}

		long r = 0;
		while (tmpd > 0) {
			r = tmpc % tmpd;
			tmpc = tmpd;
			tmpd = r;
		}

		lcm = (long) c * d / tmpc;

		countc = b / c - a / c;
		if (a % c == 0) {
			countc++;
		}
		countd = b / d - a / d;
		if (a % d == 0) {
			countd++;
		}
		countlcm = b / lcm - a / lcm;
		if (a % lcm == 0) {
			countlcm++;
		}
		ans = b - a + 1 - (countc + countd - countlcm);

		System.out.println(ans);

		//		System.out.println(countc);
		//		System.out.println(countd);
		//		System.out.println(countlcm);

	}
}

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

int main() {
    int n, x, t;
    cin>>n>>x>>t;
    int sum = 0;
    int time = 0;
    while(sum < n){
        time+=t;
        sum+=x;
    }
    cout<<time<<endl;
    return 0;
}

Measured memory_bytes: 3640
#include "bits/stdc++.h"
#define LF '\n'
#define ALL(x) x.begin(), x.end()
#define iostreamBooster() { cin.tie(nullptr); ios_base::sync_with_stdio(false); }
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
template<class Itr> void dump(Itr begin, Itr end) { for (;begin != end; ++begin) clog << *begin << LF; }

signed main()
{
  int a,b;
  cin >> a >> b;
  a *= b;
  puts(a&1 ?  "Odd" : "Even");

  return 0;
}



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

using namespace std;

const int N = 100 + 5, NO_OF_LETTERS = 4, MOD = 1e9 + 7, T_INDEX = 3;
long long no_of_strings[N][NO_OF_LETTERS][NO_OF_LETTERS][NO_OF_LETTERS];
char letter[NO_OF_LETTERS] = {'A', 'C', 'G', 'T'};

int ok(int last_1, int last_2, int last_3, int last_4)
{
    char l1 = letter[last_1], l2 = letter[last_2], l3 = letter[last_3], l4 = letter[last_4];

    if(l1 == 'A' && l2 == 'G' && l4 == 'C')
        return false;
    if(l1 == 'A' && l3 == 'G' && l4 == 'C')
        return false;
    if(l1 == 'A' && l2 == 'G' && l3 == 'C')
        return false;
    if(l2 == 'A' && l3 == 'G' && l4 == 'C')
        return false;
    if(l1 == 'G' && l2 == 'A' && l3 == 'C')
        return false;
    if(l2 == 'G' && l3 == 'A' && l4 == 'C')
        return false;
    if(l1 == 'A' && l2 == 'C' && l3 == 'G')
        return false;
    if(l2 == 'A' && l3 == 'C' && l4 == 'G')
        return false;

    return true;
}

int main()
{
    int length;
    cin >> length;

    vector <long long> total(length + 1, 0);

    for(int i = 1; i <= length; i++)
    {
        for(int last_1 = 0; last_1 < NO_OF_LETTERS; last_1++)
        {
            for(int last_2 = 0; last_2 < NO_OF_LETTERS; last_2++)
            {
                for(int last_3 = 0; last_3 < NO_OF_LETTERS; last_3++)
                {
                    no_of_strings[i][last_1][last_2][last_3] = 0;

                    for(int last_4 = 0; last_4 < NO_OF_LETTERS; last_4++)
                    {
                        if(i == 1)
                        {
                            no_of_strings[i][last_1][T_INDEX][T_INDEX] = 1;
                        }
                        else if(i == 2)
                        {
                            no_of_strings[i][last_1][last_2][T_INDEX] = 4;
                        }
                        else if(i == 3)
                        {
                            if(ok(T_INDEX, last_3, last_2, last_1))
                            {
                                no_of_strings[i][last_1][last_2][last_3] = 1;
                            }
                        }
                        else if(ok(last_4, last_3, last_2, last_1))
                        {
                            no_of_strings[i][last_1][last_2][last_3] += no_of_strings[i - 1][last_2][last_3][last_4];
                        }
                    }

                    no_of_strings[i][last_1][last_2][last_3] %= MOD;

                    total[i] = (total[i] + no_of_strings[i][last_1][last_2][last_3])%MOD;
                }
            }
        }
    }

    cout << total[length];
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

bool oomoji(char ch){
	int num=(int)(ch-'a');
	if(num>=0&&num<26)return true;
	else return false;
}

int main(){
	string s;
	cin>>s;
	bool check=true;
	if(s[0]!='A')check=false;
	string tmp=s.substr(2,s.size()-3);
	int alt=0;
	rep(i,tmp.size()){
		if(tmp[i]=='C')alt++;
	}
	if(alt!=1)check=false;
	rep(i,s.size()){
		if(i==0)continue;
		if(i>=2&&i<=s.size()-2){
			if(s[i]!='C'&&!oomoji(s[i])){
				check=false;
			}
		}else{
			if(!oomoji(s[i]))check=false;
		}
	}
	cout<<((check)?"AC":"WA")<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;


// I wrote this solution after reading the editorial.
int main(void){
  int n, k;
  cin >> n >> k;
  VL a(n);
  REP(i, 0, n) {
    cin >> a[i];
  }
  VL cum(n + 1), pos_left(n + 1), pos_right(n + 1);
  cum[0] = pos_left[0] = pos_right[n] = 0;
  REP(i, 0, n) {
    cum[i + 1] = cum[i] + a[i];
    pos_left[i + 1] = pos_left[i] + max(a[i], 0LL);
  }
  for (int i = n - 1; i >= 0; --i) {
    pos_right[i] = pos_right[i + 1] + max(a[i], 0LL);
  }
  ll ma = 0;
  REP(i, 0, n - k + 1) {
    ma = max(ma, pos_left[i] + max(0LL, cum[i + k] - cum[i]) + pos_right[i + k]);
  }
  cout << ma << endl;
}


Measured memory_bytes: 3328
#include<stdio.h>

int main(void){
  int n;
  scanf("%d",&n);

  int a[n] , count = 0;
  for(int i = 0;i < n;i ++){
    scanf("%d",&a[i]);
    if(a[i]%2 == 1){
      count ++;
    }
  }

  if(count%2 == 0){
    printf("YES\n");
  }

  else{
    printf("NO\n");
  }

  return 0;
}

Measured memory_bytes: 2020
#include<bits/stdc++.h>
#define ll long long
#define db double
#define lowbit(p) (p&(-p))
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define A first
#define B second
using namespace std;
void read(int &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void read(ll &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void Min(int &x,int y){
	if (x>y)x=y;
}
void Max(int &x,int y){
	if (x<y)x=y;
}
void Min(ll &x,ll y){
	if (x>y)x=y;
}
void Max(ll &x,ll y){
	if (x<y)x=y;
}
/*
题意:
每次选择两个点并且把其间所有的边染色,求有多少种配对方案使得所有边都被染色.

分析:
不合法的方案一定存在有一颗树内所有的点都内销了...

容斥?

树形计数DP容斥

那么DP状态?
容斥系数?
还有一堆东西?

至少一条边不合法/
至少两条边不合法...?

转移是n^3的不能考虑.
不过稍作转化说不定就可以了


还没有考虑(fa[x]->x)这一条边
dp[x][c]: 子树合法,子树内还有c条边没有连出来

转移的时候用到一个tmp数组

dp[x][c]:表示x的子树被划分为了c个联通块.

dp[x][i+j]=dp[x][i]*dp[to][j]
dp[x][i+j-1]=dp[x][i]*dp[to][j]

tmp[c]:表示当前子树内有c个点直接和x相连.


既需要知道块的个数,还需要知道块的大小

块的个数只需要知道奇偶,直接记在系数里面

*/
#define mo 1000000007
#define M 5005
struct ed{
	int x,nx;
}e[M<<1];
ll dp[M][M],g[M],tmp[M];
int cnt[M],nx[M],n,ecnt=1;
void add(int x,int y){
	e[ecnt]=(ed){y,nx[x]};
	nx[x]=ecnt++;
}
void upd(ll &x,ll y){
	x=(x+y)%mo;
}
void dfs(int f,int x){
	cnt[x]=1;
	dp[x][1]=1;
	int i,j,k,to;
	for (i=nx[x];i;i=e[i].nx)if (e[i].x!=f){
		dfs(x,e[i].x);
		to=e[i].x;
		for (k=0;k<=cnt[x];k++){
			for (j=0;j<=cnt[to];j++){
				upd(tmp[j+k],dp[x][k]*dp[to][j]%mo);
			}	
		}
		cnt[x]+=cnt[to];
		for (k=0;k<=cnt[x];k++){
			dp[x][k]=tmp[k];
			tmp[k]=0;
		}
	}
	for (i=0;i<=cnt[x];i+=2){
		upd(dp[x][0],-dp[x][i]*g[i]%mo);
	}
//	printf("%d:",x);
//	for (i=0;i<=cnt[x];i++){
//		printf("%lld ",dp[x][i]);
//	}
//	printf("\n");
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	freopen("1.in","r",stdin);
	read(n);
	g[0]=1;
	int i,x,y;
	ll res=0;
	for (i=2;i<=n;i+=2)g[i]=(g[i-2]*(i-1))%mo;
	for (i=1;i<n;i++){
		read(x); read(y);
		add(x,y);
		add(y,x);
	}
	dfs(1,1);
	res=-dp[1][0];
	res=(res%mo+mo)%mo;
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 194944
<?php
$input = trim(fgets(STDIN));
list($a,$b) = explode(' ',$input);

if ($a < $b) {
    echo  "a < b". PHP_EOL;
} elseif ($a > $b) {
    echo "a > b". PHP_EOL;;
} else {
     echo "a == b". PHP_EOL;;
}
exit;
?>

Measured memory_bytes: 15412
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


################################
n,w,r = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    #edge[y].append([z,x]) 
D=dijkstra_heap(r,edge)


for index in range(n):
    if D[index]==10**20:
        D[index]='INF'
    print(D[index])


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

#define int long long
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; }

signed main(){
	int a, b, c;
	cin >> a >> b >> c;
	if(b-a == c-b){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#define NN 999999
int main(){
	int i,j,n,sum;
	bool prime[NN];
	for(i=0;i<NN;i++) prime[i]=true;
	while(1){
		sum=0;n=0;
		scanf("%d",&n);
		if(!n) break;
		for(i=2;i<NN;i++){
			for(j=i*2;j<NN;j=j+i) prime[j]=false;
		}
		for(i=2,j=0;j<n;i++){
			if(prime[i]==true){
				sum+=i;
				j++;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 2004
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long x,a,b;
	cin>>x;
	for(long long i=-130;i<=130;i++){
	    for(long long j=-130;j<=130;j++){
	        if(i*i*i*i*i-j*j*j*j*j==x){
	            cout<<i<<' '<<j;
	            return 0;
	        }
	    }
	}
}


Measured memory_bytes: 3628
N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(lambda x: int(x)-1, input().split())

sum = 0
maxl = max(L)
minr = min(R)
for id in range(N):
    if maxl <= id and id <= minr:
        sum += 1

print(sum)


Measured memory_bytes: 10868
#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    if(n>m){
        for(int i=0;i<n;i++){
            cout<<m;
        }
    }else{
        for(int i=0;i<m;i++){
            cout<<n;
        }
    }
}


Measured memory_bytes: 888
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner s=new Scanner (System.in);
		String now=s.nextLine();
		char ans[]=now.toCharArray();
		for(int i=0;i<now.length()-4;i++){
			if(now.substring(i,i+5).equals("apple")){
				ans[i]='p';
				ans[i+1]='e';
				ans[i+2]='a';
				ans[i+3]='c';
				ans[i+4]='h';
			}else if(now.substring(i,i+5).equals("peach")){
				ans[i]='a';
				ans[i+1]='p';
				ans[i+2]='p';
				ans[i+3]='l';
				ans[i+4]='e';
			}
		}
		System.out.println(new String(ans));
	}
}

Measured memory_bytes: 11000
h,w = map(int,input().split())
sl = []

for i in range(h):
    s = list(map(str,input().split()))
    sl.append(s)

for i in range(h):
    for j in range(w):
        if sl[i][j] == "snuke":
            ans = (i, j)

ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

print(ascii_uppercase[ans[1]] +  str(ans[0]+1))

Measured memory_bytes: 3060
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int x[] = {
	1, 8, 6, 3,
	2, 0, 7, 4,
	3, 1, 8, 5,
	4, 2, 0, 6,
	5, 3, 1, 7,
	6, 4, 2, 8,
	7, 5, 3, 0,
	8, 6, 4, 1,
	0, 7, 5, 2
};
int a[362889][9], p[11], cnt, fact[11]; bool used[11];
void build(int pos) {
	if (pos == 9) {
		for (int i = 0; i < 9; i++) a[cnt][i] = p[i];
		cnt++;
		return;
	}
	for (int i = 0; i < 9; i++) {
		if (!used[i]) {
			used[i] = true; p[pos] = i;
			build(pos + 1);
			used[i] = false;
		}
	}
}
struct state {
	int pos, cost;
};
bool operator<(const state& s1, const state& s2) {
	return s1.cost < s2.cost;
}
int c[2], dist[362889], g[1451529], v[11], d[11], e[11];
int perm() {
	int ret = 0;
	for (int i = 0; i < 9; i++) {
		for (int j = i + 1; j < 9; j++) {
			if (v[i] > v[j]) ret += fact[8 - i];
		}
	}
	return ret;
}
int main() {
	build(0); fact[0] = 1;
	for (int i = 1; i <= 9; i++) fact[i] = fact[i - 1] * i;
	for (int i = 0; i < 362880; i++) {
		int ptr = -1;
		for (int j = 0; j < 9; j++) {
			if (a[i][j] == 0) ptr = j;
			v[j] = a[i][j];
		}
		for (int j = 0; j < 4; j++) {
			swap(v[ptr], v[x[ptr * 4 + j]]);
			g[i * 4 + j] = perm();
			swap(v[ptr], v[x[ptr * 4 + j]]);
		}
	}
	while (cin >> c[0] >> c[1], c[0] | c[1]) {
		vector<int> d(9), e(9);
		for (int i = 0; i < 9; i++) cin >> v[i]; int fd = perm();
		for (int i = 0; i < 9; i++) cin >> v[i]; int fe = perm();
		fill(dist, dist + 362880, 999999999); dist[fd] = 0;
		priority_queue<state> que; que.push(state{ fd, 0 });
		while (!que.empty()) {
			int u = que.top().pos; que.pop();
			for (int i = u * 4; i < u * 4 + 4; i++) {
				int z = g[i], cost = c[(i & 2) >> 1];
				if (dist[z] > dist[u] + cost) {
					dist[z] = dist[u] + cost;
					que.push(state{ z, -dist[z] });
				}
			}
		}
		cout << dist[fe] << endl;
	}
	return 0;
}

Measured memory_bytes: 25728
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define double long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
ll n;
double x[15],y[15];
double calc(int a,int b)
{
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main()
{
	cin>>n;
	double res=1.0;
	double ans=0.0;
	double temp=n-1;
	res=n*(n-1);
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j==i) continue;
			//cout<<res<<endl;
			ans+=(calc(i,j)/res)*temp;
		}
	}
	printf("%.10Lf\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int h, w;
	int i;
	char s[100][101];
	scanf("%d %d", &h, &w);
	for (i = 0; i < h; i++) {
		scanf("%s", s[i]);
	}
	for (i = 0; i < w + 2; i++) putchar('#');
	putchar('\n');
	for (i = 0; i < h; i++) {
		putchar('#');
		printf("%s", s[i]);
		puts("#");
	}
	for (i = 0; i < w + 2; i++) putchar('#');
	putchar('\n');
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
int main(int argc, const char * argv[]) {
    char s[101];
    char p[101];
    int z=0;
    long int i,j;
    long int len_s;
    long int len_p;
    int judge=0;
    long int mmm;//?¨??????¨
    scanf("%s",s);
    len_s=strlen(s);
    scanf("%s",p);
    len_p=strlen(p);
    for(i=0;i<len_s;i++){
        judge=0;
        z++;
        for(j=0;j<len_p;j++){
            mmm=i+j;
            if(mmm>=len_s){
                mmm=mmm-len_s;
            }
            if(p[j]==s[mmm]){
                judge++;
            }if(judge==len_p){
                printf("Yes\n");
                z=0;
                break;
            }
        }if(z==0){
            break;
        }
        if(z==len_s){
        printf("No\n");
        }
    }

    
    return 0;
}

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

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807
#define sortR(a,b) sort(a, b, greater<int>())

using namespace std;

long long GCD(long long a, long long b) {
	if (a < b)
		swap(a, b);
	if (b == 0) return a;
	else return GCD(b, a % b);
}
bool sosuu_check(int num) {
	int i;
	for (i = 2; i <= sqrt(num); ++i) {
		if (num%i == 0)
			return false;
	}
	return (num < 2) ? false : true;
}
int main() {
	int N, Y, j, i;
	ll sum;
	cin >> N >> Y;
	REP(i, N+1) {
		REP(j, N - i + 1) {
			sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
			if (sum == Y) {
				cout << i << " " << j << " " << N - i - j << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};



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

    int n;
    cin >> n;
    vl a(n);
    rep(i,n){
        cin >> a[i];
    }
    int cnt = 0;
    rep(i,n){
        while(i+1<n && a[i]==a[i+1])++i;
        
        if(i+1<n && a[i] < a[i+1]){
            while(i+1<n && a[i] <= a[i+1])++i;
        }
        else if(i+1<n && a[i]>a[i+1]){
            while(i+1 && a[i] >= a[i+1])++i;
        }
        ++cnt;
    }

    cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1024
import math
a,b=map(int,input().split())
for i in range(1,b+1):
  if a-b+1<i:
    print(0)
  else:
    c=math.factorial(a-b+1)//(math.factorial(i)*math.factorial(a-b+1-i))
    d=math.factorial(b-1)//(math.factorial(i-1)*math.factorial(b-i))
    print((c*d)%1000000007)


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



int main(){
	int a,b;
	cin >> a >> b;
	if(a*b*1%2 || a*b*2%2 || a*b*3%2) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

int main() {
    /* Input */
    long long int x;
    cin >> x;

    /* Main Logic */
    long long int ans = 0;
    long long int yokin = 100;
    while (yokin < x) {
        yokin += yokin / 100;
        ans++;
    }

    /* Output */
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
//#include <stdlib.h>
//#include <string.h>

using namespace std;

int main()
{
    int n,m;
    cin>>n;
    cin>>m;
    n=n%500;
    if(n>m)
        cout<<"No";
    else
        cout<<"Yes";

    return 0;
}


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

int main() {
    int a, b, c, n; std::cin >> a >> b >> c >> n;
    unsigned long long cnt = 0;

    int aa = 0;
    while (aa * a <= n) {
        int bb = 0;
        while (aa * a + bb * b <= n) {
            if ((n - aa * a - bb * b) % c == 0) {
                cnt++;
            }
            bb++;
        }
        aa++;
    }

    std::cout << cnt << std::endl;
    return 0;
}

Measured memory_bytes: 888
# AOJ 1069: Squid Multiplication
# Python3 2018.7.10 bal4u

def gcd(a, b):
	while b != 0:
		r = a % b
		a, b = b, r
	return a

while True:
	n = int(input())
	if n == 0: break
	even, odd = [], []
	b = list(map(int, input().split()))
	for i in b:
		if i & 1: odd.append(i)
		else: even.append(i)
	even.sort()
	odd.sort()
	e1, e2, o1 = even[0], even[1], odd[0];
	g = gcd(e1, o1)
	e1, o1 = e1//g, o1//g
	g = gcd(e2, o1)
	e2, o1 = e2//g, o1//g
	g = int((e1 * e2)**0.5)
	print(g)
	print(*[i//g for i in even])



Measured memory_bytes: 10052
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define ll long long
using namespace std;
int main(){
	vector<int>a(3);
	for(int i=0;i<3;i++)
	cin>>a[i]; 
	sort(a.begin(),a.end());
	if(a[0]==5&&a[1]==5&&a[2]==7){
		cout<<"YES\n";
    }else{
    	cout<<"NO\n";
	}
	
	return 0;
}


Measured memory_bytes: 256
import math
A, B, H, M = map(int,input().split())

time = H*60+M
rH = math.pi/6/60*(time%7200)
rM = math.pi/30*(time%60)
rad = abs(rH - rM)

l2 = A**2+B**2-2*A*B*math.cos(rH-rM)
print(l2**0.5)		

Measured memory_bytes: 9508
#include <stdio.h>

int n, a, b;

int main(void)
{
    scanf("%d %d %d", &n, &a, &b);
    int num;
    num = n * a;
    if (num > b) {
       printf("%d", b);
       } else if (num <= b) {
           printf("%d", num);
       }
    return 0;
}

Measured memory_bytes: 128
#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 LL long long

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

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

// lcm of several variables
long long lcm_n(int n,long long *a){
  LL ret=a[0];
  for(int i=0;i<n-1;i++){
    ret=lcm(ret,a[i+1]);
  }
  return ret;
}

// output the smallest non-negative integer N s.t. N%quots[i]=rems[i]
// if contradiction occurs, output -1
long long reminder(int n,long long *rems,long long *quots){
  if(n==1)return rems[0];
  long long x1,x2,y1,y2;
  x1=rems[0];
  y1=quots[0];
  for(int i=0;i<n-1;i++){
    x2=rems[i+1];
    y2=quots[i+1];
    for(int j=0;j<y2;j++){
      if((x1+j*y1)%y2==x2){
	x1=(x1+j*y1)%lcm(y1,y2);
	y1=lcm(y1,y2);
	break;
      }
      if(j==y2-1)return -1;
    }
  }
  return x1;
}

LL n,m,d;
LL a[10],adum[10];
LL r[100][10],rdum[10];

int main(){
  cin>>n>>m>>d;
  REP(i,m)
    cin>>a[i];
  REP(i,d){
    REP(j,m)
      cin>>r[i][j];
  }
  REP(i,d){
    int num=0;
    REP(j,m){
      if(r[i][j]>=0){
	adum[num]=a[j];
	rdum[num]=r[i][j];
	num++;
      }
    }
    if(!num)continue;
    LL ret=reminder(num,rdum,adum);
    if(ret<0 || n<ret){
      n=-1;
      break;
    }
    n=ret+lcm_n(num,adum)*((n-ret)/lcm_n(num,adum));
  }

  cout<<n<<endl;
  return 0;
}



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

const int N = 100;

char a[N], b[N], c[N];

int main(){
	scanf("%s%s%s", a, b, c);
	int lena = strlen(a), lenb = strlen(b), lenc = strlen(c);
	printf(a[lena - 1] == b[0] && b[lenb - 1] == c[0] ? "YES\n" : "NO\n");
	return 0;
}

Measured memory_bytes: 256