akhauriyash/Code-Regression huggingface dataset:
# B - ROT N
N = int(input())
S = str(input())
####
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'
ans = ''
for s in S:
    alt_idx = chars.index(s) + N
    ans += chars[alt_idx]
print(ans)


Measured memory_bytes: 3060
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())


def main():
    N = i_input()
    x, y = i_map()
    z = x + y
    w = x - y
    z_max = z
    z_min = z
    w_max = w
    w_min = w
    for i in range(1, N):
        x, y = i_map()
        z = x + y
        w = x - y
        z_max = max(z_max, z)
        z_min = min(z_min, z)
        w_max = max(w_max, w)
        w_min = min(w_min, w)
    ans = max([z_max - z_min, w_max - w_min])
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 73724
#include <iostream>
int main(){
    int a,b,d = 1;
    std::cin >> a >> b;
    for(int c = 0;c < a;c++){
        if((d * 2) >= (d + b)){
            d = d + b;
        }else{
            d = d * 2;
        }
    }
    std::cout <<d <<std::endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
int N, max, count, num;
  cin >> N;
  num = 1;
   max = 0;
  count = 0;
  while (true){
        if(N == 0){
     break; 
    }
    
    
    if(N % 2 != 0){
      N--;
     continue; 
    }
    while(N % 2 == 0){
     N /= 2;
      count++;
    }
    if(count > max){
     max = count; 
    }
  }
  for(int i = 0; i < max; i++){
    num *= 2;
  }
    cout << num << endl;
  }


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

int bin_search(int target, vector<int>& arr) {
  int left = -1;
  int right = arr.size();
  
  while (right - left > 1) {
    int mid = (right + left) / 2;
    if (target <= arr[mid]) {
      right = mid;
    } else {
      left = mid;
    }
  }

  return right;
}


int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }
  sort(arr.begin(), arr.end());
  int res = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int a = arr[i];
      int b = arr[j];
      int min_c = abs(a - b);
      int max_c = a + b; // min_c + 1 <= c < max_c
      int min_k = bin_search(min_c + 1, arr);
      int max_k = bin_search(max_c, arr);
      res += max(0, max_k - max(j + 1, min_k));
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;

ll gcd(ll a, ll b)
{
    if (a < b) {
    swap(a, b);
    }
    
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}



int main(){
  int N;
  cin>>N;
  ll ans = 0;
  for(int i = 1;i<=N;i++){
    for(int k = i;k<=N;k++){
      for(int m = k;m<=N;m++){
        if(i == k && k == m){
          ans += gcd(i,gcd(k,m));
        }
        else if(i == k || k == m){
          ans += gcd(i,gcd(k,m))*3;
        }
        else{
          ans += gcd(i,gcd(k,m))*6;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
h, w, d = map(int, input().split())
a=[list(map(int, input().split())) for i in range(h)]
q=int(input())
pos=[0]*(h*w)
cost=[[0]*(h*w//d+1) for i in range(d)]

for i in range(h):
    for j in range(w):
        pos[a[i][j]-1]=(i, j)
for i in range(d):
    j=0
    while (j+1)*d+i<w*h:
        p0=pos[j*d+i]
        p1=pos[(j+1)*d+i]
        cost[i][j]=abs(p0[0]-p1[0])+abs(p0[1]-p1[1])
        j+=1

sum_cost=[[0]*(h*w//d+2) for i in range(d)]
for i in range(d):
    for j in range(1, h*w//d+2):
        sum_cost[i][j]=sum_cost[i][j-1]+cost[i][j-1]

for i in range(q):
    l, r = map(int, input().split())
    li=(l-1)//d
    ri=(r-1)//d
    amari=(l-1)%d
    print(sum_cost[amari][ri]-sum_cost[amari][li])
   


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

using namespace std;

bool judge(int a, int limit, int r) {
	if (a >= r&&a <= limit - r) {
		return true;
	}
	return false;
}

int main() {
	int data[5];

	for (int i = 0; i < 5; ++i) {
		cin >> data[i];
	}
	if (judge(data[2], data[0], data[4]) && judge(data[3], data[1], data[4])) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 3132
#include <stdio.h>

int main() {
	int n, x;
	int s1, s2, s3;
	int x2, x3;
	int num;

	scanf("%d %d", &n, &x);
	while(n != 0 || x != 0) {
		num = 0;
		//printf("x1: %d\n", x);
		for(s1 = 1; s1 < x / 3 && s1 <= n; s1++) {
			//printf("s1: %d\n", s1);
			x2 = x - s1;
			//printf("x2: %d\n", x2);
			for(s2 = s1 + 1; s2 <= x2 / 2 && s2 <= n; s2++) {
				//printf("s2: %d\n", s2);
				x3 = x2 - s2;
				//printf("x3: %d\n", x3);
				for(s3 = s2 + 1; s3 <= x3 && s3 <= n; s3++) {
					//printf("s3: %d\n", s3);
					if(s1 + s2 + s3 == x) {
						//printf("%d %d %d\n", s1, s2, s3);
						num++;
					}
				}
			}
		}
		printf("%d\n", num);
		scanf("%d %d", &n, &x);
	}
	return 0;
}

Measured memory_bytes: 2656
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int[] before = null;
		while(true){
			if(!sc.hasNext()){break;}
			
			String str[] = sc.next().split(",");
			int[] inner = new int[str.length];
			for(int i = 0; i < str.length; i++){
				inner[i] = Integer.parseInt(str[i]);
			}
			
			if(before == null){
				before = inner;
			}else{
				int[] tmp = new int[inner.length];
				for(int i = 0; i < before.length; i++){
					if(i < tmp.length){
						if(tmp[i] < before[i] + inner[i]){
							tmp[i] = before[i] + inner[i];
						}
					}
					
					if(before.length > tmp.length){
						if ((i - 1) < tmp.length && (i - 1) >= 0) {
							if (tmp[i - 1] < before[i] + inner[i - 1]) {
								tmp[i - 1] = before[i] + inner[i - 1];
							}
						}
					}else{
						if ((i + 1) < tmp.length) {
							if (tmp[i + 1] < before[i] + inner[i + 1]) {
								tmp[i + 1] = before[i] + inner[i + 1];
							}
						}
					}
				}
				before = tmp;
			}
		}	
		
		System.out.println(before[0]);
	}
}

Measured memory_bytes: 12000
#include <iostream>

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

using namespace std;

int main(){
	int h,w;
	char input;
	bool canvas[51][51];
	bool check;
	cin >> h >> w;
	REP(j,h){
		REP(k,w){
			cin >> input;
			canvas[j][k] = (input=='#') ? true : false;
		}
	}
	const int diff[5] = {0, -1, 0, 1, 0};
	REP(j,h){
		REP(k,w){
			if (canvas[j][k]){
				check = false;
				REP(i,4){
					if (canvas[j+diff[i]][k+diff[i+1]]) check = true;
				}
				if (!check){
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
def solve(n, m, a, b):
    x = -1/2
    ans = 0
    for s, t in sorted(zip(a, b), key=lambda _:_[1]):
        if x < s:
            ans += 1
            x = t - 1/2
    return ans

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

Measured memory_bytes: 19796
n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
  p[i]=(p[i]+1)/2
a=0
for i in range(k):
  a+=p[i]
b=[a]
for j in range(1,n-k+1):
  c=b[j-1]-p[j-1]+p[j+k-1]
  b.append(c)
b.sort(reverse=True)
print(b[0])


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

#define ll long long
#define ld long double
#define pb push_back
#define mod 1000000007
#define mk make_pair


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n;
    cin>>n;
    ll i,j;
    vector<ll> v(n);
    vector<ll> pos(n);
    for(i=0;i<n;i++){
        cin>>v[i];
        v[i]--;
        pos[v[i]]=i;
    }
    multiset<ll> s;
    s.insert(-1); s.insert(-1); s.insert(n); s.insert(n);
    ll ans=0;
    for(i=n-1;i>=0;i--){
        s.insert(pos[i]);
        auto it=s.find(pos[i]);
        it--;
        ll a=*it;
        it--;
        ll b=*it;
        it++; it++; it++;
        ll x=*it;
        it++;
        ll y=*it;
        // cout<<b<<" "<<a<<" "<<x<<" "<<y<<endl;
        ans+= ((i+1)*( (a-b)*(x-pos[i]) + (y-x)*(pos[i]-a) ));

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

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

using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

typedef long long ll;
typedef long long int64;

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

  vector<int> v(n);

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

  sort(v.begin(), v.end());

  double ret = (double)v[0];

  for(int i=1; i<n; i++){
    ret = (ret + v[i])/2.0;
  }

  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
        int k; cin >> k;
        long long int ans = 0;
        for (int x = 1; x <= k; ++x){
            for (int y = 1; y <= k; ++y){
                for (int z = 1; z <= k; ++z){
                    ans += __gcd(x, __gcd(y, z));
                }
            }
        }
        cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define MAXN 300000
#define MOD 1000000007

int fact[MAXN + 1];

inline void prec() {
    fact[0] = 1;
    for(int i = 1; i <= MAXN; i++)
       fact[i] = (1LL * fact[i - 1] * i) % MOD;
}

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1)
           ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline int comb(int n, int k) {
    return (1LL * fact[n] * lgput((1LL * fact[n - k] * fact[k]) % MOD, MOD - 2)) % MOD;
}

inline int solve(int n, int m) {
    return comb(n + m - 2, n - 1);
}

int main() {
    FILE * fi, * fout;
    int i, n, m, a, b;
    //fi = fopen("A.in" ,"r");
    //fout = fopen("A.out" ,"w");
    fi=stdin;
    fout=stdout;
    fscanf(fi,"%d%d%d%d" ,&n,&m,&a,&b);
    prec();
    int ans = solve(n, m);
    for(i = 1; i <= b; i++) {
       if(i == 1)
          ans -= solve(a, m);
       else
          ans -= (1LL * solve(n - a, i) * solve(a, m - i + 1)) % MOD;
       if(ans < 0)
          ans += MOD;
    }
    fprintf(fout,"%d\n" ,ans);
    //fclose(fi);
    //fclose(fout);
    return 0;
}


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

const int N = 2e3L + 11;
char s[N], t[N];
int dp[N][N][2];

int upd(int &x, int y) {
	if(x < y) x = y;
}

int main() {
	int n, m; cin >> n >> m;
	scanf("%s%s", s + 1, t + 1);

	int ans = 0;
	memset(dp, -1, sizeof dp);
	for(int i = 0; i <= n; i ++)
		for(int j = 0; j <= m; j ++)
			dp[i][j][0] = 0;
	for(int i = 0; i <= n; i ++)
		for(int j = 0; j <= m; j ++)
			for(int k : {0, 1}) if(~dp[i][j][k]) {
				char nxt = k ? 'O' : 'I';
				if(s[i + 1] == nxt) upd(dp[i + 1][j][k ^ 1], dp[i][j][k] + 1);
				if(t[j + 1] == nxt) upd(dp[i][j + 1][k ^ 1], dp[i][j][k] + 1);
				if(k == 1) ans = max(ans, dp[i][j][k]);
			}
	cout << ans << '\n';
}

Measured memory_bytes: 34772
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        long[] nm = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long n = nm[0];
        long m = nm[1];
        long ans = 1;

        if(Math.Abs(n - m) > 1)
        {
            Console.WriteLine(0);
            return;
        }

        if (Math.Abs(n - m) == 0)
        {
            ans *= 2;
        }

        for (long i = n; i >= 1; i--)
        {
            ans *= i;
            ans %= 1000000007;
        }
        for (long i = m; i >= 1; i--)
        {
            ans *= i;
            ans %= 1000000007;
        }
        
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		int rc = 0;
		int hc = 0;
		while(input.hasNext()){
			String[] st = input.next().split(",");
			int a1 = Integer.parseInt(st[0]);
			int a2 = Integer.parseInt(st[1]);
			int a3 = Integer.parseInt(st[2]);
			int length = a1*a1+a2*a2;
			if(length == a3*a3){
				rc++;
			}else if(a1 == a2 && a1+a2 > a3){
				hc++;
			}
		}
		System.out.println(rc);
		System.out.println(hc);
		input.close();
	}
}

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

using namespace std;

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

const int N = 555;

int need[N];
int pos[N];
int to_go[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pos[i];
        pos[i]--;
    }
    for (int i = 0; i < n; i++)
        need[i] = i;
    vector<int> ans(n * n, -1);
    for (int i = 0; i < n * n; i++) {
       // if (i)
         //   cerr << ans[i - 1] << endl;
        for (int j = 0; j < n; j++) {
            if (pos[j] == i) {
                if (need[j]) {
                    cout << "No" << endl;   
                    return 0;
                }
                ans[i] = j;
                need[j] = -1;
                to_go[j] = n - j - 1;
            }
        }    
        if (ans[i] != -1)
            continue;
        int v = -1;
        for (int j = 0; j < n; j++)
            if (need[j] > 0 && (v == -1 || pos[v] > pos[j])) 
                v = j;
        if (v >= 0) {
            need[v]--;
            ans[i] = v;
            continue;
        }
        for (int j = 0; j < n; j++) 
            if (need[j] == -1 && to_go[j] > 0)
                v = j;
        if (v == -1) {
            cout << "No" << endl;
            return 0;
        }
        to_go[v]--;
        ans[i] = v;
    }
    for (int i = 0; i < n * n; i++)
        assert (ans[i] >= 0);
    cout << "Yes" << endl;
    for (int i = 0; i < n * n; i++)
        cout << ans[i] + 1 << " ";
    cout << endl;
}       

Measured memory_bytes: 2304
place = [int(input()) for _ in range(5)]
k = int(input())
bomb = 0
for p in range(len(place) - 1):
  for p_dash in range(p, len(place)):
    if place[p_dash] - place[p] > k:
      bomb += 1
      break
if bomb == 0:
  print('Yay!')
else:
  print(':(')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
    int n;
    string c;
    cin >> n >> c;
    int rcnt = 0;
    for (int i = 0; i < n; i++)
    {
        if ('R' == c[i])
        {
            rcnt++;
        }
    }
    int res = 0;
    for (int i = 0; i < rcnt; i++)
    {
        if ('R' != c[i])
        {
            res++;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3756
import numpy as np
N, M = (int(i) for i in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
money = 0
AB.sort()
for a, b in AB:
    if M == 0:
        break
    elif M >= b:
        M -= b
        money += a*b
    elif M < b:
        money += M*a
        M = 0
print(money)

Measured memory_bytes: 36852
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pye cout << "yes" << endl;
#define pno cout << "no" << endl;
#define pYe cout << "Yes" << endl;
#define pNo cout << "No" << endl;
#define pYE cout << "YES" << endl;
#define pNO cout << "NO" << endl;
#define prin(num) cout << num << endl;
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 100000000000
#define MOD 1000000007LL
#define MAX 200005
#define NIL -1
#define WHITE 0
#define BLACK 1
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

ll divi(ll n, ll k) {
    ll res, t;
    t=n/k+(n%k==0 ? 0 : 1);
    res=k*t-n;
    return res;
}

int main(void) {
    ll N;
    cin >> N;
    ll i, a[100000], b[100000];
    
    for(i=N-1; i>=0; i--) {
        cin >> a[i] >> b[i];
    }
    ll sum=0, ans=0;
    ll t;
    
    for(i=0; i<N; i++) {
        a[i]+=sum;
        t=divi(a[i], b[i]);
        sum+=t;
        ans+=t;
    }
    
    prin(ans)
}


Measured memory_bytes: 1792
import math
A, B, H, M = list(map(float,input().split()))
rad = 6*(60*H+M)-0.5*(60*H+M)
while(rad > 180):
	if rad > 360:
		rad -= 360
	else:
		rad = 360 - rad
r = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(rad*math.pi/180))
print(r)


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

const int N = 1e5 + 50;

bool p[N];
long long a[N], b[N];
int n, s;

int main() {
  scanf("%d%d", &n, &s);
  for (int i = 1; i <= n; i ++)
    scanf("%lld%lld", &a[i], &b[i]);
  long long ans = 0;
  for (int pl = 1, pr = n; ;) {
    if (a[pl] > s) {
      ans += a[pr] - s;
      break;
    } else if (a[pr] < s) {
      ans += s - a[pl];
      break;
    } else {
      if (b[pl] >= b[pr]) {
        if (!p[pl]) ans += a[pr] - a[pl];
        p[pl] = 1; b[pl] += b[pr]; pr --;
      } else {
        if (!p[pr]) ans += a[pr] - a[pl];
        p[pr] = 1; b[pr] += b[pl]; pl ++;
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


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

int main() {
  int64_t N;
  cin >> N;
  int64_t limit = ceil(sqrt(N));
  int64_t min_move = 1000000000000;
  for (int64_t i = 1; i <= limit; i++) {
    if (N % i != 0) {
      continue;
    }
    int64_t q = N / i;
    int64_t this_move = (i - 1) + (q - 1);
    if (this_move < min_move) {
      min_move = this_move;
    }
  }
  cout << min_move << endl;
}

Measured memory_bytes: 384
N,M = map(int,input().split())

A = list(map(int,input().split()))

total = sum(A)

bdr = total /(4*M)

A.sort(reverse=True)

C = 1

if A[M-1] < bdr:
  C = 0
  
if C == 1:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i = (ll)(a); i < (ll)(b); i++)
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 ll INF = 1LL << 60;
int main(){
    int N; cin >> N;
    vector<string> s(N);
    rep(i,N){cin >> s[i];}
    // multiset<string> S;
    // rep(i,N){S.insert(s[i]);}
    // rep(i,S.size())

    map<string ,ll> mp;
    rep(i,N){
        mp[s[i]]+=1;
    }

    vector<string> res;
    ll mx = 0;
    for (auto x : mp){
        if (x.second > mx){
            res.clear();
            res.push_back(x.first);
            mx = x.second;
        }else if (x.second == mx){
            res.push_back(x.first);
        }
    }

    rep(i,res.size()){
        cout << res[i] << endl;
    }



    return 0;
}

Measured memory_bytes: 29556
#include <stdio.h>

int asumisu[128];

int memo[128][128];

int search(int pos, int kazu) {
	int answer = 0;
	int i;
	if (pos >= 120) return kazu == 75;
	if (kazu > 75) return 0;
	if (memo[pos][kazu]) return ~memo[pos][kazu];
	for (i = 0; i <= asumisu[pos]; i++) {
		answer += search(pos + 1, kazu * (i + 1));
	}
	return ~(memo[pos][kazu] = ~answer);
}

int main(void) {
	int N;
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 2; i <= N; i++) {
		int mimorinn = i;
		int j;
		for (j = 2; j * j <= mimorinn; j++) {
			while (mimorinn % j == 0) {
				asumisu[j]++;
				mimorinn /= j;
			}
		}
		if (mimorinn > 1) asumisu[mimorinn]++;
	}
	printf("%d\n", search(2, 1));
	return 0;
}


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

using namespace std;

typedef long long int lli;

int n, s;

bool used[10];

lli dfs(bool used[10], int now, int sum)
{
	if (sum > s) return 0;

	if (now == n) {
		if (sum == s) return 1;
		return 0;
	}

	int res = 0;

	for (int i = 0; i < 10; ++i) {
		if (used[i]) continue;
		used[i] = true;
		res += dfs(used, now + 1, sum + i);
		used[i] = false;
	}

	return res;
}

lli fact(int n)
{
	if (n <= 1) return 1;
	return n * fact(n - 1);
}

int main()
{
    int f[10];
    for(int i = 1; i < 10; ++i) f[i] = fact(i);
	while (cin >> n >> s, n || s) {
		memset(used, false, sizeof(used));
        cout << dfs(used, 0, 0) / f[n] << endl;
	}
}

Measured memory_bytes: 1156
#include<cstdio>
#include<queue>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<set>
#include<stack>
#include<queue>
#include<map>
using namespace std;
int a[1000];
int  main(){
	int n,j,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
	int ans=100000000;
	for(i=1;i<=100;i++){
		int temp=0;
		for(j=1;j<=n;j++){
			temp+=(a[j]-i)*(a[j]-i);
		}
		ans=min(ans,temp);
	}
	printf("%d\n",ans);
	
}









Measured memory_bytes: 128
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N)] # iからの行き先
Y = [0 for i in range(N)] # iに来る辺の数
dp = [0 for i in range(N)] # iで終わる最長経路の長さ

for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    X[x].append(y)
    Y[y] += 1


Q = deque([])
for i in range(N):
    if Y[i] == 0:
        Q.append(i)

while len(Q) > 0:
    i = Q.popleft()
    for x in X[i]:
        dp[x] = max(dp[x], dp[i] + 1)
        Y[x] -= 1
        if Y[x] == 0:
            Q.append(x)

print(max(dp))

Measured memory_bytes: 23000
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int hand[5];
	int i, j;
	
	while (scanf("%d", hand) != EOF){
		int straight = 1;
		int pair = 0;
		int three = 0;
		int four = 0;
		
		for (i = 1; i < 5; i++){
			scanf("%*c%d", hand + i);
		}
		sort(hand, hand + 5);
		for (i = 0; i < 4; i++){
			if (hand[i] == hand[i + 1]){
				pair++;
			}
		}
		for (i = 0; i < 3; i++){
			if (hand[i] == hand[i + 1] && hand[i] == hand[i + 2]){
				three = 1;
				pair -= 2;
			}
		}
		for (i = 0; i < 2; i++){
			if (hand[i] == hand[i + 1] && hand[i] == hand[i + 2] && hand[i] == hand[i + 3]){
				four = 1;
			}
		}
		for (i = 0; i < 4; i++){
			if (hand[i] != hand[i + 1] - 1){
				straight = 0;
				break;
			}
		}
		if (hand[1] == 10 && hand[2] == 11 && hand[3] == 12 && hand[4] == 13 && hand[0] == 1){
			straight = 1;
		}
		if (straight == 1){
			puts("straight");
		}
		else if (four == 1){
			puts("four card");
		}
		else if (pair > 0 && three == 1){
			puts("full house");
		}
		else if (three == 1){
			puts("three card");
		}
		else if (pair == 2){
			puts("two pair");
		}
		else if (pair == 1){
			puts("one pair");
		}
		else {
			puts("null");
		}
	}
	
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
	int n = 0, count = 0;
	char c[4];
	cin >> c;
	while (n < 4) {
		for (int i = n+1; i < 4; ++i) {
			if (c[n] == c[i])
				++count;
		}
		++n;
	}
	if (count == 2)
		cout << "Yes"s;
	else
		cout << "No"s;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let v = read_vec::<u64>();
    let (l, n) = (v[0], v[1]);
    let n = n as usize;
    let mut xs: Vec<u64> = (0..n).map(|_| read::<u64>()).collect();
    let mut l_xs: Vec<u64> = (0..n).map(|i| l - xs[i]).collect();

    if n == 1 {
        println!("{:?}", std::cmp::max(xs[0], l_xs[0]));
        return;
    }

    let mut xs_sums = vec![0u64; n + 1];
    for i in 1..n + 1 {
        xs_sums[i] = xs_sums[i - 1] + xs[i - 1];
    }

    let mut l_xs_sums = vec![0u64; n + 1];
    for i in 1..n + 1 {
        l_xs_sums[i] = l_xs_sums[i - 1] + l_xs[i - 1];
    }

    let mut ans = 0;
    for i in 0..n {
        let mut temp_ans = 0;
        temp_ans += 2 * (xs_sums[(n - 2 + i) / 2 + 1] - xs_sums[i]);
        temp_ans += 2 * (l_xs_sums[n - 1 + 1] - l_xs_sums[(n + i) / 2  + 1]);
        if (n + i) % 2 == 0 {
            temp_ans += l_xs[(n + i) / 2];
        } else {
            temp_ans += xs[(n + i) / 2];
        }
        // println!("{:?}", temp_ans);
        ans = std::cmp::max(ans, temp_ans);
    }
    xs.reverse();
    l_xs.reverse();
    std::mem::swap(&mut xs, &mut l_xs);

    let mut xs_sums = vec![0u64; n + 1];
    for i in 1..n + 1 {
        xs_sums[i] = xs_sums[i - 1] + xs[i - 1];
    }

    let mut l_xs_sums = vec![0u64; n + 1];
    for i in 1..n + 1 {
        l_xs_sums[i] = l_xs_sums[i - 1] + l_xs[i - 1];
    }

    for i in 0..n {
        let mut temp_ans = 0;
        temp_ans += 2 * (xs_sums[(n - 2 + i) / 2 + 1] - xs_sums[i]);
        temp_ans += 2 * (l_xs_sums[n - 1 + 1] - l_xs_sums[(n + i) / 2  + 1]);
        if (n + i) % 2 == 0 {
            temp_ans += l_xs[(n + i) / 2];
        } else {
            temp_ans += xs[(n + i) / 2];
        }
        // println!("l temp {:?}", temp_ans);
        ans = std::cmp::max(ans, temp_ans);
    }

    println!("{:?}", ans);
}


Measured memory_bytes: 16636
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }



int main() {
	IOS;
	int h, w, n;
	cin >> h >> w >> n;
	int m = max(h, w);
	put((n + m - 1) / m);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<string>
#include<cstdlib>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------

int main(){
  int H,W;
  cin >> H >> W;
  vector<vector<int>> G(H+1,vector<int> (W+1));
  for(int i=1; i<=H; i++){
    for(int j=1; j<=W; j++){
      cin >> G[i][j];
    }
  }
  vector<pair<pair<int,int>,pair<int,int>>> ans;
  for(int i=1; i<=H; i++){
    if(i%2){
      for(int j=1; j<W; j++){
        if(G[i][j]%2){
          pair<int,int> s,t;
          s = make_pair(i,j);
          t = make_pair(i,j+1);
          G[i][j+1]++;
          ans.push_back(make_pair(s,t));
        }
      }
      if(i<H){
        if(G[i][W]%2){
          pair<int,int> s,t;
          s = make_pair(i,W);
          t = make_pair(i+1,W);
          G[i+1][W]++;
          ans.push_back(make_pair(s,t));
        }
      }
    }else{
      for(int j=W; j>1; j--){
        if(G[i][j]%2){
          pair<int,int> s,t;
          s = make_pair(i,j);
          t = make_pair(i,j-1);
          G[i][j-1]++;
          ans.push_back(make_pair(s,t));
        }
      }
      if(i<H){
        if(G[i][1]%2){
          pair<int,int> s,t;
          s = make_pair(i,1);
          t = make_pair(i+1,1);
          G[i+1][1]++;
          ans.push_back(make_pair(s,t));
        }
      }
    }
  }
  cout << ans.size() << endl;
  for(auto p: ans){
    pair<int,int> s,t;
    s = p.first;
    t = p.second;
    cout << s.first << " "  << s.second << " " << t.first << " " << t.second << endl;
  }
  return 0;
}


Measured memory_bytes: 5232
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <random>
#include <chrono>
#include <complex>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip> 

using namespace std;

#define sqr(x) ((x)*(x))
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define RE(i, n) FOR(i,1,n)
#define REP(i,n) FOR(i, 0, (int)(n)-1)
#define fst first
#define snd second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef tuple<int,int,int> iii;

string to_string(string s) {
    return '"' + s + '"';
}
    
string to_string(const char* s) {
    return to_string((string) s);
}
    
string to_string(bool b) {
    return (b ? "true" : "false");
}
    
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
    
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

void fastIO() {
    cin.sync_with_stdio(false);
    cin.tie(0);
}


int XMOV[4] = {0, 0, 1, -1};
int YMOV[4] = {1, -1, 0, 0};

//#############################
const int MAXN = 1000005;

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

    for (int x = 1; x <= 1009; x++){
        int p1 = x * 8;
        int p2 = x * 10;
        if (a == p1/100 && b == p2/100){
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 8000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int main(){
    LL x,y;
    scanf("%lld%lld",&x,&y);
    for(LL i=0;i<100;i++){
        LL temp=pow(2,i-1)*x;
        if(temp>y){
            printf("%lld\n",i-1);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
//#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 10000000000000000;
const ll mod = 1000000007;
ll test[12345678];
signed main() {
	ll n = 0, m = 0, k, l, cnt = 0, z = 0; string s; cin >> s;
	for (int h = 0; h < 3; h++) {
		if (s[h] == 'A') { n++; }
		else { m++; }
	}
	if (n == 3 || m == 3) { cout << "No" << endl; }
	else { cout << "Yes" << endl; }
	cin >> n; return 0;
}

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

int main() {
  int N, M; cin >> N >> M;
  vector<int> L(M), R(M);
  for (int i = 0; i < M; ++i) {
    cin >> L[i] >> R[i];
  }
  
  int max_l = 1;
  int min_r = N;
  
  for (int i = 0; i < M; ++i) {
    max_l = max(max_l, L[i]);
    min_r = min(min_r, R[i]);
  }
  
  int ans = min_r - max_l + 1;
  
  if (ans < 0) cout << 0 << endl;
  else cout << ans << endl;
  
  return 0;
}

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

int main(){
    int n;
    cin>>n;
    int a[100];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int j=n-1;j>0;j--){
        cout<<a[j]<<" ";
    }
    cout<<a[0]<<endl;
    
}


Measured memory_bytes: 3080
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int main(){
  int a,b;

  cin>>a>>b;

  cout<<(a + b + 1) / 2<<endl;

  return 0;
}


Measured memory_bytes: 256
n = int(input())
s = 'abcdefghijklmnopqrstuvwxyz'


def calc(n, ans):
  n, i = divmod((n - 1), 26)
  ans = s[i] + ans
  if (n > 0):
    return calc(n, ans)
  else:
    return ans


ans = calc(n, '')
print(ans)

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

using namespace std;
#define rep(i,n) for(int i = 0;i < (int)n;i++)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using P = pair<int,int>;
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};
//const int INF = (1 << 29);

#define repll(i,n) for(ll i = 0;i < (ll)n;i++)
int main(){

  ll res = 0;
  string s;
  cin >> s;
  vector<string> v;
  ll mark = 0;
  repll(i,((ll)s.size()-1))if(s[i] != s[i+1])v.push_back(s.substr(mark,i-mark+1)),mark = i+1;
  v.push_back(s.substr(mark,(ll)s.size()-mark));
  if((ll)v.size() == 1){
    res += (ll)v[0].size()*((ll)v[0].size()+1)/2;
  }else if(v[0][0] =='<'){
    for(ll i = 0;i < (ll)v.size()-1;i+=2){
      ll isize = (ll)v[i].size(),ipsize = (ll)v[i+1].size();
      res += isize*(isize+1)/2+ipsize*(ipsize+1)/2;
      res -= min(isize,ipsize);
    }
    if(v[(ll)v.size()-1][0] == '<')res += (ll)v[(ll)v.size()-1].size()*((ll)v[(ll)v.size()-1].size()+1)/2;
  }else{
    res += (ll)v[0].size()*((ll)v[0].size()+1)/2;
    if((ll)v.size()-1 == 1){
      res += (ll)v[1].size()*((ll)v[1].size()+1)/2;
    }else{
      for(ll i = 1;i < (ll)v.size()-1;i+=2){
        ll isize = (ll)v[i].size(),ipsize = (ll)v[i+1].size();
        res += isize*(isize+1)/2+ipsize*(ipsize+1)/2;
        res -= min(isize,ipsize);
      }
      if(v[(ll)v.size()-1][0] == '<')res += (ll)v[(ll)v.size()-1].size()*((ll)v[(ll)v.size()-1].size()+1)/2;
    }
  }
  cout << res;

  return 0;
}


Measured memory_bytes: 14456
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <functional>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

int128_t combi(int128_t n, int128_t r) {
    // nCr の計算。rが定数で結果が128bitにおさまる範囲を想定。nとrは明らかに32bit以下だが、念のためのオーバーフロー対策で128bitにキャストしておく。
    assert(0 <= r && r <= n);
    int128_t ret = 1;
    for (int i = 0; i < r; i++) {
        ret = ret * (n - i) / (i + 1);
    }
    return ret;
}

#define rep(i, begin, end) for(int64_t i = (begin); i <= (end); i++)
#define rev(i, begin, end) for(int64_t i = (begin); (end) <= i; i--)

void printvec(const std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); i++) { std::cout << vec[i] << " "; } std::cout << std::endl;
}

const int MAX_N = 55;
int N, A, B;
int128_t ret[MAX_N][2];
int128_t v[MAX_N];
std::unordered_map<int64_t, int> mp;

int main(int argc, char **argv) {
    std::cin >> N >> A >> B;

    rep (i, 1, N) {
        std::cin >> v[i];
        mp[v[i]]++;
    }

    std::sort(v + 1, v + 1 + N, std::greater<int128_t>());

    int128_t sum = 0;
    int same_cnt = 0;
    rep (i, 1, N) {
        sum += v[i];
        if (v[i] == v[i-1]) {
            same_cnt++;
        } else {
            same_cnt = 1;
        }
        ret[i][0] = sum;
        ret[i][1] = combi(mp[v[i]], same_cnt);
    }

    int best = A;
    int128_t best_num = ret[A][1];

    rep (i, A + 1, B) {
        if (ret[best][0] * i < ret[i][0] * best) {
            best = i;
            best_num = ret[i][1];
        } else if (ret[best][0] * i == ret[i][0] * best) {
            best_num += ret[i][1];
        }
    }

    std::cout << std::fixed << std::setprecision(12) << double(ret[best][0]) / best << std::endl;
    std::cout << best_num << std::endl;

    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<tuple>
#include<vector>
#include<functional>
#include<queue>
#include<algorithm>
using namespace std;
vector<tuple<int, int, int>>x[12000];
int n, m, a, b, c, d, dist[12000]; bool used[12000];
void dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;
	for (int i = 0; i < 12000; i++)dist[i] = 999999999;
	Q.push(make_pair(0, 1)); dist[1] = 0;
	while (!Q.empty()) {
		int a1 = Q.top().first, a2 = Q.top().second; Q.pop();
		for (int i = 0; i < x[a2].size(); i++) {
			int to = get<0>(x[a2][i]), cost = get<1>(x[a2][i]);
			if (dist[to] > a1 + cost) {
				dist[to] = a1 + cost;
				Q.push(make_pair(dist[to], to));
			}
		}
	}
}
int main() {
	while (true) {
		cin >> n >> m; if (n == 0 && m == 0)break;
		for (int i = 0; i < 12000; i++) { x[i].clear(); used[i] = false; }
		for (int i = 0; i < m; i++) {
			cin >> a >> b >> c >> d;
			x[a].push_back(make_tuple(b, c, d));
			x[b].push_back(make_tuple(a, c, d));
		}
		dijkstra();
		vector<pair<int, int>>vec2;
		for (int i = 2; i <= n; i++)vec2.push_back(make_pair(dist[i], i));
		sort(vec2.begin(), vec2.end());
		int sum = 0; used[1] = true;
		for (int i = 0; i < vec2.size(); i++) {
			int a1 = vec2[i].second;
			vector<int>vec3;
			for (int j = 0; j < x[a1].size(); j++) {
				int to = get<0>(x[a1][j]), cost = get<1>(x[a1][j]), cost2 = get<2>(x[a1][j]);
				if (used[to] == false)continue;
				if (dist[to] + cost == dist[a1])vec3.push_back(cost2);
			}
			sort(vec3.begin(), vec3.end());
			sum += vec3[0]; used[a1] = true;
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 5164
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

a.sort(reverse = True)

#l = len(bin(a[0])[2:])

ans  = 0
for b in range(60+1):
    count_1 = 0
    count_0 = 0
    for i in range(n):
        if (a[i] >> b) & 1:
            count_1 += 1
        else:
            count_0 += 1
    count_1 %= mod
    count_0 %= mod
    ans += (count_1 * count_0 * pow(2,b,mod))%mod


print(ans%mod)

Measured memory_bytes: 112508
def BFS(x,y): # 配列dの幅優先探索
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[]
    que.append([x,y])
    d[x][y]=0
    while len(que)!=0:
        [qx,qy]=que[0]
        que.pop(0)
        for i in range(4):
            nx=qx+dx[i]
            ny=qy+dy[i]
            if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                d[nx][ny]=d[qx][qy]+1
                que.append([nx,ny])
    return d[h-1][w-1]

def main():
    global h,w,maze,d
    h,w = map(int,input().split())
    d=[[-1 for _ in range(w)] for _ in range(h)]
    maze=[]
    for _ in range(h):
        maze.append(list(input()))
    n=BFS(0,0)
    if n==-1:
        print(-1)
    else:
        cnt=0
        for i in range(h):
            for j in range(w):
                if maze[i][j]==".":
                    cnt+=1
        print(cnt-n-1)

        
    





if __name__ == "__main__":
    main()

Measured memory_bytes: 40560
import Control.Monad (replicateM)

type Pos = (Int, Int)
type Height = Int

diff :: Pos -> Pos -> Height
diff (x1, y1) (x2, y2) = abs (x1 - x2) + abs (y1 - y2)

veridation :: Pos -> Height -> Pos -> Height -> Bool
veridation x h c ch = h == max 0 (ch - diff c x)

candidates :: Pos -> Height -> [(Pos, Height)]
candidates x h = map (\p -> (p, h + d p)) [(x', y') | x' <- [0..100], y' <- [0..100]]
  where d = diff x

takeSample :: [(Pos, Height)] -> (Pos, Height)
takeSample = head . filter (\(_, h) -> 0 < h)

parse :: IO (Pos, Height)
parse = do
  [x, y, h] <- map read . words <$> getLine
  return ((x, y), h)

fil' :: (Pos, Height) -> [(Pos, Height)] -> [(Pos, Height)]
fil' (x,h) cs = filter (uncurry (veridation x h)) cs

fil :: [(Pos, Height)] -> [(Pos, Height)] -> [(Pos, Height)]
fil ss cs = foldr fil' cs ss

main = do
  n <- read <$> getLine :: IO Int
  samples <- replicateM n parse
  let (sx, sh) = takeSample samples
      cs = candidates sx sh
      ((x,y), h) = head $ fil samples cs
  putStrLn $ show x ++ ' ' : show y ++ ' ' : show h


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, i, j;
    cin >> n;
    long long dp[n], a[n];
    for(i = 0; i < n; ++i) cin >> a[i], dp[i] = a[i];
    for(i = 1; i < n; ++i)
        for(j = 0; j < n-i; ++j)
            dp[j] = max(a[i+j] - dp[j], a[j] - dp[j+1]);
    cout << dp[0];
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h> 
#define ll long long
#define ld long double
#define mod 1000000007;

using namespace std;

// driver program to test above function 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.flush();
	ll t=1;
	//cin>>t;
	while(t--)
	{
		string s;
		list<char> v;
		cin>>s;
		ll N=s.size();
		for(ll i=0;i<N;i++)
		{
			v.push_back(s[i]);
			}
		
		ll q;
		cin>>q;
		ll T;
		ll c=0;
		while(q--)
		{
			cin>>T;
			if(T==1)
			{c++;}
			if(T==2)
			{
				ll f;
				char ch;
				cin>>f>>ch;
				if(c%2==0)
				{
					// no rev
					if(f==1)
					{
						v.push_front(ch);
					}
					else
					{
						v.push_back(ch);
						}
				}
				else
				{
					// else rev;
					if(f==2)
					{
						v.push_front(ch);
					}
					else
					{
						v.push_back(ch);
						}
					
				}
			}
		}
		
		
			if(c%2==0){
			for(auto i=v.begin();i!=v.end();i++)
			{
				cout<<*i;
				}
			cout<<endl;
		}
		else
		{
			
			v.reverse();
			for(auto i=v.begin();i!=v.end();i++)
			{
				cout<<*i;
				}
			cout<<endl;
			//cout<<"n:   "<<n<<endl;
		}
			
	}
	
return 0;
}


Measured memory_bytes: 10064
import java.util.Scanner;
import java.util.Arrays;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while(true){
			int length_t = sc.nextInt(), length_h = sc.nextInt();
			if(length_t==0&&length_h==0) break;
			int[] taro = new int[length_t];
			int[] hanako = new int[length_h];
			int sum_t = 0;
			for(int i=0; i<length_t; i++){
				taro[i] = sc.nextInt();
				sum_t += taro[i];
			}
			int sum_h = 0;
			for(int i=0; i<length_h; i++){
				hanako[i] = sc.nextInt();
				sum_h += hanako[i];
			}
			int sum = sum_t + sum_h;
			if(sum%2==0){
				Arrays.sort(taro);
				Arrays.sort(hanako);
				int t, h;
				for(t=0; t<length_t; t++){
					h = Arrays.binarySearch(hanako, sum/2 - sum_t + taro[t]);
					if(h>=0){
						System.out.println(taro[t] + " " + hanako[h]);
						break;
					}else if(t==taro.length-1){
						System.out.println(-1);
					}
				}
				
			}else{
				System.out.println(-1);
			}
		}
	}
}

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

//https://qiita.com/tubo28/items/e6076e9040da57368845
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 k :usize = read();
    let s :String= read();

    if s.len() <= k {
        println!("{}",s);
    }else{
        println!("{}...",&s[0..k]);
    }

}

Measured memory_bytes: 2140
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC085B_KagamiMochi
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<int> d = new List<int>();
            for (int i = 0; i < n; i++)
            {
                d.Add(int.Parse(Console.ReadLine()));
            }
            Console.WriteLine(d.Distinct().Count());

        }
    }
}


Measured memory_bytes: 13152
import itertools

N = int(input())
L = list(map(str,input().split()))

count = 0
c_list = list(itertools.combinations(L,3))
for i in range(len(c_list)):
    x = int(c_list[i][0])
    y = int(c_list[i][1])
    z = int(c_list[i][2])
    if x != y and y != z and x != z:
        if x + y > z and x + z > y and y + z > x:
            count +=1
print(count)

Measured memory_bytes: 20608
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
    int tmp;
    string a, b, c;
    cin >> a >> b >> c;

    cout << "A" << b[0] << "C" << endl;
}

Measured memory_bytes: 384
def main():
    import heapq
    inf = 10**16
    n, m, s = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*n]
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c, d]) for a, b, c, d in uvab]
    [g[b-1].append([a-1, c, d]) for a, b, c, d in uvab]
    vertex = [[inf]*2501 for _ in [0]*n]
    h = [(0, 0, min(s, 2500))]  # 時刻、位置、所持金
    heapq.heapify(h)
    while h:
        t, p, money = heapq.heappop(h)
        if vertex[p][money] != inf:
            continue
        vertex[p][money] = t
        newmoney = min(money+cd[p][0], 2500)
        if vertex[p][newmoney] == inf:
            heapq.heappush(h, (t+cd[p][1], p, newmoney))
        for a, b, c in g[p]:  # 行き先、運賃、時間
            if money < b:
                continue
            if vertex[a][money-b] != inf:
                continue
            heapq.heappush(h, (t+c, a, money-b))
    for i in vertex[1:]:
        print(min(i))


main()

Measured memory_bytes: 113644
S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

Measured memory_bytes: 66268
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

vector <lli> stone(100009);
vector <lli> dp(100009,-1);
lli N;

lli solve(lli index){

    if(index == N-1)
        return 0;

    if(dp[index] != -1){
        return dp[index];
    }

    lli ans = solve(index+1) + abs(stone[index+1] - stone[index]);

    if(index + 2 < N){
        ans = min(ans, solve(index+2) + abs(stone[index+2] - stone[index]));
    }

    return dp[index] = ans;
}

int main(){
    cin >> N;

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

    cout << solve(0) << endl;;
}

Measured memory_bytes: 7880