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

using namespace std;


#define ff				first
#define ss				second
#define int				long long
#define pb				push_back
#define mp				make_pair
#define pii				pair<int,int>
#define vi				vector<int>
#define mii 			map<int,int>
#define	pqb				priority_queue<int>
#define pqs				priority_queue<int,vi,greater<int> >
#define setbits(x)		__builtin_popcountll(x)
#define zrobits(x)		__builtin_ctzll(x)
#define mod				1000000009
#define inf 			1e18
#define ps(x,y)			fixed<<setprecision(y)<<x
#define mk(arr,n,type)	type *arr = new type[n]
#define w(x)			int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl			'\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl

const int maxn = 1e5 + 5;
void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

}


bool isPrime(int n)
{
	if (n <= 1)
		return false;
	if (n <= 3)
		return true;
	if (n % 2 == 0 || n % 3 == 0)
		return false;
	for (int i = 5; i * i <= n; i += 6)
	{
		if (n % i == 0 || n % (i + 2) == 0)
			return false;

	}
	return true;
}

set<int> Sieve(int n)
{
	bool prime[n + 1];
	memset(prime, true, sizeof(prime));
	for (int i = 2; i * i <= n; i++)
	{
		if (prime[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				prime[j] = false;
			}
		}
	}
	set<int> primes;

	for (int i = 2; i <= n; i++)
	{
		if (prime[i])
			primes.insert(i);
	}
	return primes;
}
set<int> primeFactors(int  n)
{
	set<int> factors;
	while (n % 2 == 0)
	{
		n /= 2;
		factors.insert(2);

	}
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		// int count = 0;
		while (n % i == 0)
		{
			factors.insert(i);
			n /= i;
		}
	}
	if (n > 2)
		factors.insert(n);
	return factors;
}

int power(int x, unsigned int y, int p)
{
	int res = 1;

	x = x % p;

	if (x == 0) return 0;
	;
	while (y > 0)
	{

		if (y & 1)
			res = (res * x) % p;

		y = y >> 1; // y = y/2
		x = (x * x) % p;
	}
	return res;

}

// Graph------------------------------------------------------------------------


int32_t main()
{
	FIO;
	// c_p_c();
	// --------------------------------------------------
	// Never GIVE UP !!!!


	int x, k, d;
	cin >> x >> k >> d;
	x = abs(x);
	int straigt = min(k, x / d);
	k -= straigt;
	x -= straigt * d;
	if (k & 1)
	{
		cout << d - x << endl;
	}
	else
		cout << x << endl;

}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    long long sum=0,p=0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    int mid = sum/n,ans=0,ans1=0;
    for(int i=0;i<n;i++)
    {
        ans += pow((arr[i]-mid),2);
        ans1 += pow((arr[i]-mid-1),2);
    }
    cout<<min(ans,ans1)<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int val, k;
	scanf("%d", &val);
	scanf("%d", &k);
	int jwb = 1;
	
	for(int i = 0; i < val; i++){
		if(jwb < k){
			jwb *= 2;
		} else{
			jwb += k;
		}
	}
	printf("%d", jwb);
	return 0;
}

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

using namespace std;
#define ll long long
#define f first
#define s second

int main()
{
    ll n,x,tmp,tmp2,tmp3 , l=1 , h=1e9+5 , mid , c=0 , xx , ans = 1;
    map <ll , bool> mp;
    cin >> n >> x;
    vector<ll> vec;
    for (int i=1; i<=n; i++)
    {
        cin >> xx;
        vec.push_back(xx);
    }

    tmp = abs(vec[0] - x);
    for (int i=1; i<vec.size(); i++)
    {
        tmp = __gcd(tmp , abs(x-vec[i]));
    }
    cout << tmp << "\n";

    return 0;
}


Measured memory_bytes: 1400
import sys

import numpy as np
MOD = 10 ** 9 + 7
U = 10 ** 6
def mod_cumprod(a, p=MOD):
  l = len(a); sql = int(np.sqrt(l) + 1)
  a = np.resize(a, sql**2).reshape(sql, sql)
  for i in range(sql - 1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
  for i in range(sql - 1): a[i+1] *= a[i, -1]; a[i+1] %= p
  return np.ravel(a)[:l]

def make_fac_ifac(n=U, p=MOD):
  fac = np.arange(n + 1); fac[0] = 1
  fac = mod_cumprod(fac)
  ifac = np.arange(n + 1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
  ifac = mod_cumprod(ifac)[n::-1]
  return fac, ifac

fac, ifac = make_fac_ifac()

def mod_choose(n, r, p=MOD):
  if r > n or r < 0: return 0
  return fac[n] * ifac[r] % p * ifac[n-r] % p

def make_choose_n_table(n=10 ** 9, r=U, p=MOD):
  table = [None] * (r + 1)
  table = np.arange(n + 1, n - r, -1); table[0] = 1
  table[1:] = mod_cumprod(table[1:]) * ifac[1:r+1] % p
  return table

mod_choose_n = make_choose_n_table()

n, m = map(int, sys.stdin.readline().split())

def main():
  d = abs(n - m)
  if d >= 2: res = 0
  elif d == 1: res = fac[n] * fac[m] % MOD
  else: res = fac[n] * fac[m] % MOD * 2 % MOD
  print(res)
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 74940
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;
int main(int argc, char const *argv[]) {
  string s;std::cin >> s;
  re(i, 12){
    if(i==4) std::cout << ' ';
    std::cout << s[i];
  }
  std::cout << '\n';
  return 0;
}


Measured memory_bytes: 888
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  size_t h, w, n;
  scanf("%zu %zu %zu", &h, &w, &n);

  if (h > w) std::swap(h, w);

  printf("%zu\n", (n+w-1)/w);
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s-1);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int d, g;cin>>d>>g;
    g/=100;
    int p[d], c[d];
    REP(i, d) {
        int x,y;cin>>x>>y;
        p[i]=x;
        c[i]=y/100;
    }

    int size = d, ans = 1e9;
    REP(i, 1 << size) {
        int score = 0, solve = 0;
        REP(j, size) {
            if (i & (1 << j)) {
                score += (j+1)*p[j] + c[j];
                solve += p[j];
            }
        }
        if (score >= g) {
            ans = min(ans, solve);
            continue;
        }

        RREP(j, size, 0) {
            if (!(i & (1 << j))) {
                if (g - score > (j+1)*(p[j]-1)) {
                    score += (j+1)*(p[j]-1);
                    solve += p[j]-1;
                } else {
                    int num = (g-score+j)/(j+1);
                    score += (j+1)*num;
                    solve += num;
                    break;
                }
            }
        }

        if (score >= g) {
            ans = min(ans, solve);
        } else {
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
K, N = [int(_) for _ in input().split()]
# X = int(input())
A = [int(_) for _ in input().split()]
A.sort()
diff = [A[i+1] - A[i] for i in range(N-1)]
diff.append(A[0] + K - A[-1])
print(K-max(diff))


Measured memory_bytes: 25452
#include<bits/stdc++.h>
using namespace std;
#define INF (1<<30)
int hako[2][10001];
int main(){
  int m,n;
  int p[10001],c,e;
  cin >> m >> n;
  for(int i=0;i<m;i++) cin >> p[i];
  sort(p,p+m,greater<int>());
  fill_n(*hako,2*10001,INF);
  for(int i=1;i<=n;i++){
    cin >> c >> e;
    for(int j=1;j<=m;j++){
      if(j<=c) hako[1][j] = min(hako[0][j],e);
      else hako[1][j] = min(hako[0][j],hako[0][j-c]+e);
    }
    for(int j=1;j<=m && i!=n;j++){
      hako[0][j] = hako[1][j];
      hako[1][j] = INF;
    }
  }
  int ma = 0,manju = 0;
  for(int i=1;i<=m;i++){
    if(hako[1][i] == INF) continue;
    manju += p[i-1];
    ma = max(ma,manju-hako[1][i]);
  }
  cout << ma << endl;
  return (0);
}

Measured memory_bytes: 3256
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n,*c=map(int,open(0).readlines())\n"
"l=[-1]*2**18\n"
"b=[]\n"
"for i in range(n):\n"
"  b.append(l[c[i]])\n"
"  l[c[i]]=i\n"
"dp=[1]+[0]*n\n"
"for i in range(1,n):\n"
"  dp[i]=dp[i-1]\n"
"  if c[i]!=c[i-1]and b[i]>-1:\n"
"    dp[i]=(dp[i]+dp[b[i]])%(10**9+7)\n"
"print(dp[-2])\n"
"\"";
  system(s);
  return 0;
}            

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
struct Trie {
	struct Node {
		Node *ch[26] = {NULL, NULL};
		int cnt[26] = { 0 };
	};
	Node *root = NULL;
	Node *nodes = new Node[1000001];
	int head = 0;
	void add(std::string s) {
		std::reverse(s.begin(), s.end());
		Node **node = &root;
		std::vector<Node *> path;
		s.push_back((char) 0);
		for (auto i : s) {
			if (!*node) *node = nodes + head++;
			path.push_back(*node);
			if (!i) continue;
			node = &(*node)->ch[i - 'a'];
		}
		s.pop_back();
		std::reverse(s.begin(), s.end());
		path.pop_back();
		std::reverse(path.begin(), path.end());
		bool used[26] = { 0 };
		for (int i = 0; i < (int) s.size(); i++){
			used[s[i] - 'a'] = true;
			for (int j = 0; j < 26; j++) path[i]->cnt[j] += used[j];
			/*
			for (int j = 0; j < 26; j++) {
				if (path[i]->cnt[j]) std::cerr << "    " << j << ":" << path[i]->cnt[j] << std::endl;
			}
			std::cerr << "  --- " << std::endl;*/
		}
		// std::cerr << std::endl;
	}
	int cnt(std::string s) {
		std::reverse(s.begin(), s.end());
		char back = s.back();
		s.pop_back();
		// std::cerr << s << "  +  " << back << std::endl;
		Node *cur = root;
		for (auto i : s) {
			if (!cur) return 0;
			cur = cur->ch[i - 'a'];
		}
		if (!cur) return 0;
		return cur->cnt[back - 'a'];
	}
};

int main() {
	int n = ri();
	std::string s[n];
	for (auto &i : s) std::cin >> i;
	std::sort(s, s + n, [] (auto &i, auto &j) { return i.size() > j.size(); });
	
	Trie trie;
	int64_t res = 0;
	for (auto i : s) {
		res += trie.cnt(i);
		trie.add(i);
	}
	printf("%" PRId64 "\n", res);
	return 0;
}


Measured memory_bytes: 321784
//B - Contest with Drinks Easy: 
//Assunto: 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define loop(i, a, b) for(int i = a; i < b; i++)
#define loopBack(i, a, b) for(int i = a; i >= b; i--)
#define INF INT_MAX
#define LINF LLONG_MAX
#define DINF DBL_MAX
#define MAX 100050
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n, m, d, t, total = 0, ans;
    cin >> n;
    vector<int> time(n);
    loop(i, 0, n) {
        cin >> time[i];
        total += time[i];
    }
    cin >> m;
    loop(i, 0, m) {
        cin >> d >> t;
        ans = (total - time[d-1]) + t;
        cout << ans << '\n';
    }
}

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

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define clr(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
typedef pair<ll, ll> pii;
typedef vector< ll > vl;
typedef vector< pii > vpii;
const ll N= 1e5+55,mod = 1e9+7;
int main() {
// 	freopen("Task.in","r",stdin);freopen("Task.out","w",stdout);
	string s[100];
	ll h,w,i,j,c=0;
	cin>>h>>w;
	for(i=0;i<h;i++)cin>>s[i];
	for(i=0;i<h;i++){
		for(j=0;j<s[i].size();j++){
			c=0;
			if(s[i][j]=='#'){
				cout<<s[i][j];
				continue;
			}
			if((j-1)>-1)if(s[i][j-1]=='#')c++;
			if((j+1)<w)if(s[i][j+1]=='#')c++;
			if((i-1)>-1)if(s[i-1][j]=='#')c++;
			if((i+1)<h)if(s[i+1][j]=='#')c++;
			if((i-1)>-1 && (j-1)>-1)if(s[i-1][j-1]=='#')c++;
			if((i-1)>-1 && (j+1)<w)if(s[i-1][j+1]=='#')c++;
			if((i+1)<h && (j-1)>-1)if(s[i+1][j-1]=='#')c++;
			if((i+1)<h && (j+1)<w)if(s[i+1][j+1]=='#')c++;
			s[i][j]=c+'0';
			cout<<s[i][j];
		}
		cout<<" \n";
	}
}

Measured memory_bytes: 256
import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, T = list(map(int, sys.stdin.readline().split()))
    ct = [list(map(int, sys.stdin.readline().split()))for i in range(N)]

    ret = 1001
    for n in range(N):
        if T >= ct[n][1] and ret > ct[n][0]:
            ret = ct[n][0]

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


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
n=int(input())
s=list(input())
cnt=0
for i in range(1000):
    num=str(i).zfill(3)
    base=s
    for k,j in enumerate(num):
        if j in base:base=base[base.index(j)+1:]
        else:break
        if k==2:cnt +=1
print(cnt)

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

int main() 
{
    int N;
    cin >> N;
    vector<int>A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    
    bool flag = true;
    for (int i = 0; i < N; i++) {
        if (A.at(i) % 2 == 0) {
            if (A.at(i) % 3 != 0 && A.at(i) % 5 != 0) {
                flag = false;
            }
        }
    }
    if (flag) {
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int dp[4000][4000];

int main(){
    string s,t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    rep(i,n){
        rep(j,m){
            if(s[i]==t[j]){
                dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
            }
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
            dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
        }
    }
    rep(i,n){
        dp[i+1][m] = max(dp[i][m],dp[i+1][m]);
    }
    rep(j,m){
        dp[n][j+1] = max(dp[n][j],dp[n][j+1]);
    }
    // rep(i,n+1){
    //     rep(j,m+1){
    //         cerr << dp[i][j] << " ";
    //     }
    //     cerr << endl;
    // }
    int p=n,q=m;
    string res;
    while(p!=0&&q!=0){
        if(dp[p][q]==dp[p-1][q-1]+1&&s[p-1]==t[q-1]){
            res.push_back(s[p-1]);
            p--;
            q--;
        }else{
            if(dp[p][q]==dp[p-1][q]){
                p--;
            }else{
                q--;
            }
        }
    }
    reverse(res.begin(),res.end());
    cout << res << endl;
    return 0;
}

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

int main()
{
    int64_t a, b;
    cin >> a >> b;

    if (abs(a-b) & 1)
    {
        cout << "IMPOSSIBLE" << endl;
    }
    else
    {
        int64_t ans = (a + b) / 2;
        cout << ans << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int num=0;
        for(int j=1; j*j<=i; j++)
            for(int k=1; k*k<=i; k++)
            {
                int tmp,tmp1;
                tmp=4*i-3*j*j-3*k*k-2*j*k;
                if(tmp<0)
                    continue;
                tmp1=sqrt(tmp);
                if(tmp1*tmp1!=tmp)
                    continue;
                if((tmp1-j-k)%2==0&&(tmp1-j-k)/2>=1)
                    num++;
            }
        printf("%d\n",num);
    }
    return 0;
}


Measured memory_bytes: 3696
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
int cmpint(const void *x, const void *y) {
	return *(int *)y - *(int *)x;
}
int main() {
	int n, m, a[100000], max = 0, maxpt;
	ll sum = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	qsort(a, n, sizeof(int), cmpint);
	for (int i = 0; i < m;) {
		a[0] /= 2;
		i++;
		if (i >= m)
			break;
		for (int j = 1; j < n; j++) {
			if (a[0] < a[j]) {
				a[j] /= 2;
				i++;
				if (i >= m)
					break;
			} else {
				break;
			}
		}
		qsort(a, n, sizeof(int), cmpint);
	}
	for (int i = 0; i < n; i++) {
		sum += a[i];
	}
	printf("%lld\n", sum);
	return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;

int		main(void)
{
	map<string, int> W;
	W["SUN"] = 7;
	W["MON"] = 6;
	W["TUE"] = 5;
	W["WED"] = 4;
	W["THU"] = 3;
	W["FRI"] = 2;
	W["SAT"] = 1;

	string S;
	cin >> S;
	cout << W[S] << endl;
}



Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
    let mut arr = vec![];
    for _ in 0..5 {
        let a = read::<usize>();
        arr.push(a);
    }
    let k = read::<usize>();
    if arr[4] - arr[0] > k {
        println!(":(");
    } else {
        println!("Yay!");
    }
}

#[allow(dead_code)]
fn read<T>() -> T
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf.trim().parse().unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::with_capacity(100);
    stdin().read_line(&mut buf).unwrap();
    return buf.split_whitespace().map(|s| s.parse().unwrap()).collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    use std::io::prelude::*;
    let stdin = stdin();
    let mut reader = BufReader::with_capacity(100 * 1024, stdin);
    let mut line = String::with_capacity(100);
    let mut matrix: Vec<Vec<T>> = Vec::new();

    while reader.read_line(&mut line).unwrap() > 0 {
        matrix.push(
            line.trim()
                .split_whitespace()
                .map(|s| s.parse().unwrap())
                .collect(),
        );
        line.clear();
    }

    return matrix;
}

#[allow(dead_code)]
fn read_chars() -> Vec<char> {
    let stdin = stdin();
    let mut buf = String::new();
    let _bytes = stdin.read_line(&mut buf).unwrap();
    return buf.trim().chars().collect();
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

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

	for (int i = 0; i < S.length(); i++) {
		if (i == 3) {
			cout << S[i] << " ";
		}
		else {
			cout << S[i];
		}
	}

	cout << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
int n;
double x[1005], y[1005], X, Y, d, e;
double dist(double a, double b) {
	return a*a + b*b;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
		X += x[i]; Y += y[i];
	}
	X /= n; Y /= n;
	double P = 0.1;
	for (int i = 0; i < 30000; i++) {
		int f = 0;
		d = dist(X - x[0], Y - y[0]);
		for (int j = 1; j < n; j++) {
			e = dist(X - x[j], Y - y[j]);
			if (d < e) { d = e; f = j; }
		}
		X += (x[f] - X)*P;
		Y += (y[f] - Y)*P;
		P *= 0.999;
	}
	printf("%.12lf\n",  sqrt(d));
}

Measured memory_bytes: 128
import math

def func(h, a, b, count):
  ans = 0
  for v in h:
    if v > b * count:
      ans += math.ceil((v-b*count) / (a-b))
      
  return ans <= count

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

for i in range(n):
  # heapqを最大値を取り出すように使いたいのでマイナスにする
  h.append(int(input()))

start = 1
end = math.ceil(max(h) / b)
middle = (end + start) // 2

# 二分探索する、終了条件はぶっちゃけわからん
for i in range(1000):
  if(func(h,a,b,middle)):
    end = middle
  else:
    start = middle
    
  middle = (end + start) // 2
  if (end - start) == 1:
    break
    
print(end)

Measured memory_bytes: 80952
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int d;
int c[27];
int s[366][27];
int calc(vector<int> t){
    int last[26]={};
    vector<int> ret(d);
    int ans=0;
    for(int i=0; i<d; i++){
        ans+=s[i][t[i]];
        last[t[i]]=i+1;
        for(int j=0; j<26; j++){
            ans-=c[j]*(i+1-last[j]);
        }
        ret[i]=ans;
    }
    return ans;
}
int main()
{
    cin>>d;
    for(int i=0; i<26; i++) cin>>c[i];
    for(int i=0; i<d; i++) for(int j=0; j<26; j++) cin>>s[i][j];
    vector<int> t(d);
    for(int i=0; i<d; i++){
        cin>>t[i];
        t[i]--;
    }
    int ans=calc(t);
    int m; cin>>m;
    while(m--){
        int k, q; cin>>k>>q;
        k--; q--;
        if(t[k]==q){
            cout<<ans<<endl;
            continue;
        }
        int pr=t[k], ansp=ans;
        ans-=s[k][pr];
        ans+=s[k][q];
        int l1=-1, l2=-1, r1=d, r2=d;
        for(int i=k+1; i<d; i++){
            if(t[i]==pr){
                r1=i; break;
            }
        }
        for(int i=k+1; i<d; i++){
            if(t[i]==q){
                r2=i; break;
            }
        }
        for(int i=k-1; i>=0; i--){
            if(t[i]==pr){
                l1=i; break;
            }
        }
        for(int i=k-1; i>=0; i--){
            if(t[i]==q){
                l2=i; break;
            }
        }
        ans+=c[q]*(k-l2)*(r2-k);
        ans-=c[pr]*(k-l1)*(r1-k);
        t[k]=q;
        /*if(ansp>ans){
            t[k]=pr;
            ans=ansp;
        }*/
        cout<<ans<<endl;
    }
	return 0;
}


Measured memory_bytes: 3644
import numpy as np
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(10**5+1)
for ai in A:
    B[ai]+=1
from numpy.fft import rfft, irfft
import numpy as np
B = np.array(B)
fft_len = 2**20
_B = _A = rfft(B, fft_len)
C = list(np.round(irfft(_A*_A, fft_len)).astype('int'))
cnt = 0
ans = 0
for i in range(10**5*2+1)[::-1]:
    if cnt+C[i] > M:
        ans+=i*(M-cnt)
        break
    cnt+=C[i]
    ans+=C[i]*i
print(ans)



Measured memory_bytes: 93868
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

// auto mod int
const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
  // for print
  friend ostream& operator<<(ostream &stout, const mint &ans){
    stout << ans.x;
    return stout;
  }
};

mint com(int n, int a){
  mint x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  return x/y;
}

mint f(int n) {
  if (n == 0) return 1;
  mint x = f(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n,a,b; cin >> n >> a >> b;
  mint ans = f(n);
  ans -= 1;
  ans -= com(n,a);
  ans -= com(n,b);
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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; }

using namespace std;
using ll = long long;
using P = pair<int, int>;

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

ll calc(const vector<ll>& sumx, const vector<ll>& sumy, int n) {
  ll ret = 0;
  rep(d, n) {
    // skip d-th tree at first
    auto cnt = n-d;
    auto xpos = d+cnt/2;
    auto ypos = (cnt-1)/2;
    auto now = (sumx[xpos] - sumx[d])*2;
    now += sumy[ypos]*2;
    if (cnt%2 == 0) {
      now += sumy[ypos+1] - sumy[ypos];
    } else {
      now += sumx[xpos+1] - sumx[xpos];
    }
    chmax(ret, now);
  }
  return ret;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int L, n; cin >> L >> n;
  vector<ll> x(n); rep(i, n) cin >> x[i];
  vector<ll> y(n);
  rep(i, n) {
    y[i] = L - x[n-1-i];
  }
  vector<ll> sumx(n+1), sumy(n+1);
  rep(i, n) {
    sumx[i+1] = sumx[i] + x[i];
    sumy[i+1] = sumy[i] + y[i];
  }
  cout << max(calc(sumx, sumy, n), calc(sumy, sumx, n)) << endl;
}


Measured memory_bytes: 6528
N = int(input())
L = [int(s) for s in input().split(" ")]
max_L = 0
sum_L = 0
for l in L:
  if l > max_L:
    max_L = l
  sum_L += l
 
if sum_L - max_L > max_L:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

vector<vector<int>> warshall_floyd(int &V, vector<pair<int, int>> &E){
    int INF = 1e9;
    vector<vector<int>> D(V, vector<int>(V, INF));
    for (auto i = 0; i < V; i++) D[i][i] = 1;
    for (auto iter = E.begin(); iter != E.end(); iter++){
        D[iter->first][iter->second] = 1;
        D[iter->second][iter->first] = 1;
    }
    int dij;
    for (int k = 0; k < V; k++){
        for (int i = 0; i < V - 1; i++){
            for (int j = i; j < V; j++){
                dij = min(D[i][j], D[i][k] + D[k][j]);
                D[i][j] = dij;
                D[j][i] = dij;
            }
        }
    }
    return D;
}

int main(){
    int h, w;
    string s;
    cin >> h >> w;
    int V = 0;
    vector<pair<int, int>> E;
    vector<vector<int>> X(h, vector<int>(w, -1));
    for (int i = 0; i < h; i++){
        cin >> s;
        for (int j = 0; j < w; j++){
            if (s[j] == '.') X[i][j] = V, V++;
            else continue;
            if (i > 0 && X[i - 1][j] >= 0) E.push_back(pair<int, int>{X[i - 1][j], X[i][j]});
            if (j > 0 && X[i][j - 1] >= 0) E.push_back(pair<int, int>{X[i][j - 1], X[i][j]});
        }
    }

    vector<vector<int>> D = warshall_floyd(V, E);
    int ans = 0;
    for (int i = 0; i < V; i++){
        for (int j = i; j < V; j++) ans = max(ans, D[i][j]);
    }
    cout << ans << endl;
}


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

#define forl(V, N) for(int V = 0; V < N; V++)
#define forll(V, S, E) for(int V = S; V < E; V++)
#define fore(E, X) for(auto &E:X)
#define print(X) cout << X
#define printsp(X, Y) cout << X << " " << Y << " "
#define println(X) cout << X << endl
#define printv(V) for(int it = 0; it < V.size(); it++) cout << V[it] << " "; cout << endl
#define rem(X) X.top(); X.pop()
#define mid(A, B) ((A+B) / 2)
#define setmin(A, B) A = min(A, B)
#define setmax(A, B) A = max(A, B)
#define graph unordered_map<int, unordered_set<int>>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define ll long long

int main() {
    int N;
    cin >> N;
    vi top(N+1), bot(N+1);
    forl(i, N) {
        cin >> top[i+1];
        top[i+1] += top[i];
    }
    forl(i, N) {
        cin >> bot[i+1];
        bot[i+1] += bot[i];
    }
    int ans = 0;
    forl(i, N) {
        setmax(ans, top[i+1] + bot[N] - bot[i]);
    }
    println(ans);
}

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

using namespace std;

#define INF 1e9
typedef long long ll;
typedef vector<ll> Vec;
 
struct State{
  Vec v;
  int sp,cost;
  State(Vec v,int sp,int cost) 
    : v(v),sp(sp),cost(cost) {}
  bool operator > (const State &s)const{
    return cost > s.cost;
  }
};
 
int ch,cv;
const int d[4] = {-1,1,-3,3};

ll getVal(Vec &v){
  ll res = 0LL;
  for(int i = 0 ; i < (int)v.size() ; i++){
    res *= 9;
    res += v[i];
  }
  return res;
}

int dijkstra(Vec &st,ll target,int sp){
  priority_queue<State,vector<State>,greater<State> > Q;
  Q.push(State(st,sp,0));
  unordered_map<ll,int> mp;
  mp[getVal(st)] = 0;

  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    ll val = getVal(s.v);
    if(mp.find(val) != mp.end() && mp[val] < s.cost){
      continue;
    }
    if(val == target){ return mp[val]; }
    for(int i = 0 ; i < 2 ; i++){
      int nsp = (s.sp + d[i] + 9) % 9;
      swap(s.v[nsp],s.v[s.sp]);
      ll nval = getVal(s.v);
      if(mp.find(nval) == mp.end()){
        mp[nval] = mp[val] + ch;
        Q.push(State(s.v,nsp,mp[nval]));
      }else{
        if(mp[val] + ch < mp[nval]){
          mp[nval] = mp[val] + ch;
          Q.push(State(s.v,nsp,mp[nval]));
        }
      }
      swap(s.v[nsp],s.v[s.sp]);
    }
    for(int i = 2 ; i < 4 ; i++){
      int nsp = (s.sp + d[i] + 9) % 9;
      swap(s.v[nsp],s.v[s.sp]);
      ll nval = getVal(s.v);
      if(mp.find(nval) == mp.end()){
        mp[nval] = mp[val] + cv;
        Q.push(State(s.v,nsp,mp[nval]));
      }else{
        if(mp[val] + cv < mp[nval]){
          mp[nval] = mp[val] + cv;
          Q.push(State(s.v,nsp,mp[nval]));
        }
      }
      swap(s.v[nsp],s.v[s.sp]);
    }
  }
  return INF;
}

int main(){
  while(cin >> ch >> cv, (ch|cv)){
    int sp;
    Vec s(9),t(9);
    for(int i = 0 ; i < 9 ; i++){
      cin >> s[i];
      if(s[i] == 0){ sp = i; }
    }
    for(int i = 0 ; i < 9 ; i++){
      cin >> t[i];
    }
    cout << dijkstra(s,getVal(t),sp) << endl;
  }
  return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  string s;
  cin >> n >> s;
  
  vector<vector<bool>> dp(n, vector<bool>(n, false));
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      if (s.at(i) == s.at(j)) dp.at(i).at(j) = true;
    }
  }
  
  int ans = 0;
  for (int i = 1; i < n; i++) {
    int keep = 0, limit;
    for (int j = 0; j + i < n; j++) {
      if (dp.at(j).at(i + j)) {
        if (keep == 0) {
          limit = i + j;
          keep++;
        }
        else if (j < limit) {
          keep++;
        }
        else {
          ans = max(ans, keep);
          limit = i + j;
          keep = 1;
        }
      }
      else {
        ans = max(ans, keep);
        keep = 0;
      }
      if (j + i == n - 1) ans = max(ans, keep);
    }
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 3584
#include <sys/time.h>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <cctype>

using namespace std;

using ll = long long;
using P = pair<double, double>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
ll mod = 1000000007LL;

vector<bool> check_used(string& s) {
	vector<bool> used(26, false);

	for(char c : s) {
		used[c - 'a'] = true;
	}
	return used;
}

char first_not_used(vector<bool> & used) {
	rep(i, 26) {
		if (used[i] == false) {
			return i + 'a';
		}
	}
	return -1;
}

int main() {
	string s;
	cin >> s;
	if (s == "zyxwvutsrqponmlkjihgfedcba") {
		cout << -1 << endl;
		return 0;
	}

	vector<bool> used = check_used(s);
	char first = first_not_used(used);

	if (s.size() < 26) {
		cout << s << first << endl;
		return 0;
	}
	
	for (int i = s.size() - 1; i >= 0; i--) {
		// zyxwvutsrqponmlkjihgfedcab
		// zyxwvutsrqponmlkjihgfedca


		if (s[i - 1] < s[i]) {
			used[s[i] - 'a'] = false;
			s.pop_back();

			for (int j = s[i - 1] - 'a'; j < 26; j++) {
				if (!used[j]) {
					s[i - 1] = j + 'a';
					cout << s << endl;
					return 0;
				}
			}
 			continue;
 		}
		used[s[i] - 'a'] = false;
		s.pop_back();
	}
	
	return 0;
}


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

typedef long long ll;

const int MAX_N = 100010;
int par[MAX_N];
int rnk[MAX_N];
int siz[MAX_N];

void init(int n) {
    rep(i,n) {
        par[i] = i;
        rnk[i] = 0;
        siz[i] = 1;
    }
}

int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    int s = siz[x] + siz[y];
    if (rnk[x] < rnk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rnk[x] == rnk[y]) rnk[x]++;
    }
    siz[find(x)] = s;
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int size(int x) {
    return siz[find(x)];
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M), ans(M, N * (N - 1) / 2);
    rep(i, M) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    init(N);
    for (int i = M - 2; i >= 0; i--) {
        if (same(A[i + 1], B[i + 1])) {
            ans[i] = ans[i + 1];
            continue;
        }
        ll c1 = size(A[i + 1]), c2 = size(B[i + 1]);
        ans[i] = ans[i + 1] - c1 * c2;
        unite(A[i + 1], B[i + 1]);
    }
    rep(i, M) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4864
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		int[] a=new int[10];
		for(int i=0; i<10; i++)
			a[i]=sc.nextInt();
		sort(a);
		println(""+a[9]);
		println(""+a[8]);
		println(""+a[7]);
		sc.close();
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 12000
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        int P;
        int Q;
        int R;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            P = in.nextInt();
            Q = in.nextInt();
            R = in.nextInt();
            out.println(Math.min(P + Q, Math.min(Q + R, R + P)));
        }

    }
}



Measured memory_bytes: 21972
/**
*    created: 30.06.2020 17:50:50
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#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++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcountll(bit)
using namespace std;
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 mod = 1000000007;
const long double pi = acos(-1.0);
const int inf = 1LL << 60;

signed main() {

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

    string s;
    cin >> s;
    int ans = 700;
    if (s[0] == 'o') ans += 100;
    if (s[1] == 'o') ans += 100;
    if (s[2] == 'o') ans += 100;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3592
def dfs(i, j, map)
  map[i][j] = '0'

  dfs(i + 1, j, map) if map[i + 1]    && map[i + 1][j] == '1'
  dfs(i - 1, j, map) if i >= 1        && map[i - 1][j] == '1'
  dfs(i, j + 1, map) if map[i][j + 1] && map[i][j + 1] == '1'
  dfs(i, j - 1, map) if j >= 1        && map[i][j - 1] == '1'
end

def show(map)
  puts
  map.each do |row|
    puts row.join('')
  end
  gets
end

maps = [[]]

gets(nil).each_line do |line|
  line = line.chomp
  if line == ''
    maps.push []
  else
    maps.last.push line.split('')
  end
end

maps.each do |map|
  ans = 0
  0.upto(map.size - 1) do |i|
    0.upto(map[i].size - 1) do |j|
      if map[i][j] == '1'
        dfs(i, j, map)
        ans += 1
      end
    end
  end
  puts ans
end

Measured memory_bytes: 6128
#include<bits/stdc++.h>
#define mod 1000000009
#define int long long
#define garou ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int pow(int p,int r){
	int ans=1;
	while(r>0){
     if(r&1){
		 ans=((ans%mod)*(p%mod))%mod;
	 }
	 r=r>>1;
     p=((p%mod)*(p%mod))%mod;
	}
	return ans;
}
int arr[100000];
vector<int> v;
signed main() {
	garou;
   int n;
   cin>>n;
   int ans=0;
   for(int i=2;i*i<=n;i++){
	   int cnt=0;
	  while(n%i==0){
		n/=i;
       cnt++;
	  }
	  for(int j=1;j<=cnt;j++){
		  cnt-=j;
		  ans++;
	  }
   }
   if(n>1)
   ans++;
   cout<<ans;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

enum { STRAIGHT, RIGHT, BACK, LEFT, D };

constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};
constexpr int MAX_SIZE = 30;

int w, h;
int s[MAX_SIZE][MAX_SIZE];
int c[D];

int dist[MAX_SIZE][MAX_SIZE][D];

inline bool out(int x, int y) {
	return x < 0 || y < 0 || x >= w || y >= h;
}

int dijkstra() {
	typedef tuple<int, int, int, int> state;

	priority_queue<state, vector<state>, greater<state>> que;
	fill_n((int *)dist, sizeof(dist) / sizeof(int), INT_MAX);

	que.push(state(0, 0, 0, 0));
	dist[0][0][0] = 0;

	while(!que.empty()) {
		int d, x, y, dir;
		tie(d, x, y, dir) = que.top();
		que.pop();

		if(dist[x][y][dir] < d) continue;
		if(x == w - 1 && y == h - 1) return d;

		for(int command = 0; command < 4; ++command) {
			const int next_dir = (dir + command) & 0x3;
			const int nx = x + dx[next_dir];
			const int ny = y + dy[next_dir];

			if(out(nx, ny)) continue;

			const int next_dist = d + (s[y][x] == command ? 0 : c[command]);
			if(dist[nx][ny][next_dir] > next_dist) {
				dist[nx][ny][next_dir] = next_dist;
				que.push(state(next_dist, nx, ny, next_dir));
			}
		}
	}

	assert(false);
}

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

	while(cin >> w >> h && w) {
		for(int i = 0; i < h; ++i) {
			for(int j = 0; j < w; ++j) {
				cin >> s[i][j];
			}
		}

		for(int i = 0; i < D; ++i) {
			cin >> c[i];
		}

		cout << dijkstra() << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1332
#include <bits/stdc++.h>
#define PI 3.1415926535897932
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int A,B,C,X;
  cin>>A>>B>>C>>X;
  
  int ans=0;
  
  
  for(int i=0;i<=A;i++){
    for(int j=0;j<=B;j++){
      for(int k=0;k<=C;k++){
        if(500*i+100*j+50*k==X){
          ans++;
        }
      }
    }
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 3600
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;


using ll = long long;

//#define int ll

using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;



const int N = 4e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 2e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);


//template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

string s;
int q;
bool r;
main() {
  file("threesum");
  ios;
  cin>>s>>q;
  deque<char> de;
  for (int i = 0; i < s.size(); ++i) de.pb(s[i]);
  while (q--) {
    int type;
    cin>>type;
    if (type == 1) r^=1;
    else {
      int f;
      cin>>f;
      char d;
      cin>>d;
      if (f == 1) {
        if (!r) de.push_front(d);
        else de.push_back(d);
      } else {
        if (r) de.push_front(d);
        else de.push_back(d);
      }
    }
  }
  while (!de.empty()) if (!r) cout<<de.front(), de.pop_front(); else cout<<de.back(), de.pop_back();
  return 0;
}
/**

*/


Measured memory_bytes: 976
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n) ; ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define emb emplace_back

using namespace std;
using ll = long long;
using P = pair<int,int>;

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

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

  if(n%2==1) cout << n / 2 + 1 << endl;
  else cout << n / 2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <complex>
#define EPS 1e-10
#define EQ(a, b) (abs((a) - (b)) < EPS)
using namespace std;
typedef complex<double> P;

double dot(P a, P b) {
    return(a.real() * b.real() + a.imag() * b.imag());
}

int isOrthogonal(P a, P b, P c, P d) {
    return(EQ(dot(a - b, c - d), 0.0));
}

int main(void) {
    double xa, ya, xb, yb, xc, yc, xd, yd;
    while(cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd) {
        P a(xa, ya), b(xb, yb), c(xc, yc), d(xd, yd);
        if(isOrthogonal(a, b, c, d)) cout << "YES" << endl;
        else                         cout << "NO"  << endl;
    }
    return(0);
}

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

using namespace std;

long long n, k;

int main(){
    cin >> n >> k;
    cin.ignore();

    if(n <= 0) return 0;
    if(k <= 1) return 0;

    long long kk = k;
    int cnt = 1;
    while(n >= kk){
        ++cnt;
        kk *= k;
        //printf("%lld\n", kk);
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int ret=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return w*ret;
}
int main()
{
	string s;
	cin>>s;
	if(s=="SUN") cout<<7<<endl;
	if(s=="MON") cout<<6<<endl;
	if(s=="TUE") cout<<5<<endl;
	if(s=="WED") cout<<4<<endl;
	if(s=="THU") cout<<3<<endl;
	if(s=="FRI") cout<<2<<endl;
	if(s=="SAT") cout<<1<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

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

type Stack struct {
	v []int
}

func NewStack() Stack {
	return Stack{make([]int, 0)}
}

func (s *Stack) Push(x int) {
	s.v = append(s.v, x)
}

func (s *Stack) Top(w *bufio.Writer) {
	lenS := len(s.v)
	if lenS > 0 {
		w.WriteString(fmt.Sprintf("%d\n", s.v[lenS-1]))
	}
}

func (s *Stack) Pop() {
	lenS := len(s.v)
	if lenS > 0 {
		s.v = s.v[:lenS-1]
	}
}

func (s Stack) String() string {
	return strings.Trim(fmt.Sprint(s.v), "[]")
}

func NextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	w := bufio.NewWriter(os.Stdout)

	n, _ := NextInt(sc)
	s := make([]Stack, n)
	for i := 0; i < n; i++ {
		s[i] = NewStack()
	}

	q, _ := NextInt(sc)
	for i := 0; i < q; i++ {
		cmd, _ := NextInt(sc)
		t, _ := NextInt(sc)
		switch cmd {
		case 0:
			x, _ := NextInt(sc)
			s[t].Push(x)
		case 1:
			s[t].Top(w)
		case 2:
			s[t].Pop()
		}
	}

	w.Flush()
}




Measured memory_bytes: 8868
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb(x) (x&-(x))
const int N = 101010;
int a[105];
int main(){
	int n;
	int k;
	int ans=0;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
	cin>>a[i];
	if(k-a[i]>a[i])
	ans+=a[i]*2;
	else
	ans+=(k-a[i])*2;
	}
	
	cout<<ans<<endl;




    return 0;
}


Measured memory_bytes: 256
n=int(input())
c=list(map(int,input().split()))
s=0
for i in range(n):
    d=0
    for j in range(i):
        if c[i]>=c[j]:
            d+=0
        else: 
            d+=1
    if d==0:
        s+=1
    else:
        s+=0
print(s)

Measured memory_bytes: 3060
using System;
using System.Linq;

namespace AtCoder.Abc
{
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var sp = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            for (int i = 0; i < sp.Length; i++)
            {
                if (sp[i] == 0)
                {
                    Console.WriteLine(i+1);
                    break;
                }
            }

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28088